pata da un 1 e, se la cella è occupata daun simbolo diverso, lo cancella e stampaal suo posto un 1.

La seconda parte dell'istruzione speci-fica lo stato successivo della macchina.Come per la specificazione del simbolo,l'indicazione dello stato può comportareo no un cambiamento di stato da partedella macchina. La terza parte dell'istru-

zione specifica se la testina deve esamina-re la cella adiacente a sinistra o a destra diquella appena esaminata.

Tutta l'istruzione può essere abbrevia-ta elencando i tre valori delle variabili(il simbolo sul nastro, lo stato dellamacchina e il movimento della testina)in un ordine prefissato. Per esempio, sea seguito di una data coppia di condi-

2

o o3

o o o o o oo

Macchine di TuringSotto l'aspetto logico, alla base di qualunque calcolatore digitale stauno di questi dispositivi inventati dal matematico inglese A. M. Turing,che segnano, con il solo uso di carta e matita, i limiti della computabilità

condizioni iniziali, la macchina riceveun'istruzione, articolata in tre parti, per ilsuccessivo passo. La prima parte dell'i-struzione indica il simbolo che la mac-china deve lasciare nella cella esaminata.Per esempio, se l'istruzione specifica chenella cella deve essere lasciato il simbolo1, la macchina stampa un 1 se la cella èvuota, non fa nulla se la cella è già occu-

1

STATO S, STATO S

N

el 1900 David Hilbert presentò alCongresso internazionale dei

matematici, tenutosi a Parigi, unelenco di problemi irrisolti: una sorta disfida al mondo della matematica. Il se-condo problema nell'elenco era quello didimostrare che gli assiomi dell'aritmeticasono coerenti, e le ricerche di Hilbert inmerito dovevano portarlo a proporre unproblema più generale, l'Entscheidungs-problem o problema della decisione: sco-prire un metodo generale per stabilire seuna formula della logica formale può es-sere soddisfatta, ovvero risultare vera.Il problema fu risolto solo nel 1936 e lasua risoluzione rappresentò una svoltastraordinaria e inattesa. All'Università diCambridge un giovane studente di mate-matica del King's College, Alan MathisonTuring, era venuto a conoscenza del pro-blema di Hilbert grazie a una serie di con-ferenze tenute da M. H. A. Newman. Tu-ring rifletteva spesso sul problema duran-te le sue lunghe passeggiate pomeridianenella campagna inglese, e proprio dopouna di queste passeggiate gli balenò allamente la risposta: il problema di Hilbertnon può essere risolto.

La pubblicazione in cui Turing annun-dava il suo risultato ha un significato chetravalica lo specifico problema affrontato.Nel riflettere sul problema di Hilbert, Tu-ring si chiese come fosse possibile dare unadefinizione precisa del concetto di metodo.Partì dall'idea intuitiva che un metodo è unalgoritmo, cioè un procedimento che puòessere svolto meccanicamente senza alcunintervento creativo, e dimostrò che l'ideapoteva essere perfezionata fino a dare unmodello particolareggiato del processodella computazione in cui un algoritmo èsuddiviso in una successione di passi sem-plici, atomici. La macchina di Turing èappunto il costrutto logico che costituisce ilmodello della computazione.

Per descrivere la macchina di Turing, ilmodo più semplice è quello di parlare diparti meccaniche come ruote, nastro per-forato e un meccanismo di esplorazioneche può muoversi avanti e indietro lungoil nastro. Questo apparato meccanico nonè essenziale (in ultima istanza, il dispositi-

di John E. Hoperoft

vo di Turing dà solo un corpo a un metododi ragionamento matematico), ma sareb-be fuorviante fare del tutto a meno dellametafora meccanica. La metafora risultòsuggestiva anche per Turing stesso, che fufra i pionieri nello sviluppo del calcolato-re digitale. Va anche aggiunto che oggi lamacchina di Turing è uno strumento con-cettuale di grande potenza per lo studiosodi scienze del calcolatore tanto quantoper il logico. Il suo significato per la teoriadella computazione è fondamentale: datoun tempo finito, anche se molto lungo, lamacchina di Turing è in grado di effettua-re qualunque calcolo che possa essereeseguito da un moderno calcolatore digi-tale, di qualunque potenza esso sia.

L'universalità della macchina di Turingnon significa che essa possa costituireanche un effettivo calcolatore. Un calco-latore reale può funzionare a una velocitàdi gran lunga superiore a quella di unamacchina di Turing perché, nella sua pro-gettazione, si sacrifica intenzionalmentela chiarezza di funzionamento a favoredella velocità e dell'efficienza. Tuttavia,per lo studio teorico della capacità fon-damentale dei calcolatori reali nella riso-luzione di problemi, la macchina di Tu-ring è diventata indispensabile: peresempio, ha consentito ai matematici eagli studiosi di scienze del calcolatore didimostrare l'esistenza di molti altri pro-blemi, oltre a quello di Hilbert, che nonammettono una soluzione, indipenden-temente dalla velocità o dalla potenza delcalcolatore che li affronta.

Come funziona una macchina di Turing

Che cos'è una macchina di Turing, ecome funziona? Andrew Hodges, nella suarecente biografia di Turing, la paragona auna comune macchina per scrivere. Comela macchina per scrivere, la macchina diTuring possiede una testina di stampamobile che stampa su una superficie appo-sita, uno alla volta, simboli discreti tratti daun alfabeto finito. Per semplificare i mo-vimenti della testina, si ipotizza che la su-perficie di stampa sia un nastro suddivisoin celle o segmenti discreti. La testina di

stampa della macchina di Turing deve per-tanto muoversi solo in una dimensione,verso sinistra o verso destra, e la macchinanel suo funzionamento non deve tenerconto di complessità irrilevanti come lalunghezza della riga di stampa o il valoredell'interlinea. In ogni cella del nastro puòstare un solo simbolo stampato, ma non sipongono limiti alla lunghezza del nastroné, di conseguenza, alla lunghezza della«parola», cioè della successione di simboli,che può essere stampata.

La testina mobile di stampa della mac-china di Turing può svolgere due altrefunzioni: come le testine di molte mac-chine per scrivere dell'ultimo decenniopuò eliminare o cancellare un simboloalla volta sulla superficie di stampa e (adifferenza delle macchine per scrivere)può anche «leggere», cioè registrare ilcontenuto simbolico delle celle del na-stro, una cella alla volta. I simboli sulnastro possono così fungere da ingressoper la macchina e contribuire a determi-nare il comportamento successivo.

Nel corso della sua attività una macchi-na per scrivere può assumere vari stati,cioè vari modi di funzionamento. Nellostato «normale» scrive lettere minuscolee alcuni caratteri speciali (virgola, paren-tesi ecc.), mentre nello stato con tastodelle maiuscole inserito scrive le letteremaiuscole, i numeri e altri caratteri spe-ciali. Analogamente, anche una macchinadi Turing può assumere un numero finitodi stati, ognuno dei quali costituisce pre-sumibilmente una diversa configurazionedella macchina: siccome però la macchinadi Turing è un dispositivo relativamenteastratto, di solito non si tenta di dare, diquesti stati, una descrizione meccanicapiù concreta. Sarà sufficiente descrivereciascuno stato della macchina attraversogli effetti che produce sull'attività dellamacchina stessa.

L'attività di una macchina di Turingconsta interamente di passi discreti eistantanei, e ciascun passo è determinatoda due condizioni iniziali: lo stato dellamacchina in quell'istante e il simbolo cheoccupa la cella del nastro esaminata inquello stesso istante. Data una coppia di

o o

o

o o o

SIMBOLO LETTO

STATO SUL NASTRO

O 1

S,

— O SD

S, 1,S, , D 1,S,,D

S,— STOP STOP

STATO S,

STATO

SIMBOLO LETTOSUL NASTRO

O 1

— --1—0.S,.D 0,S,,D

s21,S,,D 1,SD

S, _.__— —

—./_STOP STOP

La somma di 2 e 3 viene eseguita da una macchina di Turing in quattropassi. Ciascun numero da sommare viene rappresentato su un nastro innotazione unaria, cioè come una parola di I delimitata alle due estremi-tà da zeri. La macchina può registrare il contenuto di una cella delnastro alla volta (celle in colore) spostandosi a sinistra o a destra lungoil nastro in una serie di mosse discrete. L'obiettivo della macchina èquello di generare una parola di cinque 1 consecutivi e quindi difermarsi. La tabella delle istruzioni, riportata sotto ciascuna macchinanel diagramma, è un insieme prestabilito di mosse per tutte le possibilicondizioni iniziali e fornisce una procedura per sommare due numeriqualunque. Seguendo le istruzioni, la macchina cancella lo O che separadue parole di 1 e fa scorrere di una cella verso destra la parola di

o

STATO

SIMBOLO LETTOSUL NASTRO

O 1

— -1—0.S,,D 0.S,,D

S2

—_.--_}—1,S,,D 1,S,,D

S, __,-STOP STOP

4

STATO S,

o o o

STATO

SIMBOLO LETTOSUL NASTRO

O 1

S, .__

— -1- 0,s,,D 0,S,,D

S,

1,S,.D 1,S,,D--__/J—S, .__.__— —

—/—STOP STOP

sinistra, in modo che si unisca alla parola di destra. Il numero dellecondizioni iniziali previste nella tabella deve essere sufficientementeelevato da tener conto di tutti i casi che possono presentarsi sul nastro; ilnumero può essere aumentato aumentando il numero degli stati inter-ni, cioè delle configurazioni, presenti nella macchina di Turing. Perogni possibile combinazione di simbolo sul nastro e di stato dellamacchina, la tabella deve o fermare la macchina o specificare trevariabili. In primo luogo, deve dare il simbolo che la macchina develasciare sulla cella del nastro registrata in quel momento; in secondoluogo, deve specificare quale stato la macchina deve assumere prima diregistrare un'altra cella del nastro e, infine, deve indicare se la macchinadeve spostarsi lungo il nastro di una cella verso sinistra o verso destra.

o o o o o o

o o o o

54 55

PAROLE DI LUNGHEZZA 1:

ABC Z# 1 9 O +

i I I I I I I I I1 2 3 ... 26 27 28 36 37 38

PAROLE DI LUNGHEZZA 2:

AA AB A BA

1+50 52 ... 100 101 150 502 + 50

PAROLE DI LUNGHEZZA N:

AA.. .A

AA...B

LOAD#A/X=A/IF#X-#D0#23/GO#T0#100

1+R

2+R

R

(R=50+ 502+ . +50N-1)

50»+R

z1l0

f,

3

Le successioni di caratteri di lunghezza finita si possono mettere in corrispondenza biunivocacon gli interi positivi, purché ogni carattere sia scelto da un insieme finito. Secondo la definizionedi Georg Cantor, la corrispondenza biunivoca implica che i due insiemi siano di dimensioniequivalenti, anche se si tratta di due insiemi infiniti. Qualunque insieme che possa essere messoin corrispondenza biunivoca con l'insieme degli interi è detto «contabile» o «numerabile».Qualunque programma per calcolatore e qualunque possibile tabella di istruzioni per una mac-china di Turing possono essere codificati come successione finita di simboli e pertanto la corri-spondenza biunivoca con l'insieme degli interi dimostra che sia l'insieme dei possibili program-mi per calcolatore, sia l'insieme delle possibili macchine di Turing sono infiniti numerabili.

L'insieme delle funzion matematiche che hanno come argomenti e valori numeri interi è nonnumerabile: in altre parole, queste funzioni sono «troppe» per poter essere messe in corrispon-denza biunivoca con l'insieme infinito degli interi. Supponiamo, per assurdo, che tutte questefunzioni si possano identificare in base al loro indice sottoscritto e quindi possano essere elenca-te in un ordine dato. Il valore della funzione, per ogni intero, può essere dato allora come unasuccessione infinita di cifre. Poiché una funzione è determinata dalla sua successione infinita dicifre, si consideri una funzione costruita modificando la prima cifra nella prima successione, laseconda cifra nella seconda successione e così via. La successione di cifre che definisce lafunzione così costruita (in colore) differisce da ciascuna successione dell'elenco originale almenoper una cifra. Di conseguenza l'ipotesi che sia possibile elencare tutte le funzioni porla a unacontraddizione: è sempre possibile costruire una nuova funzione, assente nell'elenco iniziale.

fi

1 2

3

3

2

4

1

5

7

6

2

f2 5 9 1 2 1

f,

f4

9

1

2

8 1

6

161

1

2

6

4

f,

f6

1

1

1

7

2

1

4

8

111

9 6

F 2 4 2 5 2 5

STATOSIMBOLO O

SULNASTRO

COMMENTOMOSSA

ESEMPLIFI-CATIVA

SIMBOLO 1SUL

NASTROCOMMENTO

MOSSAESEMPLIFI-

CATIVA

S, 0, S„ D Comincia con uno spostamento a destrafino all'estremità sinistra del registro N.

A, B 0, S, D Contrassegna l'estremità sinistra delregistro N con uno 0.

1

S, 0, S,, D Scorrimento a destra oltre la separazione. 4. 12, 20 1, S'2 D Scorrimento a destra lungo il registro Ndal contrassegno fino alla separazione.

2. 3, 11

5, 1, S,. S Copia 1 all'estremità destra del registro P. 5, 14, 23 1, 5,' D Scorrimento a destra lungo gli 1 nelregistro P. 13, 21. 22

S, O, S,, S Scorrimento a sinistra oltre laseparazione. 6. 16, 26 1, S,, S Scorrimento a sinistra lungo il registro P. 15, 24, 25

S 6 1, S., S

Individuato il contrassegno Oall'immediata sinistra della separazione,il che indica come sia stata aggiuntaal registro P una copia completadel registro N.

27 1, Se S'

Scorrimento a sinistra di una unità, dallaseparazione all'interno del registro N. Lostato non può rimanere S 6 ; se così fosse,l'eventuale incontro con il contrassegno Ofarebbe fermare prematuramente lamacchina di Turing.

7, 17

S, 1, S,, D Comincia lo spostamento delcontrassegno O di una unità a destra.

9, 18 1, Se S'Continua lo scorrimento a sinistra lungoil registro N fino al contrassegno 0.

8

S,La condizione non è mai incontrata, diconseguenza si può inserire qualunqueistruzione fittizia oppure si può noninserire alcuna istruzione.

0, S,, DCompleta il trasferimentodel contrassegno O di una unità a destra;ripete il ciclo.

S, Completato il sottoprogramma di copia,si ferma o attende nuove istruzioni.

30 1, S6 S'Scorrimento a sinistra fino all'estremitàsinistra del registro N. 28, 29

La macchina di Turing copiatrice fa parte di dispositivi più comples-si. Data una parola su un nastro (una successione di 1), la macchina

ne scrive una seconda con lo stesso numero di I alla destra dello Oche segna la fine della prima. Qui la macchina copia la parola 111.

SEPARAZIONEi

7 15Ls.»

23Lisd

ArL

i'', r.1 Lssrl

00111'100000

I 1'00011010,00j

1 1

0010101100 0011001 1Q0REGISTRO A/ 'REGISTRO P N P N P N P

B 8 16 24 Lis.rjLIS,rj Ls.»Lis`

O O I 1 I O O O 0 0I

000 1 1O1 0001 0 011 011 O 1 1 1 O O 010 1 1 O 011 11110jN P N P N P N

1 9 17 Lis,ri 25L1S4jLsii I s

h il001 1 1 O O 00 O 0i0 O 1101

I I00 () 00 1 011 01111 O 0 0011 00 11111 O

N P N P I N P N P

2L s.J

10 18Lis'i

26Ls41Lsid

0001110

1

0000 0011101000 001010I

1100 1001100111110I- N P 1 N 1 P 1 N P I N P

3

HS2j

11 19 271_ S2_1 L Sr] L,s5_1

O 00I

11 00 00 O 'O 010 I 01 000 0 O lil 011 10 0 0 0 1 110,011 li 0N P I N P 1 N P N P

4LIS21-1

12 20 28I S,1

i LiS2 j S8 T)

O 00 1 10 O O 00 O O 01 110

I1 00 0 0 O 1 1

I

01iIO O 00 1 1 110 1 1 1 ON 1 P N P N I P N I P

5 13

Lis'j21 29 Ls.JLS371 Sia J

000111

00000 0010101000 0011001100 00 1101110N P N P 1 N 1 P 1 N I P

6 14 Lssi 22 30Lis,j LIS,i LI% j

0 00I

1 1 1 0 1 00 O O 01 0 1 0 11 1

00 0 0 01 1 001 1 0 O O O 111 O 1 11 ON P I N P

,N P N P

zioni iniziali la macchina deve lasciare ilsimbolo 1 nella cella esaminata, assume-re poi lo stato S2 e spostare la testina distampa sulla cella adiacente a sinistra,l'istruzione può essere abbreviata nellaforma (1, S2, S).

C'è un ottimo modo per capire comefunzioni una macchina di Turing: cercaredi costruirne una. In questo contesto, co-struire una macchina di Turing significacostruire una tabella di istruzioni che spe-cifichi l'attività della macchina stessa pertutte le possibili coppie costituite da uno

rappresentato sul nastro come una «paro-la» formata da N 1. Se debbono esserestampati sul nastro due numeri M e N, èpossibile rappresentarli con una parolaformata da M 1, seguita a destra da uno Oe ancora a destra da una parola di N 1.Supponiamo che la macchina di Turingsia nello stato iniziale S i e che la testinastia esaminando 1'1 più a sinistra nellaparola di M 1. Per costruire una macchinadi Turing che effettui le addizioni, si vuolgenerare una tabella di istruzioni che in-duca infine la macchina a stampare unaparola di M +N1 e quindi a fermarsi.

Per raggiungere l'obiettivo, basta sem-plicemente prendere la parola più a sini-stra, quella di M 1, e spostarla di una cellaverso destra. Se questo scorrimento è ef-fettuato correttamente, le due parole nonsono più separate da uno zero e l'unica pa-rola che ne risulta ha la lunghezza M + N.La macchina di Turing non può spo-stare la parola di 1 tutta in una volta: latestina può procedere di una sola cellaalla volta. Per ottenere il risultato volutosi può creare allora una serie di istruzioniper una macchina di Turing a tre stati. Nelprimo stato la testina esamina il nastro dasinistra verso destra, una cella alla volta,finché non raggiunge 1'1 più a sinistra.Cambia 1'1 in O, entra nel secondo stato econtinua a muoversi verso destra. Nelsecondo stato, quando la testina trova un1 in una cella, non fa nulla (non modificané il simbolo sul nastro né lo stato dellamacchina), ma si limita a spostarsi a de-stra di una cella. In questo modo la testinaesamina gli M - 1 simboli 1 che restanonella prima parola. Quando, infine, trovauno O, le istruzioni dicono alla testina dimodificare lo O in un 1 e di fermarsi.

A questo punto il lettore è invitato acostruire una macchina di Turing che tro-vi il prodotto di due numeri dati. Le con-venzioni per l'ingresso sono identiche: idue interi da moltiplicare sono rappresen-tati da due parole consecutive di 1, sepa-rate da uno O. L'uscita, una parola di 1 lacui lunghezza deve essere uguale al pro-dotto delle prime due parole, può essererappresentata da una terza parola alladestra delle prime due. Potete trovare unmodello funzionante nell'illustrazione apagina 58. Mi sembra giusto avvertirvisubito che la costruzione fa uso di qualchetrucco e richiede un'accurata registrazio-ne delle mosse. Mi sembra corretto anchedare qualche suggerimento: chi ama irompicapo e vuole provare senza aiutinon deve fare altro che saltare il prossimoparagrafo.

Come si costruiscono programmicomplessi

Il procedimento della moltiplicazionerisulta molto più facile se prima si svilup-pa un programma per copiare una parolaimmediatamente a destra di un puntodato. È sempre possibile copiare N 1 conuna macchina a N stati: gli stati possonoeffettivamente contare gli 1 nella parola.Però, dal momento che il numero deglistati non deve crescere indefinitamente, èutile trovare un sistema per copiare la

stato e da un simbolo sul nastro. In prati-ca, la costruzione della tabella significaanche attribuire alla macchina un numerodi stati abbastanza grande da consentirlel'esecuzione del compito in gioco.

La macchina addizionatrice

Come si può progettare una macchinadi Turing che sommi due numeri e si fer-mi? Di solito (ma non è essenziale) siammettono solo due simboli, per esempioO e 1. Un dato numero N allora può essere

56

57

UN SIMBOLO

1239 7r

DUE SIMBOLI

11 99 9! (=l x2x3x4x5x6x7x8x9=362 880) 9 9 (=387 420 489)

TRE SIMBOLI

DUE 9+9 3'4 (=3x[3x(3x 3)J=34=81)

999 (=9387 420 489; / 0369 700 000)

QUATTRO SIMBOLI33 27

NOVE 10" 3TT4 (=31[3T(3t3)]=3 3 =33 =37625 597 484 987

103 638 000 000 000)

CINQUE SIMBOLI)333 LIVELLI3

DIECI 31114 ( = 311[311(31-13)] = 3Tif31133 1=3113"

.3

:3)3LIVELLI= 33

}333 LIVELLI

59 SIMBOLI

IL# SUCCESSORE # DEL # MASSIMO* NUMERO# ESPRIMIBILE #CON# 59# SIMBOLI

Il paradosso di Richard (dal nome del matematico francese Jules Richard) si presenta se sisuppone che gli interi positivi possano essere ordinati, cioè elencati, in funzione del numero disimboli necessari per specificarli. Singoli interi molto grandi possono essere indicati con simbo-li speciali, come la notazione a frecce introdotta da Donald E. Knuth della Stanford Universi-ty. In base alla sua descrizione, il numero che sembra specificato, nella tabella. con 59 simboli,dovrebbe essere maggiore di qualunque numero specific.,hile con 59 simboli: un paradosso.Un altro paradosso si presenta se si cerca di trovare una a..ta macchina di Turing in un elencodi macchine di Turing ordinate secondo la lunghezza della parola necessaria per codificarle.

101ARAZIONE SE PARAZ IO N E

134 139r17":7TY

Tri i. i i i ........ 001 i i i., i i .... 0100 i i. 111 II

i i i ....135

REGISTRO M REGISTRO N REGISTRO P M N P . M N

.

P

102L s.i 185 [ S. I

O 1011100000000I I

ooÌoiI I

1101110000 014111011111 0I 1 I

M N P N P N P103 136

41.11101110...186

, ,00 011100000i 00, I 01 0111.1111110,M N P M N P M N P

104 137 187

•001 1 100000000 01 011101110000 O 1011 01111110M N P M N P M N P

105 138Ls1j

188i s,, j

O O 1 O 1iooI

O O O O O Oi i

O 1 O 1 I I O I I I O O O O 110 0 1 1 101 1 111 0

'. M N P M N P M N P

STATOSIMBOLO O

SULNASTRO

COMMENTOMOSSA

ESEMPLIFI-CATIVA

SIMBOLO 1SUL

NASTROCOMMENTO

MOSSAESEMPLIFI-

CATIVA

s, a O, DS,,, Comincia con lo scorrimento a destrafino all'estremità sinistra del registro M.

101 0, S„, D Contrassegna con uno O l'estremitàsinistra del registro M.

102

s,, 0, S,, D

Scorrimento a destra oltre la separazionefra i registri M e N; comincia ilsottoprogramma di copia (si vedal'illustrazione della pagina precedente).

104, 138 1, 5 1 , D'

Scorrimento a destra lungo il registro Mdal contrassegno fino alla separazione.

103

sa o, S,,, SScorrimento a sinistra oltre laseparazione fra i registri N e M; fine delsottoprogramma di copia.

134, 185 1, S,, SScorrimento a sinistra fino all'estremitàsinistra del registro N.

Nonindicata

s,, i, sl a , s

Individuazione del contrassegno Oall'immediata sinistra della separazionefra i registri N e M, indicante che ilprodotto dei numeri immagazzinati neiregistri M e N è stato memorizzato nelregistro P.

186 1, S1,, S

Scorrimento a sinistra di una unità nelregistro M dalla separazione fra i registriN e M. Lo stato non può restare 5,,: secosì fosse, l'eventuale incontro con ilcontrassegno O farebbe fermareprematuramente la macchina di Turing.

135

s„ 1, 5, 4 , DComincia il trasferimento delcontrassegno O nel registro M, una unitàa destra.

136 1, S,,, DContinua lo scorrimento a sinistra lungoil registro M fino al contrassegno 0'

Non

s,,1

La condizione non è mai incontrata, diconseguenza si può inserire qualunqueistruzione fittizia oppure si può noninserire alcuna istruzione.

0, 5, 1 , DCompleta il trasferimento delcontrassegno O nel registro M una unità adestra; ripete il ciclo.

137

S„ o,—,—Completato il sottoprogramma dimoltiplicazione, si ferma o attende nuoveistruzioni.

188 1, S, SScorrimento a sinistra fino all'estremitàsinistra del registro M. 187

Una macchina di Tming può effettuare una moltiplicazione se vieneinclusa in un'altra macchina di Tuting che può copiare una parola di 1.Nell'esempio la macchina richiede 88 cicli per trovare il prodotto di 2 e di3; le interruzioni nella numerazione sono cicli di macchina che saltano a

stati definiti per la macchina copiatrice (si veda l'illustrazione dellapagina precedente). Nell'ultimo ciclo il prodotto di 2 e di 3 viene visualiz-zato come una parola di sei 1 in quella sezione del nastro che vienechiamata «registro P», subito dopo lo O che la separa dai due fattori.

NUMERO DI STATIMASSIMO NUMERO

DI 1 STAMPATI LIMITE INFERIORE PER IL VALORE DI c

3 o-(3) 6

4 o- (4) 12

5 o-(5) 17

6 tr(6) 35

7 o- (7) 22 961

8 a- (8) 392 _;- 7,9 x 104'

9 (7(9) 392 + 1

10 c7(10) .', a

problema dell'«alacre castoro» («busy beaver» problem) consiste nel trovare il massimo nume-ro di 1 che può essere stampato da una macchina di Turing a V stati che inizi la sua attività conun nastro pieno di O e alla fine si fermi. Il numero, che dipende da N, è il valore di una funzioneche viene indicata come a(N). Nel 1962 Tibor Rado dell'Ohio State University ha dimostratoche la funzione cresce troppo rapidamente per essere computabile. Nella tabella sono indicati isuoi confini inferiori, stimati per piccoli valori di N. Il confine inferiore per a (10) può essereespresso con un numero a il cui valore è circa a (10) è a elevato alla a elevato alla a... e cosìvia, per una serie di a, esponenti l'uno dell'altro, la cui «altezza» è espressa da un'altra serie di a,esponenti l'uno dell'altro. Questo processo di definizione di una serie di esponenti medianteun'altra serie di esponenti è eseguito 10 volte, per poter esprimere il confine inferiore dia (10).

parola senza contarne gli elementi. Si puòfar scorrere un contrassegno lungo la pa-rola da sinistra a destra; il contrassegno èuno O che progressivamente prende ilposto di ciascun 1 nella parola. Ogni voltache il contrassegno procede da una cellaalla successiva, le istruzioni dicono allatestina di andare fino all'estremità destradella parola, di saltare uno O che indica laseparazione e quindi di modificare in un 1

il successivo O incontrato. Se la testina fala spola avanti e indietro una volta perogni passo avanti del contrassegno, im-mediatamente a destra della prima parolaviene scritta una nuova parola di 1 (siveda l'illustrazione della pagina 57).

Con un po' di pratica si impara in frettacome costruire macchine di Turing in gra-do di eseguire semplici programmi di cal-colo e come combinarle per eseguire cal-

coli più complessi. Per esempio, si può va-lutare un'espressione polinomiale com-binando i programmi per l'addizione, perla copiatura e per la moltiplicazione.Ancora più versatili si dimostrano breviprogrammi elementari per la manipola-zione di simboli, come «sposta la testina adestra finché incontra uno O» e «sposta diuna cella a destra il contrassegno dellaparola più a sinistra». Varianti di questi

brevi programmi sono utilizzate sia nellamacchina di Turing copiatrice, sia nellamacchina moltiplicatrice.

Se si è disposti a tentare di costruire,per esempio, la macchina di Turing cheeffettua le moltiplicazioni, presto si co-minciano a capire le difficoltà che si in-contrano nella progettazione di un utileprogramma di calcolatore. La maggiorparte delle macchine di Turing con pochistati possibili non eseguono alcun compi-to utile o addirittura solo sensato. Moltefiniscono in cicli infiniti e fanno la spolaindefinitamente avanti e indietro su unnastro, senza mai fermarsi. Fra le macchi-ne che eseguono operazioni sensate, poi,bisogna scegliere una combinazione dimacchine che lavorino insieme con effi-cienza. L'impressione iniziale può essereche i compiti più semplici siano tremen-damente difficili e che non vi sia speranzadi arrivare a calcoli realistici. Le difficoltàpossono essere frustranti, ma sono pura-mente tecniche: con pochi programmiben scelti la potenza della macchina diTuring nella soluzione di problemi crescein forma esplosiva e si è colpiti non dalladebolezza della macchina, ma dal suopotenziale. Come Turing riuscì a dimo-strare, è possibile combinare semplicimacchine di Turing in una macchina ingrado di eseguire qualunque compitodescrivibile in maniera esplicita.

Il calcolatore elettronico, che in partedeve la sua esistenza alle macchine con-cettuali di Turing, probabilmente è ladimostrazione più convincente della ca-pacità di calcolo di queste macchine. Nelcorso del suo lavoro, Turing sottolineòche qualunque macchina di Turing M puòessere codificata su nastro come una suc-cessione di O e 1. La realizzabilità di que-sta codificazione è possibile, fondamen-talmente, grazie al fatto che una macchinadi Turing è definita univocamente dallasua tabella di istruzioni, tabella che deveavere lunghezza finita perché tanto glistati della macchina quanto l'alfabeto deisimboli per il nastro sono finiti.

La macchina di Turing universale

Turing dimostrò che il funzionamentodi qualunque macchina di Turing su qua-lunque parola di simboli X sul nastro puòessere simulato da un'altra macchina diTuring, la «macchina universale». I sim-boli sul nastro registrati dalla macchinauniversale di Turing sono raggruppati indue sezioni principali: a sinistra si trova ladescrizione codificata della macchina diTuring M e a destra si trova la successionedi simboli X che M avrebbe incontratoesaminando il proprio nastro. La macchi-na universale è poi costruita in modo taleche la sua testina di stampa faccia la spolaavanti e indietro fra la sezione sinistra equella destra del nastro. Essa conservatraccia dello stato codificato di M che vie-ne consultato mediante un complesso si-stema di contrassegni. Turing dimostròche la macchina universale ha sulla parolaX esattamente lo stesso effetto cheavrebbe la macchina M.

La macchina universale di Turing,

dunque, simula con successo qualunquemacchina di Turing M e questo perché Mè una macchina descrivibile completa-mente mediante un numero finito di sim-boli. In linea di principio, però, qualun-que calcolatore digitale può essere de-scritto nello stesso modo: il calcolatore ha

un numero di stati interni molto elevato,ma pur sempre finito, e la sua risposta aidati forniti in ingresso è determinatacompletamente dall'insieme finito deglienunciati che costituiscono la sua pro-grammazione. Ne segue che una descri-zione completa di qualunque calcolatore

58

59

STATO

SIMBOLO LETTOSUL NASTRO

0O 0 O

Si 1 ,S7,D

O O O S2 1.S3.D

Si noti innanzitutto che a è monotona crescente: cioè, se X >Y,a (X)>a (Y). Qualunque sia ilnumero di 1 stampati da una macchina di Turing a N stati che si ferma, è sempre possibile costruireuna macchina di Turing a (N + 1) stati che aggiunga un 1 alla parola di 1 e quindi si fermi.

Lis„i

Supponiamo che esista una macchina di Turing a Z stati che calcoli a (Ma).Per la definizione di a e per il calcolo mostrato nell'illustrazione della pagina a fronte,

a (M + 19 + (W). (1).Se M è abbastanza grande, però, l'enunciato (1) contraddice il fatto chea è monotona crescente.Per dimostrarlo, poniamo M = Z + 20, ovvero Z = M — 20.Allora M + 19 + Z = M + 19 +M — 20= 2M— 1.Per le leggi dell'algebra elementare 2M- 1 = M' - (M - 1) 2 e pertanto M + 19 +Z = M' - (M - 1)'.Poiché (M - 1) 2 > 1, M - 1 > W - (M - 1)'.Pertanto, poiché a è monotona crescente,

a (M 2 — 1) > a (M' — — 1) 2 ) = a (M + 19 + Z) a (M).Dal momento che a (M' — 1) > a (M a), però, a non può essere monotona crescente e pertantol'ipotesi che esista una macchina di Turing a Z stati in grado di calcolare a (W) porta a unacontraddizione.

o 1 1 H 1 010

Ir(N)

SN

0 1 1 .21 00!

0 1

••• 1 1 O

cr(N) + 1

STATOSIMBOLO LETTO

SUL NASTRO

O 1

SN 1 .SN n i .S 1 .SN.D

SN- i STOP STOP

I passi finali nella dimostrazione della non computabilità di a(N) derivano una contraddizionedall'ipotesi che esista una macchina di Turing a Z stati che, data una parola di M 2 1, calcola a (M2).

O 111 0 o ololo'

S,,,

O 1 . —L1_0101

M-1

1

SA4+1

011 ••• 1 1 o

ism+1,81

1 1

o

S M -1 1.Sm_ 1.S

1 O

1 ••• 1 1 O 1 1

M

••• 1 O 1 1 • •• 1

M M2

••• 1 0 1 1 •••

M m2

"4 O 1 1 •••

O

O

O

O1•••

A42

NUMERO TOTALEDI STATI

M

STAMPA M 1SUL NASTRO VUOTO

AVVIA IL SOTTOPRO-GRAMMA DI COPIA

M+1

SOTTOPROGRAMMADI MOLTIPLICAZIONE

STATOSIMBOLO LETTO

SUL NASTRO

O 1

Sm..17 D.Sm,,,D D.Sim,I,D

5M+18 0•Sm+ /9• D 0,SA4* 19 D

Sm. 19 0.SM-12 --l• D 0.Sm9,D

COPIA

M+9MOLT PLICA

M x M

M+16 Sm+L 1 +15

O 1 1 ••• 1

M

Sm+

ni

7 i

CANCELLA GLI 1 NEIAllW1 1 1PRIMI DUE REGISTRI

M

SM+18

0 0 1 1 .—

M— 1

O O O o • 0 0

M

M+19

O O O ••• O O

M

SM+19+2

CALCOLA a (Ma)O 1

M2

M+ 19 + I 1!111+19+Z

La dimostrazione della non computabilità di a (N) inizia con una stimadel numero di stati necessari per generare una parola di M 2 1 su unnastro inizialmente pieno solo di 0. Le macchine di Turing per copiare emoltiplicare, visualizzate nelle illustrazioni delle pagine 57 e 58, sono

SA,

SOTTOPROGRAMMA DI COPIA

M m2

MJ••• 0 0 l 1 ... 1 O

M m2

STATOSIMBOLO LETTO

SUL NASTRO

O 1

Sm.19+1 7

Sm 19+Z STOP

STOP

combinate a formare una macchina con M + 16 stati. Tre ulteriori staticancellano le due parole più a sinistra, lasciando una parola di M2 1. Siassume l'esistenza di una macchina a Z stati che, data una parolaqualunque formata da N 1, generi una parola di a(N)1 (in colore).

digitale può essere codificata su un nastrocome una successione di O e 1, e qualun-que dato in ingresso può essere codificatosul nastro alla destra della descrizione delcalcolatore. Consultando alternativa-mente sul nastro la descrizione del calco-latore e la successione dei dati in ingresso,la macchina universale di Turing puòsimulare passo per passo il modo di ope-rare del calcolatore sui dati in ingresso.

Qualunque calcolatore reale, se è forni-to di una memoria abbastanza capiente dasvolgere il ruolo di nastro per la manipo-lazione dei simboli, può recitare la partedella macchina universale di Turing. Peresempio, se un microcalcolatore domesti-co fosse programmato per funzionarecome una macchina universale di Turing ese, come dati in ingresso, ricevesse unadescrizione codificata di un grande calco-latore «mainframe», esso simulerebbe ilfunzionamento del grande calcolatore suqualunque successione di simboli di dati.In questo senso tutti i calcolatori digitalipossono calcolare esattamente la stessaclasse di funzioni matematiche, e cioè laclasse delle funzioni che possono esserecalcolate da qualche macchina di Turing.L'unicità di questa classe di funzioni costi-tuisce un forte sostegno per la definizioneformale che Turing diede di «computabi-lità»: una funzione matematica è compu-tabile se può essere calcolata da qualchemacchina di Turing. (La lingua inglesepossiede un solo vocabolo, to compute,per le due nozioni; tradizionalmente, initaliano si riservano, in questi contesti, ilverbo «calcolare» e i suoi derivati per lanozione intuitiva e il verbo «computare»e i suoi derivati per la nozione formale.)Turing sostenne in modo persuasivo chela sua definizione è equivalente a qualun-que ragionevole interpretazione del con-cetto intuitivo di calcolabilità. Probabil-mente vale però la pena di dire che non hasenso chiedere una dimostrazione mate-matica rigorosa del fatto che una defini-zione formale come quella di Turing cat-turi a pieno il senso di qualche nozioneintuitiva.

Il programma di Hilbert

Per capire come mai Turing si preoccu-passe tanto di definire la computabilità, ènecessario avere qualche idea della storiadella logica matematica prima del 1936.11rigore matematico che conosciamo oggi èuno sviluppo relativamente recente. Ilprimo tentativo serio di ridurre gli enun-ciati matematici a enunciati della logicaformale fu intrapreso da Gottlob Fregenel 1879, con la pubblicazione della suaopera Begriffsschrift, sulla notazione deiconcetti. Il problema posto da Hilbertpertanto aveva un significato immediatoper la matematica: se lo schema di Fregepoteva essere completato e se si trovavaun metodo per determinare la verità o lafalsità di qualunque enunciato della logi-ca formale, allora quel metodo potevadeterminare anche la verità o la falsità diqualunque enunciato matematico, indi-pendentemente dalla sua complessità. Sesi poteva trovare un metodo simile, con-

getture matematiche come l'«ultimo teo-rema» di Pierre de Fermat, che per secoliaveva resistito ai tentativi di dimostrazio-ne (o di refutazione), potevano essereimmediatamente risolte. Una rispostaaffermativa all'audace sfida di Hilbertridurrebbe così tutta la matematica al cal-colo meccanico.

Gran parte del programma di Hilbertfu messa in disarmo, nei primi decenni delsecolo, da due importanti sviluppi. Nel1901 Bertrand Russell scoprì un parados-so inconfutabile nella teoria elementaredegli insiemi, teoria essenziale per il pro-gramma fregeano di riduzione della ma-tematica alla logica. Russell comunicò lasua scoperta a Frege proprio mentre an-dava in stampa il secondo volume dell'ul-tima grande opera di Frege sui principidell'aritmetica. Grundgesetze der Arith-metik. Frege chiuse così il volume con unanota di sconforto: «A uno scrittore discienza ben poco può giungere più sgradi-to del fatto che, dopo completato un lavo-ro, venga scosso uno dei fondamenti dellasua costruzione. Sono stato messo in que-sta situazione da una lettera del signorBertrand Russell, quando la stampa diquesto volume era quasi completa». Fre-ge non poté eliminare le falle dalla suaopera, ma comunque in seguito Russell eAlfred North Whitehead riuscirono a sal-vare il programma fregeano e ad aggirareil paradosso nella teoria degli insiemi.

La seconda grande scoperta è dovuta a

Kurt Géèdel, a quel tempo all'Universitàdi Vienna. Nel programma hilbertianoera implicita l'assunzione che dovesse esi-stere qualche metodo per distinguere,nella logica formale, gli enunciati veri daquelli falsi: il problema era trovare unmetodo del genere. Ma l'assunzione nonaveva fondamento: Góclel dimostrò nel1931 che qualunque sistema coerente dilogica formale, abbastanza potente daformulare enunciati della teoria dei nu-meri, deve comprendere enunciati veridi cui non è possibile dare una dimostra-zione. Poiché sistemi assiomatici coeren-ti come quello formulato da Russell eWhitehead non consentono di dimostraretutti gli enunciati veri sull'argomento chetentano di formalizzare, tali sistemi sonodetti incompleti.

La logica della computabilità

Il teorema di &Met stroncava il pro-gramma di Hilbert: non può esistere unmetodo che consenta di stabilire, per qua-lunque enunciato della matematica, se èvero o falso. Se un metodo simile esistes-se, costituirebbe una dimostrazione ditutti gli enunciati veri, e Gódel avevadimostrato che nell'ambito di un sistemaassiomatico coerente, abbastanza potenteda formalizzare l'aritmetica, una dimo-strazione del genere è impossibile. L'at-tenzione dei logici si spostò dal concettodi verità a quello di dimostrabilità e in

O 1 1

O 1 1

O 1 1

Lf1M+19

0 1 1

O o I o

60

61

NON

E

(P O Q) E (NON R)

h

C

e

questo contesto rimaneva aperto un pro-blema analogo a quello di Hilbert: esisteun metodo unico grazie al quale tutti glienunciati dimostrabili della matematicapossono essere dimostrati a partire da uninsieme di assiomi logici?

Negli anni immediatamente successivialla dimostrazione di Gódel, della logicadella dimostrabilità si occupò principal-mente Alonzo Church della PrincetonUniversity. Church e due suoi studenti,Stephen C. Kleene e J. Barkley Rosser,svilupparono un linguaggio formale coe-rente, chiamato lambda calcolo, utile perriflettere su funzioni matematiche comela radice quadrata e il logaritmo, e suqualsiasi altra funzione più complicatache possa essere definita. (Lambda, la let-tera greca corrispondente alla L del no-stro alfabeto, fu scelta da Church per direche il suo sistema formale è un linguag-gio.) Il Lisp (nome che sta per List Pro-cessing), linguaggio di programmazioneper calcolatori, è modellato sul lambdacalcolo. Kleene dimostrò che con questosono esprimibili ampie classi di funzionimatematiche, comprese quelle utilizzateda Go5del nella sua dimostrazione.

Il passo successivo in questa direzione èopera di Church, il quale sostenne che seuna funzione matematica può essere cal-colata (p cioè se può essere valutata pertutti i numeri nel suo campo di definizio-ne) allora può essere definita nel lambdacalcolo. Church dimostrò che se esistesseuna funzione matematica esprimibile nellambda calcolo ma non calcolabile, alloranon esisterebbe un metodo per stabilirese un dato enunciato matematico è dimo-strabile o no (e meno che mai per stabilirese è vero o no). L'unica ipotesi del pro-gramma di Hilbert rimasta in vita sarebbeconfutata. Nell'aprile del 1936 Churchpubblicò una formula logica che non ècalcolabile nel suo sistema.

Anche Turing, lavorando indipenden-temente da Church, aveva afferrato il col-legamento tecnico fra il problema di Hil-bert e l'idea di funzione calcolabile. Nel-l'affrontare il problema, però, era proce-duto in modo molto più diretto e concre-to. Era necessario un modello semplicema preciso del processo di calcolo, e lemacchine di Turing erano proprio pensa-te per soddisfare questa necessità. Unavolta specificate le loro proprietà, però,Turing tracciò un brillante collegamentofra l'idea di funzione computabile e i risul-tati delle ricerche svolte circa mezzo seco-lo prima dal matematico tedesco GeorgCantor. Cantor aveva sostenuto che, seb-bene non esista un numero intero «piùgrande di tutti», qualunque insieme infi-nito di oggetti che possano essere contati,ovvero messi in corrispondenza biunivocacon i numeri interi, è un insieme dellestesse dimensioni dell'insieme dei numeriinteri. Qualunque macchina di Turingpuò essere espressa come una successionedi caratteri di lunghezza finita, quindi tut-te le possibili macchine di Turing, e conesse tutte le funzioni computabili, posso-no essere elencate in ordine numerico oalfabetico; di conseguenza possono esse-re messe in corrispondenza biunivoca con

i numeri interi (si veda l'illustrazione inalto a pagina 56). Ovviamente non esistelimite superiore alle dimensioni di unamacchina di Turing. Ciononostante, l'a-nalisi di Cantor mostra che l'insieme ditutte le possibili funzioni calcolabili è del-le stesse dimensioni dell'insieme deinumeri interi: ambedue gli insiemi si di-cono «contabili» o «numerabili».

Cantor aveva dimostrato anche che esi-stono insiemi infiniti non numerabili:sono insiemi «più grandi» di quello degliinteri, nel senso che non possono esseremessi in corrispondenza biunivoca conesso. Un esempio di insieme non nume-rabile è l'insieme di tutte le funzioni degliinteri positivi a valori interi. Un'analisiprecisa mostra che queste funzioni deb-bono essere più numerose degli interi. Laconseguenza è che non tutte le funzionisono computabili: non esistono abbastan-za programmi di calcolatore per compu-tare tutte le funzioni possibili.

Il problema della fermata

Quali funzioni non sono computabili?Sfortunatamente non è facile ricavareesempi di funzioni non computabili dalledimostrazioni di Church e Turing, ma glistudiosi di scienze del calcolatore negliultimi vent'anni sono riusciti a costruirneparecchie, utilizzando le macchine di Tu-ring. Uno dei primi esempi di funzionenon computabile fu trovato da TiborRado, della Ohio State University, nel1962. Consideriamo tutte le macchine diTuring che hanno lo stesso numero di statiN. Supponiamo che tutte comincino laloro attività con un nastro vuoto, in altreparole un nastro che porta uno O in tuttele celle. Immaginiamo per il momento cheda questo insieme siano escluse tutte lemacchine di Turing che non si fermanomai. Fra tutte le altre, isoliamo la macchi-na o quel gruppo di macchine che stam-pano il maggior numero di 1 in successio-ne sul nastro vuoto prima di fermarsi. Ilnumero degli 1 stampati, per ciascun va-lore di N, è il valore della funzione diRado, normalmente indicata come a (N).La dimostrazione della non computabilitàdi a (N) è per assurdo: cioè si assume che

la funzione sia computabile e da questaipotesi si ricava una contraddizione. L'ar-gomentazione è diretta, ma i particolaritecnici sono un po' complicati: sono ripor-tati nelle illustrazioni delle due pagineprecedenti.

Si può pensare che la costruzione nonsia corretta perché ipotizza che le mac-chine di Turing a N stati che non si ferma-no mai possano essere identificate in anti-cipo. L'obiezione è seria. Consideriamo,dunque, come si possa cercare di calcola-rea (N) brutalmente. Elenchiamo tutte lemacchine di Turing a N stati, in qualcheordine numerico, simuliamone ciascunasu una macchina di Turing universale escegliamo la macchina o il gruppo di mac-chine che stampano il maggior numero di1. Questo metodo di calcolo sembra evi-tare l'obiezione, ma la difficoltà relativaalle macchine di Turing che non si ferma-no mai ricompare in una forma intrattabi-le. Alcune fra le macchine a N stati chenon si fermano mai possono essere elimi-nate da algoritmi semplici, ma esistonoaltre macchine per le quali tale decisionenon può essere presa. Se non si può stabi-lire se una macchina non si fermerà, lamacchina non può essere eliminata dall'e-lenco delle macchine a N stati e la simula-zione deve continuare. Poiché la macchi-na potrebbe effettivamente non fermarsimai, non v'è garanzia che il calcolo di a(N) possa essere portato a termine.

La macchina di Turing inizialmente haavuto una grande importanza per la logi-ca, ma dagli inizi degli anni sessanta hasvolto un ruolo di primo piano anche nellescienze del calcolatore. Nel 1965 JurisHartmanis e Richard E. Stearns, allora aiLaboratori di ricerca della General Elec-tric di Schenectady nello stato di NewYork, hanno mostrato come la macchinadi Turing consenta di fissare limiti precisialla complessità dei calcoli. Altri ricerca-tori in seguito hanno cominciato a classi-ficare i problemi secondo il modo in cui, alvariare delle dimensioni del problema,varia il tempo di esecuzione, ovvero variail numero dei passi di calcolo (le due for-mulazioni si equivalgono). Supponiamo,per esempio, che N punti siano collegatida linee, in modo da formare un grafo. Il

Due problemi sono equivalenti se la soluzione dell'uno fornisce immediatamente la soluzionedell'altro. Qui il problema di determinare le condizioni alle quali una formula booleana complessa(una proposizione logica) è vera è stato trasformato nel problema di colorare i vertici di un grafocon tre colori in modo che due vertici collegati non siano mai dello stesso colore. La verità o falsitàdi una formula booleana dipende dalla verità o falsità delle proposizioni atomiche che la costitui-scono e dal modo in cui i valori di verità vengono combinati mediante i connettivi «o», «e» e«non». Per ogni possibile formula booleana si può costruire un semplice grafo, colorabile con trecolori se, e solo se, esiste una assegnazione di valori di verità alle proposizioni atomiche che rendavera la formula complessa. Per esempio, consideriamo la formula complessaP o Q, costituita dalleproposizioni atomiche P e Q. PoQe vera se, e solo se, è vera la proposizione P, o se è vera laproposizione Q, o se sono vere entrambe. Queste condizioni si traducono nella colorazione delgrafo a sinistra in alto (a), in cui il verde rappresenta il vero e il blu il falso. La colorazione puòessere completata in modo che il vertice più a destra sia verde (vero) solo se almeno uno dei verticietichettati è verde (b-e). Analogamente, la formula complessa PeQ è vera se, e solo se, leproposizioni atomiche P e Q sono ambedue vere, e questa situazione si riflette in un grafo in cui ivertici che rappresentano P e Q sono entrambi verdi (f). Infine, la formula non P è vera se, e solose, il vertice P è blu (g) e la formula P è vera se, e solo se, il vertice non P è blu (h). In basso adestra si può vedere il grafo che corrisponde alla formula booleana più complessa (P0 Q) e (nonR); la colorazione (i) visualizza i vincoli imposti dai connettivi «o», «e», «non». In basso (j) èriportato uno dei quattro possibili modi di colorazione del grafo, corrispondente a una delleassegnazioni di valori di verità alle proposizioni atomiche che soddisfano la formula complessa.

62

63

problema è quello di colorare i vertici delgrafo in modo tale che due vertici collega-ti da una linea non abbiano mai lo stessocolore. Supponiamo poi che il metodo piùveloce, fra quelli noti, per risolvere il pro-blema richiéda un tempo che varia pro-porzionalmente a qualche potenza di N,supponiamo N 2 . Si dice allora che il pro-blema fa parte di quella classe di problemiche possono essere risolti in tempo poli-nomiale, e che viene indicata con P. Laclasse P è diventata molto importante:molti studiosi di scienze del calcolatoretendono a considerare intrattabili tutti iproblemi che non sono in P.

La moderna teoria della complessità

Va notato che un problema viene asse-gnato alla classe P solo se nessun casoparticolare del problema richiede più diun tempo polinomiale per la sua soluzio-ne. In altre parole, il metodo di soluzionedel problema è deterministico, nel sensoche garantisce una soluzione in un tempoinferiore a qualche potenza ben precisa diN, dimensione del problema. Si può defi-nire anche una macchina di Turing nondeterministica: cioè una macchina chepuò risolvere un problema congetturandola risposta e poi verificandola. Per esem-pio, per stabilire se un dato intero è com-posto, la macchina non deterministica con-gettura un divisore, prova a effettuare la

Organizzazione Mondiale della Sanità

Agenzia Internazionaleper la Ricerca sul Cancro

Monografie IARC per la valutazionedel rischio cancerogeno da sostanzechimiche per l'uomo. Suppf 4.

Sostanze chimiche,processi industrialie lavorazioniassociati a tumorenell'uomo

Ed. italiana 1984a cura della Sezione fiorentinadella Lega Italiana perla lotta contro i tumori

Prezzo del volume: L 30.000Distributore per l'Italia:

Libreria Le Monnier(Via S. Gallo, 53/r. - 50129 Firenze)Acquistatelo direttamente o tramitecontrassegno versando l'importosul c.c. postale n. 16857500

divisione e, se ottiene un quoziente esat-to, verifica che il numero sia composto.La macchina deterministica, invece, devecercare sistematicamente un divisore.

Il tempo necessario per risolvere unproblema con una macchina non deter-ministica è misurato dalla lunghezza delcalcolo più breve, quindi sembrerebbeche la macchina non deterministica godadi un enorme vantaggio rispetto a quelladeterministica. L'esperienza comune ci fapensare che sia più facile verificare unasoluzione che non trovarla. Cionondime-no, nessuno ha saputo dimostrare che iproblemi risolubili in tempo polinomialecon una macchina non deterministica(che costituiscono la classe NP) siano in-trinsecamente più difficili dei problemidella classe P. Non sappiamo se la classe Pe la classe NP siano distinte: stabilirlo èuno dei maggiori problemi aperti dellamatematica (è il problema spesso deno-minato «problema P-NP»).

Nel 1970 Stephen A. Cook dell'Uni-versità di Toronto ha compiuto un impor-tante passo avanti sul problema P-NP.Cook studiava il problema della determi-nazione delle condizioni sotto le quali unaproposizione logica complessa è vera. Peresempio, la proposizione complessa for-mata collegando con la congiunzione «o»due proposizioni semplici è vera se alme-no una delle due proposizioni semplici èvera. In generale è molto difficile deter-minare per le proposizioni semplici lagamma delle condizioni di verità che sod-disfano una proposizione complessa, inaltre parole che la rendono vera. Cookriuscì a dimostrare che il problema, chia-mato problema della soddisfacibilità, èdello stesso grado di difficoltà di qualun-que altro problema della classe NP. Esisteun algoritmo efficiente per risolvere ilproblema della soddisfacibilità solo seesiste un algoritmo efficiente per risolve-re ogni altro problema della classe NP.Un problema che abbia questa proprietà,rispetto a un'intera classe di problemi, sidice completo per tale classe.

Passò un anno prima che la maggior par-te dei ricercatori afferrasse l'importanzadel risultato di Cook. Nel 1971 Richard M.Karp dell'Università della California aBerkeley cominciò a chiedersi quali altriproblemi naturali possano svolgere lo stes-so ruolo del problema della soddisfacibilitàrispetto alla classe NP, e scoprì che moltiproblemi importanti della ricerca operati-va, compreso il problema di colorare ungrafo con tre colori, hanno lo stesso gradodi difficoltà di tutti i problemi che possonoessere assegnati alla classe NP: sono dun-que problemi NP- completi. Si può dimo-strare direttamente, mettendo in corri-spondenza un problema con il dominiodell'altro, che il problema della colorazio-ne dei grafi e quello della soddisfacibilitàsono equivalenti (si veda l'illustrazione del-la pagina precedente).

In modo analogo si è dimostrato checentinaia di problemi, che in precedenzasi credevano distinti, sono in effetti va-rianti notazionali l'uno dell'altro. Tuttiquesti problemi sono equivalenti al pro-blema della soddisfacibilità e pertanto

sono NP - completi. Sono state scopertemolte altre serie di problemi completi, siaper la classe P, sia per le classi di problemiintrattabili per le quali il numero dei passinecessari per una soluzione su una mac-china di Turing cresce esponenzialmentecon le dimensioni del problema. Sembraancora prematuro, comunque, affrontareil problema P-NP. Qualche sviluppo re-cente della teoria della computazione cioffre il modo di valutare qualcuna delladifficoltà ancora presenti.

Computabilità relativa

L'idea della computabilità di una fun-zione mediante una macchina di Turingpuò essere estesa, facendo sì che la com-putabilità dipenda da parole di simboliche la macchina può incontrare sul suonastro. Se una parola sul nastro appartie-ne a un insieme prestabilito di parole A, èpossibile impartire alla macchina di Tu-ring istruzioni che la facciano procedere auno stato speciale che continua a calcola-re la funzione in questione. Se la parolanon appartiene all'insiemeA, la macchinadecide che la funzione non è computabile.Si dice allora che la funzione è computabi-le relativamente all'insieme A. Se si po-tesse costruire A con tutte le parole checodificano macchine di Turing che si fer-mano quando ricevono in ingresso un na-stro vuoto, la funzione di Rado a (N)sarebbe computabile relativamente ad A.

Nel 1974, Theodore P. Baker dellaCornell University, John Gill della Stan-ford University e Robert M. Solovay del-l'Università della California a Berkeley sichiesero se fosse possibile dimostrare lanon equivalenza delle classi P e NP per lacomputabilità relativa. Nel corso della lororicerca, essi fecero una scoperta sconcer-tante. Riuscirono a specificare due insie-mi, A e B, per i quali le relazioni frale classi P e NP sono contraddittorie. Inaltre parole, per la computabilità relati-vamente all'insieme A, P e NP sono equi-valenti, mentre per la computabilità rela-tivamente a B le due classi non sono equi-valenti. Si è scoperto, inoltre, che per qua-lunque sistema formale esistono calcolirelativi per i quali si può assumere o che Pe NP sono equivalenti, o che non lo sono,senza alcun detrimento per la coerenzadel sistema. Altri ricercatori hanno poiscoperto che è possibile relativizzare mol-ti altri problemi in modo che sia vero l'u-no o l'altro dei due esiti possibili.

Ovviamente la situazione non è soddi-sfacente. Finora nessuno dei problemirelativizzati in due modi in conflitto è sta-to risolto e per molti questo fatto sembrastia a indicare che le soluzioni di queiproblemi sono al di fuori della portataattuale della matematica. Ciononostante,bisogna ricordare che la pura formulazio-ne di questi problemi, apparentementeintrattabili, è stata resa possibile dallasemplice soluzione data a un problemaimpenetrabile della generazione prece-dente. In retrospettiva, il prossimo pro-gresso ci sembrerà probabilmente sem-plice come le macchine nate dall'immagi-nazione creativa di A. M. Turing.

64