La completezza di Turing descrive la capacità di un sistema di risolvere una classe identica di problemi come su un modello semplificato di computer programmabile - una macchina di Turing. In altre parole, è l’abilità di un sistema di calcolo di simulare un altro sistema di calcolo a condizione di risorse quali tempo e memoria. Nell’articolo di oggi, vogliamo raccontarvi di Alan Turing e del suo contributo alla scienza. 

Alan Turing –  illustre matematico e logico

Alan Turing è passato alla storia come uno dei padri fondatori dell’informatica moderna. È nato il 23 giugno 1912. Fin da bambino dimostrò eccezionali doti matematiche. Studiò all’Università di Cambridge, dove il suo lavoro portò al concetto di macchina di Turing, in grado di eseguire calcoli arbitrari se fattibili dal punto di vista algoritmico. Durante la Seconda Guerra Mondiale, lavorò alla rottura di Enigma. Fu anche pioniere dell’intelligenza artificiale, creando il test di Turing per determinare se una macchina fosse stata in grado di pensare in modo simile all’uomo. Morì a soli 41 anni, il 7 giugno 1954.

Curiosità: Una forma inversa del test di Turing è il CAPTCHA (Completely Automated Public Turing Test to tell Computers and Humans Apart), che determina se un programma sta interagendo con un umano o, ad esempio, con un bot di intelligenza artificiale. 

La macchina di Turing - operazione

Nel 1936, il matematico propose un modello computazionale astratto che definisce la base teorica del funzionamento dei moderni computer. Una macchina di Turing è costituita dai seguenti elementi: un nastro infinito diviso in celle, una testina in grado di leggere e scrivere simboli sul nastro e un insieme di regole che controllano la testina. Il modello consente di eseguire calcoli arbitrari se sono algoritmicamente possibili ed è in grado di simulare il funzionamento di qualsiasi computer. 

La completezza di Turing – definizione

La macchina di Turing descritta in precedenza è la base per definire la completezza di Turing, ovvero la capacità di un sistema computazionale di eseguire calcoli che sono teoricamente possibili per la macchina stessa. Come accennato nell’introduzione, se un linguaggio di programmazione o un sistema computazionale è Turing-completo, può simulare qualsiasi altro sistema computazionale, ammesso che abbia memoria e tempo sufficienti. 

Riassunto – che cos’hanno in comune le criptovalute e la completezza di Turing?

Si dice che la macchina virtuale di Ethereum (EVM) sia caratterizzata dalla completezza di Turing. Le operazioni sulla rete Ethereum richiedono l’uso di gas per eseguire le disposizioni degli smart contract. Il gas è un’unità di misura delle risorse computazionali necessarie per completare un’operazione. La sua esistenza garantisce che la rete non possa andare in loop. Inoltre, fornisce ricompense ai validatori. Ethereum è caratterizzato dalla completezza di Turing, in quanto l’EVM consente di eseguire qualsiasi calcolo se vengono fornite risorse adeguate.

Naturalmente, Ethereum non è un caso isolato di completezza di Turing nella rete blockchain. Altri esempi di spicco come Cardano, TRON, NEO, Tezos, Polkadot, Solana e altri ancora, offrono agli utenti una serie di vantaggi e soluzioni, pur mantenendo la completezza di Turing.