Macchina che termina sempre

Nella teoria della computabilità una macchina che termina sempre, chiamata anche un deciderSipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co. o macchina di Turing totale,Kozen, D.C. (1997), Automata and Computability, Springer. è un particolare di tipo di macchina di Turing per cui, al contrario del modello generale, vi è garanzia 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 macchine di questo tipo è esattamente l'insieme dei linguaggi ricorsivi.

Funzioni computabili da macchine di Turing totali Per esempio, un albero di decisione finito non contiene cicli e quindi 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), si possono esprimere tutte le funzioni ricorsive primitiveMeyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.. Un esempio di questa macchina è fornito dal linguaggio di programmazione giocattolo PL-{GOTO} di Brainerd e LandweberBrainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley..

Inoltre si può definire un programma in cui è possibile assicurare che funzioni persino più sofisticate terminino sempre. Ad esempio la funzione di Ackermann, che non è ricorsiva primitiva, termina sempre e si può garantire questa proprietà considerandola un sistema di riscrittura con un buon ordine dei suoi argomentiOhlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer. pag.67. È una cosa simile ad usare l'induzione matematica per provare che una funzione ricorsiva raggiunge sempre il suo caso base.

Note

Categoria:Macchina di Turing