Turing equivalenza
Da Wikipedia, l'enciclopedia libera.
La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una Macchina di Turing Universale.
Un modello che ha lo stesso potere computazionale di una MdT Universale si dice Turing equivalente o Turing completo.
[modifica] 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
Anche i più comuni linguaggi di programmazione, sia imperativi che funzionali sono Turing equivalenti. In particolare un linguaggio è Turing equivalente quando è in grado di compilare sé stesso.
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.
