Macchina di Turing, Informatica

La macchina di Turing

Per macchina di Turing (o più brevemente MdT) si intende un modello astratto con cui definiamo una macchina in grado di eseguire degli algoritmi e dotata di un nastro infinito su cui leggere e/o scrivere dei simboli, i quali sono posti sul nastro in sequenza. La MdT è stata introdotta come macchina di calcolo nel 1936 da Alan Turing, il quale mostra come tale macchina possa fare tutte quelle elaborazioni effettuabili dagli altri modelli di calcolo già noti all'uomo (es. funzioni ricorsive, lambda calcolo, logica combinatoria algoritmi); in base a ciò, si ha la convinzione che per ogni problema calcolabile, vi sia una MdT in grado di risolverlo. Inoltre, gli algoritmi che vengono eseguiti da una MdT si dicono "algoritmi Turing-computabili".

Problemi della macchina

L'evoluzione illimitata di una MdT, anche se fattibile, è considerata la maggior parte delle volte un insuccesso perché se si vuole cercare un elemento con determinate caratteristiche in un insieme numerabile infinito, la macchina stessa procederà nella ricerca senza dare un'indicazione; si creerebbe così una situazione insoddisfacente in cui si è incerti sull'interrompere un'elaborazione inutile invece di continuare ad attendere un risultato. Questa situazione di incertezza è riconducibile al problema dell'arresto della macchina di Turing. Tale problema spinge i ricercatori a chiedersi se vi sia una macchina in grado di arrestarsi da sola e la questione è resa ancor più significativa dall'esistenza, dimostrata da Turing, di una macchina di Turing universale, che può simulare qualsiasi evoluzione di qualsiasi MdT (anche le evoluzioni di se stessa).

Tuttavia lo stesso Turing ha mostrato che la macchina di Turing universale non può però decidere il problema dell'arresto, perciò nessuna macchina di Turing può farlo e il problema dell'arresto è quindi Turing-indecidibile.

Esecutori

Esistono diverse varianti di esecutori di Turing:

• MdT semplificate: le macchine di Turing possono essere semplificate senza perdere l’elaborazione dei dati; tuttavia alcune semplificazioni non si possono attuare contemporaneamente:
  • Nastro illimitato solo in una direzione
  • Alfabeto di soli due caratteri, uno dei quali il simbolo blank
  • Solo due stati
• Mdt multinastro: la MdT con più nastri fa dipendere la transizione da quanto viene letto sulle caselle e decidere quali caratteri devono essere modificati sui vari nastri.
• MdT con memoria bidimensionale: può simulare le macchine a più nastri ed effettuare elaborazioni grafiche.
• MdT non deterministica: si distingue poi ...