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 wikitesto]

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.

Note[modifica | modifica wikitesto]

  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.