La macchina di Turing

La macchina di Turing è un concetto teorico stabilito dal matematico britannico Alan Turing nel 1936 ed è la base per la teoria informatica e di tutto ciò che si è realizzato finora. Si basa su una semplice macchina che legge e scrive su un nastro infinito.

Alan Turing è stato dei primi a sviluppare la logica del funzionamento dei computer e interessarsi all’intelligenza artificiale. Sebbene il concetto di IA viene menzionato continuamente oggi grazie alle ultime novità sviluppate da OpenAi, Google e Microsoft, qualunque macchina tecnologica possiede una qualche forma di ‘intelligenza’.

Nella sua formulazione iniziale la macchina di Turing ha i seguenti componenti:

• Un insieme finito di simboli che rappresenta l’alfabeto usato per scrivere con la macchina compreso quello per indicare uno spazio vuoto;
• Un nastro di lunghezza infinita suddiviso in caselle di cui soltanto una parte contiene inizialmente simboli diversi dallo spazio vuoto;
• Una testina che scorre sopra il nastro capace di leggere o di scrivere sulle caselle;
• Un dispositivo di controllo in grado di dire alla macchina cosa fare in base al contenuto della casella del nastro sotto la testina e allo stato della macchina.

Ad esempio, una macchina potrebbe avere lo stato di lettura, di ascolto, di dettatura o di scrittura. A seconda dello stato, la macchina sa se deve pronunciare la parola letta o scrivere la parola pronunciata da qualcuno.

Esempio di macchina di Turing

Vediamo il seguente esempio: una macchina in grado di aumentare un numero binario. A questo riguardo, bisogna considerare che il sistema binario è formato soltanto da due cifre: 0 e 1. Il numero 0 viene scritto 00, mentre 1 viene scritto 01.

Ma il numero 2 viene scritto nel seguente modo:

• Si guarda l’ultima cifra del numero precedente: se è 0 viene convertito in 1 e ci fermiamo, come nel passaggio sopra;
• Se l’ultima cifra è 1, la convertiamo in 0 ma ci spostiamo una cifra a sinistra. Fino a quando la cifra è 1 viene convertita in 0 e continuiamo a spostarci; appena troviamo uno 0, lo convertiamo in 1 e ci fermiamo.

Così il numero 2 è 10, il numero 3 è 11, il numero 4 è 100.

Possiamo creare delle funzioni che simulano una macchina di Turing con qualunque linguaggio di programmazione. In questo esempio utilizzeremo il linguaggio C#. Iniziamo creando un progetto con VS Code.

A questo punto creiamo un file con estensione .cs che conserva la classe per il nostro algoritmo. Creiamo una classe e inseriamo gli stati che ci interessano e anche una funzione che verifica che il numero inserito dall’utente è corretto:

public class MacchinaTuring
    {
        //Lista degli stati
        enum Stato
        {
            Inizio,
            Fine
        }

        //Funzioni che riportano in una variabile lo stato di inizio e fine
        static Stato IniziaStato() {
            return Stato.Inizio;
        }
        static Stato FinisciStato() {
            return Stato.Fine;
        }

        private static bool VerificaNumeroBinario(int[] numero)
        {
            //Lista dei simboli
            int[] simboli = [0, 1];
            return numero.All(valore => valore == simboli[0] || valore == simboli[1]);
        }
    }

A questo punto possiamo creare la funzione per aggiungere un bit al nostro numero binario.

public static int[] AggiungiUnBit(int[] numeroBinario)
        {
            //Leggiamo lo stato iniziale
            Stato stato = IniziaStato();
            int[] numeroBinarioTemp = (int[])numeroBinario.Clone();
            int posizione = numeroBinarioTemp.Length - 1;


            //Inseriamo le istruzioni per aggiungere un bit
            while (stato == Stato.Inizio)
            {
                //Verifica che si tratta di un numero binario
                if (!VerificaNumeroBinario(numeroBinarioTemp))
                {
                    return CreaNumeroBinario();
                }

                if (posizione < 0)
                {
                    return AggiungiUnitàAlBinario(numeroBinarioTemp);
                }

                switch (numeroBinarioTemp[posizione])
                {
                    case 0:
                        numeroBinarioTemp[posizione] = 1;
                        stato = FinisciStato();
                        break;
                    case 1:
                        numeroBinarioTemp[posizione] = 0;
                        posizione--;
                        break;
                    default:
                        return AggiungiUnitàAlBinario(numeroBinarioTemp);
                }

            }

            //Quando tutto è finito ritorniamo il nuovo numero
            return numeroBinarioTemp;
        }

Adesso, nel file Program.cs dobbiamo:

int[] numeroBinario1 = [1, 1, 2];
int[] numeroBinario2 = [1, 0, 1];
int[] numeroBinario3 = [1, 1, 1];


int[] risultato1 = MacchinaTuring.AggiungiUnBit(numeroBinario1);
int[] risultato2 = MacchinaTuring.AggiungiUnBit(numeroBinario2);
int[] risultato3 = MacchinaTuring.TogliUnBit(numeroBinario3); //Funzione da aggiungere


Console.WriteLine(MacchinaTuring.ConvertiBinarioInStringa(risultato1));
Console.WriteLine(MacchinaTuring.ConvertiBinarioInStringa(risultato2));
Console.WriteLine(MacchinaTuring.ConvertiBinarioInStringa(risultato3));

• Inserire alcune variabili che contengono numeri binari;
• Inserire delle variabili che contengono il numero successivo a quelle iniziali;
• Mandare a schermo i nuovi risultati.

Questo è un esempio per aumentare di un’unità un numero binario. Prova i seguenti esercizi:

• Aggiungere le funzioni mancanti;
• Aggiungi una funzione per diminuire un numero binario;
• Aggiungi delle funzioni per aumentare un numero binario con più bit.
• Trovare i bug del programma e renderlo più efficiente.