1. Comportamento della macchina di Turing
È un modello di calcolo introdotto dall’ing. Alan Turing nel 1936, per simulare il processo di calcolo umano. Analogamente ai calcolatori di oggi essa possiede una memoria su cui poter leggere e scrivere e un’unità di elaborazione centrale (CPU, dall’inglese Central Processing Unit). La memoria è composta da un nastro infinito, suddiviso in celle al quale la CPU può accedervi attraverso una testina di lettura/scrittura). La CPU di una macchina di Turing è composta da un registro di stato il quale contiene lo stato attuale della macchina e da un programma contenente le istruzioni che deve eseguire.
Inizialmente, nel nastro è contenuta la stringa di input preceduta e seguita da una serie infinita di simboli vuoti, la testina è posizionata sul primo simbolo della stringa di input e la CPU si trova nellostato iniziale. A seconda dello stato in cui si trova la CPU e del simbolo letto dalla testina, la macchina esegue un’istruzione del programma che può:
- modificare il simbolo attualmente letto;
- spostare la testina a destra oppure a sinistra;
- cambiare lo stato della CPU.
La macchina prosegue nell’esecuzione del programma fino a quando la CPU non si trova nello stato finale, oppure non esistono istruzioni del programma che sia possibile eseguire.
Quando l’esecuzione termina la stringa di output sarà racchiusa in quella parte di nastro delimitata dalla testina e dal primo simbolo vuoto alla sua destra.
2. Macchina di Turing universale e tesi di Church
Nel 1854, il matematico britannico George Boole, elaborò la matematica algebrica. Nell’algebra booleana un simbolo può assumere solo uno dei due seguenti valori: vero o falso. Analogamente alle leggi della logica, le operazioni di calcolo si possono eseguire utilizzando gli operatori matematici(OR, AND, NOT, ecc.)
Grazie a Boole il matematico britannico Alan Turing immaginò una macchina con la quale dimostrò la possibilità di eseguire qualsiasi algoritmo. In tal modo, Turing inaugurò quella parte di informatica dal nome di intelligenza artificiale.
La prima sfida per Turing era quella di cercare un algoritmo in grado di effettuare le operazioni elementari (sottrazione, addizione, divisione e moltiplicazione).
Ad esempio, supponiamo di dover effettuare la somma 2+4.
Vedendo una sequenza di numeri naturali ordinati in successione, consideriamo il numero 2 e ripetiamo tante volte quanto il valore di n l’operazione di passaggio al numero successivo: 2→3, 3→4, 4→5, 5→6. In questo modo è possibile trovare facilmente il risultato della somma. Ragionando in questo modo Turing ha trovato gli algoritmi di risoluzione di tutte le operazioni elementari.
Nel 1936 viene proposta la tesi di Church:
«Qualunque funzione sui numeri naturali effettivamente calcolabile è ricorsiva»
Il concetto di “effettivamente calcolabile” è definito solo meccanicamente e fisicamente. Nello stesso anno Turing dichiara: «Una Logical Computing Machine (LCM) può eseguire qualunque calcolo che può essere descritto come puramente meccanico». Quindi se esiste una procedura per ottenere il valore di una funzione matematica, allora tale funzione è calcolabile da una LCM/MdT (Macchina di Turing).
Secondo Turing ogni algoritmo può essere espresso da un’opportuna MdT, ma dal momento che la classe delle funzioni T‐calcolabili coincide con la classe delle funzioni ricorsive generali, allora la tesi è riformulata come «Una funzione è effettivamente calcolabile solo se è ricorsiva generale»
La UTM può simulare qualsiasi TM quindi, per la tesi di Church, è in grado di calcolare qualunque funzione computabile. Una TM è una macchina specifica per l’esecuzione di un unico algoritmomentre la UTM è un’evoluzione di essa in quanto è programmabile: quindi eseguire qualsiasi algoritmo.
La UTM rappresenta il passo dalla computabilità alla programmazione.
UTM: Universal Turing Machine
3. Uso del simulatore della Macchina di Turing per risolvere semplici problemi
Il funzionamento di una MdT può essere programmato definendo un insieme di regole sotto forma di quintuple del tipo:
(stato-interno-corrente, simbolo-letto, prossimo-stato-interno, simbolo-scritto, direzione testina).
Una quintupla che inizia con stato-interno-corrente, simbolo-letto deve essere univoca. Ad esempio, non possono coesistere due regole del tipo (q0, x, …) (q0, x, …). Deve cambiare almeno lo stato corrente o il simbolo letto.
Se la macchina raggiunge uno stato interno per cui non esiste nessuna quintupla per la coppia: stato-interno-corrente, simbolo-letto allora la MdT si ferma e termina la sua esecuzione.
In particolare, la MdT:
Esempio: cambiamo A in B
“Si imposti una Macchina di Turing in modo che, dato sul nastro di input una stringa contenente i caratteri A e B, li rimpiazza l’uno con l’altro.”
Ipotizzando che la testina sia posizionata sul primo simbolo della stringa dobbiamo scrivere le regole che ci permettono l’esecuzione dell’algoritmo sopra mostrato.
Dopo aver passato tutta la stringa data in input (AABBAA) la testina si troverà un carattere vuoto e quindi l’esecuzione sarà arrestata poiché non esiste una quintupla che inizia con la coppia q0, vuoto.
Esistono diversi simulatori della Macchina di Turing reperibili facilmente online. Con questi è possibile capire in maniera solida il funzionamento di esso. Per scaricarne uno è sufficiente digitare su internet “MdT Simulator” oppure “Simulatore macchina di turing”. Con una semplice grafica sarà possibile inserire le quintuple (regole), la stringa in input e visualizzare la stringa di output.
