Apri il menu principale

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 equivalentiModifica

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

NoteModifica

  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. ^   (EN) Aroma1997, Conway's Game of Life in Factorio, su YouTube, 5 settembre 2017. URL consultato l'11 dicembre 2018.
  5. ^   (EN) Aroma1997, Conway's Game of Life in Factorio - How it works, su YouTube, 6 settembre 2017. URL consultato l'11 dicembre 2018.

Voci correlateModifica