• l'insieme vuoto e I sono ricorsivi
(suggerimento:collegare le relative fun-
zioni caratteristiche alla funzione iniziale
Z);• se X, Y C N K sono ricorsivi, anche la loro intersezione
X n
Y, la loro unione X U Y e il complemento I — X sono ricorsivi(suggerimento:
si noti fxny=
fx fy, fxuy = sg(fx+ fy), fN
k _ x = s9fx );
• come applicazione del punto precedente, le relazioni >, > e < e l'insieme dei numeri dispari sono ricorsivi;
• anche la relazione di divisibilità tra naturali è ricorsiva.
Notiamo adesso che, tra le funzioni degli esempi precedenti, quelle parziali (sot-trazione, quoziente, resto) derivano da un impiego del procedimento di minima-lizzazione. Del resto, possiamo ricordare che le funzioni iniziali sono totali e che i meccanismi di composizione e recursione preservano la proprietà di essere to-tali e non possono generare funzioni parziali a partire da quelle iniziali. Diciamo allora che una funzione totale f è
ricorsiva primitiva
se e solo se esiste una se-quenza ordinata finita fo , . . . ,fn,
di funzionitotali
delle qualif = fn,
è l'ultima e tali che, per ogni i < n, fi è iniziale oppure si ottiene da funzioni precedenti per composizione, o per recursione (senza quindi coinvolgere la minimalizzazione).È ragionevole chiedersi se, tra le funzioni totali, quelle ricorsive primitive esaurisco-no l'intera classe delle funzioni ricorsive (in altre parole, se la minimalizzazione è superflua per definire le funzioni totali ricorsive). La risposta è negativa. Si con-sideri infatti il seguente esempio di funzione totale binaria A (chiamatafunzione di Ackermann
dal nome di chi la ideò): per ogni scelta di x1 e x2 naturali,(a) A(0, x2) = x 2 + 1, II
(b) A(x i +1, 0) = A(xi, 1),
(e) A(x i +1, x2 + 1) = A(xi , A(x i +1, x2)).
Si può verificare che le tre condizioni (a),
(b)
e (e) definiscono effettivamente una funzione totale A ed anzi le forniscono un algoritmo esplicito di calcolo. Ad esempio A(1, 2) = 4 perchè implicaA(1, 2) = A(0, A(1, 1)), A(1, 1) = A(0, A(1, 0)) e da (a) e
(b)
segueA(1, 0) = A(0, 1) = 2;
allora A(1, 1) = A(0, 2) = 3 e A(1, 2) = A(0, 3) = 4. In effetti A (come tutte le funzioni per cui è noto un algoritmo di calcolo) è ricorsiva. D'altra parte, si può provare che A non è ricorsiva primitiva: in altre parole, per dimostrarne la ricorsività, si ha bisogno di utilizzare il meccanismo di minimalizzazione: com-posizione e recursione non sono sufficienti a raggiungerla partendo dalle funzioni iniziali.
4.4 Church o Turing?
L'approccio alla calcolabilità tramite le funzioni ricorsive pare chiaramente di- verso da quello mediante le macchine di Turing. Il primo è assai più astratto,
l'altro più concreto, ed anzi dichiaratamente ispirato dal tentativo di simulare il comportamento della mente umana. In questo ambito, anzi, il secondo approccio risulta più convincente, se è vero, come è vero, che scienziati importanti come Gidel, assai dubbiosi a proposito della Tesi di Church, si dichiaravano invece as-solutamente persuasi dalla calcolabilità secondo Turing, proprio per questa sua maggiore concretezza. Possiamo allora chiederci a chi credere, se a Church op-pure a Turing, dunque quale modello di computabilità preferire.
In realtà la scelta è tutto men che drammatica, perché è possibile dimostrare che i due approcci, pur così differenti in natura, sono tuttavia tra loro equivalenti e dun-que ugualmente accettabili (o rifiutabili). Conseguentemente le due tesi, dun-quella sulle macchine di Turing e quella di Church, sono coincidenti, tanto che le abbia-mo già implicitamente congiunte nel Capitolo 2 quando abbiaabbia-mo parlato tranquil-lamente di Tesi di Church-Turing.
Non va poi trascurato che proprio questa equivalenza, e dunque la coincidenza concentrica di punti di vista tanto diversi verso lo stesso obiettivo, è argomen-to che corrobora e sostiene ulteriormente i due approcci alla calcolabilità, tanargomen-to quello di Turing che quello di Church. Ma passiamo alla enunciazione e alla dimostrazione del teorema di equivalenza.
Teorema 4.4.1 Sia f una funzione parziale k-aria (dai naturali ai naturali). Al-lora f è calcolabile (nel senso di Turing) se e solo se f è parziale ricorsiva.
In particolare, quando f è totale, si può dedurre che f è calcolabile (secondo Turing) se e solo se è ricorsiva. Si può poi dedurre facilmente:
Corollario 4.4.2 Sia L C lc . Allora L è decidibile (secondo Turing) se e solo se L è ricorsivo.
Basta infatti osservare che un insieme L di k-uple di naturali è decidibile (secondo Turing) se e solo se la sua funzione caratteristica è calcolabile (secondo Turing).
Passiamo ora alla dimostrazione del teorema: ne daremo solo i cenni principali, evitando di disperderci in troppi dettagli.
Dimostrazione. Assumiamo dapprima f parziale ricorsiva e verifichiamo che f è calcolabile secondo Turing. Ricordiamo che le funzioni ricorsive sono quelle che si ottengono dalle funzioni iniziali applicando un numero finito di volte i procedimenti di composizione, recursione e minimalizzazione. Ci basta allora dimostrare quanto segue:
(i) le funzioni iniziali sono calcolabili con MdT,
(ii) funzioni che si ottengono per composizione, oppure per recursione, oppure per minimalizzazione da funzioni che sono calcolabili con MdT sono a loro volta calcolabili con MdT.
Le relative verifiche sono più noiose che difficili. Del resto, (i) è già stato trattato nel Capitolo 2 almeno a livello di esercizi e quando abbiamo introdotto compo-
sizione, recursione e minimalizzazione, abbiamo anche accennato ad algoritmi
11
capaci di calcolare le funzioni corrispondentemente ottenute. Tutti questi proce-dimenti si possono adattare con un minimo di pazienza al contesto e al linguaggio delle MdT.
Passiamo allora a controllare l'implicazione inversa: abbiamo una funzione ziale k-aria f che è calcolabile secondo Turing e vogliamo mostrare che f è par-ziale ricorsiva. Sia
M
una MdT che computa f. Siano poi qj , gli stati diM.
Possiamo assumere cheM
si arresti se e solo seM
entra nello stato q: se questo non è il caso, ci basta aggiungere aM
un nuovo stato (senza istruzioni che lo riguardino) e alla funzione di transizione diM
le istruzioni che conducano ogni configurazione di arresto diM
al nuovo stato. Definiamo a questo punto quattro funzioni totali(k
1)-arieqm, im, sm, dm tali che, per ogni scelta di E l etEN,
qm(Y, t), im(± +, t), sm(X, t), dm(x, t) codificano rispettivamente
• lo stato di
M,
• che cosa è scritto sulla cella esaminata da
M,
• che cosa è scritto sul nastro a sinistra della cella esaminata da
M,
• che cosa è scritto sul nastro a destra della cella esaminata da
M
al passo
t
della computazione diM
sull'input corrispondente a Y. Ad esempio,qm(Y, t) è
rappresentato dall'indice 0, o 1, . . ., o n dello stato corrispondente;im
(At)
è una cifra di un qualche alfabeto dei naturali (ad esempio, 0, o 1, . . o 9 se adoperiamo la rappresentazione decimale) oppure un ulteriore numero (10, se vogliamo) per denotare il carattere bianco *;SAI
e dM richiedono invece una definizione più accurata, che utilizza in modo opportuno le consuete tecniche di codifica ed in particolare il teorema di decomposizione in fattori primi: ne omet-tiamo qui i dettagli. Osserviamo poi che, se per un certo input ±*M
converge in T passi, allora per ogni naturalet >
T si convieneqm
(±',t) =
qm(A T), im(ì, t) = im(±, T), dM (x, t) = dM (x, T), sm(ì, t) = sm(x, T),si cristallizza cioè la situazione al momento dell'arresto di M. In questo modo si ottiene che le nostre quattro funzioni diventino totali. A questo punto si prova che
qM,
im,xm, dM
sono ricorsive. Ad esempio si osserva che, per ogni E 14,qm(£,
O) = O, perché al passo inizialeM
è nello stato TI , eim(ì,
O)i
è la prima cifra della prima componente x 1 di (quella più a sinistra quando inizia la computazione), mentre, per ogni naturale t,
qm
(x,
t + 1), i m (ì, t + 1)si desumono in modo effettivo dalle istruzioni della funzione di transizione di M sulla coppia
(qm(2, t), im(2, t))
ed inoltre da s (±+, t) e dm (2, t). Analogamente per sm (x, t +1), dM (2, t+ 1).
In questo modo, con qualche maggior attenzione per i dettagli, si mostra che le nostre quattro funzioni sono ricorsive.
A questo punto si nota che, per ogni x
E I ,
• g
è nel dominio di f se e solo se M converge su -X', e quindi se e solo se, per qualche naturale t, M entra nello stato qr, al passo t della computazione su ovvero qm(2., t) = n;• in tal caso, f (2) si ottiene da iM (Y, t), s m (x, t) e dm (2, t) dove t è il minimo naturale per cui qm(ì, t) = n.
Si intravede in questa definizione il meccanismo di minimalizzazione applicato a funzioni ricorsive (quali qm, im, sm e dM). Se ne deduce che f è, a sua volta, parziale ricorsiva, proprio come volevamo dimostrare. ❑ Il teorema ci aiuta a caratterizzare in termini di funzioni ricorsive anche la semide-cidibilità. Infatti con riferimento al teorema 3.5.1 possiamo considerare linguaggi L C N tali che L = O oppure L è immagine di qualche funzione totale ricorsiva 1-aria f . Chiamiamo ricorsivamente enumerabile un tale linguaggio L e deduciamo banalmente:
Corollario 4.4.3 L CNè ricorsivamente enumerabile se e solo se è semidecidi-bile.
I linguaggi ricorsivamente enumerabili si riconoscono allora anche come i domini delle funzioni parziali ricorsive 1-arie (sempre per il teorema 3.5.1).
4.5 Esercizi
1. Ricorrendo alla definizione di insieme ricorsivo, si provi che O, N sono ricor-sivi e che gli insiemi ricorricor-sivi si preservano per unioni, intersezioni, comple-mentari. Che cosa si può dire a questo proposito degli insiemi ricorsivamente enumerabili?
2. Ancora ricorrendo alla definizione di insieme ricorsivo, si mostri che l'insieme dei numeri primi è ricorsivo.
3. Si dia un esempio di insieme I ricorsivamente enumerabile e non ricorsivo che contiene un insieme J ricorsivo e infinito.
NIIIIIIIIIIIIIIIIIIIIP il í,b'
4. Si dimostri che un insieme infinito I C N è ricorsivo se e soltanto se I è l'immagine di una funzione totale ricorsiva 1-aria crescente.
Riferimenti bibliografici