2. La macchina di Turing

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.

la macchina di Turing
Algoritmo di addizione, immagine a cura di Alessandro Frasconi

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).

la macchina di Turing
Associazione alle quintuple della MdT, immagine a cura di Alessandro Frasconi

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:

la macchina di Turing
Funzionamento generale della MdT, immagine a cura di Alessandro Frasconi

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.

la macchina di Turing
Esempio di regole in una MdT, immagine a cura di Alessandro Frasconi
la macchina di Turing
Esempio di funzionamento di una MdT, immagine a cura di Alessandro Frasconi

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.

Hai qualche segnalazione da farci sull'appunto?

Accedi

[mepr-login-form use_redirect="true"]

Registrati

Accedi o Registrati

Il manuale di sopravvivenza alla MATURITÀ 2024

Dalla prima prova al colloquio orale, tutto ciò di cui hai bisogno è qui!

PRE-Vendita disponibile fino alle 23:59 del 27 Novembre!