Problemi senza Soluzione
3.2 Problemi risolubili algoritmicamente
Il paragrafo è dedicato a presentare e discutere alcuni esempi di funzioni calco-labili secondo Turing. Per cominciare non è difficile vedere che le familiari ope-razioni dell'aritmetica, come l'addizione, la moltiplicazione, la divisione - intesa come la coppia di funzioni parziali quoziente e resto - sono tutte calcolabili; del resto, il Capitolo 2 include già esempi ed esercizi a questo proposito.
Ecco un caso più sofisticato e astratto di funzione calcolabile.
Esempio. Sia
f
la funzione da N a N definita come segue: per ogni x E N,f (x) =
{
1 se
Ox (x)
l' altrimenti.Dimostriamo che
f è
una funzione calcolabile. Usiamo la Tesi di Church-Turing proponendo un algoritmo che la calcola a un alto livello di astrazione e deducendo che c'è una MdT che la computa. L'algoritmo procede così. Dato un input x, si decodificax
per ottenere la MdT Mx che calcola Ox . A questo punto si manda in esecuzione Mx sull'input x. Se e quando l'esecuzione termina, si converge sull'output convenuto 1. Altrimenti la divergenza di Mx induce la divergenza dell' algoritmo che calcolaf .
Ci sono poi casi sorprendenti e "anomali" di funzioni che si dimostrano calcolabili senza che si riesca a determinare con precisione una MdT, o anche un algoritmo, che le computi. Eccone un esempio.
Esempio. Consideriamo la funzione totale g : N —> N tale che, per ogni x E N, 1 se nell'espansione decimale di 7r
g(x)
esistono almeno x 5 consecutivi, O altrimenti
La funzione g è calcolabile perché esiste infatti un algoritmo che genera l'espan-sione decimale di 7r. Allora per g ci sono due casi possibili. Ammettiamo dappri-ma che l'espansione decidappri-male di 7r riesca a includere un numero arbitrariamente grande di occorrenze successive di '5'; allora g coincide con la funzione costan-te 1, che è chiaramencostan-te calcolabile. Altrimenti c'è un massimo numero k di '5' consecutivi nello sviluppo decimale di 7r, e quindi, per ogni x E N,
1 se x < k, g(x) =
O altrimenti.
Anche questa seconda opzione è calcolabile.
Pertanto g corrisponde ad una delle due possibilità elencate, e in ogni caso g è
calcolabile. D'altra parte siccome lo sviluppo decimale di ir è infinito aperiodico, non è dato sapere direttamente da una sua lettura parziale se vale il primo o il secondo caso per g e, semmai, quale è k nel secondo caso, nè si conoscono attual-mente altre strategie per chiarire la questione. In conclusione, sappiamo che g ha un algoritmo di calcolo, ma non sappiamo quale è questo algoritmo.
Esistono poi funzioni di cui non è ancora noto se siano calcolabili o non calcola-bili.
Esempio. Consideriamo la funzione totale g' : N -+ N definita come segue: per
ogni x E N,
1 se nell'espansione decimale di 7r
(x) = esistono esattamente x 5 consecutivi, O altrimenti.
Chi potesse leggere per esteso lo sviluppo decimale di 7r potrebbe anche calcolare esaminandovi le occorrenze di 5; ma purtroppo lo sviluppo di 7r è infinito e sfugge ai nostri occhi. Potrebbero tuttavia esistere altre strategie più mirate per risolvere il problema. Ma ad oggi non è ancora noto alcun algoritmo convincente.
Quindi, per quanto ne sappiamo, g' può essere calcolabile, ma può anche non esserlo.
Esempi di funzioni non calcolabili in alcun modo saranno presentati nei prossimi
paragrafi.
3.3 La Macchina Universale
I moderni calcolatori, così come li intendiamo comunemente, sono "macchine"
capaci di eseguire svariati programmi. Una macchina di Turing invece, al di là del nome e della sua descrizione esteriore, è determinata dalla funzione 6 che ne stabilisce le istruzioni ed è quindi un programma di computazione, delegato a calcolare sempre la stessa funzione. C'è tuttavia modo di costruire una MdT 1,f che riesce a simulare il lavoro di ogni altra MdT M, nel senso che, per ogni M, e per ogni input naturale y, 1,1 accoglie (M, y) come input e riproduce la computazione di M su y. Per questo 11 è chiamata "universale". Vediamo come è possibile definirla.
C'è una ovvia perplessità relativa a questa ipotetica U, e cioè: come si fa a fornire a 1,f come input un'altra MdT M? Infatti l'alfabeto di U tratta numeri e non macchine. D'altra parte, abbiamo visto nel Capitolo 2 come ogni MdT riceva un suo numero di etichetta, secondo una biiezione effettiva tra numeri e macchine.
In altre parole M = Mx per un unico naturale x che può essere esplicitamente calcolato da M. Quindi possiamo proporre ali come input
• il numero x come codice di M,
• il numero y come input di M.
Ci aspettiamo che U ci fornisca come output della coppia (x, y) quello di
n
M su y, e cioè 0,(y). Dimostriamo allora l'esistenza di U.
Teorema 3.3.1 Esiste una MdT universale U. In altre parole, la funzione g : N2 -+ N definita ponendo, per ogni x, y E N,
g(x , y) = Ox (y) è calcolabile secondo Turing.
Dimostrazione. Informalmente, ci basta, per ogni scelta di x, y E N, prima de-codificare x per ottenere la MdT x-esima Mx , poi far lavorare Mx su y. Entram-bi i passaggi sono possiEntram-bili, in quando la decodifica è algoritmica e le regole di funzionamento di una macchina di Turing sono anch'esse algoritmiche.
Comunque, per non far sembrare questa soluzione un gioco di prestigio, diamo una descrizione più dettagliata della costruzione di U. LI può essere pensata come una macchina con due nastri ausiliari (sappiamo infatti che questo modello è equi-valente a quello di una MdT con un solo nastro). Dapprima U controlla che il suo input sia una coppia (M, y), per qualche macchina di Turing M = IVt e qualche input y per M. Poi U passa a simulare M sull'input y. In particolare, LI adopera il primo nastro ausiliario per mantenere traccia degli stati e della posizione della testina di M e il secondo nastro per memorizzare le istruzioni di M. Così 1,1 copia, di volta in volta, una configurazione q, a, n) di M dal nastro di input/output sul primo nastro ausiliario; poi per determinare la regola di transizione (q, a, 4, a', x) di M da usare, U estrae q e a, quindi determina (d , a', x) cercando nel secondo nastro l'istruzione per (q, a). A quel punto si comporta come dettato dalla terna (q', a', x) per sviluppare sul nastro di input/output la sua computazione. ❑
3.4 Il Problema dell'Arresto
Esistono funzioni che le macchine di Turing non riescono a calcolare, e linguaggi à che non riescono ad accettare, oppure accettano e non riescono a decidere. Ne e abbiamo già accennato alla fine del paragrafo 3.2. Così, se accogliamo la tesi di
a Church-Turing, queste funzioni e questi linguaggi non ammettono alcun algoritmo e capaci di trattarli.
Il prototipo di queste situazioni è il seguente
e Problema dell'Arresto. Determinare un algoritmo per stabilire, per ogni scelta di una MdT M e di un input y E N, se M 4. y o no.
e Allora, se prestiamo fede alla tesi di Church-Turing secondo cui tutto quello che è algoritmicamente risolubile può essere trattato con successo da MdT, il Problema n dell'Arresto ci chiede una MdT che, ricevuti in input x, y E N (e in particolare,
Notiamo che la macchina cercata non può essere quella universale t I. Infatti U, dati x, y, simula la computazione di Mx su y, ma non può prevederne l'esito e, se Mx diverge su y, è condannata a divergere su (x, y), a proseguire cioè indefini-tamente la sua computazione senza potersi accorgere a nessun passo dell'assenza di una conclusione. Invece la MdT cercata converge per ogni scelta di x, y e anzi calcola la seguente funzione totale h' da N2 a N: per x, y E N,
17,1 (x, y) = 01 se 4bx (Y) se cAtx (y) t
Ebbene questa macchina non esiste. Anzi, vale un risultato per certi versi più negativo.
Teorema 3.4.1 La funzione h tale che, per ogni input x E N, h(x) = 01
non è calcolabile da nessuna MdT.
Dimostrazione. Supponiamo per assurdo il contrario, che esista cioè una MdT con questa capacità. Consideriamo la seguente funzione k per x E N,
Dalla calcolabilità della funzione h segue facilmente quella di k. Dunque c'è una MdT che calcola k; sia j E N il suo codice; in altre parole sia 4 = k. Ma allora abbiamo
Oi(j) <—> k(j) — O < > h(j) — O <--> (fii(j) t,
il che costituisce una evidente contraddizione. Quindi h non è calcolabile. ❑
Il metodo usato per trovare una contraddizione nella prova del precedente teorema è un esempio della tecnica della diagonalizzazione già introdotta nel paragrafo 3. 1 ; dall'elenco
00, Oh 02, • •
delle funzioni calcolabili e dall'apparentemente innocua equivalenza, valida per ogni naturale x,
k(x) 1, se e solo se Ox (x) t
si deduce, per k = q5i e per x = j, la contraddizione (j) .1, se e solo se'/ (j) t e dunque si conclude che k non può essere calcolabile.
Corollario 3.4.2 L'insieme K = {x EN: M x x} non è decidibile.
Dimostrazione. La funzione h del teorema 3.4.1 non è altro che la funzione
caratteristica di K. ❑
Corollario 3.4.3 La funzione h' tale che, per ogni scelta di x, y E N, h' (x, y) = 1- se Ox (y) 1,,
0
se Ox (y) t non è calcolabile da nessuna MdT.
Dimostrazione. Altrimenti si vede facilmente che anche h è calcolabile; infatti
h(x) = h' (x , x) per ogni x E N ❑
Corollario 3.4.4 L'insieme K' = {(x, y) E N2 : Mx y} non è decidibile.
Dimostrazione. Basta notare che h' = fK'. ❑
La prova di questi corollari illustra il metodo della riduzione introdotto sempre nel paragrafo 3.1: per esempio l'incapacità di calcolare 11 è dedotta dall'ana- logo risultato per h. Diagonalizzazione e riduzione costituiscono entrambe utili strumenti teorici per dimostrare l'indecidibilità di linguaggi e l'incomputabilità di funzioni.
a
ie Il
tti I
La soluzione negativa del problema dell'arresto ha delle importanti conseguenze anche nell' ambito della teoria della programmazione. In particolare, essa indica chiaramente che non è possibile costruire un perfetto sistema di "debugging", che sia in grado di stabilire se un programma termini o meno sull'input dato.
Notiamo poi che, sebbene il problema dell'arresto, nella sua piena generalità, sia stato dimostrato indecidibile, è tuttavia possibile ottenere risultati positivi in casi parziali. Per esempio abbiamo già affermato nel capitolo precedente la calcolabilità della funzione f che a ogni tema (x, y, z) di naturali associa
f (x, y, z) = j 1 se Mx sull'input y termina in z passi, o altrimenti.
In questo caso, infatti, si limita con z il numero di passi di computazione di M, e questa specificazione consente il calcolo effettivo dell'immagine di f in ogni situazione.
Il problema dell'arresto non è l'unico esempio indecidibile in Informatica Teorica.
Altre questioni condividono la sua assenza di soluzioni algoritmiche. Citiamo qui il caso del Problema dell'equivalenza tra MdT che adesso enunciamo
Problema dell'Equivalenza tra Macchine di Turing. Determinare un algoritmo per decidere, per ogni scelta di due naturali x, y (e delle corrispondenti MdT M e My), se Ms e n calcolano o no la stessa funzione, cioè se = (ky o no.
In altre parole, sulla base della tesi di Church-Turing, si domanda se E = { (x, y) E N2 : = 4y} è o no decidibile. Si intende con ox = Irby che (fix e Oy hanno lo stesso dominio e agiscono allo stesso modo sui suoi elementi. Ma si prova che il problema non è decidibile secondo Turing e dunque, per la tesi di Church-Turing, non è risolubile da nessun modello di calcolo.
Un caso particolarmente critico in questo ambito più "generale" è quello dei lin-guaggi di programmazione cui dedicheremo il Capitolo 6. Qui la soluzione nega-tiva del problema dell'equivalenza implica che non sarà mai possibile decidere se due generici programmi calcolano la stessa funzione o, in altri termini, se hanno la stessa semantica. Ciò preclude la speranza di trovare un algoritmo per l'ana-lisi e la verifica di correttezza automatica dei programmi: le tecniche di testing rimangono così le uniche strategie per scoprire errori in un dato programma.
La nostra dimostrazione dell'indecidibilità del problema dell'equivalenza per MdT procede in tre passi.
a) Dapprima mostriamo che non è possibile decidere se una funzione calcolabile è totale (cioè converge su tutti gli input) o meno.
b) Proviamo poi che non è possibile riconoscere quali funzioni calcolabili coin-cidono con l'identità id di N, cioè con la funzione di N in N che lascia fisso ogni naturale.
c) Dimostreremo infine l'indecidibilità dell'equivalenza tra MdT.
Si noti che anche i passi a), b) costituiscono per proprio conto risultati di indecidi-bilità. Procediamo con la prova di a). Usiamo un argomento di diagonalizzazione:
I
Teorema 3.4.5 L'insieme
T = {x E N : Ox è totale (cioè 0x converge su ogni input)}
non è decidibile.
Dimostrazione. Ammettiamo per assurdo che T sia decidibile. Allora siamo capa-ci di riconoscere effettivamente nell'enumerazione 01 , 02 , ... di tutte le fun-zioni calcolabili quelle che sono anche totali. C'è dunque una funzione totale e calcolabile f tale che, per ogni x E N,
f (x) = indice della x-ma funzione totale nell'enumerazione.
Così ogni funzione calcolabile totale è della forma Of (x ) per un unico naturale x.
Poniamo adesso
g(x) = f( x )(x) + 1, per ogni x E N.
Allora, per ogni x, g calcola l'output Of(x) di Mf (x ) su x e poi gli aggiunge 1. Ovviamente g è calcolabile totale. Così esiste un unico ab E N tale che g = f (x0 ). Ma allora
f (xo)(x0) + 1 = 9(xo) = f (xo)(x 0 ) ,
e questo è assurdo. Segue che T è indecidibile. ❑
Passiamo alla prova di b). Usiamo qui una tecnica di riduzione ad a).
Teorema 3.4.6 L'insieme I = {x E N : = id} non è decidibile.
Dimostrazione. Mostriamo che, se I è decidibile, anche l'insieme T del prece-dente teorema lo è; così possiamo concludere che I non è decidibile.
Consideriamo la funzione parziale f da N2 a N tale che, per ogni scelta di x, y naturali,
f(x,y)=
{
Yt se (fix(Y) altrimenti.
Non è difficile vedere che f è calcolabile. Supponiamo di fissare il primo argo-mento x della funzione f . Otteniamo allora per ogni x una funzione calcolabile gx da N a N così definita: per ogni y,
9s (y) = y se Ox (y) t altrimenti.
Tutte le funzioni gx sono calcolabili e quindi compaiono nell'enumerazione delle funzioni calcolabili. Così c'è una funzione calcolabile r da N a N tale che, per ogni x E N,
Or(x) = gx-
Osserviamo poi che, per ogni x,
gx = id se e solo se
O,
è totale.Segue che, per ogni x, x E T se e solo se è totale, cioè se e solo se q5,.( x ) = id e in conclusione se e solo se r
(x)
E I. Così un algoritmo che decide I ne produce uno che decide T: basta che, per ogni x E N, prima si calcoli r(x)
e poi si applichi a r(x) l'algoritmo di I; se esso ci dice r(x) E I, deduciamox
E T, e viceversa.Teorema 3.4.7 L'insieme E = {(x, y) E N 2 : ick =
(h}
non è decidibile.Dimostrazione. Di nuovo usiamo una tecnica di riduzione, stavolta riferita a b).
Osserviamo che la funzione id è certamente calcolabile e dunque id = sc4 per qualche
j.
Ma allora, per ogni x,x E I se e solo se
(x, j)
E E.Quindi E non è decidibile perché non lo è neppure I. ❑