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.

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 come Turing equivalente quando è possibile scrivere un compilatore di programmi usando 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à[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]