In informatica teorica un sistema di regole di manipolazione dei dati (come un modello di calcolo, il set di istruzioni di un computer, un linguaggio di programmazione o anche, volendo, un semplice automa cellulare) è detto Turing-completo o altresì computazionalmente universale se può essere usato per simulare qualsiasi macchina di Turing (ideata dal matematico e informatico inglese Alan Turing). Ciò significa che tale sistema Turing completo è in grado di riconoscere o decidere altri insiemi di regole di manipolazione dei dati, anche diversi da quelli originali. La completezza di Turing viene utilizzata per esprimere la potenza di un insieme di regole per la manipolazione dei dati. La totalità dei linguaggi di programmazione moderni sono considerati, per inciso, Turing-completi.
I computer costruiti fino ad oggi possono essere analizzati funzionalmente come una macchina di Turing a nastro singolo (il “nastro” corrisponde alla loro memoria); quindi la matematica associata può essere applicata astraendo il loro funzionamento abbastanza lontano. Tuttavia, i computer reali hanno risorse fisiche limitate, quindi sono completi solo di automi lineari vincolati. Al contrario, un computer universale è definito come un dispositivo con un set di istruzioni completo di Turing, memoria infinita e tempo disponibile infinito.
Un concetto correlato è quello di equivalenza di Turing: due computer P e Q sono detti equivalenti se P può simulare Q e Q può simulare P. La tesi di Church-Turing congettura che qualsiasi funzione i cui valori possono essere calcolati da un algoritmo può essere calcolata da una macchina di Turing, e quindi che se qualsiasi computer del mondo reale può simulare una macchina di Turing, è equivalente a una macchina di Turing. Una macchina di Turing universale può essere utilizzata per simulare qualsiasi macchina di Turing e, per estensione, gli aspetti computazionali di qualsiasi possibile computer del mondo in cui viviamo.
Per dimostrare che qualcosa è Turing-completo, è sufficiente dimostrare che può essere usato per simulare un sistema Turing-completo. Nessun sistema fisico può disporre di una memoria infinita, chiaramente, ma se si ignora la limitazione della memoria finita, la maggior parte dei linguaggi di programmazione sono altrimenti Turing-completi.
Usa il codice
189ed7ca010140fc2065b06e3802bcd5 per ricevere 5 € dopo l'iscrizione
Nell’uso colloquiale, i termini “Turing-completo” e “Turing-equivalente” sono usati per indicare che qualsiasi computer o linguaggio informatico di uso generale del mondo reale può simulare approssimativamente gli aspetti computazionali di qualsiasi altro computer o linguaggio informatico di uso generale del mondo reale. Nella vita reale, questo porta ai concetti pratici di virtualizzazione ed emulazione.
Immagine di copertina: ritratto di Alan Turing generato dall’intelligenza artificiale di StarryAI
👇 Contenuti da non perdere 👇
- Cellulari 📱
- Lavoro 🔧
- monitoraggio servizi online 📈
- Scrivere 🖋
- Sicurezza & Privacy 👁
- Svago 🎈
- 💬 Il nostro canale Telegram: iscriviti
- 🟠 4chan: nei meandri del dark web e della community più controversa al mondo
- 🔴 Come registrare i domini internazionalizzati e con caratteri accentati (IDNA)
- 🟠 Dal linguaggio Logo a Turtle per Python
