Apri il menu principale

Macchina che termina sempre

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 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. Dato il problema della fermata, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile,non c'è nessun algoritmo per determinarlo.[La costruzione sintattica involuta rende estremamente difficile la comprensione di questo periodo.]

Funzioni computabili da macchine di Turing totaliModifica

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.[La costruzione sintattica involuta rende estremamente difficile la comprensione di questo periodo.] 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 primitive[3]. Un esempio di questa macchina è fornito dal linguaggio di programmazione giocattolo PL-{GOTO} di Brainerd e Landweber[4].

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

NoteModifica

  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 sovrastante.