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 (MdTu).

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

Noti modelli Turing equivalenti[modifica | modifica sorgente]

I più noti modelli di calcolo Turing equivalenti sono:

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.

Voci correlate[modifica | modifica sorgente]