Lo scambio di informazioni e la certezza delle transazioni nei protocolli blockchain

8 qualsiasi di celle e di leggere e scrivere in una qualsiasi delle celle un simbolo di un alfabeto prefissato. Questa macchina, pur nella sua semplicità, può calcolare in un numero finito di passi elementari qualsiasi funzione computabile 6 . Il nastro si estende idealmente in modo infinito nei due versi e risulta diviso in celle, ciascuna contenente un simbolo appartenente a un insieme finito di simboli detto alfabeto. Ogni macchina di Turing deve possedere un alfabeto che contenga il simbolo speciale b (blank, spazio), i simboli 0 e 1, e un numero finito di altri simboli, come X e Y, usati come segnaposto. In ogni istante solo un numero finito di celle contiene simboli diversi da b. Il nastro funziona pertanto da input, da output e da memoria. La macchina è costituita da un numero finito k di stati o configurazioni ed è pensata per eseguire solo un tipo di operazione primitiva. A ogni operazione corrispondono tre azioni o comandi: scrittura di un nuovo simbolo nella cella, posizionamento in un nuovo stato, spostamento di una cella verso destra o verso sinistra. Le istruzioni possibili per la macchina sono: stato corrente, simbolo corrente, prossimo simbolo, prossimo stato, direzione di spostamento. Una macchina di Turing può eseguire un’intera sequenza di istruzioni, poiché risulta sincronizzata da una sorta di orologio interno. La macchina è pertanto un modello di agente di calcolo generale che modellizza ciò che effettivamente può compiere un calcolatore. La macchina di Turing ha permesso di dimostrare che alcuni problemi non ammettono nessuna soluzione generale calcolabile. La tesi o congettura di Church- Turing afferma infatti che, se esiste un algoritmo per eseguire un compito che manipola simboli, allora esiste una macchina di Turing in grado di eseguire quel compito. Pertanto, è possibile utilizzare il modello della macchina di Turing per definire i limiti della computabilità: se per un problema non esiste una macchina di Turing in grado di risolverlo allora il problema si dice incomputabile o irrisolvibile. Nel 1940, grazie alla macchina “Bomba” gli inglesi decrittarono con successo i messaggi crittografati da Enigma e l'intelligence raccolta da queste comunicazioni intercettate divenne nota come Ultra. Le informazioni decifrate fornirono 6 Una funzione si dice computabile se esiste un algoritmo che la calcola. In termini matema ci, si dice che un algoritmo calcola una funzione f(x) se, per ogni possibile valore x_0 della variabile indipendente, assegnando questo valore come input dell'algoritmo, l'algoritmo fornisce come risultato f(x_0).