Turing equivalenza

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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 wikitesto]

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 se stesso.[senza fonte]

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à[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ (EN) This is a Turing Machine implemented in Conway's Game of Life, su rendell-attic.org, 2 aprile 2005. URL consultato l'11 dicembre 2018 (archiviato dall'url originale l'8 luglio 2009).
  2. ^ (EN) Spartan universal computer-constructor, su conwaylife.com, 16 giugno 2009. URL consultato l'11 dicembre 2018.
  3. ^ (EN) DaveMcW, Combinator Game of Life, su factorio.com, 24 luglio 2015. URL consultato l'11 dicembre 2018.
  4. ^ Filmato audio (EN) Aroma1997, Conway's Game of Life in Factorio, su YouTube, 5 settembre 2017. URL consultato l'11 dicembre 2018.
  5. ^ Filmato audio (EN) Aroma1997, Conway's Game of Life in Factorio - How it works, su YouTube, 6 settembre 2017. URL consultato l'11 dicembre 2018.

Voci correlate[modifica | modifica wikitesto]