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.
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
👇 Da non perdere 👇
- 📈 Analizza Cellulari 📱
- 🔐 AI che dolor, Chat 🏴
- 🎯 Targetizza Database SQL 🗄
- 📊 Analizza Errori più comuni 📛
- 🚧 Costruisci Evergreen 📟
- 👩💻 Programma Gratis 🎉
- 💻 Configura Hosting a confronto 💑
- 🔒 Conosci Hosting reti e domini 💻
- 👩💻 Tapioca Informatica 🖥
- 💻 Iconizza Internet 💻
- 🔒 Gestisci Lavoro 🔧
- 💡 Mostra Marketing & SEO 🌪
- 🔑 Apprendi Meteo ⛅
- 🤯 Visiona Mondo Apple 🍎
- 🔍 Supervisiona Mondo Domini 🌐
- 🚀 Metti in cloud monitoraggio servizi online 📈
- 🔮 Anatomizza Nuove tecnologie 🖥
- 🔒 Antani PEC e firma digitale 📩
- 👀 Prematura Programmare 🖥
- 🎮 Lonfa Scrivere 🖋
- 🔒 Conosci Servizi di SMS 📶
- 👀 Guarda Sicurezza informatica e privacy digitale 🖥
- 🎮 Ricorda Siti web 🌎
- 🤖 Ottimizza Spiegoni artificiali 🎓
- 🧠 Neuralizza Svago 🎈
- 📡 Quantizza Usare Excel 🌀
- 🤖 Sovrascrivi Windows 😲
- 🎨 Personalizza Wireless 🚁
- 🔑 Decifra WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟢 Come si collega la presa industriale ad un cavo tripolare
- 🟢 Come cercare i file che occupano più spazio (SSH) – Liberare spazio
- 🟠 Client vs. server: cos’è e come funziona
