La Turing Completezza è dove meno te l'aspetti

I requisiti necessari per ottenere una macchina Turing equivalente sono quasi sempre spiegati in termini comprensibili da una macchina di Turing, naturalmente. Una macchina di Turing è semplicemente un'ipotetica scatola nera che svolge una piccola serie di operazioni matematiche e logiche su una striscia di nastro di carta la cui lunghezza è potenzialmente infinita. La scatola scivola avanti e indietro lungo il nastro, leggendo e scrivendo dati in delle celle, a partire dalle quali, successivamente, potrà fornire delle risposte ad alcune domande. Questo è ciò che significa capacità computazionale — una garanzia che la macchina non continuerà a svolgere calcoli per sempre, ma che utilizzerà nel corso del tempo e in maniera intelligente i risultati già ottenuti. Qualunque vero computer non è altro che una simulazione di questa astrazione primitiva.

L'idea di una macchina di Turing non mi è mai piaciuta troppo. Parte del problema è che la macchina di Turing, come è descritta sopra, è spesso definita per ciò che è — una scatola che svolge operazioni matematiche su celle poste su una striscia di nastro di carta — e non per ciò che significa. Ciò che la macchina di Turing sta a significare è che esiste una condizione per cui è possibile risolvere qualunque problema computazionale se si è a disposizione di abbastanza tempo e memoria macchina.

Perché qualcosa sia definibile Turing completo, deve poter risolvere qualunque problema risolvibile da qualunque altro computer esistente o di cui si può immaginare l'esistenza (come nel caso della macchina di Turing). Potrebbe essere più facile vederla da un altro punto di vista: un computer Turing incompleto non è in grado di risolvere alcune classi conosciute di problemi invece risolvibili da un altro computer. Di solito, quando si parla di equivalenza di Turing, si parla di computer in quanto insieme di linguaggi di programmazione, ovvero sistemi per descrivere come risolvere diversi problemi.

Molti linguaggi di programmazione di cui avrete sentito parlare sono Turing completi. Non ci sono problemi computazionali risolvibili con il C che non possono essere risolti in Javascript, o problemi Java in Python o, ancora, problemi Python in Java. Una interessante eccezione è l'SQL — il linguaggio utilizzato per l'implementazione dei database — che nella sua forma più base è considerato essere Turing incompleto. Il che ha piuttosto senso visto che l'SQL non esiste per scopi di programmazione generali e non ha bisogno di caratteristiche come i loop e il branching if-then (che permette a sezioni di codice di essere saltate sotto determinate circostanze).

Similmente, l'HTML non è Turing completo, non che debba esserlo. Il suo utilizzo è descrittivo e non computazionale.

Un aspetto interessante dell'equivalenza di Turing è che non è per niente difficile da ottenere. Infatti, si manifesta in giro per il mondo quasi per caso. Il ricercatore in ambito bitcoin e darknet Gwern Branwen ha pubblicato un piccolo catalogo di strutture "sorprendentemente Turing complete" che suggeriscono alcune implicazioni di sicurezza curiose e preoccupanti.

"Qualcuno potrebbe pensare che riuscire a ottenere un sistema abbastanza intelligente da far girare qualunque programma potrebbe essere un traguardo difficile da raggiungere, al contrario sembra molto più difficile riuscire a programmare un sistema utile che non finisce immediatamente per essere Turing completo," scrive Branwen. "La sorpresa è che basta avere un po' di controllo sull'input da inserire in un macchina che trasforma un input in un output per riuscire a trasformare, con un po' di sforzo, questo tipo di controllo in un vero e proprio sistema Turing completo. Può essere divertente, utile (anche se spesso non lo è), dannoso o incredibilmente insicuro."

Alcuni esempi includono  Magic the Gathering, il CSS e le notazioni musicali più comuni. Nel caso di  Magic, è vero solo se si considera una sequenza infinita di carte che obbligano le mosse del giocatore, di fatto eliminando la sua possibilità di scelta. Le meccaniche possono diventare davvero profonde. Il CSS — ovvero cascading style sheet, che permette di aggiungere informazioni all'aspetto di una pagina web — nel frattempo, diventa Turing completo quando includiamo i click dell'utente nel sistema e, dunque, l'abilità di cambiare lo stato del sistema. In altri casi, il CSS, in quanto linguaggio descrittivo come l'HTML, non fa poi granché. Con qualche leggera modifica, la notazione musicale comune può essere convertita nell'esoterico linguaggio di programmazione Turing completo Choon.

Un paper del 2013 pubblicato da Stephen Dolan, informatico della University of Cambridge, e citato da Branwen, offre un contendente per il premio titolo più breve per un paper di informatica: "il mov è Turing completo." Si sta riferendo a un'istruzione del linguaggio Assembly — un comando a livello hardware, di base — che muove un'unità dati da un indirizzo di memoria a un altro. È un comando di una lunga lista di istruzioni Assembly, ma ciò che Dolan ha mostrato è che qualunque altra istruzione può essere ridotta a questa singola azione. È folle.

Questa implicazione di sicurezza potrebbe non essere ovvia. Gran parte della sicurezza informatica, in genere, si basa sull'evasione e la difesa di codice maligno che potrebbe ottenere un punto di accesso nel tuo sistema e fare cose che non vorresti fossero fatte. Per farlo è necessario riconoscere questo tipo di codice in quanto tale e ciò non è possibile quando si parla di Pokémon o di cellule cardiache umane. La computazione è ovunque.

The security implication is maybe not obvious. Some large part of computer security, generally, is evading and defending against malicious code that might gain entry into your system and do unwanted things. Doing so requires being able to identify such code as code, and not, say, Pokemon and or human heart cells. Computation could be anywhere.