Turing equivalenza

La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu).

Un modello che ha lo stesso potere computazionale di una MdTu si dice Turing equivalente o Turing completo.

Noti modelli Turing equivalenti

I più noti modelli di calcolo Turing equivalenti sono:

• le funzioni ricorsive;
• il modello di Kleene basato sulle equazioni funzionali;
• il lambda calcolo di Church;
• la logica combinatoria;
• gli algoritmi normali di Markov;
• i sistemi combinatori di Post;
• le macchine a registri elementari come la macchina URM;
• il calcolo dei predicati (si veda in proposito il teorema di completezza di Gödel e il teorema di Church).

Anche i più comuni linguaggi di programmazione, sia imperativi sia funzionali, sono Turing equivalenti.

Poiché la compilazione di un programma richiede l'uso di costrutti condizionali, cicli e memoria illimitati, un linguaggio general purpose dotato di tali costrutti (e quindi Turing equivalente) permette di scrivere un compilatore. Ciò ha generato la consuetudine di considerare un generico linguaggio $L$ come Turing equivalente quando è possibile scrivere un compilatore di programmi $L$ usando $L$ stesso. In realtà non è necessario attendere che un linguaggio venga usato in un simile progetto: è sufficiente che esibisca alcune proprietà elementari, come si vede dai modelli Turing equivalenti più semplici (ad esempio le macchine a registri elementari).

Esempi di modelli di calcolo che sono meno potenti di una MdT Universale sono le espressioni regolari, gli automi a stati finiti e le macchine che terminano sempre.

Curiosità

• Il Gioco della vita è considerato Turing equivalente.
• Nel videogioco Factorio è possibile riprodurre il Gioco della vita, pertanto anch'esso è considerato Turing equivalente.

Voci correlate

• Tesi di Church-Turing

Collegamenti esterni

• (EN) Eric W. Weisstein, Turing equivalenza, su MathWorld, Wolfram Research.