Macchina che termina sempre

Da Wikipedia, l'enciclopedia libera.

Nella teoria della computabilità, una macchina che termina sempre — chiamata anche un decider[1] o macchina di Turing totale[2] — è un particolare di tipo di macchina di Turing che, al contrario del modello generale, è 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 fermata, 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.

Funzioni computabili da macchine di Turing totali[modifica | modifica sorgente]

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 (come il ciclo FOR in BASIC), possiamo esprimere tutte le funzioni ricorsive primitive[3]. Un esempio di tale macchina è fornito dal linguaggio di programmazione giocattolo PL-{GOTO} di Brainerd e Landweber[4].

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[5]. È una cosa simile ad usare l'induzione matematica per provare che una funzione ricorsiva raggiunge sempre il suo caso base.

Confronto con le macchine di Turing parziali[modifica | modifica sorgente]

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 input. 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 dn = d(n) una procedura ricorsiva per enumerare D come {d0, d1, d2, ...}. Ne segue che F è anche ricorsivamente enumerabile con l'enumerazione {[[d0]], [[d1]], [[d2]], ...}.

Ora definiamo la funzione diagonale g(n)=[[dn]](n) + 1 (altre funzioni possono essere costruite rimpiazzando 1 con 2, 3, ecc). Questa funzione è ricorsivamente computabile, dal momento che entrambe dn=d(n) e [[dn]](n) sono computabili. È anche totale dal momento che [[dn]](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.

Note[modifica | modifica sorgente]

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


Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sottostante.