Blog Matematico

BLOG MATEMATICO di Umberto Cerruti


E' possibile consultare l'archivio degli articoli precedenti. -- Math News -- Home

30 Novembre 2004


Alan Turing e i suoi alacri castori.


Come promesso nell'ultimo blog, facciamo ancora una visita alla OEIS (On-Line Encyclopedia of Integer Sequences) che, da un paio di settimane, ha superato le 100000 voci. Se clicchiamo su Welcome, troviamo:

New Users:

Let's begin at once with an example of a sequence of great importance:
ID Number: A060843
Sequence: 1,6,21,107
Name: Busy Beaver problem: maximal number of steps that an n-state Turing
machine can make on an initially blank tape before eventually halting.
Comments: The function Sigma(n) (A028444) denotes the maximal number of tape
marks which a Turing Machine with n internal states and a two-way
infinite tape can write on an initially empty tape and then halt. The
function S(n) (the present sequence) denotes the maximal number of steps (shifts)
which such a machine can make (it needs not produce many tape marks).
Given that 5-state machines can compute Collatz-like congruential
functions (see references), it may be very hard to find the next term.
The sequence grows faster than any computable function of n, and so is
non-computable.
(.... seguono riferimenti ....)

Probabilmente non capiremo molto, di primo acchito. Forse la cosa più inquietante è che la sequenza è dichiarata non computabile. Eppure i primi quattro termini ci sono. Si può proseguire? E' solo un problema di potenza di calcolo, o c'è sotto qualcosa di più fondamentale?
Come può questa successione S(n) crescere più in fretta di qualsiasi funzione f(n) che io posso calcolare?

Procediamo con calma. Alan Turing, intanto. Chi era costui?

Alan Mathison Turing nacque a Paddington (Londra) nel 1912 e morì nei pressi di Manchester nel 1954, in circostanze poco chiare.
Fu uno studente indisciplinato, che non piaceva agli insegnati sebbene in matematica vincesse tutti premi possibili. Amava molto la chimica, ma era disapprovato dai professori, perché seguiva per gli esperimenti una scaletta tutta personale. Studiava molte cose (per conto suo), dalla relatività alla meccanica quantistica. Nel 1928 strinse una forte amicizia con Christopher Morcom, un allievo dell'anno seguente. Finalmente poteva parlare di scienza con qualcuno! Purtroppo il ragazzo morì nel 1930, e questo avvenimeneto fu per Alan un colpo durissimo.
Nel 1931 entrò al King's College di Cambridge. A Cambridge tutto fu più facile per lui, e Turing poté studiare i lavori di Russell e Von Neumann. Dopo la laurea nel 1934 seguì il corso di Max Newman sui fondamenti della matematica, nel quale si parlava dei lavori di Godel e Hilbert. Tra il 1936 e il 1937 ideò la macchina astratta che ora viene chiamata appunto "macchina di Turing", e descrisse un numero non computabile. Ottenne anche risultati importanti in teoria della probabilità e sulla funzione zeta di Riemann. Durante la guerra fu uno dei principali artefici della rottura del codice crittografico tedesco Enigma (si veda la biografia di Hodge).
Lavorò in diverse discipline, comprese la chimica e la biologia. Ancora oggi è citato un suo articolo sulla morfogenesi. Alan Turing fu tra i primi ad occuparsi di intelligenza artificiale e fu uno dei fondatori della moderna teoria della computabilità.

Vediamo ora in dettaglio che cosa è una macchina di Turing. Una macchina di Turing consta di un nastro illimitato nelle due direzioni, suddiviso in celle identiche adiacenti, e di una testina mobile. La testina può leggere e scrivere simboli nelle celle. Inoltre può spostarsi a destra o a sinistra. Il tempo è discreto: t = 0, 1, 2, ... Al tempo 0 la testina si trova in una data posizione iniziale. Quando parliamo di macchina di Turing con n stati intendiamo effettivamente dire che ci sono sono n+1 stati possibili: n stati ordinari numerati da 1 a n, più uno stato speciale che denotiamo con H (halt). Se la macchina perviene in questo stato, cessa ogni sua attività. Ma che cosa fa questa macchina? La macchina ad ogni istante t legge il simbolo x contenuto nella cella sulla quale è posizionata la testina. In funzione di x e dello stato s(t) in cui si trova fa tre cose:


L'insieme A dei simboli (o caratteri) che la macchina può leggere o scrivere contiene per ipotesi q elementi, che possono essere arbitrari (lettere o cifre della vostra tastiera, per esempio). In ogni caso A deve contenere un carattere speciale, detto blank. Quando la macchina scrive il carattere blank, cancella quello che c'è nella cella, la restituisce allo stato originario. In sostanza per noi il nastro vuoto è il nastro dove in ogni cella c'è il blank.
Denotiamo con Q l'insieme degli n stati ordinari, con QH l'insieme di tutti gli stati e con M l'insieme dei (due) possibili movimenti.
Con queste notazioni una macchina di Turing T è descritta completamente dalla funzione FT:

[1]
FT : A × Q  --------->  A × QH × M 
La corrispondenza appena evidenziata tra le macchine di Turing e le funzioni [1] permette di contare quante sono le macchine di Turing con n stati. Ricordando che
[2]
ci sono |B||A| funzioni tra l'insieme A e l'insieme B
(dove |X| denota il numero di elementi di X)
otteniamo subito che
[3]
ci sono (2·q·(n+1))q·n
macchine di Turing con n stati, su un alfabeto di q simboli.
E' impossibile capire veramente un'idea matematica (e le sue conseguenze) senza fare degli esempi. Sicuramente Alan Turing trascorse molte ore con carta e penna (se non faceva tutto nella mente) per simulare il comportamento le sue amate macchinette. Ora ci viene in aiuto il computer. Io ho utilizzato una bellissima applet creata da Suzanne Skinner. Potete trovarla qui con le istruzioni per l'uso.

Utilizzerò nel seguito le stesse convenzioni di Susanne Skinner. Tutti i programmi per la macchina di Turing che seguono, girano effettivamente sulla sua applet.

[4]
Un Turing-programma è una lista finita di quintuple r1, r2, r3, r4, r5 dove:
  • r1 e r3 appartengono all'insieme Q degli stati
  • r2 e r4 appartengono all'insieme A dei simboli
  • r5 appartiene all'insieme M dei movimenti
  • r1 è lo stato nel quale si trova la macchina
  • r2 è il simbolo letto dalla testina
  • r3 è lo stato in cui la macchina si troverà nel passo seguente
  • r4 è il simbolo che la testina scrive sul nastro
  • r5 è la direzione in cui muoverà la testina
Inoltre conveniamo che:
  • esiste nella lista una sola quintupla che inizia con r1, r2
  • Q = { 1, 2, 3, ..., n, H }, dove n è il numero degli stati e H è lo stato di arresto
  • A contiene q simboli, compreso il blank che denotiamo con _
  • M = { <, > }
Ad ogni passo la macchina T si trova in un determinato stato r1 e legge il simbolo r2 contenuto nella cella sulla quale è posizionata la testina. Allora T va a cercare la riga che inizia con r1, r2 e, conseguentemente, passa nello stato r3, sostituisce r2 con il simbolo r4, si sposta a destra di una cella se r5 è > oppure si sposta a sinistra se r5 è <.

Per definire completamente una macchina di Turing a n stati su un alfabeto di q simboli occorre scrivere q · n quintuple (vedi [1]). In certi casi però possiamo sapere a priori che, nel corso del calcolo, alcune coppie simbolo-stato non si presenteranno. Più in generale vogliamo che un Turing-programma sia accettato come valido indipendentemente dal numero di quintuple che contiene. Facciamo pertanto la seguente convenzione:

[5]
Se al tempo t la macchina legge il simbolo u e si trova nello stato v
e non esiste nel programma alcuna riga che inizia con u, v allora
la macchina si ferma: non scrive nulla e non si sposta più.
Cosideriamo per esempio il seguente Turing-programma:
[6]
_,1,_,1,>
Questa istruzione suona così: "Se il nastro è vuoto e sono nello stato 1 allora lascio il nastro vuoto, rimango nello stato 1 e mi sposto a destra di una casella".
Poiché ogni macchina deve avere almeno uno stato (lo stato 1), e il blank _ è sempre in A, questo programma di una riga può girare su qualsiasi macchina di Turing. Se passiamo questo programma ad una macchina T, possono accadere sostanzialmente tre cose: