Macchina che termina sempre

Da Wikipedia, l'enciclopedia libera.

Nella teoria della computabilità, una macchina che termina sempre — chiamata anche un decider (Sipser, 1996) o macchina di Turing totale (Kozen, 1997) — è un modello computazionale che, al contrario della più generale macchina di Turing, è garantito che termini per ogni input.

Poiché si ferma sempre, la macchina è in grado di decidere se una data stringa è membro di un linguaggio formale. La classe dei linguaggi che possono essere decisi da tale macchina è esattamente l'insieme dei linguaggi ricorsivi. È importante notare che, dato il problema della terminazione, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile - non c'è nessun algoritmo per determinarlo. L'insieme delle macchine che terminano sempre è solo ricorsivamente enumerabile.

In pratica, è possibile costruire una macchina che termini sempre, e già computa molte funzioni interessanti, come da esempio, quando si limita le capacità di controllo di flusso così che nessun programma farà entrare la macchina in un ciclo infinito. Come esempio banale, un albero di decisione finito non contiene cicli, così termina naturalmente. Non si richiede che la macchina non abbia capacità di svolgere cicli. Se si limitano i cicli ad un ben definito limite prevedibile (non diversamente dal ciclo FOR in BASIC), possiamo esprimere tutte le funzioni ricorsive primitive (Meyer and Ritchie, 1967). Un esempio di tale macchina è fornito dal linguaggio di programmazione giocattolo PL-{GOTO} di Brainerd e Landweber (1974).

Possiamo inoltre definire un programma in cui possiamo assicurare che terminino sempre funzioni persino più sofisticate. Ad esempio, la funzione di Ackermann, che non è ricorsiva primitiva, tuttavia termina sempre, e possiamo garantire questa proprietà considerandola un sistema di riscrittura con un buon ordine dei suoi argomenti (Ohlebusch, 2002, pp.67). È una cosa simile ad usare l'induzione matematica per provare che una funzione ricorsiva raggiunge sempre il suo caso base.

Si noti, tuttavia, che ci saranno sempre programmi che terminano sempre che non sono esprimibili in questi modelli semplificati. In effetti, il seguente teorema mostra che le macchine che terminano sempre sono leggermente meno potenti delle macchine di Turing:

Ci sono funzioni totali (Turing-)computabili che non sono computabili da una macchina che termina sempre.

Prova: La prova segue il Teorema 2.3 di Brainerd e Landweber (1974) per il linguaggio PL-{GOTO}, e procede da un argomento diagonale. Sia F l'insieme di tutte le funzioni computabili da una macchina che termina sempre. Queste funzioni sono totali dal momento che la macchina termina per ogni ingresso. Come al solito, e senza perdere di generalità, possiamo prendere queste funzioni per mappare i numeri naturali ai naturali. Il nostro scopo è trovate una funzione computabile g(n), con $g,n \in N$ , che non è in F.

Per la definizione di F, per ogni funzione f in F c'è una descrizione della macchina (o un programma) d che computa f fino all'esecuzione. Denotiamo l'esecuzione di d con delle doppie parentesi quadre, quindi [[d]](n) = f(n). Dal momento che ogni descrizione porta la macchina a terminare in qualche punto, non è difficile vedere che l'insieme di descrizioni della macchina D che porta alle funzioni totali è un ricorsivamente enumerabile. Sia d_n = d(n) una procedura ricorsiva per enumerare D come {d₀, d₁, d₂, ...}. Ne segue che F è anche ricorsivamente enumerabile con l'enumerazione {[[d₀]], [[d₁]], [[d₂]], ...}.

Ora definiamo la funzione diagonale g(n)=[[d_n]](n) + 1 (altre funzioni possono essere costruite rimpiazzando 1 con 2, 3, ecc). Questa funzione è ricorsivamente computabile, dal momento che entrambe d_n=d(n) e [[d_n]](n) sono computabili. È anche totale dal momento che [[d_n]](n) termina per ogni n. Tuttavia, per costruzione, g è diversa da ogni membro di F. Quindi, g è totale e ricorsivamente computabile, ma non computabile da una macchina che termina sempre. In alternativa, per la tesi di Church-Turing, "ricorsivamente computabile" può essere rimpiazzato da "macchina di Turing computabile", c.v.d.

[modifica] Bibliografia

Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.
Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Kozen, D.C. (1997), Automata and Computability, Springer.
Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.

Teoria degli automi: linguaggi formali e grammatiche formali
gerarchia di Chomsky	Grammatiche	Linguaggi	automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Sensibile al contesto	Sensibile al contesto	Lineare-limitato
Tipo-2	Context-free	Context-free	Automa a pila
Tipo-3	Lineare (o Regolare)	Lineare (o Regolare)	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.