Dispensa di informatica - Fondamenti: Linguaggi Formali, Calcolabilità e Complessità
Anteprima
ESTRATTO DOCUMENTO
CHAPTER 9
Le grammatiche regolari e la gerarchia di
Chomsky
I n questo capitolo si studieranno le famiglie di grammatiche CF che generano
esattamente i linguaggi regolari. Saranno dunque collocate in un contesto più
ampio: riassumeremo brevemente dei risultati (alcuni dei quali presenti in questo
testo) che permettono di classificare le grammatiche in base all’espressività dei
linguaggi generabili e presenteremo la classificazione insiemistica completa delle
grammatiche. 1. Grammatiche Regolari
Una grammatica CF si dice lineare destra se ogni produzione è della forma:
→ +
∈ oppure
A wB w T ,
→ +
∈
A w w T
→
più eventualmente Se invece tutte le produzioni sono della forma:
S ε. → +
∈ oppure
A Bw w T ,
→ +
∈
A w w T
→
più eventualmente si dice lineare sinistra.
S ε, 0
9.1. Data una grammatica lineare destra esiste una grammatica
G G
Lemma
equivalente (in forma normale di Greibach) tale che tutte le produzioni sono della
forma: → ∈ oppure
A aB a T,
→ ∈
A a a T
→
più eventualmente S ε. → · · ·
Ogni produzione della forma viene sostituita dalle
A a a a B
Proof. 1 2 n
→ → →
produzioni: ove sono
A a C , C a C , . . . , C a B, C , . . . , C
1 1 1 2 2 n−1 n 1 n−1
→ · · ·
nuovi simboli non terminali. Similmente, viene sostituita dalle
A a a a
1 2 n
→ → →
produzioni: .
A a C , C a C , . . . , C a
1 1 1 2 2 n−1 n
85
86 9. LE GRAMMATICHE REGOLARI E LA GERARCHIA DI CHOMSKY
9.2. Se è generato da una grammatica lineare destra, allora è
L L
Teorema
un linguaggio regolare. hV,
Grazie al Lemma 9.1 possiamo supporre che tale
G = T, P, Si
Proof.
che sia nella forma semplificata descritta nell’enunciato di tale lemma.
L(G) = L hQ,
Costruiremo un NFA che riconosce
M = Σ, δ, q , Fi L.
0
{⊥};
• ∪
Q = V
• ;
Σ = T → →
• ∈ ∈ ⊥ ∈ ∈
sse sse è
B δ(A, a) A aB P, δ(A, a) A a P; δ(⊥, a)
∈
indefinito per ogni simbolo a Σ.
• q = S;
0
•
{⊥, → ∈
se
S} S ε P
F = {⊥} altrimenti G
⇒
^ ∩ 6
Si deve mostrare che se e solo se per ogni stringa
δ(S, w) F = S w, w.
∅ ∗
|w| ≥ ∈
Iniziamo mostrando, per induzione su che per ogni (dunque
0, A V
6 ⊥)
A = G
⇒
^
∈ sse
A δ(S, w) S wA
∗
{S}.
^
Base: Sia Per definizione, Per la forma della grammatica
w = ε. δ(S, ε) =
G
⇒ sse
S εA S = A.
∗
Passo: Sia w = va.
^ ^
S
∈ ∈
sse def di nei NFA
A δ(S, va) A δ(B, a) δ
^
B∈ δ(S,v)
S
∈
sse ip. induttiva
A δ(B, a)
G
⇒
B : S vB
∗
G
⇒ −→ ∈
sse def di (B
S vaA δ aA P)
∗
Da questo risultato, per definizione di si ha che:
F,
G
⇒ ^ ∩ 6
(1) se e solo se
S ε δ(S, ε) F = ∅;
∗
G G
⇒ ⇒ → ∈
(2) se e solo se esiste tale che e Ciò accade
S va A S vA A a P.
∗ ∗
^ ^
∈ ⊥ ∈ ⊥ ∈
se e solo se e ovvero
A δ(S, v) δ(A, a), δ(S, va).
9.3. Se è un linguaggio regolare, allora è generato da una
L L
Teorema
grammatica lineare destra.
hQ,
Sia il DFA che riconosce Costruiamo una
M = Σ, δ, q , Fi L.
Proof. 0
hV,
grammatica lineare destra tale che nel modo seguente:
G = T, P, Si L(G) = L
• V = Q;
• T = Σ; 3. GRAMMATICHE DI TIPO 1 87
• → ∈ sse
A aB P δ(A, a) = B
→ ∈ ∈
sse
A ε P A F
• .
S = q 0 G
|w| ⇒
^
Si mostra per induzione su che se e solo se
δ(q , w) = p q wp
|w|
0 0
^ ∈
[Esercizio]. A questo punto si ha immediatamente che se e solo se
δ(q , w) F
0
G
⇒
q w.
|w|
0 Per costruzione, la grammatica ottenuta può avere e dunque non
ε-produzioni
è della forma desiderata. Si applichi dunque l’eliminazione di tali per
ε-produzioni
ottenere la grammatica nella forma voluta.
Il Teorema 9.3 implica che ogni linguaggio regolare è anche CF.
Si possono mostrare risultati analoghi ai teoremi 9.2 e 9.3 per le grammatiche
lineari sinistre (si veda [13]).
2. Grammatiche di tipo 0
Le grammatiche di tipo 0 (a struttura di frase) sono le grammatiche della
hV,
forma in cui contiene produzioni
G = T, P, Si P →
α β
∗
+
∈ ∪ ∈ ∪
ove .
α (V T ) , β (V T )
9.4. per grammatica a struttura di frase se e solo se
L = L(G) G L
Teorema
è un insieme ricorsivamente enumerabile.
Che sia r.e. è evidente. Data genero via via tutte le derivazioni
L(G) G
Proof. ∈
di lunghezza 0,1,2, ecc. Se prima o poi la trovo. Per il viceversa, si
x L(G)
veda [13].
3. Grammatiche di tipo 1
Le grammatiche di tipo 1 (monotone o dipendenti dal contesto) sono le gram-
hV,
matiche della forma in cui contiene produzioni
G = T, P, Si P
→
α β
|α| |β|,
+ +
∈ ∪T ∈ ∪T ≤
ove , e con l’eccezione dell’eventuale produzione
α (V ) , β (V )
−→ (in tal caso richiediamo che non occorra mai in
S ε S β).
Per queste grammatiche esiste una forma normale per le produzioni, che de-
vono essere del tipo: →
α Aα α βα
1 2 1 2
|α | |α |.
6 ≤
con Si osservi che
β = ε. Aα βα
1 2 1 2
Si osservi inoltre che se è in forma normale di Chomsky (o di Greibach)
G
è banalmente di tipo 1, dunque vale l’inclusione dell’insieme dei linguaggi CF in
quello dei linguaggi di tipo 1.
88 9. LE GRAMMATICHE REGOLARI E LA GERARCHIA DI CHOMSKY
Vediamo ora come la suddetta forma normale possa essere ottenuta in tre
semplici passi.
Si prenda una generica produzione del tipo
→
A A . . . A B B . . . B
1 2 m 1 2 n
∈ ∪
ove .
A , B V T
i j
(1) Se si “accorci” il lato destro sostituendo la produzione con le due
n > m
produzioni: →
A A . . . A B B . . . B X
1 2 m 1 2 m−1
→
X B B . . . B
m m+1 n
ove è una nuova variabile, usata solo per questa occorrenza (si provi,
X ⇒
per esercizio, che ) Si osservi che la seconda
A A . . . A B B . . . B
1 2 m 1 2 n
produzione è già in forma normale.
(2) Si consideri ora Si rimpiazzi la produzione con le seguenti
m = n > 2.
produzioni: →
A A B X
1 2 1 1
→
X A B X
1 3 2 2
..
.
→
X A B B
m−2 m m−1 m
⇒
(si provi, per esercizio, che )
A A . . . A B B . . . B
1 2 m 1 2 n
(3) Consideriamo dunque le sole produzioni del tipo
→
A A B B
1 2 1 2
Si rimpiazzi la suddetta produzione con le seguenti 4 produzioni:
→
A A X A
1 2 1 2
→
X A X Y
1 2 1 1
→
X Y B Y
1 1 1 1
→
B Y B B
1 1 1 2
ove sono nuove variabili, usate solo per questa produzione (si provi,
X , Y
1 1 ⇒
per esercizio, che ). Si osservi che le quattro produzioni
A A B B
1 2 1 2 2
inserite sono in forma normale.
9.5. Ogni linguaggio generato da una grammatica dipendente dal
L
Teorema
contesto è ricorsivo. ∗
∈ ∈
Sia ; dobbiamo decidere se Consideriamo sod-
x T x L(G). G
Proof. |α| |β|.
≤
disfacente la condizione di monotonia Generiamo tutte le derivazioni di
|x|.
lunghezza tra 0 e Siano queste e siano le corrispondenti stringhe
t α , . . . , α
1 t
3. GRAMMATICHE DI TIPO 1 89
derivate. Considero il grafo i cui nodi sono gli e vi è un arco tra e se e
α α α
i i j
⇒ ∈
solo se . Si dimostra che se e solo se esiste un cammino nel
α α x L(G)
i 1 j
grafo da a
S x.
Tuttavia: 9.6. Ci sono insiemi ricorsivi che non sono generati da nessuna
Teorema 1
grammatica dipendente dal contesto. {0},
Fissiamo il linguaggio e consideriamo le grammatiche dipen-
T =
Proof. {X }, {X }, {X },
denti dal contesto costruite sui simboli non terminali .
, X , X , X . . .
0 0 1 0 1 2
A meno di rinomina delle variabili ogni grammatica dipendente dal contesto su
{0} sarà di questa forma. Possiamo dunque, con un pò di pazienza ed atten-
T =
zione, enumerare tali grammatiche come .
g , g , g , . . .
0 1 2
Dal teorema precedente sappiamo che ciascun è ricorsivo. Scriviamo un
L(g )
i
∈
programma che dato produce la macchina di Turing che esegue l’algoritmo
P i N
di decisione descritto nel teorema 9.5 per la grammatica . Qualcuno potrebbe
g i
trovarlo noioso, ma si può fare.
Si ottiene dunque una enumerazione di macchine di Turing in
M , M , M , . . .
0 1 2
grado di decidere l’appartenenza a , rispettivamente (dunque
L(g ), L(g ), L(g ), . . .
0 1 2
{0}
∗
∈
in particolare accettano in input stringhe e sono totali).
x
Si consideri ora l’insieme: {0}
∗
∈
L = x : M (x) = no
|x|
|x|,
dove la lunghezza dell’input può anche essere interpretata come la codifica
x,
unaria da parte di di un numero naturale.
x |x|,
1) è ricorsivo. Per decidere l’appartenenza di ad calcolo simulo la
L x L
computazione della macchina sull’input So che tale macchina è totale
M x.
|x|
dunque prima o poi termina. Complemento dunque l’output. {0}
∗
⊆
2) non è un linguaggio dipendente dal contesto. Infatti è diverso
L L
∈
da ognuno dei linguaggii . Dato infatti, vale che
L(g ), L(g ), L(g ), . . . i N
0 1 2
⇔
i i
∈ ∈
0 L 0 / L(g )
i
Abbiamo trovato pertanto mostrato esistere un linguaggio ricorsivo, ma non
di tipo 1.
{a
i i i ≥
Nell’Esempio 8.2 abbiamo mostrato che non è un linguaggio
b c : i 1}
CF. Mostreremo ora che tale linguaggio è un linguaggio dipendente dal contesto.
9.7. La grammatica di tipo 1:
Esempio →
→ | bC bc
S aSBC aBC →
→ cC cc
CB BC
→ →
bB bb aB ab
1 La comprensione di questo teorema è subordinata alla lettura dei capitoli 11, 14, 15.
90 9. LE GRAMMATICHE REGOLARI E LA GERARCHIA DI CHOMSKY
{a i i i ≥
genera esattamente il linguaggio Si osservi che tutte le derivazioni
b c : i 1}.
G
⇒ · · · · · ·
iniziano con Le sono già a posto. Le e le
S aaa aBCBCBC BC. a B C
∗
tengono traccia del numero di e da inserire. Prima di inserire i simboli termi-
b c
nali, tuttavia, bisogna riordinare le occorrenze dei corrispondenti non terminali.
→
Le tre regole che possono essere usate sono che sistema la più
aB ab b
a sinistra (a onor del vero, tale regola poteva essere applicata anche prima) op-
→ →
pure che potremmo definire regola di scambio, e la regola
CB BC, bC bc.
L’applicazione anticipata di quest’ultima, tuttavia, genererebbe una sottostringa
che non permetterebbe più di eliminare il simbolo non terminale
bcB B.
Invece, con un numero opportuno di applicazioni della regola di scambio, si
G
⇒ → →
· · · · · · · · ·
giunge a a da cui applicando
S aaa abCBC BC C bB bb, bC bc,
∗
→
e si ottiene la stringa attesa.
cC cc,
Le grammatiche ci permettono di calcolare funzioni di numeri naturali. Pre-
n −→
cisamente è calcolata da sse
f : G
N N
x x x f(x ,...,x )
· · · ∈
L(G) = 1 01 0 01 01 : x , . . . , x
n n
1 2 1 N
1 n
9.8. Si mostri che
Esercizio
(1) La funzione 0 è calcolata da una grammatica regolare.
(2) Le funzioni successore, proiezione + e - sono calcolate da gram-
i-esima,
matiche libere dal contesto
x
(3) Le funzioni e sono calcolate da una grammatica di tipo 1. Sug-
xy 2 → · · ·
gerimento: Si parta con una produzione del tipo (B: begin,
S B E
end) e si scrivano poi le regole per muovere verso destra la L’idea
E: B.
è che quando la incontra la la riscrittura deve terminare. Potrebbe
B E →
rimanere una regola non monotona (ad esempio ma a questo
BE ε,
punto non è difficile effettuare qualche semplificazione . . . )
4. La Gerarchia di Chomsky
Ricordiamo: {a
i i
• ≥
dagli esempi 5.3 e 6.4 sappiamo che il linguaggio è un
b : i 0}
linguaggio CF ma non regolare. Sappiamo inoltre che le grammatiche
(CF) lineari destre e sinistre generano esattamente i linguaggi regolari.
{a i i i
• ≥
Dagli esempi 8.2 e 9.7 sappiamo che il linguaggio è un
b c : i 1}
linguaggio dipendente dal contesto ma non CF.
• Dai Teoremi 9.6 e 9.4 sappiamo che la classe di linguaggi generati da
grammatiche dipendenti dal contesto è inclusa strettamente nella classe
di linguaggi generati da grammatiche a struttura di frase.
Pertanto viene indotta una gerarchia di grammatiche, nota come gerarchia di
Chomsky, fatta di inclusioni proprie, che si può trovare in Figura 1.
4. LA GERARCHIA DI CHOMSKY 91
' $
Struttura di frase $
' Dipendenti dal contesto $
' Libere dal contesto
'
' $ $
Lineari destre
Lineari sinistre
& & % %
& %
& %
& %
La gerarchia di Chomsky
Figure 1. Part 2
Teoria della calcolabilità
CHAPTER 10
Nozione intuitiva di algoritmo
In questa parte del testo presenteremo alcuni sistemi formali introdotti per
studiare in modo rigoroso i concetti di algoritmo, programma e funzione calcolabile.
S
In generale, un sistema formale è un sistema di formule e regole per combinare
formule, descritto mediante un insieme finito o numerabile di simboli, e tale
S
k
⊆ ∈
che per ogni regola per un qualche sia possibile stabilire in modo
R S k N,
finito (decidibile) se una formula è conseguenza di secondo ovvero
f f , . . . , f R,
1 k−1
hf ∈
se Il senso dei sistemi formali è quello di definire in modo
, . . . , f , fi R.
1 k−1
rigoroso, mediante simboli e regole, l’impalcatura entro cui derivare asserzioni su
un dato modello della realtà. Il calcolo proposizionale e la logica del prim’ordine
sono esempi noti di sistemi formali.
Studieremo dunque alcuni sistemi formali per descrivere in modo rigoroso la
nozione intuitiva di calcolabilità. Ciò permetterà di stabilire al tempo stesso i limiti
intrinseci dell’informatica moderna e studiare alcuni formalismi per rappresentare
il “calcolo”, apparentemente lontani tra loro, ma equivalenti nel potere espressivo
riguardante ciò che è calcolabile.
La corrente Parte 2 del testo, che riguarda questi argomenti, è strutturata nel
modo seguente: nel par. 1 del presente capitolo sarà introdotta la nozione informale
ed intuitiva di algoritmo, o di funzione calcolabile. In seguito, nel Capitolo 11 sarà
presentata la nozione di Macchina di Turing (MdT in breve), come primo sistema
formale per definire il concetto di funzione calcolabile. L’importanza della MdT è,
oltre che culturale, essendo una delle prime formalizzazioni del concetto di calcola-
bilità, anche tecnica: ad esempio, mediante MdT sono attualmente formalizzate le
nozioni più importanti nella teoria moderna della complessità degli algoritmi che
studieremo nella parte 4 del testo. Nel Capitolo 12 introdurremo le funzioni parziali
ricorsive, come modello matematico per le funzioni calcolabili. L’equivalenza tra
questi due modelli di calcolo ci porterà, nel Capitolo 13, all’analisi della Tesi di
Church-Turing e successivamente, nei Capitoli 14 e 15 ad enunciare alcuni risultati
generali sulla calcolabilità ed alcuni problemi algoritmicamente insolubili.
1. Requisiti di un algoritmo
Discuteremo ora le caratteristiche che deve avere un algoritmo partendo da
quella che è l’esperienza e l’idea intuitiva che tutti ne abbiamo. Un algoritmo viene
descritto in un certo linguaggio, che può anche essere semplicemente l’italiano,
95
96 10. NOZIONE INTUITIVA DI ALGORITMO
cosı̀ come usando i linguaggi nati appositamente per descrivere algoritmi quali i
linguaggi di programmazione e i sistemi formali che vedremo nei prossimi capitoli.
Facciamo qui riferimento all’esperienza personale e immaginiamo di guardare un
algoritmo. Possiamo concordare che, indipendentemente dal problema che intende
risolvere, ha delle caratteristiche comuni.
a: Un algoritmo è di lunghezza finita.
b: Esiste un agente di calcolo che porta avanti il calcolo eseguendo le
istruzioni dell’algoritmo.
c: L’agente di calcolo ha a disposizione una memoria dove vengono im-
magazzinati i risultati intermedi del calcolo.
d: Il calcolo avviene per passi discreti.
e: Il calcolo non è probabilistico.
I punti a–c hanno una ovvia interpretazione. Il punto d afferma che il calcolo non
avviene mediante dispositivi analogici. Il punto e afferma che il calcolo non obbe-
disce a nessuna legge di probabilità. Associato al punto a parleremo di espressioni
simboliche ovvero espressioni in un linguaggio di simboli che costituisce il linguag-
gio per decrivere un algoritmo.
Altre caratteristiche degli algoritmi sono:
f: Non deve esserci alcun limite finito alla lunghezza dei dati di ingresso.
g: Non deve esserci alcun limite alla quantità di memoria disponibile.
Mentre il punto f è ragionevole: ad esempio un algoritmo di somma deve poter
funzionare per ogni possibile addendo, ovvero numero naturale, per il punto g è
necessario un chiarimento. Per evidenziare la necessità di assumere una memoria
illimitata facciano osservare che, limitandola, alcuni algoritmi noti per calcolare
2
semplici funzioni non potrebbero funzionare. Ad esempio la funzione non
λx. x
sarebbe calcolabile poiché lo spazio di memoria necessario per calcolare il quadrato
di dipende da e per il punto f, esso deve essere illimitato.
x x,
Le seguenti osservazioni sono essenziali per comprendere la natura del calcolo
e la sua complessità.
h: Deve esserci un limite finito alla complessità delle istruzioni eseguibili
dal dispositivo.
i: Sono ammesse esecuzioni con un numero di passi finito ma illimitato.
Il punto h, in relazione al punto a, stabilisce la intrinseca finitezza del disposi-
tivo di calcolo. Ad esempio, pensando ad un calcolatore, esso sarà in grado di
calcolare solo indirizzando direttamente una parte finita della sua memoria (reg-
istri o memoria RAM) stabilendo quindi un limite nella complessità delle istruzioni
eseguibili. Questo è un punto chiave nell’analisi che vedremo della nozione di effet-
tiva calcolabilità. Un dispositivo di calcolo può effettivamente tenere traccia solo
di un numero finito di simboli, ovvero esso può reagire (eseguendo un istruzione)
tenendo conto di un numero finito di simboli ricordati. Questo venne intuitiva-
mente giustificato da Turing che per primo analizzò formalmente il concetto di
effettiva calcolabilità, con l’intrinseca limitazione della memoria umana. Tuttavia,
2. FUNZIONI CALCOLABILI 97
non c’è limite alla memoria ausiliaria, come visto nel punto g. Per quanto riguarda
il punto i, osserviamo che non essendo limitabile il numero di passi richiesti per
2
eseguire un generico algoritmo (si pensi alla moltiplicazione o alla funzione λx. x
discussa nel punto g), non è possibile stabilire a priori un limite massimo sul nu-
mero di passi nell’esecuzione di un algoritmo. Uno studio approfondito su come
legare il numero di passi alla lunghezza dei dati è argomento trattato nella teoria
della complessità degli algoritmi (si veda la Parte 4 del testo).
2. Funzioni calcolabili
Secondo quanto appena illustrato, un algoritmo definisce una funzione, ovvero
{input} ; {output}.
una associazione Questa può essere rappresentata matemati-
camente come una funzione sui dati manipolati dall’algoritmo. Possiamo pertanto
asserire che un algoritmo “calcola” funzioni. Diremo quindi che una funzione è
f
calcolabile se esiste un algoritmo ed un agente di calcolo tale che ad ogni input x
restituisce come risultato del calcolo f(x).
Tuttavia, una definizione intuitiva di questo tipo riguardante ciò che e’ intuiti-
vamente calcolabile non è soddisfacente. Supponiamo di trattare solo funzioni sui
1
numeri naturali. Supponiamo di poter descrivere in questo modo tutti i processi
−→
di calcolo sui numeri naturali, ovvero che una funzione sia calcolabile
f : N N
se esistono un algoritmo ed un agente di calcolo come descritti nei punti a–i sopra,
∈ ∈
tale che per ogni input l’algoritmo resituisce Ovvero, secondo
x f(x)
N, N.
queste ipotesi, una funzione è calcolabile se esiste un algoritmo ed un agente di
calcolo che terminano restituendo comunque un risultato, per ogni input. Pur non
assumendo limiti nel tempo e spazio impiegati dall’agente di calcolo per eseguire
i suoi conti, le precedenti ipotesi stabiliscono che ciò che è calcolabile lo sia co-
munque, per ogni input, a seguito di un insieme potenzialmente illimitato (ma
finito) di passi elementari di calcolo eseguiti dall’agente. Ovvero le funzioni con-
siderate come “calcolabili” secondo le ipotesi a–i sono tutte totali , ovvero sempre
definite per ogni input.
Essendo gli algoritmi di lunghezza finita ed essendo possibile descrivere l’agente
di calcolo mediante un insieme finito di simboli e regole che ne disciplinano il cal-
colo, è possibile enumerare gli algoritmi e gli agenti di calcolo. Sia dunque l’x-
P
x
esimo programma-agente che calcola una data funzione . Per le ipotesi a–i la fun-
g x
zione è totale, ovvero sempre definita. Definiamo la funzione
g h(x) = g (x) + 1.
x x
È chiaro che la funzione è calcolabile: tutti noi conosciamo un algoritmo per
h
incrementare un naturale, ed inoltre per ipotesi è calcolabile, essendo calcolata
g
x
dall’algoritmo-agente . Quindi, essendo calcolabile, deve esistere un algoritmo-
P h
x
agente che la calcola e che avrà un dato indice nella numerazione. Sia questo in-
dice , ovvero sia calcolata dal programma-agente (h ). Si ottiene in
x h P = g
0 x x
0 0
1 Questa non è una limitazione, poiché, come vedremo in seguito, ogni struttura dati, anche
la più complessa, può essere messa in corrispondenza biunivoca con un sottoinsieme dei numeri
naturali, modulo una opportuna codifica dei dati in numeri.
98 10. NOZIONE INTUITIVA DI ALGORITMO
questo modo una evidente contraddizione:
g (x ) = h(x ) = g (x ) + 1
x 0 0 x 0
0 0
Non è possibile che una funzione sempre definita sui naturali sia uguale al suc-
cessore di se stessa. La funzione è quindi non calcolabile nel nostro formalismo
h
scelto, che pertanto, essendo intuitivamente calcolabile, non esprime tutto ciò
h
che è intuitivamente calcolabile.
3. Algoritmi e Programmi
Con le suddette ipotesi si è dimostrato che non si è mai in grado di descrivere
tutto ciò che è “intuitivamente calcolabile”. Ovvero, sarà sempre possibile costru-
ire funzioni, intuitivamente calcolabili e totali, non esprimibili nel sistema formale
adottato. Questo chiaramente rappresenta un limite insormontabile alla nostra
teoria, rendendola inadeguata a trattare la nozione di calcolabilità. Abbiamo
bisogno di estendere i precedenti punti a–i con una nuova ipotesi fondamentale:
si assumerà che un processo di calcolo possa non terminare. Questo corrisponde
all’intuizione che, un programma chiaramente non terminante del tipo:
· · ·
while do endw
read(x); true
corrisponde ad una funzione non definita su tutti gli argomenti, per la quale sappi-
amo pensare ad un programma (quello sopra) ed un agente di calcolo che la calcola
(un computer). Si noti ora la necessità di introdurre degli oggetti sintatticamente
del tutto simili agli algoritmi, ma senza la proprietà di sicura terminazione. Sono
questi i programmi.
È quindi necessario, per superare la precedente limitazione dei punti a–i, as-
sumere che, oltre ai punti a–i vale la seguente ipotesi:
l: Sono ammesse esecuzioni con un numero di passi infinito (cioè non ter-
minanti).
Il punto l rappresenta una necessità intrinseca, e come abbiamo visto irrinunciabile,
nella trattazione matematica di ciò che è effettivamente calcolabile. Secondo questa
ipotesi, la funzione descritta in precedenza può risultare indefinita su alcuni
h ↑
argomenti (ad esempio ), ovvero indicando con il simbolo di indefinito, la
x 0
precedente uguaglianza può risultare valida (non contraddittoria):
↑ ↑
= g (x ) = h(x ) = g (x ) + 1 = .
x 0 0 x 0
0 0
CHAPTER 11
Macchine di Turing
In questo capitolo introduciamo le Macchine di Turing (MdT), ideate da Alan
Turing negli anni ’30 per rappresentare in modo formale una macchina in grado
di eseguire algoritmi costituiti da passi elementari e discreti di calcolo, secondo la
definizione informale data precedentemente. Turing, nella sua analisi del concetto
di calcolabilità, introduce per primo la parola “computer”, con il significato di
una persona che fa un calcolo composto da passi elementari e discreti utilizzando
un foglio di carta (memoria). Questa nozione di computer include tutte le carat-
teristiche di base dei calcolatori moderni (memoria, input/output, stato) e, come
vedremo, modella in modo soddisfacente il concetto di effettiva calcolabilità.
1. Descrizione modellistica e matematica
Nell’eseguire un calcolo (manuale), dato un input, calcoliamo un risultato con
l’ausilio della scrittura su carta. L’idea di Turing è quella di pensare ad una sem-
plice macchina in grado di scrivere simboli su un nastro potenzialmente infinito,
rappresentando il fatto (anche espresso nel punto g) che nei calcoli abbiamo soli-
tamente a disposizione una quantità illimitata di carta dove registrare i risultati
parziali del calcolo. L’organizzazione del nastro è fatta mediante celle che rapp-
resentano la quantità di memoria unitaria. La macchina cosı̀ pensata utilizzerà
un alfabeto finito, col quale possiamo rappresentare una infinità di dati. Il corpo
pensante della macchina (detto controllo) sarà realizzato mediante un automa a
stati finiti deterministico (DFA). Questa restrizione modella perfettamente il punto
h precedente, dove è stata assunta una complessità limitata nell’esecuzione delle
istruzioni da parte della macchina. Tutto questo viene rappresentato matematica-
mente con una macchina detta Macchina di Turing (MdT in breve).
Una MdT è un dispositivo di calcolo rappresentabile con un nastro di lunghezza
illimitata nel quale vengono immagazzinati i dati o sequenze di simboli del calcolo.
Uno di questi simboli è $ rappresentante l’assenza di simboli (spazio bianco). Il
controllo della MdT ha accesso al nastro attraverso una testina di lettura e scrit-
tura che permette di leggere o scrivere un simbolo alla volta. Una MdT è pertanto
costituita da due parti: il programma finito secondo cui verrà eseguito il calcolo
e gli organi meccanici per lo scorrimento del nastro e il comando della testina.
La struttura a stati finiti della parte di controllo modella una macchina con una
memoria che potremmo dire a breve termine, finita, mentre il nastro modella una
99
100 11. MACCHINE DI TURING
memoria a lungo termine, potenzialmente infinita. Questa distinzione tra memo-
ria a breve e lungo termine è riscontrabile anche nelle architetture dei moderni
calcolatori. ··· ···
` ` ` s r r r
3 2 1 1 2 3
⇑
q
Il modello meccanico della Macchina di Turing
Figure 1.
Ad ogni istante nel calcolo, il simbolo presente nella casella esaminata dalla
testina rappresenta l’input alla macchina (in Figura 1, il simbolo In risposta
s).
la macchina può decidere di modificare il simbolo e/o spostare il nastro a sinistra
o a destra della casella esaminata. Questo permette di avere in input un simbolo
diverso per eseguire il passo successivo della computazione (il simbolo se lo
` 1
spostamento sarà a sinistra, se a destra). Inoltre la testina (che si trova nello
r 1
stato finita) può cambiare il suo stato scegliendolo da un insieme
q—memoria
finito di stati possibili.
Il comportamento di una MdT è descrivibile mediante una tabella detta ma-
trice funzionale della macchina in cui le righe rappresentano gli stati del controllo
mentre le colonne rappresentano i simboli di ingresso. In una generica cella è de-
scritta l’azione eseguita dalla macchina nello stato corrispondente in riga e leggendo
dal nastro il simbolo corrispondente in colonna.
s j
q q s L
i r k
L’azione compiuta, essendo il controllo nello stato e leggendo il simbolo ,
q s
i j
è in questo caso:
• portarsi in uno stato (interno) q
r
• scrivere il simbolo s k
• spostare il nastro a destra o a sinistra
R L.
Nel caso , la macchina lascia inalterato il simbolo sul nastro. Se la
s = s
j k hs i
casella corrispondente alla coppia è vuota, la macchina si ferma. Una com-
, q
j i
putazione di una MdT sarà dunque una sequenza di passi compiuti dalla macchina.
Più formalmente, definiamo una MdT come segue.
11.1. Una Macchina di Turing consiste di:
M
Definizione 1. DESCRIZIONE MODELLISTICA E MATEMATICA 101
{s }
(1) un alfabeto finito con almeno due simboli distinti $
Σ = , . . . , s s =
0 n 0
(blank) e (tally);
s = 0
1 {q }
(2) un insieme finito di stati tra i quali vi è lo stato iniziale
Q = , . . . , q
0 m
(dunque è non vuoto);
q Q
0 {I }
(3) un insieme finito non vuoto di istruzioni (o quintuple) P = , . . . , I
1 p
ognuna delle quali di uno dei seguenti 2 tipi base:
0 0
• q s q s R
0 0
• q s q s L
tale che non esistono due istruzioni che iniziano con la medesima coppia
q, s.
Si può dunque immaginare come la descrizione “estensionale” (ovvero per
P {R,
× −→ × ×
casi) di una funzione (in generale) parziale Tale
δ : Q Σ Q Σ L}.
funzione è detta funzione di transizione.
δ
Si osservi la caratteristica locale delle istruzioni: il loro significato è univoca-
mente determinato dalla parte di nastro immediatamente adiacente alla testina
e dallo stato in cui la macchina si trova. Lo stato in cui si trova l’intera MdT
in un certo istante del calcolo è dunque esprimibile mediante la nozione di de-
scrizione istantanea di una MdT, che rappresenta lo stato interno del controllo, il
posizionamento della testina e il nastro.
11.2. Una descrizione istantanea (ID) della macchina è una
Definizione
quadrupla hq, v, s, wi
?
∈
dove rappresentano i caratteri significativi (cioè escludendo la sequenza
v, w Σ
illimitata di $ sempre presenti a destra e a sinistra) presenti sul nastro a sinistra
ed a destra della testina, è il simbolo letto dalla testina, essendo la macchina
s
nello stato q.
Ad esempio, se la situazione è s $ $ $
$ $ $ s . . . s . . .
. . . s . . . s i i+1 j
1 i−1 ⇑
q
allora , e .
v = s . . . s s = s w = s . . . s
1 i−1 i i+1 j
Vediamo ora come definire formalmente il generico passo di calcolo di una
MdT. Definiamo una relazione tra descrizioni istantanee, ovvero una relazione
` ⊆ × che rappresenti l’esecuzione di un singolo passo di calcolo in una
ID ID,
data MdT. `
11.3. Il successore è una “mappa” tra descrizioni istantanee
Definizione
definita come: 0 0 0 0 0 0
• hq, ` hq hq, ` hq
e $, se è
v, r, s wi , v r , s, wi v, r, εi , v r , εi q r q r R
una istruzione di P;
102 11. MACCHINE DI TURING
0 0 0 0 0 0
• hq, ` hq hq, ` hq
e $, se è
v s, r, wi , v, s, r wi ε, r, wi , ε, r wi q r q r L
una istruzione di P.
Una computazione sarà dunque definita come segue, ovvero come una sequenza
finita di passi. 11.4. Una computazione è una sequenza finita di ID α , . . . , α
Definizione 0 n
tale che
• hq e,
α = , v, s, wi
0 0 {0,
• ` ∈
per ogni
α α i . . . , n − 1}.
i i+1 0 0 0
≥ hq, i
Una computazione è detta terminante se esiste un per cui
n 0 α = v , s , w
n
0 0
e non vi è nessuna istruzione di iniziante con ed (cioè non è definita),
P q s δ(q, s )
6`
i.e. .
α
n
In accordo con il punto l della precedente sezione, esistono MdT che non
terminano, ovvero che non calcolano nulla a partire da un dato input.
Osserviamo come una MdT cosı̀ descritta soddisfa i requisiti per la definizione
ragionevole di algoritmo.
a: Le istruzioni della MdT sono finite.
b: La MdT è l’agente di calcolo che esegue l’algoritmo.
c: Il nastro rappresenta la memoria della macchina.
d: La MdT opera in modo discreto.
e: Ad ogni ID corrisponde una sola azione (determinismo della MdT).
f: Non esiste alcun limite all’input, essendo il nastro illimitato.
g: La capacità della memoria (nastro) è illimitata.
h: Le operazioni eseguibili sono semplici e quindi di complessità limitata.
i: Non esiste alcun limite al numero di istruzioni eseguite in quanto la
medesima quintupla può essere usata più volte.
l: Possono esistere MdT che non calcolano nulla generando una sequenza
infinita di ID. ` ` ∈
11.5 (Determinismo). Se e con allora
α β α γ α, β, γ ID,
Teorema
≡
β γ. 0 0
Ovvio, poiché per definizione non esistono due quintuple q s q s X
Proof.
aventi la medesima coppia
q, s.
11.6. Incremento di uno in binario.
Esempio
{$,
Sia Si vuole passare da una configurazione iniziale
Σ = 0, 1}. $ $ $ $ $ $
. . . s . . . s . . .
$
n 0 ⇑
q 0
ad una finale 0 0
$ $ $ $ $ $
. . . s . . . s . . .
$ m 0
⇑
q
2
1. DESCRIZIONE MODELLISTICA E MATEMATICA 103
ove X X
m n
0
i i
· ·
2 s = 1 + 2 s .
i
i
i=0 i=0
Una possibile definizione della funzione sarà la seguente:
δ
$ 0 1
δ $
q q L
0 1
q q 1 L q 1 L q 0 L
1 2 2 1
q q 0 L q 1 L
2 2 2
11.7. Copia di una stringa unaria.
Esempio
{$,
Sia Si vuole passare da una configurazione iniziale
Σ = 0}. $ $ $
$ $ $ . . .
. . . 0 . . . 0 $
| {z } ⇑
n q
0
ad una finale $ $ $ $ $ $
. . . 0 . . . 0 0 . . . 0 . . .
$
| {z } {z }
|
⇑
n n
q f
Una possibile definizione della funzione sarà la seguente:
δ
$ 0
δ $
q q L
0 1 $
q q R
1 2
$
q q R q 0 R
2 3 2
q q 0 L q 0 R
3 4 3
$
q q L q 0 L
4 5 4
q q 0 L q 0 L
5 6 5
$ $
q q R q R
6 7 2
q q 0 R
7 7 {$,
Si provi, per esercizio, a definire supponendo di disporre di
δ Σ = 0, 1}.
11.8. Definiamo una MdT che calcola il successore in base 10 di un
Esempio {0, {q }
numero. essendo lo stato di terminazione. La
S = . . . , 9}, Q = , q q
0 1 1
matrice funzionale in figura 2 definisce la MdT desiderata che calcola il successore
104 11. MACCHINE DI TURING
··· $
δ 0 1 2 7 8 9
···
q q 1 R q 2 R q 3 R q 8 R q 9 R q 0 L q 1 R
0 1 1 1 1 1 0 1
···
q 1 MdT per l’incremento in base 10
Figure 2.
di un numero scritto sul nastro supponendo che la MdT inizi il calcolo essendo la
testina posizionata sulla cifra meno significativa del numero da incrementare.
11.9. Si scriva la funzione di transizione per le macchine di Turing
Esercizio
soddisfacenti i seguenti requisiti:
(1) si calcoli il successore di un numero decimale
(2) decisione di quale sia la più lunga tra due stringhe di poste una a
0
sinistra ed una a destra della testina. Si scelga una opportuna forma di
risposta (che tenga conto anche della possibilità che le due stringhe siano
uguali);
(3) si effettui la somma (in binario) di due stringhe non nulle di e poste
0 1
entrambe a sinistra della testina ed inframmezzate da un $;
(4) si sposti la testina di posizioni a destra rispetto a quella di partenza,
n
ove è letto da un input binario;
n
(5) si calcoli il numero di occorrenze di in una data sequenza binaria;
1
(6) si ordini, con ripetizioni, una stringa in input di e
0 1.
(7) Similmente all’esempio 11.7, si descriva una MdT che copia a destra una
stringa binaria.
2. Funzioni calcolabili da MdT
Ad ogni MdT può essere facilmente associata una funzione che diremo calcolata
dalla MdT. Poiché in questa parte del corso trattiamo solo funzioni sui naturali, è
necessario fissare una opportuna codifica dei naturali come stringhe nell’alfabeto
della MdT. Ad esempio è possibile utilizzare una codifica binaria nel caso Σ =
{$, o una codifica decimale. Nella seguente definizione, assumeremo invece
0, 1} ∈
una codifica unaria, ovvero un generico numero sarà rappresentato come
n N
una sequenza di 0 consecutivi. Questa codifica è particolarmente
n + 1-simboli
conveniente, anche se del tutto inessenziale, per la seguente definizione di funzione
calcolabile da una MdT. n −→
11.10. Una funzione è Turing–calcolabile se esiste
f :
Definizione N N
una MdT tale che, partendo dalla configurazione iniziale
$ $ $ $ $ $ $ $
. . . x . . . x . . .
$ 1 n
⇑
q
0
2. FUNZIONI CALCOLABILI DA MDT 105
termina nella configurazione
$ $ $
. . . . . . f(x , . . . , x )$ . . .
$ 1 n
⇑
q
f ∈
se è definita, non termina altrimenti; dove per ogni
f(x , . . . , x ) (x , . . . , x )
1 n 1 n
n , sono le rappresentazioni in unario rispettivamente di
x , . . . , x , f(x , . . . , x )
N 1 n 1 n ∈
(mentre è tale per cui $) è indefinito).
x , . . . , x , f(x , . . . , x ) q Q δ(q ,
1 n 1 n f F
Si osservi che non poniamo restrizioni sul contenuto del nastro a sinistra della
testina e a destra di nella configurazione finale. Invece assumiamo
f(x , . . . , x )
1 n
che a sinistra e a destra dell’input nella configurazione iniziale ci siano solo $.
Chiaramente, per come viene data la definizione, una funzione Turing-calcolabile
non è necessariamente totale. Vedremo in seguito il significato più profondo di fun-
zione parziale nella teoria della calcolabilità.
11.11. Le seguenti funzioni sono Turing-calcolabili:
Esempio {q }.
• descritto da:
λ x.x: Q = δ
0 $ 0
δ
q
0
{q }.
• definito come segue:
λ x.0 : Q = , q , q δ
0 1 2 $
δ 0
$
q q L
0 1
q q 0 R q 0 R
1 2 2
q
2
{q }.
• definito come segue:
λ x.x + 1 : Q = , q δ
0 1 $
δ 0
q q 0 R
0 1
q
1
• λ x . . . x .x :
1 n i
{q }. definito come segue:
Q = , . . . , q δ
0 i
for j = 0, . . . , i − 1
δ(q , 0) = (q , 0, R);
j j
$) $,
δ(q , = (q , R).
j j+1
11.12. Si definiscano delle MdT per le tre funzioni di base 0, succes-
Esercizio
sore, e proiezione, che funzionino correttamente anche senza l’ipotesi che a destra
106 11. MACCHINE DI TURING
e a sinistra dell’input ci siano solo $ (suggerimento: si dovrà fare un passo in più
a destra e/o a sinistra aggiungendo un $).
11.13. Si definiscano tre MdT che calcolano le medesime funzioni
Esercizio
dell’esercizio precedente ma che soddisfano le ulteriori ipotesi di (1) non scrivere
mai nulla a sinistra della posizione iniziale della testina e (2) di terminare in una
configurazione in cui a sinistra della testina rimane l’input (suggerimento: si dovrà
utilizzare la definizione della MdT che copia delle stringhe unarie—esempio 11.7).
11.14. Si osservi che, se esiste una MdT computante la funzione allora
f,
Nota
ne esistono infinite calcolanti la stessa funzione (si aggiungano arbitrariamente
stati o simboli ‘inutili’). 3. MdT generalizzate
Il modello di MdT che abbiamo visto è solo uno dei possibili modelli matem-
atici per definire l’effettiva calcolabilità di funzioni. È infatti possibile definire
una vasta gamma di MdT differenti ma equivalenti rispetto alla classe di fun-
zioni Turing-calcolabili che esse possono indurre. Questo perchè qualunque MdT
ottenuta anche con modifiche strutturali (per esempio aumentando il numero dei
nastri o delle testine) se soddisfa le 10 condizioni che abbiamo definito per caratter-
izzare la nozione intuitiva di algoritmo, può essere simulata da una MdT definita
come nella Definizione 11.1. I seguenti risultati, dei quali non riportiamo di-
mostrazione, forniscono un esempio di come si possa modificare il modello di MdT
senza modificare l’insieme delle corrispondenti funzioni calcolabili. La potenza del
formalismo delle MdT non viene dunque ridotta/aumentata modificando l’insieme
dei simboli/stati o modificando la struttura stessa della macchina (numero di nastri
e/o testine).
• ≥
Una MdT con nastri ed testine (m può essere simulata da una
n m n)
MdT con 1 nastro ed una testina;
• Una MdT con simboli ed stati può essere simulata da una MdT con
n m
2 stati, aumentando opportunamente il numero dei suoi simboli;
• Una MdT con simboli ed stati può essere simulata da una MdT con
n m
2 simboli, aumentando opportunamente il numero dei suoi stati;
• Ogni MdT può essere simulata da una MdT che può solo scrivere e non
rimpiazzare simboli sul nastro.
Per approfondimenti su queste tematiche, si consulti, ad esempio [13].
CHAPTER 12
Funzioni parziali ricorsive di Kleene & Robinson
Lo scopo primario di questa parte del corso è di studiare le funzioni sui numeri
naturali, esprimibili in modo effettivo o algoritmico. La definizione intuitiva del
concetto di funzione effettivamente calcolabile o funzione calcolabile mediante un
algoritmo, ovvero mediante una sequenza discreta di passi elementari di calcolo di
una MdT, fornita nel capitolo precedente, può sembrare limitativa rispetto a ciò
che intuitivamente ci sembra effettivamente calcolabile. Per valutare la robustezza
di questa formalizzazione del concetto di funzione calcolabile, nei seguenti due
paragrafi studieremo diverse nozioni di calcolabilità che, come vedremo, si equiv-
algono e sono a loro volta tutte equivalenti alla calcolabilità mediante MdT.
Nel Paragrafo 1 studieremo la caratterizzazione di effettiva calcolabilità sui
naturali nota con il termine di funzione ricorsiva. Arriveremo alla trattazione
delle funzioni parziali ricorsive, dette anche funzioni ricorsive generali , di Kleene
& Robinson, arricchendo via via con nuovi costrutti, o metodi di composizione,
1
alcune funzioni elementari sui naturali, dette funzioni ricorsive di base. Questi
costrutti, come vedremo nel Cap. 16, corrispondono a costrutti noti ed ampiamente
utilizzati nei moderni linguaggi di programmazione.
1. Funzioni primitive ricorsive
L’insieme dei numeri naturali è facilmente caratterizzabile mediante induzione,
ovvero affermando che ogni numero naturale è esprimibile come una iterazione
n n
della operazione elementare di successore applicata al valore costante 0: n = S (0).
Pertanto {0,
= S(0), S(S(0)), S(S(S(0))), . . .}
N
Nel seguito indicheremo spesso con Questo procedimento induttivo per
S(x) x + 1.
definire i numeri naturali si basa sull’idea che ogni numero naturale è definibile a
partire da un numero più semplice (in questo caso minore nell’ordinamento usuale
sui naturali) applicando l’operazione di successore. Questo modo di procedere
è comune in matematica e informatica (si veda il paragrafo 2.6), e trova svari-
ate applicazione nelle cosı̀ dette definizioni ricorsive di funzioni. Una definizione
ricorsiva di funzione è una definizione dove il valore della funzione per un dato ar-
gomento è direttamente correlato al valore della medesima funzione su argomenti
1 Nel seguito per funzione ricorsiva intenderemo una funzione ricorsiva totale. Nel caso di
funzioni parziali, parleremo di funzioni parziali ricorsive.
107
108 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
“più semplici” o al valore di funzioni “più semplici”. Ad esempio, la seguente
funzione definisce ricorsivamente la successione di Fibonacci: 1, 1, 2, 3, 5, 8, 13,
... f(0) = 1
f(1) = 1
f(x + 2) = f(x + 1) + f(x).
Al fine di comprendere meglio queste definizioni è pertanto dare un significato
preciso al concetto informale di “più semplice”. Identifichiamo le funzioni “più
semplici” in assoluto con le funzioni costanti. Trattando i naturali, consideriamo
dunque la costante come funzione costante elementare. Supponiamo inoltre di
0
avere a disposizione come funzione elementare l’operazione di successore, che ci
permette di definire qualsiasi numero naturale, e la funzione identica. Queste
assunzioni ci portano a definire il concetto di funzione ricorsiva di base.
12.1. Si dicono funzioni ricorsive di base le seguenti funzioni:
Definizione
• la funzione costante 0: λx. 0;
• La funzione successore S: λx. x + 1;
• · · · ≤ ≤
La funzione identità, o proiezione, con
i-esima π : λx x . x 1 i
i 1 n i
n.
Formalizziamo ora il meccanismo di definizione di funzioni per composizione
e ricorsione primitiva. Questo meccanismo generalizza i precedenti esempi.
n −→
12.2. Una funzione si dice:
f :
Definizione N N n k
• −→ −→
definita per composizione da e se
g , . . . , g : h :
N N N N
1 k
f(x , . . . , x )=h(g (x , . . . , x ), . . . , g (x , . . . , x ))
1 n 1 1 n k 1 n
n−1 n+1
• −→ −→
definita per ricorsione primitiva da e se
g : h :
N N N N
f(x , . . . , x , 0) = g(x , . . . , x )
1 n−1 1 n−1
f(x , . . . , x , y + 1) = h(x , . . . , x , y, f(x , . . . , x , y))
1 n−1 1 n−1 1 n−1
Tutte e sole le funzioni definibili a partire dalle precedenti funzioni ricorsive
di base mediante composizione e ricorsione primitiva definiscono l’insieme delle
funzioni primitive ricorsive. L’idea è quella di costruire via via funzioni effettiva-
mente calcolabili a partire dalle funzioni (banalmente) effettivamente calcolabili di
base, ovvero e costruendo da queste, per composizione e ricorsione primitiva,
0 S,
funzioni via via più complesse P
12.3. La classe delle funzioni primitive ricorsive è la più pic-
Definizione
cola classe (ovvero l’intersezione di tutte le classi) di funzioni contenenti le funzioni
ricorsive di base e chiuse per composizione e ricorsione primitiva.
12.4. Segue direttamente dalla definizione che, per ogni funzione f,
Nota
∈ P sse esiste una sequenza finita di funzioni , tale che: e per
f f , . . . , f f = f
1 n n
≤
ogni funzione , con o è una funzione ricorsiva di base, oppure è ottenuta
f j n, f
j j
1. FUNZIONI PRIMITIVE RICORSIVE 109
mediante composizione o ricorsione primitiva a partire da funzioni con
f , . . . , f
i i
1 k
e per le quali vale la stessa proprietà. Queste non sono altro che le
i , . . . , i < j
1 k
condizioni per fissare un sistema formale.
12.5. Consideriamo la sequenza di funzioni ottenute come visto in
Esempio
precedenza: f = λx. x
1
f = λx. x + 1
2
f = λx x x . x
3 1 2 3 2
f = f f = λx x x . x + 1
◦
4 2 3 1 2 3 2
Tale che:
f =
5 f (0, x ) = f (x )
5 2 1 2
f (y + 1, x ) = f (y, f (y, x ), x )
5 2 4 5 2 2
f = f (f , f )
6 5 1 1
È facile vedere che e che Dimostrare per esercizio.
f = λx. 2x f = λxy. x + y.
6 5
Le funzioni primitive ricorsive sono molto frequenti in matematica ed informat-
ica. Il seguente esempio elenca alcune tra le più note funzioni primitive ricorsive.
12.6. Le seguenti funzioni sono ricorsive primitive (per semplicità si
Esempio
denoteranno numerali con numeri):
n · · ·
Zero: definibile come
0 = λx x . 0: 0(π (x , . . . , x ));
1 n 1 1 n
n
n · · ·
· · · · · ;
Costante: definibile come (0 (x , . . . , x ) ) )
c = λx x .c: S(· S 1 n
1 n {z } | {z }
| c c
11
Identità: Id = λx.Π (x);
Somma:
+(x, 0) = x
+(x, y + 1) = S(+(x, y))
Rispetto alla notazione utilizzata:
• è di arità
f +, 2,
• è la funzione identità, di arità
g 1, 2
• di arità è la funzione ottenuta come
h(x, y, z), 3, S(π (x, y, z)).
3
Un esempio di ‘computazione’ nel formalismo che si sta definendo è il
seguente:
2 D’ora in poi saremo un po’ meno formali eliminando in e le variabili inutili sapendo che
g h
tali situazioni si possono formalizzare di volta in volta — un esempio tipico sarà il predecessore.
110 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
+(S(S(0)), S(S(S(0)))) = S(+(S(S(0)), S(S(0))))
= S(S(+(S(S(0)), S(0)))
= S(S(S(+(S(S(0)), 0)))))
= S(S(S(S(S(0))))))
Moltiplicazione:
·(x, 0) = 0
·(x, ·(x,
y + 1) = +(x, y))
Potenza:
0
x = S(0)
y+1 y
·(x
x = , x))
Iper-potenza:
iper(x, 0) = π (x)
1
x
iper(x, y + 1) = iper(x, y) ... x
x
Si osservi che iper(x, y) = x |{z}
y
Predecessore:
pred(0) = 0
pred(y + 1) = π (y)
1
Differenza:
−(x, 0) = π (x)
1
−(x, y + 1) = pred(−(x, y))
Fattoriale:
0! = S(0)
·(S(y),
(y + 1)! = y!)
Segno:
sg(0) = 0
sg(y + 1) = S(0)
Definiamo inoltre sg(x) = −(1, sg(x)).
if–then–else: Vogliamo codificare la funzione che si comporta nel seguente
f
modo:
if
f(x, y, z) y > z
h(x, y, z) = Altrimenti
g(x, y, z)
Sarà sufficiente scrivere h(x, y, z) = f(x, y, z)sg(−(y, z))+g(x, y, z)sg(−(y, z)).
1. FUNZIONI PRIMITIVE RICORSIVE 111
|
Valore assoluto della differenza: (il
− (x, y)| = +(−(x, y), −(y, x));
primo dei tre segni “-” è l’operatore sugli interi)
Minimo e massimo:
min(x, y) = −(x, −(x, y))
max(x, y) = +(x, −(y, x))
Divisione intera: Assumiamo che div(x, 0) = mod(x, 0) = 0.
mod(0, x) = 0
·
mod(y + 1, x) = S(mod(y, x)) sg(−(x, S(mod(y, x))))
div(0, x) = 0
div(y + 1, x) = div(y, x) + sg(−(x, S(mod(y, x))))
Produttoria:
Sia una funzione ricorsiva primitiva binaria, allora definiamo la funzione
f y−1
Π f(x, z) = Π f(x, z):
z<y z=0
Π f(x, z) = S(0)
z<0
·(f(x,
Π f(x, z) = y), Π f(x, z))
z<y+1 z<y
Sommatoria:
Sia una funzione ricorsiva primitiva binaria, allora definiamo la funzione
f y−1
Σ f(x, z) = Σ f(x, z):
z<y z=0
Σ f(x, z) = 0
z<0
Σ f(x, z) = +(f(x, z), Σ f(x, z))
z<y+1 z<y
limitato di minimizzazione:
µ-operatore
Sia una funzione primitiva ricorsiva aria.
f n + 1
g(x , . . . , x , y) = µz < y. (f(x , . . . , x , z) = 0)
1 n 1 n
il più piccolo minore di
z y
= tale che se tale esiste
f(x , . . . , x , z) = 0 z
1 n
altrimenti
y
Tale funzione è primitiva ricorsiva:
g(x , . . . , x , y) = Σ (Π sg(f(x , . . . , x , u))).
1 n v<y u≤v 1 n
12.7. Si definiscano le seguenti funzioni ricorsive primitive:
Esercizio
(1) la funzione che, dato fornisce il numero dei suoi divisori;
x,
(2) la funzione che, dato restituisce se è primo, altrimenti;
x, 1 x 0
(3) la funzione che, dato restituisce l’x-esimo numero primo (si assuma
p x,
p(0) = 0).
(4) la funzione che restituisce l’esponente di nella fattorizzazione di
p(y) x;
112 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
(5) la funzione che restituisce se e solo se è un cubo perfetto;
1 x
(6) la funzione che restituisce se e solo se è ottenibile come somma di
1 x
due cubi.
12.8. Le funzioni primitive ricorsive sono totali.
Teorema
Per induzione strutturale sulla complessità (nel senso di numero di
Proof. P
operazioni di composizione e ricorsione primitiva) delle funzioni definite in os-
serviamo che le funzioni ricorsive di base sono totali, e la composizione di funzioni
totali è totale. Resta da dimostrare che la composizione mediante ricorsione prim-
itiva di funzioni totali è totale. Questo passo è lasciato per esercizio.
I precedenti esempi ci lascerebbero pensare che la nozione di funzione primitiva
ricorsiva catturi esattamente il concetto intuitivo di funzione calcolabile mediante
un algoritmo. Questo è falso! Innanzitutto, il Teorema 12.8 afferma che le funzioni
primitive ricorsive sono totali e, come vedremo, questa è una limitazione, ovvero
una funzione calcolabile può essere indefinita su alcuni (o tutti) i valori di input. Le
funzioni primitive ricorsive hanno inoltre un’ulteriore limitazione anche all’interno
delle funzioni totali sui naturali. Per dimostrare questo fatto, è sufficiente dare
un testimone, ovvero una funzione evidentemente calcolabile e totale, ma non
P.
appartenente a Una tale funzione è la funzione di Ackermann.
Ne vedremo ora due versioni. Nella prima versione, si tratta di una funzione
3 −→
in 3 argomenti, definita come segue:
ack : N N,
ack(0, 0, y) = y
ack(0, x + 1, y) = ack(0, x, y) + 1
ack(1, 0, y) = 0
ack(z + 2, 0, y) = 1
ack(z + 1, x + 1, y) = ack(z, ack(z + 1, x, y), y).
Per esercizio si verifichi che la funzione è totale (ed è ben definita, cioè non vi sono
chiamate ricorsive ad oggetti ‘più grandi’).
Vediamo di capire il significato della definizione di Dalle prime due
ack.
equazioni segue che La terza e quarta definzione costituiscono
ack(0, x, y) = y+x.
le condizioni iniziali per la quinta che è la vera e propria chiamata ricorsiva di ack.
Questa afferma che è ottenuta calcolando
λxy. ack(z + 1, x, y)
se
0 z + 1 = 1
y = ack(z + 1, 0, y) =
0 se
1 z + 1 > 1
1. FUNZIONI PRIMITIVE RICORSIVE 113
e quindi applicando la funzione volte, ovvero la sequenza:
λwy. ack(z, w, y) x
y = ack(z + 1, 1, y) = ack(z, y , y)
1 0
y = ack(z + 1, 2, y) = ack(z, y , y)
2 1
y = ack(z + 1, 3, y) = ack(z, y , y)
3 2
... ... ...
y = ack(z + 1, x, y) = ack(z, y , y)
x x−1
Quindi abbiamo: ack(0, x, y) = y + x
·
ack(1, x, y) = y x
x
ack(2, x, y) = y y
··
y
ack(3, x, y) = y x-volte
... ...
27 14
Ad esempio, .
ack(3, 3, 3) = 3 > 10
Nella seconda versione che presentiamo, la funzione viene espressa come una
funzione di due argomenti e definita come segue:
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
Anche questa presenta una crescita che appare subito non controllabile:
A(0, y) = y + 1
A(1, y) = 2 + (y + 3) − 3
A(2, y) = 2(y + 3) − 3
y+3
A(3, y) = 2 − 3
z}|{
y+3
2
··
2
A(4, y) = 2 − 3
... ...
12.9. non è ricorsiva primitiva [25].
ack
Teorema
La dimostrazione del Teorema 12.9 è basata sul fatto che cresce più veloce-
ack
mente di qualunque funzione ricorsiva primitiva. Questa funzione, universalmente
accettata come funzione calcolabile non è primitiva ricorsiva pur essendo totale.
114 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
Per far ciò si definisce la seguente relazione. Sia una funzione (a
f n-aria
≺ ∈
arbitrario). se e solo se esiste tale che per ogni di numeri
f A t n-upla
N }).
naturali vale che max{x
x , . . . , x f(x , . . . , x ) < A(t, , . . . , x
1 n 1 n 1 n
6≺
Si osservi che se lo fosse allora esisterebbe un tale Ma allora
A A; t.
max{t}) assurdo.
A(t, t) < A(t, = A(t, t):
Nel Teorema si mostra per induzione strutturale sulla definizione di funzione
≺
primitiva ricorsiva, che per ogni primitiva ricorsiva vale che pertanto
f f A, A
non è primitiva ricorsiva. La dimostrazione completa del teorema si può trovare in
http://planetmath.org/encyclopedia/PropertiesOfAckermannFunction.html.
Inoltre da questo segue che esistono infinite funzioni totali e chiaramente cal-
colabili che non sono esprimibili mediante ricorsione primitiva: basta aggiungere
alla funzione una generica costante.
ack 2. Diagonalizzazione
In questa sezione studieremo uno degli strumenti fondamentali della teoria
delle funzioni calcolabili: la diagonalizzazione. Il suo uso, già evidenziato nel
Capitolo 10, sarà frequente nel seguito. La tecnica di diagonalizzazione fu per la
prima volta utilizzata da Cantor nel 1874 per dimostrare uno dei risultati fonda-
mentali nella teoria classica degli insiemi, ovvero la non enumerabilità dei numeri
reali (si veda anche il Capitolo 2).
L’idea della diagonalizzazione è la seguente: Dato un insieme numerabile,
S
costruiamo una matrice nel modo seguente: in ogni riga è presente una possibile
i
enumerazione di che identifica univocamente una funzione
S: s , s , s , . . .
i,0 i,1 i,2
−→
totale Supponiamo che l’insieme di tali enumerazioni sia numerabile
f : S.
N
e tale enumerazione la leggiamo scandendo la matrice riga per riga.
s s s ...
0,0 0,1 0,2
s s s ...
1,0 1,1 1,2
s s s ...
2,0 2,1 2,2
... ... ... ...
−→
Sia una funzione totale che non sia mai l’identità su ovvero tale che
d : S S S,
∀s ∈ 6 (una tale funzione ovviamente esiste). Da questa costruzione,
S. d(s) = s
consideriamo la diagonale , , , . . . che viene trasformata da nella
s s s d
0,0 1,1 2,2
sequenza: d(s ), d(s ), d(s ) . . . .
0,0 1,1 2,2
La caratteristica essenziale di questa sequenza è che essa differisce da ogni altra riga
della matrice. Pertanto esiste una enumerazione di non presente nella matrice.
S
Ciò contraddice con l’ipotesi che l’insieme delle enumerazioni n(e dunque delle
funzioni totali da a è numerabile. Pertanto, data una qualsiasi enumerazione
S
N
degli oggetti di un sistema formale dato, in questo modo sarà sempre possibile
2. DIAGONALIZZAZIONE 115
“costruire” un oggetto che non appartiene alla numerazione, ovvero esterno al
sistema formale dato.
Come esempio di applicazione di questa tecnica, dimostreremo l’inadeguatezza
della classe delle funzioni primitive ricorsive nell’esprimere ciò che intuitivamente
viene ritenuto effettivamente calcolabile. Ovvero mediante un “argomento diag-
onale” dimostreremo che è possibile definire effettivamente una classe di funzioni
calcolabili non esprimibili mediante ricorsione primitiva. In realtà la diagonaliz-
zazione ha un ben più ampio campo di utilizzo in quanto è applicabile ad ogni
sistema formale le cui istruzioni definite su un alfabeto dato, sono effettivamente
enumerabili. L’inadeguatezza della classe delle funzioni primitive ricorsive per es-
primere la calcolabilità era comunque già chiara dal fatto che la funzione calcolabile
di Ackermann non è primitiva ricorsiva. P
Consideriamo l’insieme delle funzioni primitive ricorsive ed un formalismo,
ovvero un insieme finito di simboli con il quale sia possibile descrivere tutte le
P.
possibili derivazioni associate alle funzioni in Un siffatto alfabeto può essere
ad esempio {a,
Σ = b, c, . . . , z, 0, 1, 2, . . . 9, (, )}
P
Ogni derivazione associata ad una funzione in è quindi descrivibile con una
∗
opportuna sequenza finita di simboli in . È inoltre facile definire una procedura
Σ
∗
∈
che verifichi se una data stringa corrisponde ad una derivazione legittima
σ Σ
P
per una funzione in (si veda anche la Nota 12.4). È pertanto possibile enumerare
tutte le derivazioni legittime per funzioni primitive ricorsive esaminando le stringhe
in di lunghezza 1, quindi quelle di lunghezza 2 etc. Sia quindi l’(x
Σ Q + 1)-esima
x
derivazione in questa lista e sia la funzione di cui è derivazione. Definiamo
g Q
x x
la funzione come segue:
h h(x) = g (x) + 1
x
Evidentemente abbiamo un algoritmo per calcolare dato generiamo la lista
h: x,
delle derivazioni fino a , quindi utilizziamo per calcolare e sommiamo
Q Q g (x)
x x x
cosı̀ costruita non è primitiva ricorsiva altrimenti, se lo fosse, avremmo
1. h per un qualche , e quindi l’assurdo:
h = g x
x 0
0 g (x ) = h(x ) = g (x ) + 1
x 0 0 x 0
0 0
Si noti l’analogia di questa dimostrazione (informale) con la dimostrazione di Can-
tor sulla non enumerabilità di È pertanto possibile “costruire”, mediante
℘(N).
diagonalizzazione, una funzione a tutti gli effetti calcolabile che non è primitiva
ricorsiva.
Il problema posto dalla diagonalizzazione sembra limitare in modo intrinseco e
insuperabile ogni definizione matematica di funzione calcolabile codificabile con un
alfabeto finito di simboli. Infatti, per diagonalizzazione sembra possibile costruire
funzioni calcolabili che sfuggono ad ogni definizione formale, basata ad esempio su
un alfabeto finito, di funzione calcolabile.
116 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
L’idea fondamentale che permette di superare la difficoltà indotta dalla diago-
nalizzazione su un dato sistema formale è quella di ammettere algoritmi, o insiemi
di istruzioni per calcolare sia funzioni totali che parziali . Per comprendere meglio
questo aspetto fondamentale da cui è iniziato lo studio della teoria della calcola-
bilità, cerchiamo di applicare un argomento diagonale al caso di sistemi formali per
esprimere funzioni parziali. Osserveremo che un sistema formale che caratterizzi
un sottoinsieme opportuno di funzioni parziali, non è soggetto a limitazioni dovute
ad argomenti diagonali.
Sia la funzione parziale corrispondente all’(x+1)-esimo insieme di istruzioni
ψ x
in un dato sistema formale per funzioni parziali, e sia tale che è la
P x ψ
x 0 x
0
funzione parziale definita dalle seguenti istruzioni: trova , calcola e, se
ϕ P ψ (x)
x x
e quando si ottiene un risultato, restituisci come output di il valore
ϕ ψ (x) + 1.
x
Trattandosi di funzioni parziali, l’equazione
ψ (x ) = ϕ(x ) = ψ (x ) + 1
x 0 0 x 0
0 0
non genera contraddizioni, poiché può non essere definita.
ϕ(x )
0
Questo metodo di procedere, ovvero considerare la teoria della effettiva calco-
labilità come una teoria di funzioni parziali è alla base degli approcci di Kleene,
Church e Turing sviluppati negli anni ‘30. Tutti i sistemi formali che vedremo
infatti hanno in comune una descrizione in un opportuno sistema formale, ovvero
mediante un opportuno insieme di simboli e regole, di ciò che sono gli algoritmi
ed una conseguente caratterizzazione del sottoinsieme delle funzioni parziali cal-
colabili in quel sistema formale, ovvero calcolabile dagli algoritmi cosı̀ descritti.
Abbiamo già visto un esempio di questo modo di procedere nella descrizione delle
MdT come sistema formale per esprimere algoritmi e nella funzioni calcolabili da
una MdT come descrizione di opportune funzioni parziali. Queste considerazioni
generali sulla natura parziale delle funzioni calcolabili giustificano l’assunzione l
nella descrizione intuitiva di ciò che è effettivamente calcolabile. Indicheremo nel
↓ ↑
seguito con il fatto che è definita mentre con il fatto che
f(x) f(x) f(x) f(x)
non è definita. 3. Funzioni parziali ricorsive
Introduciamo ora un metodo generale per costruire funzioni parziali a partire
da funzioni totali (ad esempio primitive ricorsive). aria, allora definiamo la
12.10. Sia una funzione totale n + 1
f
Definizione
funzione
ϕ(x , . . . , x ) = µz. (f(x , . . . , x , z) = 0)
1 n 1 n
il più piccolo t.c. se esiste
z f(x , . . . , x , z) = 0 z
1 n
= ↑ altrimenti
3. FUNZIONI PARZIALI RICORSIVE 117
Tale operatore tra funzioni è detto ed una funzione cosı̀ definita è
µ-operatore
detta definita per minimizzazione o da
µ-ricorsione f.
Chiaramente una funzione definita per minimizzazione è in generale, per definizione,
parziale. 12.11. Analizziamo l’ipotesi che sia una funzione totale. Questa
f
Nota
ipotesi può essere rilasciata definendo la minimizzazione, o nel modo
µ-ricorsione
seguente: Sia una funzione parziale; è definita per da se
ψ ϕ µ-ricorsione ψ
↓ ∧
≤
ϕ(x , . . . , x ) = µz. (∀y z. ψ(x , . . . , x , y) ψ(x , . . . , x , z) = 0)
1 n 1 n 1 n
La rimozione dell’ipotesi di totalità nella Definizione 12.10 provocherebbe un chiaro
non senso. Infatti, per determinare il minimo tale che si
z f(x , . . . , x , z) = 0
1 n
ricorre al seguente algoritmo (facilmente descrivibile con una MdT) calcolando la
sequenza f(x , . . . , x , 0), f(x , . . . , x , 1), . . .
1 n 1 n
fino a che non si trova il primo valore tale che Se fosse
z f(x , . . . , x , z) = 0. f
1 n
parziale, ovvero il suo calcolo potesse non convergere, la procedura cosı̀ descritta
non sarebbe effettiva. Inoltre, come dimostrato da Kleene nel ‘52, le funzioni
3
parziali ricorsive non sono chiuse rispetto allo schema
ϕ(x , . . . , x ) = µz. (ψ(x , . . . , x , z) = 0).
1 n 1 n
12.12. La classe delle funzioni parziali ricorsive è la minima
Definizione
PR P
classe di funzioni contenente e chiusa per µ-ricorsione.
12.13. Si osservi come si possa utilizzare il per la definizione
µ-operatore
Esempio
delle seguenti funzioni:
• logaritmo (intero): (y+1)
blog xc = µy. (leq(x, a ) = 0),
a
ove è una funzione ricorsiva primitiva tale che se e solo
leq leq(x, y) = 0
se x < y;
• radice (intera):
n-esima
√ n
b n xc = µy. (leq(x, (y + 1) ) = 0);
3 Tale risultato si può mostrare facilmente ma utilizzando risultati e nozioni che vedremo in
seguito nel Cap. 17. Anticipando alcune nozioni, se è un insieme ricorsivamente enumerabile
A
ma non ricorsivo, allora definendo: ⇔ ∧ ∨
∈
ψ(x, y) = 0 (y = 0 x A) y = 1
si ha che è parziale ricorsiva; ma definendo abbiamo che non può
ψ f(x) = µy. (ψ(x, y) = 0), f
essere parziale ricorsiva altrimenti, se lo fosse, essendo chiaramente totale, sarebbe ricorsiva e
⇔ ∈
poiché anche sarebbe ricorsivo.
f(x) = 0 x A A
118 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
4. Equivalenza tra MdT e funzioni parziali ricorsive
Il seguente risultato dimostra l’equivalenza delle funzioni calcolabili da MdT
e le funzioni parziali ricorsive di Kleene & Robinson.
−→
12.14. è parziale ricorsiva se e solo se è Turing-
f :
Teorema N N
calcolabile. Per dimostrare il verso conviene dimostrare un teorema più
(→),
Proof.
forte: se è parziale ricorsiva, allora esiste una MdT che la calcola che:
ϕ
(1) Funziona anche se il nastro a sinistra dell’input e a destra della posizione
iniziale della testina non è una sequenza infinita di $.
(2) Quando termina, termina subito a destra dell’input, il quale non viene
modificato nella computazione (inoltre, per definizione, l’output è subito
a destra della testina).
(3) Inoltre, la parte del nastro che sta a sinistra della posizione iniziale della
testina non viene modificata.
Queste 3 assunzioni ci permetteranno di applicare l’ipotesi induttiva.
Si tratta ora di descrivere le MdT che calcolano le funzioni di base soddis-
facendo alle restrizioni suddette e poi mostrare che disponendo delle MdT che
soddisfano le condizioni sopra e che calcolano delle funzioni, siamo in grado di
definire quelle necessarie per calcolare la funzione che fa la loro composizione (le
proprietà sopra saranno essenziali), ricorsione primitiva e minimizzazione. Non
daremo le funzioni di transizione di tali macchine di Turing, ma solo la descrizione
del loro funzionamento.
Base: Per le funzioni di base, si completi l’esercizio 11.13.
Passo: Studiamo dapprima il caso della composizione. Per non perdere il senso
della dimostrazione distratti da apici e pedici, ragioniamo nel caso di dover definire
una macchina che calcola nell’ipotesi di possedere le macchine di
f(g(x), h(x)) −→
Turing che calcolano le funzioni La dimostrazione
M , M , M f, g, h : N N.
f g h
nel caso generale di funzioni non necessariamente unarie è del tutto analoga.
k
Nella Figura 1 è illustrata la successione di azioni da svolgere. Si tratta di
richiamare le macchine di turing definenti inframezzando ogni chiamata da
f, g, h
uno spostamento di una stringa (operazione che abbiamo già implementato in
precedenza — si veda esempio 11.7). Si osservi come i prerequisiti (1)–(3) sono
rispettati dalla macchina risultante.
Analizziamo ora il caso della ricorsione primitiva. Date le macchine di Turing
3
−→ −→
che definiscono le funzioni e definiamo la MdT
M , M g : h :
N N N N,
g h 2 −→
che calcola la funzione definita per ricorsione primitiva:
f : N N
f(x, 0) = g(x)
f(x, y + 1) = h(x, y, f(x, y))
4. EQUIVALENZA TRA MDT E FUNZIONI PARZIALI RICORSIVE 119
⇒
$ $ ⇒
· · ·
$ $ $
. . . x . . . x h(x) . . . Si copi a dx di
x h(x)
M
⇑ ⇑
h
h h
q q
e
0 ⇒
$ $
· · ·
$ $ $ $ $
$ h(x) x . . . x h(x) x g(x)$ . . .
. . . x M
⇑ ⇑
g
g ge
q q
0 ⇒ ⇒
$ · · ·
$ $ $ $ $
. . . x h(x) x g(x) h(x)
Si copi a dx di
h(x) g(x) M
⇑ f
f0
q
$
$ $ $ $ $
$ h(x) x g(x) h(x) f(g(x), h(x)) . . .
. . . x ⇑
fe
q
Si copi a sin della prima occorrenza
f(g(x), h(x)) $ $
. . . x f(g(x), h(x)) . . .
$
⇑
di (si usino i 5 $ come segnali)
x q e
Macchina di Turing per la composizione
Figure 1.
(x potrebbe essere sostituito da senza bisogno di particolari modifiche
x , . . . , x
1 n−1
nel prosieguo della dimostrazione). Si osservi che la ricorsione primitiva può essere
rimpiazzata da un ciclo for, ad esempio,
f(x, 3) = h(x, 2, f(x, 2)) = h(x, 2, h(x, 1, f(x, 1)))
= h(x, 2, h(x, 1, h(x, 0, f(x, 0))))
= h(x, 2, h(x, 1, h(x, 0, g(x))))
equivarrebbe a:
F = g(x);
for(i=0; i < 3; i++)
F = h(x,i,F);
La macchina di Turing descritta in figura 2 sfrutta tale idea. Si osservi come i
prerequisiti (1)–(3) sono rispettati dalla macchina risultante.
Rimane il caso del ovvero, data una macchina di Turing che
µ-operatore, M g
2 −→
calcola la funzione si deve definire la macchina di Turing che
g : M
N N, f
calcola la funzione Si tratta di lanciare dapprima
f(x) = µy(g(x, y) = 0). M g
120 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
Si aggiunga un $ a dx di e
y
e
si copino y
x ⇒
$ $ $ $ $ $ $ $
... x y ... ... x y x y − 1 ...
$
⇑ ⇑
alla dx del nuovo $.
h q
q 0 Si decrementi di 1 y
Se (ovvero si vada alla riga sotto (lancio di )
y − 1 = ε y = 0) M g
decrementando ulteriormente di 1 il secondo.
altrimenti si copino y − 1
x,
Si reiteri fino ad arrivare a: $
$ $ $ $ $ $ $ $ $ $ $ $ $ $
... x y x y − 1 x y − 2 ... x 1 x 0 x ...
⇑
0
q
si torni indietro di due $ e si lanci M g ⇒
$ · · ·
$ $ $ $ $ $ $ $ $ $ $ $
$ y x y − 1 x y − 2 . . . x 1 x 0 x
. . . x M
⇑ g
g0
q $
$ $ $ $ $ $ $ $ $ $ $ $ $ $
. . . x y x y − 1 x y − 2 . . . x 1 x 0 x g(x) . . .
⇑
ge
q
si ricordi che Si copi a sinistra e si lanci
g(x) = f(x, 0). f(x, 0) M h ⇒
$ · · ·
$ $ $ $ $ $ $ $ $ $ $ $ $
. . . x y x y − 1 x y − 2 . . . x 1 x 0 f(x, 0) M
⇑ h
h
q 0 $
$ $ $ $ $ $ $ $ $ $ $ $
$ y x y − 1 x y − 2 . . . x 1 x 0 f(x, 0) h(x, 0, f(x, 0))$ . . .
. . . x ⇑
h
q
e
si ricordi che Si copi a sinistra di tre $ e si lanci nuovamente
h(x, 0, f(x, 0)) = f(x, 1). f(x, 1) M h
Si reiteri fino ad incontrare i due $ affiancati.
$
$ $ $ $ $ $
. . . x y x y − 1 f(x, y − 1)) h(x, y − 1, f(x, y − 1))$ . . .
⇑
h
q e
si ricordi che Si copi a sinistra e si termini.
h(x, y − 1, f(x, y − 1)) = f(x, y). f(x, y)
$ $
. . . x y f(x, y)$ . . .
$
⇑
q
e Macchina di Turing per la ricorsione primitiva
Figure 2.
4. EQUIVALENZA TRA MDT E FUNZIONI PARZIALI RICORSIVE 121
con Se termina e l’output è 0 ci si ferma, copiando a sinistra il risultato.
x, 0.
Altrimenti si incrementa il secondo parametro e si richiama iterativamente.2
M g
Mostriamo ora l’implicazione inversa e cioé che se è Turing-calcolabile allora
ϕ
è parziale ricorsiva.
ϕ −→
Sia una funzione calcolabile da una MdT L’obiettivo è quello
ϕ : Z.
N N
di codificare la MdT come una funzione sui naturali che sia parziale ricorsiva.
Z
Per semplicità assumiamo, senza incorrere in limitazioni, che la MdT sia definita
Z
con 2 simboli, che corrispondono ai numeri e rispettivamente:
0 1
{0,
Σ = 1}
{q }
Q = , . . . , q
0 k
Con queste ipotesi possiamo rappresentare una generica ID come una tupla di
numeri, associando un numero nell’intervallo a ogni simbolo di stato in
[0, k] Q.
4
−→ ∈
Definiamo ID tale che, per ogni ID della forma:
ar : α
N · · · · · ·
α = b b b s q c c c
2 1 0 h 0 1 2
{0, {b }
∈ ∈ ⊆
con e allora: dove
s 1}, h [0, k] , c Σ, ar(α) = (h, s, m, n)
i i i∈N
P P
∞ k
i i
m
m = b 2 = b 2
i i
i=0 i=0
P P
∞ k
i i
n
n = c 2 = c 2
i i
i=0 i=0
6 6
ove (k ) è il massimo intero per cui (rispettivamente In questo
k i b = 0 c = 0).
m n i i
modo, poiché il numero di sul nastro non può essere infinito (siamo partiti con
1
un numero finito di 1 ed abbiamo effettuato un numero finito di passi), per ogni
ID in una computazione di segue che associa in modo univoco ad ogni ID
Z, ar
una quadrupla di naturali (aritmetizzazione di ID).
Una computazione di una MdT è definita come una sequenza (anche infinita)
` `
di ID: Definiamo dunque una funzione che esprime un passo di
α α . . ..
1 2
transizione tra ID, ovvero una funzione che manipola quadruple di naturali. A tal
× −→ × −→
proposito, definiamo le seguenti funzioni: e
δ : Q Σ Q, δ : Q Σ Σ
Q Σ
{0,
× −→ tali che:
δ : Q Σ 1}
x • è lo stato che la MdT assume trovandosi nello stato con
δ (q, s) Z q
Q
simbolo in lettura s;
• è il simbolo che la MdT produce trovandosi nello stato con
δ (q, s) Z q
Σ
simbolo in lettura s;
• è lo spostamento a destra (= o sinistra (= compiuto dalla
δ (q, s) 1) 0)
x
MdT trovandosi nello stato con simbolo in lettura
Z q s.
Per i valori non definiti si assegni il valore per renderle totali. Si noti che ,
k + 1 δ
Q
e sono funzioni definite dalla matrice funzionale di e sono chiaramente
δ δ Z,
Σ x
funzioni primitive ricorsive (lo si dimostri per esercizio). Possiamo quindi definire
le trasformazioni compiute eseguendo un singolo passo della MdT sulle quadruple
Z
122 12. FUNZIONI PARZIALI RICORSIVE DI KLEENE & ROBINSON
rappresentanti una generica ID di Z:
g (q, s, m, n) = δ (q, s)
Q Q
g (q, s, m, n) = (m mod 2)(1 − δ (q, s)) + (n mod 2)δ (q, s)
Σ x x
g (q, s, m, n) = (2m + δ (q, s))δ (q, s) + (m div 2)(1 − δ (q, s))
M Σ x x
g (q, s, m, n) = (2n + δ (q, s))(1 − δ (q, s)) + (n div 2)δ (q, s).
N Σ x x
Queste funzioni sono chiaramente primitive ricorsive, essendo la composizione di
`
funzioni primitive ricorsive. Possiamo dunque rappresentare una transizione α β
nel modo seguente: Se allora
ar(α) = (q, s, m, n)
ar(β) = (g (q, s, m, n), g (q, s, m, n), g (q, s, m, n), g (q, s, m, n)).
Q Σ M N
Per rappresentare l’effetto di o passi di calcolo della MdT
t-transizioni Z,
definiamo le seguenti funzioni di argomenti:
5
• è lo stato (∈ ottenuto dopo partendo da
P (t, q, s, m, n) [0, k]) t-passi
Q
una ID tale che
α ar(α) = (q, m, s, n);
{0,
• è il simbolo (∈ ottenuto dopo partendo da
P (t, q, s, m, n) 1}) t-passi
Σ
una ID tale che
α ar(α) = (q, m, s, n);
• è il valore (∈ rappresentante il nastro a sinistra della
P (t, q, s, m, n) N)
M
testina ottenuto dopo partendo da una ID tale che
t-passi α ar(α) =
(q, m, s, n);
• è il valore (∈ rappresentante il nastro a destra della
P (t, q, s, m, n) N)
N
testina ottenuto dopo partendo da una ID tale che
t-passi α ar(α) =
(q, m, s, n). 4
È facile vedere che, ad esempio, può essere definita nel modo seguente:
P
Q
P (0, q, s, m, n) = q
Q
P (t + 1, q, s, m, n) = P (t, g (q, s, m, n), g (q, s, m, n),
Q Q Q Σ
g (q, s, m, n), g (q, s, m, n))
M N
∈
Supponiamo che la MdT abbia uno stato di terminazione, ovvero tale
Z q Q
1
che le uniche caselle vuote della matrice funzionale di siano in corrispondenza
z
della riga . È chiaro che ogni MdT può essere trasformata in modo tale da
q
1
avere uno stato di terminazione di questo tipo. Pertanto, la MdT termina il suo
Z
calcolo nel primo (minimo) tale che: essendo
t P (t, q , s , m , n ) = k + 1, α
Q 0 0 0 0 0
la configurazione iniziale tale che Ovvero, il numero di
ar(α ) = (q , m , s , n ).
0 0 0 0 0
passi necessario per terminare, è definibile mediante come:
µ-ricorsione
µt. (k + 1 − P (t, q , s , m , n ) = 0).
Q 0 0 0 0
4 Se il lettore non fosse sufficientemente soddisfatto della definizione multipla della ricor-
sione, può modificare la definzione definendo un’unica funzione che restituisce quadruple anzichè
quattro funzioni che restituiscono ciascuna un singolo elemento di una quadrupla.
4. EQUIVALENZA TRA MDT E FUNZIONI PARZIALI RICORSIVE 123
∈
Sia un numero naturale di input. Al solito, assumiamo che la MdT inizi il
x N
suo calcolo avendo il numero sul nastro alla destra della sua testina codificato
x
come una sequenza di x + 1-uni
· · · · · · · · ·
0
0 1 1 0
| {z }
⇑ x+1
q 0 x+1
Pertanto avremo che Usiamo la solita
q = 0, s = 0, m = 0, n = 2 − 1.
assunzione che la MdT si fermerà in uno stato:
· · · · · ·
· · · 0 1 1 0
0 | {z }
⇑ f(x)
q 0
f(x)+1 · · · · · ·
per cui dove in ci saranno esponenti di 2 di grado
n = (2 − 1) +
superiore (ma lo dopo l’output ci permette di determinare da Sia
0 f(x) n). C
la funzione primitiva ricorsiva tale che dato numero del tipo sopra, permette
n
di calcolare puødefinire nel seguente modo. Prima definiamo come
f(x). Csi f
e Dunque
f(x, 0) = x f(x, y + 1) = f(x, y)/2.
≤ mod
C(n) = µy n (f(n, y) 2 = 0) − 1
. È dunque chiaro che, avendo un modo algoritmico primitivo ricorsivo dato da
una funzione per rappresentare come potenza di il numero alla destra della
C 2
testina nella ID terminale, la funzione calcolata da è esprimibile dalla seguente
ϕ Z
funzione parziale ricorsiva: x+1 x+1
ϕ(x) = C(P (µt. (k + 1 − P (t, 0, 0, 0, 2 − 1) = 0), 0, 0, 0, 2 − 1)).
N Q
∈ PR
12.15 (Forma normale di Kleene). Per ogni funzione ϕ
Corollario ∈ P
(o equivalentemente Turing calcolabile) esistono tali che
f, g
ϕ = λx. f((µt. g(t, x) = 0), x) .
CHAPTER 13
Tesi di Church-Turing
Negli stessi anni in cui venivano proposti i vari formalismi per definire la
effettiva calcolabilità, ad esempio le MdT, le funzioni ricorsive, il etc.,
λ-calcolo
veniva dimostrata anche la loro l’equivalenza. Si dimostrava cioè che i diversi
sistemi permettono di calcolare esattamente la stessa classe di funzioni. Abbiamo
visto degli esempi nelle sezioni precedenti riguardanti le MdT e le funzioni parziali
ricorsive di Kleene & Robinson.
Questi risultati (in particolare l’equivalenza del con le funzioni parziali
λ-calcolo
ricorsive) portarono Church e Turing nel ‘36 a formulare la seguente Tesi fonda-
mentale: Tesi di Church-Turing: La classe delle funzioni “intuitiva-
mente calcolabili” coincide con la classe delle funzioni Turing
calcolabili.
Si tratta chiaramente di una tesi indimostrabile, vista l’impossibilità di maneggiare
formalmente (= matematicamente) la nozione di “intuitivamente calcolabile”. Ac-
cettando la Tesi di Church-Turing si osserva immediatamente la notevole impor-
tanza che assumono le funzioni calcolabili da MdT, o equivalentemente, le funzioni
parziali ricorsive o Queste classi di funzioni vengono a rappresentare,
λ-definibili.
in virtù della Tesi di Church-Turing, la classe delle funzioni calcolabili effettiva-
mente mediante un algoritmo. La Tesi di Church-Turing ha pertanto notevole
interesse metamatematico. Lo stesso Gödel scrisse nel ‘46 le seguenti osservazioni
riguardanti la Tesi di Church-Turing, in riferimento ad una presentazione di Tarski
sul medesimo argomento:
Tarski has stressed in his lecture (and I think justly) the great
1
importance of the concept of general recursiveness (or Tur-
ing’s computability). It seems to me that this importance is
largely due to the fact that with this concept one has for the
first time succeeded in giving an absolute definition of an in-
teresting epistemological notion, i.e. one not depending on the
formalism chosen. [ . . . ] By a kind of miracle it is not neces-
sary to distinguish orders and the diagonal procedure does not
lead outside the defined notion.
1 . . . che noi chiamiamo ricorsività a la Kleene & Robinson.
125
126 13. TESI DI CHURCH-TURING
[K. Gödel, Princeton 1946]
La Tesi di Church-Turing permette di limitare l’estensione di ciò che è effet-
tivamente calcolabile: se dimostriamo che una funzione non è parziale ricorsiva,
allora, in virtù della Tesi di Church-Turing, essa non è calcolabile in nessun modo
effettivo. Analogamente, dare un algoritmo per una funzione corrisponde a di-
mostrare, per la Tesi di Church-Turing, che essa è una funzione parziale ricorsiva.
Questo utilizzo della Tesi di Church-Turing è fondamentale in questo corso. Infatti,
sarà sufficiente dimostrare la realizzabilità di un algoritmo per affermare l’esistenza
di una MdT o di una funzione parziale ricorsiva corrispondente, senza dover es-
ibire una tale macchina o una funzione per calcolarlo. Questo ci permetterà di
sviluppare un certo numero di strumenti a supporto della teoria delle calcolabilità,
senza dover esibire esplicitamente complesse MdT o funzioni parziali ricorsive.
Questa caratteristica della Tesi di Church-Turing darà un aspetto apparentemente
informale alle dimostrazioni di effettiva calcolabilità di funzioni. Dimostrazioni di
questo tipo, che si basano su una non banale applicazione della Tesi di Church-
Turing, saranno dette dimostrazioni mediante Tesi di Church-Turing. Pertanto,
ogni volta che una funzione risulterà “palesemente” calcolabile, la si accetterà come
effettivamente calcolabile da uno dei formalismi prescelti, senza dover costruire la
MdT o altra funzione corrispondente. Nel seguito dunque considereremo equiv-
alenti i concetti di calcolabilità: “effettiva” (ovvero associata all’esistenza di una
MdT), “algoritmica” (ovvero associata all’esistenza di un algoritmo che soddisfi i
requisiti a–l) o “ricorsiva” (ovvero associata ad una funzione ricorsiva parziale che
la calcola).
A questo punto della trattazione, è bene distinguere, per chiarezza, tra due
nozioni diverse di calcolabilità. Infatti è possibile definire una funzione per cui
g
sappiamo esistere un algoritmo ma per la quale non sappiamo dare l’algoritmo che
la calcola. Consideriamo le funzioni definite nel modo seguente:
se esattamente ‘5’ consecutivi appaiono nella
1 x
f(x) = espansione decimale di π
altrimenti
0
se almeno ‘5’ consecutivi appaiono nella espansione
1 x
g(x) = decimale di π
altrimenti
0
È chiaro che è calcolabile: dato un algoritmo che genera l’espansione decimale
g
di sarà o la funzione costante nel caso vi sia un numero arbitraria-
π, g g(x) = 1,
mente grande di occorrenze successive di ‘5’ in che è chiaramente una funzione
π,
calcolabile; oppure sarà la funzione calcolata da un qualche algoritmo che, fissato
13. TESI DI CHURCH-TURING 127
un (ed esempio il massimo numero di ‘5’ consecutivi in calcola:
k π),
≤
se
1 x k
g(x) = se
0 x > k
In questo secondo caso esiste sicuramente un tale che permette di individuare
k
l’algoritmo cercato, ma ci è impossibile sapere quale sia il giusto. In entrambi i
k
casi la funzione è calcolabile (ed é in particolare primitiva ricorsiva), ma in gen-
g
erale non sappiamo costruire effettivamente un algoritmo per calcolarla. Al con-
trario, per non siamo in grado a tutt’oggi di affermare nulla sulla sua calcolabilità
f
effettiva. Pertanto, mentre per è possibile invocare la Tesi di Church-Turing, ed
g
affermare che esiste una MdT che la calcola, anche se non si sa quale, per questo
f
non è possibile. Accettando quindi di considerare calcolabile ogni funzione per la
un algoritmo che la calcoli, possiamo nel seguito utilizzare la Tesi di
quale esiste
Church-Turing ogni qual volta sia chiara l’esistenza di un algoritmo per calcolare
una data funzione. CHAPTER 14
Aritmetizzazione e universalità
Aritmetizzazione significa semplicemente traduzione nel linguaggio dell’aritmetica.
Il primo utilizzo dell’aritmetizzazione è dovuto a Gödel nel 1931 nella dimostrazione
del risultato fondamentale di incompletezza dell’aritmetica; da qui anche il termine
equivalente di Gödelizzazione. Nel seguito considereremo le MdT come esempio
ed applicheremo alle MdT il concetto di aritmetizzazione. Per la Tesi di Church-
Turing, sappiamo che questa non è una restrizione, ed analoghe aritmetizzazioni
possono essere definite per ogni sistema formale equivalente alle MdT.
1. Enumerazione delle MdT
{$,
Sia Quante sono le macchine di Turing ‘distinte’ descrivibili? Si
Σ = 0}.
{q }.
supponga Si tratterà di riempire la tabella
Q = 0 $ 0
q
0
in tutti i modi (significativi) possibili, ossia ogni singola casella potrà essere
(1) vuota (si immagini di scrivere $ $ $);
(2) $
q R;
0
(3) $
q L;
0
(4) q 0 R;
0
(5) q 0 L.
o ×
Dunque ci sono esattamente macchine di Turing distinte ad un solo
25 = 5 5
stato.
Si può pensare a questo punto di definire un ordinamento sulle macchine di
Turing ad uno stato definibili; fissato un ordinamento su (poniamo $ sia
Σ < 0),
Σ
inoltre e si consideri la cella a sinistra più importante di quella a destra,
L < R
M {L,
essendo insieme dei possibili movimenti della testina, cioé
M M = R}.
Si assuma che $ $ $ sia minore di qualunque terna allora si avrà (in
q s m,
0
una estensione lessicografica i cui parametri sono, nell’ordine cella e contenuto):
h$ h$ · · · h$ hq · · · hq
$ $, $ $ $i $ $, $ $ $, $ $ $ $i
q Li q 0 Ri L, 0 R, q 0 Ri.
0 0 0 0 0
{q }, {s
Più in generale, sia $,
Q = , . . . , q Σ = = s = 0}, m = L,m = R;
0 n−1 0 1 0 1
·
si definisca inoltre un ordinamento tra le celle presenti (per righe, colonne,
2 n
129
130 14. ARITMETIZZAZIONE E UNIVERSALITÀ
a zig zag etc.). Definendo esplicitamente l’ordinamento per ogni cella nel modo
seguente: {L,
• ≺ ∈ ∈ ∈
$ $ $ per ogni
q s m q Q, s Σ, m R};
i i
• ≺ se oppure (i e ) oppure
q s m q s m i < i = i j < j
i j k i j k 1 2 1 2 1 2
1 1 1 2 2 2
(i e e ).
= i j = j k < k
1 2 1 2 1 2
si ha un buon ordine sull’insieme delle macchine di Turing aventi stati, che sono
n
in tutto 2n 2n
· · ·
(n 2 2 + 1) = (4 n + 1) ,
4 6
dunque ci saranno MdT ad uno stato, MdT a due stati, MdT a tre
25 9 13
stati,. . . . Si può dunque pensare di associare un numero naturale (un indice) ad
ogni macchina di Turing in maniera biunivoca:
÷ MdT ad uno stato
1 25 4
÷ MdT a due stati
26 25 + 9
4 4 6
÷ MdT a tre stati
25 + 9 + 1 25 + 9 + 13
... ...
all’interno di ogni gruppo, poi ci si basa sulla relazione di ordinamento. In generale,
∈
con un semplice algoritmo, dato si può risalire alla MdT
x x-esima.
N
14.1. Assumendo un ordinamento delle celle per cui la più im-
Esempio
portante è quella in alto a sinistra, la macchina di Turing n. ha due stati
4399
{q }),
(Q e la sua funzione di transizione è la seguente:
= , q
0 1 $
δ 0
$
q q R
0 1
q 1
Una differente aritmetizzazione delle MdT si basa sulle proprietà della de-
composizione in fattori primi dei numeri naturali. Analogamente al caso prece-
dente, è possibile, in modo algoritmico, passare da una MdT ad un numero na-
turale che la aritmetizza, e viceversa è possibile determinare se un numero è o no
l’artimetizzazione di una MdT. Consideriamo ancora una generica MdT definita
su un alfabeto finito: {s }
Σ = , . . . , s
0 n
{q }
Q = , . . . , q
0 m
{L,
X = R}
1. ENUMERAZIONE DELLE MDT 131
∈ ∪ ∪
ed associamo, ad ogni simbolo un numero dispari maggiore di 1:
x Σ Q X
≥ 6 6
per qualche tale che se allora Ad esempio:
a(x) = 2k + 1 k 1, x = y a(x) = a(y).
R L s q s q ...
0 1 1 2
↓ ↓ ↓ ↓ ↓ ↓ ...
3 5 7 9 11 13 ... ∗
∈ ∪ ∪
Definiamo numero di Gödel di una espressione il numero:
E (Σ Q X)
Y
k a(x )
i
gn(E) = p
i
i=1
essendo il numero dei simboli in l’i-esimo numero primo e l’i-esimo sim-
k E, p x
i i
bolo di Per l’unicità della decomposizione in fattori primi, per ogni espressione
E.
esiste uno ed un solo numero di Gödel corrispondente; inoltre tale numero è pari
nell’ipotesi sia una stringa di almeno un simbolo.
E ∗
Poiché le quintuple di una MdT sono a tutti gli effetti espressioni in ,
(Σ∪Q∪X)
è possibile in modo algoritmico associare ad ogni quintupla un corrispondente
numero di Gödel, e viceversa verificare se un dato numero è numero di Gödel di
una quintupla legittima.
Definiamo numero di Gödel di una MdT ovvero di una sequenza di quintuple
Z,
{E } il numero:
Z = , . . . , E
1 h Y
h gn(E )
i
p i
i=1
Questo numero è anch’esso unico, per l’unicità della decomosizione in fattori primi,
∗
∈ ∪ ∪
e non risulta confondibile con per una qualche espressione ,
gn(E) E (Σ Q X)
poiché, al contrario di è ottenuto mediante esponenziazione pari. Analoga-
gn,
mente, due sequenze con lo stesso numero di Gödel sono identiche (verificare per
esercizio).
In generale è possibile definire infinite aritmetizzazioni diverse per MdT, e
quindi funzioni parziali ricorsive. L’artimetizzazione scelta non è quindi sostanziale
nello sviluppo della teoria della calcolabilità. Essenziale è che, come dimostrato
in precedenza, esistano metodi algoritmici per codificare MdT all’interno dei nu-
meri naturali (suoi argomenti di calcolo). La possibilità di vedere i numeri come
al tempo stesso rappresentanti gli argomenti del calcolo e le MdT che eseguono il
calcolo, permette di applicare ai sistemi formali analizzati fino ad ora, uno dei prin-
cipi alla base dell’informatica moderna, ovvero quello di poter passare programmi
come argomenti ad altri programmi. In tutto ciò la scelta della particolare arit-
1
metizzazione è inessenziale.
1 La libertà di poter applicare MdT a MdT (autoapplicazione o referenziazione) condurrebbe
immediatamente a paradossi tipo paradosso di Russell nella teoria che stiamo sviluppando. An-
cora una volta, l’assunzione fondamentale che le funzioni calcolabili siano essenzialmente parziali,
132 14. ARITMETIZZAZIONE E UNIVERSALITÀ
Nel seguito dunque indicheremo con:
• l’insieme di istruzioni di una MdT di indice ove è il corrispondente
P x, x
x
indice o numero di Gödel della macchina, in una data aritmetizzazione.
• la funzione calcolata dalla macchina .
ϕ P
x x
Il seguente risultato è banale in seguito ad una qualsiasi aritmetizzazione delle
MdT. ℵ
14.2. Ci sono macchine di Turing distinte o funzioni parziali
Teorema 0
ℵ
ricorsive, e funzioni ricorsive.
0
Segue banalmente dal fatto che tutte le funzioni costanti sono ricor-
Proof. ℵ
sive. Pertanto ci sono almeno funzioni ricorsive.
0
Segue dunque per la Tesi di Church-Turing che:
ℵ
14.3. Ci sono esattamente funzioni calcolabili.
Teorema 0
Indicheremo nel seguito con la funzione parziale ricorsiva di indice o numero di
ϕ x
Gödel Chiaramente sappiamo che esiste un algoritmo per passare da a e/o
x. x P x
e viceversa. Pertanto, con indicheremo indifferentemente l’x-esima MdT o
ϕ ϕ
x x
funzione parziale ricorsiva in una data aritmetizzazione.
Il seguente risultato dimostra che la cardinalità delle funzioni calcolabili è
strettamente minore della cardinalità di tutte le possibili funzioni sui naturali.
Si tratta di una rivisitazione del Teorema di Cantor, nel contesto delle funzioni
calcolabili. Ne consegue che l’insieme delle funzioni calcolabili è strettamente
contenuto (ne rappresenta una piccolissima parte) nell’insieme di tutte le funzioni,
ovvero nell’insieme di tutti i possibili problemi esprimibili mediante funzioni sui
−→
naturali. In particolare, potendo selezionare una funzione in è facile
N N,
dimostrare che la probabilità di selezionarne una calcolabile è 0.
−→
14.4. Esistono funzioni (totali) non Turing calcolabili.
f :
Teorema N N
Sappiamo che, dal Teorema di Cantor (vedi Cap. 2) che:
Proof.
|{f |{f {0,
−→ ≥ −→
: : 1}}|
N N}| N
|℘(N)|
= |N|
>
| |
≥ −→ è Turing calcolabile
f : : f
N N
Rispetto a quanto visto nelle sezioni precedenti, abbiamo pertanto dimostrato
le inclusioni tra classi di funzioni come evidenziate nella Figura 1.
permette di superare tali paradossi, rendendo la teoria della calcolabilità una teoria consistente.
Si veda in proposito la Nota 15.4.
2. MACCHINA DI TURING UNIVERSALE 133
$
'
−→
N N
calcolabili
& %
Diagramma di inclusione tra insiemi di funzioni
Figure 1.
2. Macchina di Turing Universale
Per quanto si è illustrato nella sezione 1, dato un numero naturale si può
x
facilmente risalire ad una tabella definente la funzione di transizione della x-esima
macchina di Turing. D’altro canto ogni singola macchina di Turing è un oggetto
provvisto di un compito fisso. Una volta definita la funzione di transizione non vi
è modo di modificarla.
Il passo immediatamente successivo (che fornisce la base teorica al concetto di
calcolatore programmabile) è il seguente: si supponga di disporre della macchina
hx i,
di Turing con un unico input che, interpretiamo come una coppia con il
, x
1 2
seguente comportamento:
• è l’indice di una macchina di Turing ;
x P
1 x
1
• è la rappresentazione di un input che va immaginato come input per
x
2
la macchina .
P
x 1
La macchina in questione dapprima calcola la funzione di transizione della
macchina , memorizzando questa funzione. Suppone poi (cioè lo memorizza
P
x
1
opportunamente) di essere nello stato . Si posiziona dunque in corrispon-
q
0
denza del primo carattere di input (chiamiamolo e va a vedere—sulla tabella
s)
memorizzata—cosa farebbe , ossia computa Procede dunque nella
P δ (q , s).
x P 0
x1
1
simulazione andando a modificare il carattere sulla zona di nastro dedicata all’input,
lo stato nella opportuna zona in cui va memorizzato, e sposta idealmente la testina,
in base al risultato di δ (q , s).
P 0
x1
Una tale MdT si riesce ovviamente a costruire (anche se non può essere con-
siderato un facile esercizio) e dunque avrà un suo indice nella enumerazione delle
MdT; sia esso Si avrà pertanto:
u. ∀x i)
x . P (hx , x = P (x )
1 2 u 1 2 x 2
1
ove il simbolo in questo contesto sta a significare che, se una macchina termina,
=
allora terminano entrambe fornendo lo stesso risultato, altrimenti entrambe ci-
clano. Come interessante ed immediata conseguenza avremo, ad esempio, P (hu, ui) =
u
P (u).
u Più in generale possiamo dimostrare il seguente risultato, che rappresenta una
prima dimostrazione mediante Tesi di Church.
134 14. ARITMETIZZAZIONE E UNIVERSALITÀ
14.5. Esiste un indice tale che per ogni e
z x y,
Teorema
se è definita
ϕ (y) ϕ (y)
x x
ϕ (x, y) =
z ↑ altrimenti
Sia l’insieme di istruzioni di una MdT di indice Sappiamo che
P x.
Proof. x
esiste un metodo effettivo per ottenere da Applichiamo all’input e,
P x. P y
x x
quando questa termina, prendiamo il risultato come output di una funzione di 2
argomenti Pertanto abbiamo che:
ψ(x, y).
se converge
ϕ (y) ϕ (y)
x x
ψ(x, y) = ↑ se diverge
ϕ (y)
x
Applicando la Tesi di Church-Turing, possiamo concludere che è parziale ricor-
ψ
siva e pertanto esiste un indice tale che .
z ψ = ϕ z
La funzione ottenuta nella dimostrazione del precedente teorema è detta
ϕ z
funzione parziale universale e corrisponde alla MdT universale vista in precedenza.
≥
Chiaramente, il precedente teorema può essere generalizzato a funzioni di k 1
≥
variabili, in modo tale che, per ogni funzione di variabili, esiste una funzione
k 1
di variabili che gioca il ruolo di funzione universale parziale.
k + 1 14.6. Formulare e dimostrare il precedente teorema per funzioni
Esercizio
≥
di variabili.
k 1 3. Il Teorema s-m-n
Il seguente risultato, noto con il nome Teorema s-m-n e dovuto a Kleene, sarà
fondamentale nel seguito. Anch’esso rappresenta un esempio di dimostrazione
basata sulla Tesi di Church-Turing. ≥
14.7 (s-m-n). Per ogni coppia di interi esiste una funzione
m, n 1
Teorema m
ricorsiva totale di variabili tale che per ogni abbiamo che:
s m + 1 x, y , . . . , y
1 m
n
∀z · · · z . ϕ (y , . . . , y , z , . . . , z ) = ϕ (z , . . . , z )
m
1 n x 1 m 1 n 1 n
s (x,y ,...,y )
m
1
n
Consideriamo per semplicità il caso La dimostrazione per
m = n = 1.
Proof. ≥
il caso più generale per è simile. Fissati e , la funzione
m, n 1 x y λz. ϕ (y , z)
0 0 x 0
0
è chiaramente una funzione calcolabile in una sola variabile. Per ogni e , la
x y
0 0
funzione dipenderà costruttivamente da e , pertanto esisterà
λz. ϕ (y , z) x y
x 0 0 0
0
per la Tesi di Church-Turing, una funzione ricorsiva (totale!) tale che per ogni
s z
.
ϕ (y , z) = ϕ
x 0 s(x ,y )(z)
0 0 0
Come sarà fatta la funzione suddetta? Ad esempio, data la MdT per si
x
0
aggiungono un numero di stati tali per cui vengono scritti all’inizio sul nastro
“uni” (di quanti stati abbiamo bisogno?) e ricalcoliamo dunque l’indice
y + 1
0
della nuova macchina di Turing.
3. IL TEOREMA S-M-N 135
Il Teorema s-m-n gioca un ruolo essenziale nello sviluppo della teoria della ri-
corsività, e spesso verrà utilizzato, come la Tesi di Church-Turing, tacitamente. Ri-
portato alla programmazione ‘tradizionale’, il significato è più o meno il seguente.
Se avete scritto un programma che implementa un certo algoritmo su dati in
m+n
input e da un certo momento in poi di questi sono fissati, allora sapete ottenere
m
un programma ‘specializzato’ che accetta solo parametri in input. Questa è
n
la giustificazione al lavoro delle software house che ‘installano’ del software ges-
tionale generale alle varie ditte (che permettono di fissare, con i loro dati, gli m
parametri).
Il seguente risultato è una semplice applicazione del Teorema s-m-n.
14.8. Esiste una funzione ricorsiva in due argomenti tale che per
g
Teorema
ogni e .
x y: ϕ = ϕ ϕ
◦
x y
g(x,y) ↓ ↓,
Si definisca se e
ψ(x, y, z) = ϕ (ϕ (z)) ϕ (z) ϕ (ϕ (z))
Traccia. x y y x y
indefinita altrimenti. Per la tesi di Church è calcolabile, scrivo la MdT che la
◦
calcola, sia (ora noto) il suo indice, per cui . A questo
a ϕ (x, y, z) = ϕ ϕ
a x y ◦
punto se fissiamo e per il Teorema s-m-n vale che .
x y, ϕ (z) = ϕ ϕ
21 x y
S (a,x,y)
Essendo ormai noto (indice della macchina che fa la composizione), la funzione
a
è basata solo sui due parametri e
x y.
Riportiamo ora una modalità d’uso “rapida” per il Teorema s-m-n che sarà uti-
lizzata diffusamente nel resto del corso (e per la risoluzione degli esercizi d’esame).
Definiamo una funzione calcolabile a due argomenti (non pensiamo troppo al
suo significato, la costruzione si applicherà ad ogni funzione calcolabile)
2 ∈
se
b − 3 a K
ψ(a, b) = ↑ altrimenti
è calcolabile in quanto, dati e simulo la computazione di se
ψ a b, M (a);
a
2
questa termina restituisco Se non termina semplicemente non restiturò
b − 3.
mai un valore dunque, di fatto, è indefinito. Essendo calcolabile, posso
ψ(a, b)
scrivere una MdT che la calcola. Supponiamo sia il suo indice. A questo punto
x
^
è un valore definito e dunque per ogni e
a b
ψ(a, b) = ϕ (a, b)
x
^ 11
Il Teorema s-m-n ci garantisce che esiste la funzione ricorsiva totale tale
s
che per ogni e
a b ϕ (a, b) = ϕ (b)
11
x
^ s (^
x,a)
Essendo fissato, è come se ci fosse un’unica funzione ricorsiva totale tale che
x
^ 11
dato restituisce Sia pertanto tale funzione:
a s (^
x, a). g
11
g(a) = s (^
x, a)
136 14. ARITMETIZZAZIONE E UNIVERSALITÀ
Partendo dalla definizione di e verificato che essa è calcolabile, abbiamo
ψ,
stabilito che esiste ricorsiva totale tale che:
g ψ(a, b) = ϕ (b)
g(a)
Come detto sopra, possiamo usare il Teorema s-m-n in questo modo “abbre-
11
viato” omettendo il passaggio intermedio con l’indice e .
x
^ s
CHAPTER 15
Problemi insolubili
In questo Capitolo analizzeremo alcuni problemi classici non risolvibili nella
teoria della effettiva calcolabilità sviluppata fino ad ora. Il più classico problema
insolubile è il problema della terminazione posto da Turing.
Esiste una procedura effettiva tale che dati e determina se
x y
è definita o no?
ϕ (y)
x 1
Il seguente risultato preliminare dimostra l’insolubilità di un problema correlato.
15.1. Non esiste una funzione ricorsiva tale che per ogni
g x:
Lemma
↓
se
1 ϕ (x)
x
g(x) = ↑
se
0 ϕ (x)
x
Supponiamo per assurdo che esista una MdT di indice tale che
i
Proof. 0
. Allora possiamo definire la funzione:
g = ϕ i
0 ↑ se g(x) = 1 = ϕ (x)
i
0 0
g (x) = se
0 g(x) = 0 = ϕ (x)
i
0
0 0
Dunque anche sarà calcolabile e dunque esiste tale che . Ma allora
g i ϕ = g
1 i 1
abbiamo che: ↓ ⇔ ⇔ ⇔ ↑
0
ϕ (i ) g (i ) = 0 g(i ) = 0 ϕ (i )
i 1 1 1 i 1
1 1
↑ ⇔ ↑ ⇔ ⇔ ↓
0
ϕ (i ) g (i ) g(i ) = 1 ϕ (i )
i 1 1 1 i 1
1 1
Che è assurdo. Dunque non esiste un tale indice , ovvero non esiste l’indice
i i
1 0
che calcoli ovvero non è ricorsiva.
g, g
In base al Lemma 15.1, segue il teorema:
15.2. Non esiste una funzione ricorsiva tale che per ogni e
ψ x y:
Teorema
↓
se
1 ϕ (y)
x
ψ(x, y) = ↑
se
0 ϕ (y)
x
↓
1 Si ricorda che con si intende che la macchina di Turing sull’input termina
ϕ (y) x-esima y
x ↑
o equivalentemente, che la funzione ricorsiva parziale è definita per l’input Con
x-esima x. ϕ (y)
x
si intende l’opposto di tale affermazione. 137
138 15. PROBLEMI INSOLUBILI
Se esistesse allora esisterebbe un indice tale che
x ϕ (x) = ψ(x, x).
Proof. 0 x 0
non è altro che la funzione dimostrata non esistere nel Lemma 15.1.
ψ(x, x) g(x)
Il problema della terminazione è stato, storicamente, uno dei primi problemi
matematici dimostrati come insolubili, ovvero per i quali non esiste una procedura
in grado di “decidere” il problema per ogni possibile input, e rappresenta, per la
sua semplicità ed importanza pratica e teorica, uno dei risultati più importanti
ottenuti in matematica nel ventesimo secolo.
In generale, se è una proprietà (una relazione) sulle variabili , si
P x , . . . , x
1 n
dice che è decidibile se esiste una funzione ricorsiva totale tale che
P f
se vale
1 P(x , . . . , x )
1 n
f(x) = altrimenti
0
è indecidibile altrimenti. è semi-decidibile se se esiste una funzione ricorsiva
P P f
tale che se vale
1 P(x , . . . , x )
1 n
f(x) = ↑ altrimenti
↓
Pertanto la proprietà è semi-decidibile ma indecidibile.
P(x, y) = M (y)
x
Il seguente risultato, dovuto a Kleene, dimostra la non risolubilità di un altro
semplice problema correlato alle funzioni ricorsive, ovvero non è possibile decidere
se una funzione parziale ricorsiva data è totale. Il problema è chiaramente legato
alla non decidibilità della terminazione.
15.3. Non esiste una funzione ricorsiva tale che per ogni
f x:
Teorema
se è totale
1 ϕ x
f(x) = se non è totale
0 ϕ x
La dimostrazione utilizza un argomento diagonale. Supponiamo che
Proof.
esista una tale funzione Allora definiamo una funzione che associa ad ogni
f.
naturale una corrispondente funzione ricorsiva.
g(0) = µy. (f(y) = 1)
∧
g(x + 1) = µy (y > g(x) f(y) = 1).
Poiché sappiamo che esistono funzioni ricorsive totali, anche sarà totale. Per
ω g
la tesi di Church e questa osservazione è quindi ricorsiva. Definiamo una funzione
tale che Per la definizione di segue che è totale, e quindi,
h h(x) = ϕ (x)+1. f h
g(x)
per la Tesi di Church-Turing, ricorsiva. Sia dunque l’indice per cui
z h = ϕ
0 z
0
e sia tale che . Questo indice esiste per definizione di Allora
y g(y ) = z g.
0 0 0
Ma per definizione di . Poiché
h(y ) = ϕ (y ) + 1. ϕ (y ) = h(y ) y h
0 0 0 0 0
g(y ) g(y )
0 0
è totale, questa è una contraddizione.
15. PROBLEMI INSOLUBILI 139
Pertanto la proprietà è totale è indecidibile (vedremo in seguito che non è
ϕ x
nemmeno semi-decidibile).
15.4. Argomenti diagonali e insolubilità sono nozioni strettamente legate
Nota
tra loro. Ritorniamo brevemente sulla questione delle funzioni parziali. Abbiamo
visto che, ricorrendo alle funzioni parziali, si possono superare i limiti imposti da
argomenti di tipo diagonale ai sistemi formali introdotti per definire il concetto
di effettiva calcolabilità. La necessità di utilizzare funzioni parziali in luogo di
funzioni totali segue anche dalla possibilità, dimostrata in precedenza, di definire
macchine universali o funzioni ricorsive universali. Questa possibilità, associata
alla ipotesi di totalità delle funzioni calcolabili, conduce infatti direttamente a
2
paradossi simili al paradosso di Russell. L’aritmetizzazione infatti non impone
nessuna distinzione tra funzioni (MdT) e argomenti, come nella teoria degli in-
siemi classica non vi è distinzione tra insiemi e loro argomenti. Questa mancanza
di struttura permette una indisciplinata possibilità di definizioni di insiemi o fun-
zioni, che conduce ai ben noti paradossi.
È noto che è possibile codificare coppie, terne etc. con numeri naturali. Ad
× −→
esempio la seguente funzione pair è biiettiva (verificare per esercizio
: N N N
che è biiettiva e che sia lei che le due inverse e tali che pair((x)
(·) (·) x = , (x) )
1 2 1 2
sono primitive ricorsive). 1 2 2
pair(x, (x + 2xy + y + 3x + y).
y) = 2
Essa permette di associare in modo univoco, ad ogni coppia di naturali, un numero
naturale corrispondente. Quindi per la Tesi di Church-Turing esisterà un indice
tale che, se è la funzione parziale universale vista in precedenza, allora:
x y)
U(x,
0 y) = ϕ (g(x, y))
U(x, x
0
Inoltre, essendo sia che calcolabili, esisterà un indice tale che
g ϕ y ϕ (x) =
x 0 y
0 0
Sarà quindi lecito definire la funzione:
ϕ (g(x, x)).
x 0
se
1 ϕ (x) = ϕ (x) = 0
y x
0
f(x) = 6
se
0 ϕ (x) = ϕ (x) = 0
y x
0
Anche questa funzione avrà un opportuno indice . Segue quindi che
z ϕ (z ) = 0
0 z 0
0
6
se e solo se che è chiaramente una contraddizione. Per superare
ϕ (z ) = 0,
z 0
0
questo paradosso, del tutto analogo al paradosso di Russell, analogamente a quanto
visto per superare i limiti imposti dalla diagonalizzazione, basterà ancora assumere
che la funzione calcolabile calcolata dalla -esima MdT, diverga in , essendo
f, z z
0 0
2 Il paradosso di Russell nella teoria classica degli insiemi è ottenuto considerando come
{x | ⇔
6∈ ∈ 6∈
definibile nella teoria stessa l’insieme Quindi da cui segue che
A = x x}. x A x x,
⇔
∈ 6∈
A A A A.
140 15. PROBLEMI INSOLUBILI
quindi parziale ricorsiva. La funzione
↓
se
1 ϕ (y)
x
y) =
U(x, ↑ ↑
se ϕ (y)
x
è dunque necessariamente parziale ricorsiva, ed infatti, l’algoritmo che la calcola è
facilmente identificabile con la MdT universale vista in precedenza.
15.5. Dimostrare che i seguenti problemi non ammettono soluzione
Esercizio
ricorsiva:
(1) Decidere se, per ogni (Traccia: Sia la funzione ricorsiva
x: ϕ = λx.0. f
x ↓,
parziale definita come se indefinita altrimenti. Per
f(x, y) = 0 ϕ (y)
x
s-m-n si ha che per totale ricorsiva. Se, per assurdo,
f(x, y) = ϕ (y) r
r(x)
esistesse t.c. se altrimenti, si definisca
g g(x) = 1 ϕ = λx.0, g(x) = 0
x
e si giunga ad un assurdo rispetto all’enunciato del Lemma
h(x) = g(r(x))
15.1).
(2) Decidere se, per ogni è costante;
x: ϕ x
(3) Decidere se per ogni e . (Traccia: si mostri che allora si
x y: ϕ = ϕ
x y
saprebbe decidere il problema 1).
(4) Decidere se per ogni e
x, y z: ϕ (y) = z.
x
CHAPTER 16
Calcolabilità e Linguaggi di Programmazione
In questo capitolo vedremo alcune applicazioni tra le più importanti della teo-
ria elementare della calcolabilità vista nel precedente capitolo al progetto ed alla
implementazione dei moderni linguaggi di programmazione. In particolare metter-
emo in evidenza come l’espressività (in senso lato) di un linguaggio dipenda dalla
possibilità offerta da quest’ultimo di codificare uno dei formalismi affrontati per
definire il concetto di effettiva calcolabilità. Questi problemi hanno dato origine,
negli anni ‘60, alla ricerca di linguaggi di programmazione ad alto livello, in grado
cioè di esprimere tutte le funzioni effettivamente calcolabili. Tale ricerca ha dato
origine a una vasta famiglia di linguaggi come ALGOL e PASCAL, progenitori dei
più moderni linguaggi C, C++, e Java. Inoltre vedremo come l’esistenza (almeno
teorica) di strumenti ampiamente utilizzati nella moderna pratica informatica per
manipolare programmi, come i compilatori, gli interpreti, e i programmi di spe-
cializzazione, dipenda dai risultati di universalità visti nella caratterizzazione delle
funzioni calcolabili. 1. Il linguaggio While
Abbiamo fino ad ora definito il concetto di effettiva calcolabilità su una sem-
plicissima struttura dati: i numeri naturali Come vedremo, questa apparente
N.
restrizione in realtà si dimostra essere perfettamente equivalente ad ogni definizione
di calcolabilità data su strutture dati più evolute, quali stringhe, alberi etc. I nu-
meri naturali sono pertanto sufficienti per rappresentare ogni possibile struttura
dati su cui si vogliono definire algoritmi.
Al fine di evitare l’aritmetizzare dei programmi, in questo capitolo studieremo
un semplice linguaggio di programmazione imperativo chiamato in grado
While
di manipolare strutture dati più complesse. è un linguaggio ad alto livello
While
adeguato per rappresentare tutte le funzioni calcolabili che permette di manipolare
semplici strutture dati. Le strutture dati impiegate in sono molto simili a
While
quelle impiegate nei linguaggi e LISP. Questa estensione ci permetterà di
Scheme
evitare l’aritmetizzazione (operazione di interesse preminentemente matematico)
permettendo quindi di considerare direttamente i programmi come dati. Questo,
come abbiamo visto, è il passo fondamentale per definire il concetto di funzione
universale. 141
142 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
2. Strutture dati
Le strutture dati del linguaggio sono alberi binari. Questi permettono
While
di rappresentare la sintassi concreta dei programmi come dati. Sia un insieme
A
finito di atomi, o espressioni elementari, e nil l’albero vuoto. L’insieme degli alberi
è definito ricorsivamente come il più piccolo insieme tale che:
D A ∈
nil D A
⊆
A D A
∀d ∈ ∈
, d . (d .d )
D D
1 2 A 1 2 A
{a },
In altri termini, se è il linguaggio generato dalla grammatica
A = , . . . , a D
1 n A
| | | |
−→ · · ·
CF: nil
D a a (D .D ).
A 1 n A A
Ad esempio, l’albero in Figura 1 è rappresentato come: dove
((a.((b.b).c)).d),
{a, è il corrispondente insieme di atomi.
A = b, c, d} •
((a.((b.b).c)).d)
•
(a.((b.b).c)) d
•
a ((b.b).c)
• c
(b.b)
b b
L’albero ((a.((b.b).c)).d)
Figure 1.
16.1. è isomorfo a
Teorema D N
A
È semplice definire una biiezione tra e . Ad esempio si possono
Traccia. N D A
prima contare gli alberi di altezza 0, poi quelli di altezza 1 e cosı̀ via. Ad esempio,
{a }:
se A = , . . . , a
1 n 2 2
0 1 2 ... n n + 1 n + 2 ... n + 3n + 2 n + 3n + 3 ...
nil a a ... a (nil.nil) (nil.a ) . . . (a .a ) (nil.(nil.nil)) ...
1 2 n 1 n n
3. SINTASSI 143
3. Sintassi
Nel seguito assumeremo di avere a disposizione un insieme infinito e numerabile
di variabili La loro sintassi può essere descritta dalla seguente grammatica
Var.
CF: → V
Var Num
→ |9Dig
· · ·
1Dig|2Dig|
Num → |9Dig
· · ·
Dig ε|0Dig|1Dig|
Per semplicità saranno indicate da eccetera.
x, y, z, x , y , z
1 1 1
La sintassi di è definita da una grammatica CF nel modo seguente
While
∈ ∈
dove e (per essere precisi, dovremmo scrivere in luogo di
x, y Var, d D
D A A
(similmente per e tuttavia ci farà comodo nel seguito identificare con
d x Var); ∈
un arbitrario elemento di , pertanto usiamo questa notazione). Inoltre,
d d D A
per facilitare la lettura e la scrittura delle regole per la semantica, aggiungiamo
dei pedici a occorrenze multiple della stessa variable (ad esempio ). A
Exp , Exp
1 2
rigore non ci andrebbero.
→ | | | | |
cons(Exp hd(Exp) tl(Exp)
Exp x d , Exp ) (Exp = Exp )
1 2 1 2
→ | | |
skip while do endw
Com x := Exp Com ; Com Exp Com
1 2
→ read(Listavar); write(Listavar)
Prog Com;
→ |
Listavar x x, Listavar
Assumiamo inoltre che in le variabili siano tutte distinte. Si osservi come
Listavar
in questo linguaggio non vi sia la dichiarazione di tipo per le variabili. Tutte le
variabili infatti possono assumere solo valori di “tipo” .
D A
16.2. Il seguente programma è ben definito [darne l’albero
Esempio While
di derivazione per esercizio]. read(x);
nil;
y :=
while do
x cons(hd(x),
y := y);
tl(x)
x :=
endw;
write(y)
144 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
4. Semantica
La semantica di un programma è data in termini di un sistema di
While
transizione [26, 31]. Per definirla, dobbiamo prima definire il concetto di stato.
Questo rappresenta la memoria della macchina preposta all’esecuzione di pro-
grammi La memoria può essere vista come un nastro in cui ogni cella
While.
corrisponde esattamente ad una variabile in e può contenere esclusivamente
Var
valori in . Pertanto, uno stato è rappresentabile come una funzione parzial-
σ
D A →
mente definita da variabili in valori . L’insieme di tutti gli stati
σ : Var D A
∈
è detto Se allora il valore dello stato (memoria) in cor-
State. σ State, σ
∈
rispondenza alla variabile è dato dal valore della funzione in ovvero
x Var σ x,
∈ . Un comando ha lo scopo di modificare lo stato corrente.
σ(x) D A
Per semplicità assumeremo che le variabili abbiano sempre il valore iniziale nil
e dunque non ci occuperemo del caso semplice ma noioso del trattamento della
⊥
propagazione del valore di cella indefinita in tutte le regole che definiremo.
La semantica intuitiva dei comandi di è data nel seguente modo:
While
I programmi hanno variabili di ingresso (read) e uscita (write).
Possono usare inoltre quante altre variabili si voglia, prese da
I comandi modificano lo stato nel seguente modo:
Var.
• skip lascia lo stato invariato;
• memorizza il valore di calcolato nello stato
x := Exp Exp
corrente nella cella di memoria rappresentata dalla vari-
abile x;
• corrisponde all’esecuzione del comando nello
C ; C C
1 2 2
stato lasciato dall’esecuzione del comando ;
C
1
• while do endw esegue il comando fino a che l’albero
E C C
rappresentato dalla espressione non è vuoto.
E
La semantica di un programma:
read(x write(y
, . . . , x ); C; , . . . , y )
1 n 1 m
è quindi data dalla funzione che associa ad ogni variabile in
ingresso il valore delle variabili in uscita
x , . . . , x y , . . . , y
1 n 1 m
determinato nello stato modificato da C.
Possiamo quindi dare la semantica formale di induttivamente sulla sintassi
While
come sistema di transizione:
Semantica delle espressioni: Ogni espressione rappresenta un albero.
Al fine di valutare espressioni contenenti variabili è necessario per la
loro valutazione ricorrere alla memoria. La semantica delle espressioni è
data dunque da una funzione di interpretazione semantica:
→
E ×
: Exp State D A
definita come in Tabella 1. Il risultato dell’espressione può
E = E
1 2
essere false oppure true; queste entità sintattiche possono essere usate
liberamente come abbreviazioni degli alberi nil e rispettivamente.
(nil.nil),
4. SEMANTICA 145
E[[x]]σ E[[d]]σ
= σ(x) = d
E[[cons(E E[[E E[[E
, E )]]σ = (E[[E ]]σ.E[[E ]]σ) = E ]]σ = (E[[E ]]σ = ]]σ)
1 2 1 2 1 2 1 2
E[[E]]σ E[[E]]σ
se se
c = (t.c) t = (t.c)
E[[tl(E)]]σ E[[hd(E)]]σ
= =
nil altrimenti nil altrimenti
Semantica delle espressioni
Table 1.
Semantica dei comandi: La semantica dei comandi è definita induttiva-
mente sulla sintassi dal sistema di transizione in Tabella 2. Le configu-
×
razioni del sistema di transizione sono definite da coppie: Com State.
hC,
Ogni configurazione rappresenta il comando da eseguire e lo
σi C
stato in cui questo viene eseguito. Il sistema di transizione definisce
σ −→⊆ × × ×
una relazione che rappresenta
(Com State) (Com State)
il generico passo di calcolo. Nel seguito, se il comando è vuoto (stringa
hε,
vuota allora la configurazione corrispondente è rappresentata
ε), σi
semplicemente come σ.
E[[E]]σ=d
hx:=E,σi−→σ[d/x] hskip,σi−→σ
0
hC ,σi−→σ
1 0
hC i
;C ,σi−→hC ,σ
1 2 2
E[[E]]σ=nil
while do endw
h E C ,σi−→σ
E[[E]]σ6 nil
=
while do endw while do endw
h E C ,σi−→hC; E C ,σi
Semantica dei comandi
Table 2.
Semantica dei Programmi: La semantica di un programma è
While
definita a partire dalla semantica dei comandi, o meglio dalla chiusura
∗
−→
transitiva della relazione di transizione dei comandi. Essa definisce
una funzione parziale da di alberi in di alberi, ovvero:
n-uple m-uple
→ → {↑})
W n m ∪
[[·]] : Prog (D D
A A
146 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
↑ W
dove indica la non terminazione di un programma. La semantica [[P]]
di un programma
read(x write(y
P = , . . . , x ); C; , . . . , y )
1 n 1 m
∈
è definita come segue, per ogni :
d , . . . , d D
1 n A
∗ 0
hC, −→
se [d ]i
e , . . . , e /x , . . . , d /x σ
1 m 1 1 n n
W 0 0
[[P]] (d , . . . , d ) = e σ (y ) = e , . . . , σ (y ) = e
1 n 1 1 m m
↑ altrimenti
16.3. Come esempio di semantica di un semplice programma
Esempio While,
consideriamo la semantica del programma dell’Esempio 16.2 che calcola l’inverso
P
di una lista rappresentata come un albero sbilanciato a sinistra.
16.4. Si fornisca una semantica formale per i comandi:
Esercizio
• if then else , dal significato intuitivo seguente: si valuti l’espressione
Exp C C
1 2
se è diverso da nil si esegua l’istruzione , altrimenti si esegua
Exp; C 1
l’istruzione .
C 2
• for do endfor. La semantica intuitiva di questo importante
x := Exp C
costrutto, ripreso nella Sezione 6, è la seguente: si valuta sul valore
Exp
dello stato iniziale. Essa sarà un albero che necessita di esattamente
≥ ∈
operazioni di tipo tl per restituire l’espressione atomica nil o
n 0 a i
A. L’istruzione viene quindi ripetuta per volte; all’inizio ha il
C n x
valore iniziale di poi viene via via ridotto fino a raggiungere nil
Exp, x =
∈ A.
o e le variabili che occorrono in non possono essere
a x Exp
i
modificate entro C.
16.5. Si mostri, scrivendo frammenti di codice in cui sono
Esercizio While
introdotte (se servono) ulteriori variabili, che i due costrutti suddetti possono essere
definiti all’interno del linguaggio (in altri termini che il codice scritto ha,
While
sulle variabili originarie, la stessa semantica).
16.6. Si mostri come il comando if-then-else dell’esercizio prece-
Esercizio
dente possa essere simulato dal comando for definito nello stesso esercizio. Sug-
gerimento: se è l’espressione dell’if-then-else, si assegnino le variabili e nel
α u v
seguente modo: nil); nil); Si eseguano dunque due cicli for:
u := (α = v := (u =
uno controllato da che esegue e uno da che esegue .
u C v C
2 1
{a,
16.7. Sia Si scriva un Programma che
A = . . . , z}.
Esercizio While
verifica se un elemento di è presente nell’albero (restituisce
x A x y = (nil.nil)
1 2
in caso affermativo, nil altrimenti).
y =
5. Espressività di e Turing completezza
While
È possibile rappresentare i numeri naturali in . La rappresentazione in
D D
A A
La seguente definizione illustra uno dei modi a nostra
del numero è denotata
n n.
5. ESPRESSIVITÀ DI E TURING COMPLETEZZA 147
WHILE
disposizione di codificare i numeri naturali:
nil
0 =
n + 1 = (nil . n) · · ·
nil)
Utilizzando il cons e la sua semantica, anche cons(nil, cons(nil, cons(nil , )
. . . ,
{z }
| n
rappresenta il numero n. →
k
16.8. Una funzione è se esiste un
f :
Definizione While-calcolabile
N N ∈
programma tale che per ogni
P x , . . . , x
While N:
1 k
W
[[P]] (x , . . . , x ) = f(x , . . . , x )
1 k 1 k
16.9. Il seguente programma calcola la funzione f(x, y) =
Esempio While
x + y: read(x , x );
1 2
while do
x
2 cons(nil,
x := x );
1 1
tl(x
x := )
2 2
endw;
write(x )
1
16.10. Si scrivano i programmi per il calcolo della differenza
Esercizio While
tra numeri naturali, del prodotto, delle operazioni e del test x < y.
div, mod,
L’ampiezza della classe delle funzioni è determinata dal
While-calcolabili
seguente teorema, che conferma la Tesi di Church-Turing anche per i linguaggi
di programmazione imperativa.
→
16.11. è sse è Turing-calcolabile.
f :
Teorema While-calcolabile
N N
Per induzione sulla sintassi di costruiamo una MdT
(→)
Proof. While,
che calcola la medesima funzione calcolata dal corrispondente programma While.
Poiché i programmi sono costituiti da sequenze di comandi, è sufficiente indurre
sulla complessità sintattica dei comandi. Similmente a quanto fatto nella di-
mostrazione del Teorema 12.14, poniamo delle restrizioni alle MdT che costruiamo
in modo tale da semplificare l’applicazione dell’ipotesi induttiva.
(1) Per semplicità, l’alfabeto delle MdT coincide con l’alfabeto della gram-
matica usata per costruire .
D A
(2) Tali macchine hanno, prima dell’esecuzione, a sinistra dell’input la de-
scrizione del contenuto delle variabili . Solo un numero finito
x , x , x , . . .
1 2 3
di queste è diverso da 0. Sia la variabile di indice maggiore tra quelle
x k
diverse da 0. Fin dall’inizio sappiamo quali variabili saranno toccate dal
148 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
programma. Assegnamo valore nil alle altre. Alla fine della computazione
(se termina) a sinistra della testina vi sarànno invece i valori finali di tali
variabili.
(3) Ci serviranno MdT per il calcolo di espressioni. In tal caso assumiamo
che la parte sinistra del nastro sia come sopra, mentre immediatamente
a destra della testina sia memorizzata l’espressione calcolata (si ricorda
che le variabili coinvolte nelle espressioni sono note dall’inizio).
(4) Inoltre le macchine sono definite in modo tale da essere indipendenti dal
contenuto del nastro sulla parte destra rispetto alla posizione iniziale
della testina.
Base: Vi sono 3 MdT di base:
• Calcolo di una espressione In vi saranno dati da e variabili. Si
E: E D A
costruisce l’espressione a partire da ciò. [Esercizio], mettendo il risultato
subito a destra della posizione finale della testina.
• istruzione skip: una MdT che non fa nulla soddisfa a tutti i requisiti.
• Si parte dal calcolo dell’espressione (vedi sopra). Una volta
x := E.
i
pronta, si mette il valore dell’espressione calcolata nella posizione della
variabile , dopo avere spostato a sinistra i contenuti delle variabili
x i .
x , . . . , x
i+1 k
Passo: Come caso induttivo, affrontiamo i 3 casi possibili:
(1) Supponiamo che la MdT simuli l’istruzione e la MdT simuli
M C M
1 1 2
l’istruzione :
C 2
Si attiva la macchina . Se questa termina, si attiva la
M 1
macchina .
M 2
(2) Analizziamo il caso del comando while. Supponiamo di avere, per ipotesi
induttiva, una MdT per il comando ed una per la valutazione
M C M
C E
della espressione La seguente MdT corrisponde alla esecuzione del
E.
comando while do endw:
E C
Si attiva . Se sul nastro a destra della testina vi è nil, allora
M E
termina. Altrimenti si attiva e, qualora termini, si reitera.
M C
Sia una funzione Turing calcolabile. Dal Teorema 12.14, sappiamo che
(←) f
∈ PR. La dimostrazione prosegue per induzione sulla struttura delle funzioni
f
parziali ricorsive. Costruiamo ed utilizziamo solo programmi che inizializzano
tutte le variabili che usano.
Base: • read(x); nil; write(x);
λx. 0: x :=
• read(x); cons(nil, write(x);
λx. x + 1: x := x);
• : read(x skip; write(x
λx . . . x . x , . . . , x ); ).
1 n i 1 n i
Passo: Analizziamo i tre casi induttivi.
(1) Supponiamo per ipotesi induttiva che esista un programma :
P
h
h h h
read(x write(y
, . . . , x ); C ; )
h
1 k
5. ESPRESSIVITÀ DI E TURING COMPLETEZZA 149
WHILE
che calcola la funzione e :
h P , . . . , P
g g
1 k
g g g
i
read(x write(y
, . . . , x ); C ; )
i i
g
n
1 i
che calcolano le funzioni . Supponiamo inoltre che tali pro-
g , . . . , g
1 k
grammi usino tutti variabili diverse (altrimenti le rinominiamo). Sia il
µ
massimo indice di variabile usato in quei programmi. Allora la funzione
si calcola nel modo
f(x , . . . , x ) = h(g (x , . . . , x ), . . . , g (x , . . . , x ))
1 k 1 1 n k 1 n
seguente:
read(x , . . . , x );
µ+1 µ+n
g g
1 1
x := x ; . . . ; x := x ; C ;
n
µ+1 µ+n g
1 1
..
. g g h g
h g
k k ; C ;
x := x ; . . . ; x := x ; C ; . . . ; x := y
; x := y k
1
n h
µ+1 µ+n g k
1
1 k
write(y )
h
(2) Sia ora definita per ricorsione primitiva (per semplicità denotazionale
f
usiamo invece di ):
x x , . . . , x
1 n
f(x, 0) = g(x)
f(x, y + 1) = h(x, y, f(x, y))
e supponiamo, per ipotesi induttiva, che alle funzioni ed corrispon-
g h
dano i programmi: g1
read(x write(y
); C ; )
g g
h h h
read(x write(y
, x , x ); C ; )
h h
1 2 3
Supponiamo ancora che tali programmi usino variabili diverse e sia il
µ
massimo indice di variabile usato. Il seguente programma implementa la
150 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
funzione f:
read(x , x );
µ+1 µ+2
x := x ; C ; x := y ; x := nil;
g µ+1 g µ+3 g µ+4
while do
x
µ+2
h h 3
x := x ; x := x ; x := x ;
µ+1 µ+4 µ+3
1 2 h
C ;
h tl(x cons(nil,
x := ); x := x );
µ+2 µ+2 µ+4 µ+4
x := y ;
µ+3 h
endw;
write(x )
µ+3
(3) Sia infine definita per minimizzazione a partire da una funzione
ϕ f :
n+1 −→ calcolata da:
N N, f1 fn fn+1
read(x write(y
, . . . , x , x ); C ; ).
f f
e siano variabili non usate in esso. Il seguente pro-
x , . . . , x , y, temp
1 n
gramma calcola la funzione ϕ:
read(x , . . . , x );
1 n
y := nil; fn+1
1f fn := x ; x := y;
x := x ; . . . ; x n
1
C ;
f
while do
y f cons(nil,
y := y);
1f fn fn+1
x := x ; . . . ; x := x ; x := y;
n
1
C ;
f
endw;
write(y)
È possibile generalizzare quanto visto per il linguaggio ad un arbi-
While
L
trario linguaggio di programmazione. Sia un linguaggio di programmazione che
L
definisce funzioni su un insieme di dati Nel seguito con indicheremo la classe
D. L.
dei programmi sintatticamente corretti scritti nel linguaggio Supponiamo che
∈
esista una codifica univoca dei numeri naturali in ovvero per ogni e
n: n
D, D
6. FOR-CALCOLABILITÀ E FUNZIONI PRIMITIVE RICORSIVE 151
L
6 6 L
per ogni Sia la semantica del linguaggio definita in modo
n = m: n = m. [[·]]
1
formale: → → {↑})
L L ∪
[[·]] : (D D
→
k L-calcolabile ∈ L
Una funzione è se esiste un programma tale che
f : P
N N
∈
per ogni x , . . . , x N:
1 k , . . . , x ) = f(x , . . . , x )
[[P]](x k 1 k
1 L
16.12. Un linguaggio di programmazione è detto Turing-
Definizione L-calcolabili
completo se l’insieme delle funzioni coincide con la classe delle funzioni
Turing-calcolabili.
Il linguaggio è dunque Turing-completo per il Teorema 16.11. In par-
While
ticolare, ogni linguaggio di programmazione sufficientemente espressivo per codi-
ficare i numeri naturali e comprendente i comandi di base di assegnamento, com-
posizione ed iterazione condizionata tipo è Turing-completo. Infatti, per
While
dimostrare la Turing-completezza di un linguaggio è sufficiente dimostrare che
questo è in grado di simulare i costrutti di base di While.
16.13. Una Macchina di Turing si può rappresentare mediante un
Esercizio
insieme (lista) di quintuple (lista di 5 elementi). Si scriva un programma While in
grado di simulare il comportamento (interpretare) una data macchina di Turing
(questa è una dimostrazione alternativa che ogni funzione Turing-calcolabile è
While-calcolabile).
6. For-calcolabilità e funzioni primitive ricorsive
In questa sezione presenteremo una variante al linguaggio Sosti-
While.
tuiremo al comando while due comandi, uno di selezione ed uno iterativo molto us-
ati in programmazione: l’if-then-else ed il ciclo for. Nell’esercizio 16.4 tali costrutti
sono stati definiti e la loro simulazione utilizzando il while è stata richiesta come
(semplice) esercizio. Mostreremo ora come un linguaggio che disponga di questi
due costrutti più l’assegnamento permette una espressività pari a quella del for-
malismo delle funzioni primitive ricorsive.
Nelle stesse ipotesi generali dei programmi definiamo un programma
While, ∈ ∈
mediante una grammatica CF nel modo seguente dove e
x, y Var, d
For D A
(in particolare, può essere nil):
d
→ | | | | |
cons(Exp hd(Exp) tl(Exp)
Exp x d , Exp ) Exp = Exp
1 2 1 2
→ | | |
skip
Com x := Exp Com ; Com
1 2
if then else endif| for do endfor
Exp C C x := Exp C
1 2
→ read(x write(y
Prog , . . . , x ); Com; , . . . , y )
1 n 1 m
1 È noto che ad ogni linguaggio di programmazione, anche complesso e di alto livello, è
possibile associare una semantica formale [31, 21].
152 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
La semantica intuitiva dei due costrutti è definita nell’esercizio 16.4. Inoltre,
come mostrato nell’esercizio 16.6, il costrutto if-then-else è simulabile dal for e
→
k
dunque superfluo (non ne parleremo nelle dimostrazioni). Una funzione f : N N
∈
è se se esiste un programma tale che per ogni
P x , . . . , x
For-calcolabile For N:
1 k
L , . . . , x ) = f(x , . . . , x )
[[P]] (x k 1 k
1
Nel teorema seguente si forniranno delle definizioni più tecniche e precise, ma la
sua comprensione e definizione ne può fare a meno.
m −→
16.14. è se e solo se è primitiva
f : f
Teorema For-calcolabile
N N
ricorsiva. Per mostrare che una funzione primitiva ricorsiva è
Traccia. For-calcolabile
è sufficiente ripetere la seconda parte della dimostrazione del Teorema 16.11 fino
al passo induttivo 1. Bisogna mostrare anche il passo induttivo 2 con il nuovo
3 −→
linguaggio. Supponiamo che alla funzione corrisponda il programma:
h : N N
1h 2h 3h
read(x write(y Il seguente programma implementa la funzione
, x , x ); C ; ). f
h h
definita per ricorsione primitiva:
read(n, x);
x := x;
g
C ;
g
temp := y ;
g
for do
w := n
1h 2h 3h
x := temp; x := w; x := x;
C ;
h
temp := y ;
h
endfor;
write(temp)
Leggermente più tecnico è il viceversa. Dobbiamo mostrare che ogni funzione
calcolata da un programma è calcolabile con una funzione primitiva ricorsiva.
For
Innanzitutto partiamo dalle seguenti assunzioni:
• Assumiamo che ogni espressione usata nel programma sia tale che per
ogni istanziazione delle variabili in essa in numerali si ottiene un nu-
merale. Questa assunzione è eliminabile grazie all’isomorfismo tra e
D A
ma snellisce la dimostrazione.
N,
• Assumiamo al solito che ogni variabile non presente tra quelle di input
sia immediatamente inizializzata a nil (0).
6. FOR-CALCOLABILITÀ E FUNZIONI PRIMITIVE RICORSIVE 153
• Assumiamo che un programma usi tutte e sole le variabili e
v , . . . , v
1 p
che le variabili di input siano le prime variabili .
x , . . . , x n v , . . . , v
1 n 1 p
≤ ≤
In generale si avrà che e (m è il numero di variabili di
m p n p
output). p
• −→
Ogni comando è visto come un insieme di funzioni da
C p N N.
• Le funzioni calcolate da un programma
m P
read(v write(v
, . . . , v ); C; , . . . , v )
1 n i i m
1
Pi Pi
saranno dunque le funzioni definite nel seguente modo: se
f , . . . , f m
1
C C sono le funzioni calcolate da sulle variabili di output, allora,
f , . . . , f C
i i m
1
per j = 1, . . . , m
Pi C
f )
(x , . . . , x ) = f (x , . . . , x , 0, . . . , 0
{z }
|
1 n 1 n
i
j j p
ovvero con le variabili del programma non presenti tra gli input inizializ-
C
zate a 0. Ovviamente, se le sono primitive ricorsive, lo saranno anche
f
P
le .
f
• Per brevità, con si denota la lista .
x̄ x , . . . , x
1 p
Ci si concentra dunque sulle funzioni calcolate dai comandi.
Base: C
skip: Per ogni si avrà che ovvero una proiezione.
i = 1, . . . , p f (x̄) = x i
i C
6
Per ogni si avrà che ovvero una
v := E: i = 1, . . . , p, i = j f (x̄) = x
j i
i
C
proiezione. Per quanto riguarda per l’assunzione sopra, o è un
f (x̄), E
j
C
∈
numerale e dunque (ovviamente p.r.) oppure è del tipo
` f (x̄) = ` E
N j C
· · · · · ·
cons(nil, cons(nil, ovvero per qualche intero,
, v ) ) f (x̄) = x + ` `
k k
j
· · · · ·
oppure del tipo tl(tl(· (eventualmente alternate con delle
(tl(v )) ))
k
C
hd) ovvero per qualche intero, o una combinazione degli
f (x̄) = x − `, `
k
j
ultimi due casi. Anche in questo caso la funzione è p.r.
Passo: C C
: Siano, per ipotesi induttiva, per le funzioni e .
1 2
C ; C i = 1, . . . , p f f
1 2 i i
Allora le funzioni associate alla composizione sono, per i = 1, . . . , p:
C C C
2 1
f (f (x̄), . . . , f (x̄))
1
p
i 1
for do endfor: Siano, per ipotesi induttiva e per le
v := E C i = 1, . . . , p,
j C E
funzioni primitive ricorsive equivalenti al comando e quelle as-
f C f
i i
sociate al comando Definisco allora per le funzioni
v := E. i = 1, . . . , p,
j
154 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
nel seguente modo:
h i
6
h (x̄, 0) = x i = j
i i
h (x̄, 0) = 0
j
C 6
h (x̄, n + 1) = f (h (x̄, n), . . . , h (x̄, n)) i = j
i 1 p
i
h (x̄, n + 1) = h (x̄, n) + 1
j j
La funzione da associare al comando for, per ogni sarà:
i = 1, . . . , p,
E
g (x̄) = h (x̄, f (x̄))
i i j
7. Interpreti e Metaprogrammazione
In questa sezione introduciamo il concetto di interprete e di metaprogram-
mazione. Per metaprogrammazione si intende la costruzione di programmi che
manipolano programmi. Questa possibilità, sancita dalla universalità dei sistemi
di calcolo Turing-completi, risiede nel fatto che i programmi possono essere codifi-
cati in modo univoco nei dati manipolati dai programmi stessi. La MdT universale
è il prototipo di metaprogramma: essa prende in input l’indice di una data
x
U
MdT ed un dato e restituisce in output il risultato ottenibile attivando la
M y,
macchina sul dato
M y:
x
↓
se
ϕ (y) ϕ (y)
x x
y) =
U(x, ↑ altrimenti
Traslando questo ragionamento sui linguaggi di programmazione, si ottiene il
L S
concetto di interprete. Siano ed due linguaggi di programmazione Turing-
completi; assumiamo che operino sul medesimo insieme di dati D.
∈ L S-programma
16.15. Un programma tale che, per ogni
int
Definizione ∈
e per ogni dato
P d D: L S
[[int]] (P, d) = [[P]] (d)
L S-programmi S).
è un interprete in di (o semplicemente di
↑, ↑.
S L
Ovviamente, se allora anche
[[P]] (d) [[int]] (P, d)
L’esistenza di un interprete è assicurata dalla Turing-completezza dei linguaggi
L S-programma
in oggetto. In altri termini in si deve simulare l’esecuzione del
sull’input istruzione per istruzione. Per far ciò ci si baserà sulla semantica
P d S. L
(formalmente definita) del programma nel linguaggio Un interprete in per
P
L L.
programmi è detto metainterprete del linguaggio
Vedremo nel dettaglio come realizzare un metainterprete del linguaggio While.
Per altri linguaggi Turing-completi, il lavoro da fare sarà analogo. Innanzitutto
7. INTERPRETI E METAPROGRAMMAZIONE 155
read(v write(v
); C; ) = ((var.i).(C.(var.j)))
i j = (; .(C .C ))
C ; C 1 2
1 2
while do endw
E C = (while(E.C))
v := E = (:= .((var.i).E))
i v = (var.i)
i = (quote.d)
d
cons(E , E ) = (cons.(E .E ))
1 2 1 2
hd(E) = (hd.E)
= (tl.E)
tl(E)
(E = E ) = (= .(E .E ))
1 2 1 2
Sintassi concreta del linguaggio
Table 3. While
è necessario rappresentare in i programmi A tal fine definiamo un
While.
D A
insieme finito di atomi: 00
{‘‘ }
00 00 00 00 00 00 00 00
A = := , ‘‘var , ‘‘while , ‘‘cons , ‘‘tl , ‘‘hd , ‘‘nil , ‘‘; , ‘‘quote
In possiamo codificare i numeri naturali, mediante sintassi concreta:
D A · · · · · ·
nil)
n = (nil.(nil. (nil. ))
| {z }
n {v },
Assumendo che l’insieme delle variabili useremo la seguente
Var = , v , v , . . .
0 1 2
codifica per codificare un insieme infinito di variabili: la variabile è codificata da
v
i
Useremo poi una parola chiave per ogni costrutto, espressione o comando,
(var.i).
previsto nella sintassi di Useremo per dire che l’espressione (un
quote
While.
albero privo di variabili) non necessita di essere ulteriormente codificata. La
d −→
seguente funzione di traduzione da programmi ad alberi
: While While
D A
, è definita induttivamente sulla sintassi in tabella 3.
D A · · · · · ·
Se vi sono più variabili di ingresso/uscita si userà una lista del tipo: ((var.1).((var.2). (var.n)) ).
∈
Se è un programma allora è detta sintassi concreta di Ad
P P P.
While, D A
esempio, la sintassi concreta del programma nell’Esempio 16.3, assumendo come
x
156 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
e come è data dal seguente albero (parentesi più, parentesi meno):
v y v
1 2
( (var.1).
( (; .((:= .((var.2).(quote.nil))))).
((while.((var.1).
(; . ((:= .((var.2).(cons. ((hd.(var.1)(var.2))))))).
(:= .((var.1).(tl. (var.1))))
).
(var.2)))))
) 16.16. Esiste un interprete in per
Teorema While While.
Scrivere l’interprete per esercizio, utilizzando i costrutti di
Proof. While,
eventualmente estesi con costrutti condizionali tipo Suggerimento: utilizzare
case.
le strutture dati ad albero per rappresentare la sintassi concreta dei programmi ed
una pila implementata con una lista per la valutazione delle espressioni.
La possibilità offerta da un linguaggio Turing-completo della metaprogram-
mazione è alla base della esistenza di problemi algoritmicamente non risolvibili. I
limiti di ciò che è calcolabile nascono quindi dalle potenzialità del sistema di calcolo
stesso. Cosı̀ come l’indecidibilità della terminazione è dimostrata utilizzando fun-
zioni universali, daremo una dimostrazione della indecidibilità della terminazione
utilizzando il linguaggio senza ricorrere all’aritmetizzazione dello stesso.
While, def ∈
Supponiamo esista un programma read(x write(y)
halt = , x ); C; While,
1 2
tale che:
↓
W
(nil.nil) [[P]] (d)
W
[[halt]] (P, d) = ↑
W
nil [[P]] (d)
∈
Definiamo il programma nel modo seguente:
R While
read(x);
x := x; x := x;
1 2
C;
while do endw;
y y := y
write(y)
Sia dunque la rappresentazione in del programma
R R.
D
8. SPECIALIZZATORI E PROIEZIONI DI FUTAMURA 157
↓,
W
• Se allora l’output di che termina sempre per ipotesi, è
[[R]] (R) C,
Ma allora il programma entra in loop nel ciclo
y = (nil.nil). R while.
↑.
W
Questo implica che [[R]] (R)
↑
W
• Se allora l’output di è nil. Ma allora il programma non en-
[[R]] (R) C R ↓.
W
tra nel ciclo while e dunque termina restituendo nil. Dunque [[R]] (R)
Entrambi i casi portano ad un assurdo.
8. Specializzatori e Proiezioni di Futamura
Dalla Turing-completezza dei linguaggi di programmazione derivano altri stru-
menti importanti per la moderna programmazione di sistemi complessi. Abbiamo
già visto che la Turing-completezza assicura l’esistenza di programmi universali,
ovvero di interpreti. Vedremo ora che essa permette di implementare programmi
che operano come specializzatori di programmi. L’esistenza di questi programmi
segue dal Teorema s-m-n, la cui dimostrazione segue a sua volta dalla possibilità
di implementare programmi che manipolano programmi. Rileggiamo tale teorema
nella calcolabilità:
While 16.17 (Teorema s-m-n). Esiste un programma tale che
spec
Teorema While
∈
per ogni programma e per ogni porzione del suo input
P s [[spec]](P, s)
While D,
∈
è un programma e per ogni vale che:
d
While D
[[[[spec]](P, s)]](d) = [[P]](s, d)
Vediamo cosa dovrebbe fare il programma Dato
spec. P:
Proof. read(x write(y)
, x ); C;
1 2
∈
e deve restituire il programma:
s D read(x write(y).
); x := s; C;
2 1
E’ immediato scrivere un programma che fa ciò in
While.
Lo specializzatore per programmi del teorema sopra potrebbe essere
While
scritto facilmente in ogni altro linguaggio di programmazione. Pensate ad esempio
di disporre di un compilatore C. Scrivere un programmino C che prende in input
un programma e lo specializza non ci porterebbe via più di qualche minuto.
While
Similmente lo potremmo fare in Prolog, LISP, ecc. Possiamo dunque enunciare:
L
16.18. Sia un linguaggio di programmazione Turing-completo.
Corollario ∈ L
Allora esiste un programma tale che per ogni programma e
spec P
While
L
∈
per ogni porzione del suo input è un programma e per
s [[spec]] (P, s) While
D,
∈
ogni vale che:
d D L W W
[[[[spec]] (P, s)]] (d) = [[P]] (s, d)
La dimostrazione del corollario sopra è basata su due fatti:
L
(1) Disponiamo di un linguaggio Turing-completo che sappiamo utilizzare
(ovvero di cui conosciamo bene sintassi e semantica).
158 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
(2) Conosciamo bene sintassi e semantica del linguaggio ai cui pro-
While
grammi vogliamo applicare la specializzazione.
Ovviamente, conoscendo bene sintassi e semantica di un terzo linguaggio di
S
programmazione sullo stesso insieme di dati potremmo pensare di ripetere
D,
la cosa (in altri termini, ad esempio, potremmo scrivere in C uno specializzatore
per Prolog, oppure in Java uno specializzatore per Pascal, e cosı́ via). Possiamo
dunque enunciare: L S
16.19. Siano e due linguaggi di programmazione Turing-
Corollario
completi, operanti sullo stesso insieme di dati Allora esiste un programma
D.
∈ L ∈ S
tale che per ogni programma e per ogni porzione del suo input
spec P
L
∈ S ∈
è un programma e per ogni vale che:
s [[spec]] (P, s) d
D, D
L S S
[[[[spec]] (P, s)]] (d) = [[P]] (s, d)
Quest’ultimo corollario del Teorema s-m-n sancisce l’esistenza di uno special-
izzatore, ovvero: 16.20. Un programma scritto in un linguaggio di imple-
spec
Definizione
L ∈ L
mentazione è uno specializzatore se per ogni programma scritto
spec P
S ∈
in un linguaggio di programmazione e per ogni porzione di suo input s D,
L
S-programma: ∈
restituisce un tale che per ogni dato
[[spec]] (P, s) d D:
L S S
[[[[spec]] (P, s)]] (d) = [[P]] (s, d).
Dunque uno specializzatore non interpreta un programma ma ne restituisce
uno nuovo sulla base di uno esistente (in un dato linguaggio) e di una parte del suo
input. Il suo compito è simile a quello della funzione ricorsiva totale del Teorema
s-m-n. L S
Disponendo di due linguaggi di Programmazione e sullo stesso insieme di
dati e conoscendo la semantica (meglio se data mediante regole operazionali) del
D, S L S.
linguaggio possiamo pensare di interpretare in il linguaggio Precisamente:
L S
16.21. Dati due linguaggi di Programmazione e sullo stesso
Definizione ∈ L S
insieme di dati programma è un interprete del linguaggio se per ogni
int
D,
∈ S ∈
e per ogni vale che:
P d D L S
[[int]] (P, d) = [[P]] (d).
L’esistenza degli interpreti discende immediatamente dalla Tesi di Church.
Dalla combinazione di interpreti e specializzatori è possibile costruire
int spec
una famiglia di programmi assai complessi e utili, quali i compilatori e programmi
che generano compilatori . Per ottenere questi strumenti a supporto della program-
mazione, utilizziamo le proiezioni di Futamura [14]. Esse permettono di costruire
semplici compilatori e programmi che generano compilatori a partire dai concetti
e dall’esistenza di interpreti e specializzatori. Chiaramente, più è sofisticato lo
specializzatore, es. programmi per la ottimizzazione del codice, più è possibile
costruire in questo modo strumenti di compilazione sofisticati ed utili.
8. SPECIALIZZATORI E PROIEZIONI DI FUTAMURA 159
L, S, T
Nei tre risultati sotto riportati assumiamo che e siano linguaggi di
programmazione Turing-completi operanti sul medesimo insieme di dati D. ∈ S
16.22 (I proiezione di Futamura). Dato un programma source
Teorema ∈ T
possiamo generare un programma equivalente .
target
Dimostreremo che tale programma è:
Proof. def L ∈ T
target = [[spec]] (int, source)
L T L
Sia uno specializzatore, scritto in di programmi, ove è un linguag-
spec L S. ∈ T
gio di implementazione, non necessariamente diverso da e Sia ora int
T S-programmi.
un interprete in di Allora:
S T T S
Per Def. di -Interprete per
[[source]] (d) = [[int]] (source, d)
L T Per Def. di Specializzatore
= [[[[spec]] (int, source)]] (d)
T Per Def. di
= [[target]] (d) target
Dunque, dato uno specializzatore assegnandogli come input l’interprete
spec,
S T T
di programmi scritto in e il programma restituisce il programma
source,
desiderato. 16.23 (II proiezione di Futamura). Possiamo generare un compila-
Teorema
S T T
tore da a scritto in . def L
Dimostreremo che: comp = [[spec]] (int, spec, int).
Proof. ∈ T
Sia come stabilito dalla I proiezione. Allora:
target L def. da I proiezione
target = [[spec]] (int, source)
T T L
def. di -interprete per
= [[int]] (spec, int, source)
L T L T
def. di specializzatore in per
= [[[[spec]] (int, spec, int)]] (source)
T
= [[comp]] (source)
Dunque, per generare un compilatore, basta prendere uno specializzatore e
mettere come input il suo codice e quello di un interprete.
Il terzo risultato di Futamura riguarda i generatori di compilatori:
16.24 (III proiezione di Futamura). Possiamo generare un genera-
Teorema T
tore di compilatori scritto in .
Dimostreremo che il generatore di compilatori è:
Proof. def L
compgen = [[spec]] (int, spec, int, spec)
160 16. CALCOLABILITÀ E LINGUAGGI DI PROGRAMMAZIONE
Dalla definizione di specializzatore e dalla II proiezione segue che:
L
comp = [[spec]] (int, spec, int)
T T L
def. di Interprete in per
= [[int]] (spec, int, spec, int)
L T L T
def. di specializzatore in per
= [[[[spec]] (int, spec, int, spec)]] (int)
T
= [[compgen]] (int)
Part 3
Teoria matematica della ricorsione
CHAPTER 17
Insiemi ricorsivi e ricorsivamente enumerabili
Abbiamo visto nel Cap. 10 diverse formalizzazioni per definire ciò che noi rite-
niamo effettivamente calcolabile. Queste comprendono le MdT, le funzioni parziali
ricorsive di Kleene & Robinson, ed i linguaggi di programmazione imperativa, tipo
In questo capitolo studieremo alcuni risultati classici della teoria della ri-
While.
corsività, indipendentemente dal sistema formale adottato per esprimere algoritmi,
o funzioni calcolabili. L’equivalenza tra le diverse definizioni di calcolabilità e la
Tesi di Church-Turing ci permettono di studiare l’effettiva calcolabilità in un modo
per cosı̀ dire “più astratto”. In particolare la Tesi di Church-Turing ci permette di
astrarre dalla particolare MdT o programmi e trattare in modo formale il
while,
concetto (informale) di funzione effettivamente calcolabile, indipendentemente dal
formalismo adottato per rappresentarla. Nel seguito assumeremo di avere fissato
{ϕ }
una data enumerazione delle MdT o delle funzioni parziali ricorsive o dei
i i∈N
programmi Il materiale contenuto in questa parte è tratto in larga parte
While.
dai testi di riferimento [27, 2, 19, 14, 22].
In questo capitolo studieremo le proprietà ricorsive di insiemi di numeri nat-
urali. La scelta di studiare insiemi di numeri naturali non è affatto limitativa per
gli scopi dell’informatica. Tutti i dati manipolabili da un algoritmo sono infatti
numerabili e possono quindi essere messi in corrispondenza biunivoca con l’insieme
Un analogo ragionamento si può applicare ad insiemi di stringhe su di un al-
N.
fabeto, ovvero ad un linguaggio, o ad insiemi di alberi sintattici, rappresentanti
∗
È infatti noto l’isomorfismo tra e rispettivamente e ,
Σ
While-programs. N D A
essendo un dato alfabeto e un dato insieme di atomi . Da questo consegue
Σ A
che studiare proprietà degli elementi di equivale a studiare le proprietà degli
℘(N)
∗ e e che ogni definizione/proprietà che vedremo per in-
elementi di ) ℘(D ),
℘(Σ A
siemi di naturali, si applica senza restrizione alcuna a linguaggi (ovvero elementi di
∗ e a insiemi di alberi sintattici. In questo senso, il passaggio da funzioni ad
℘(Σ ))
insiemi è naturale e rappresenta una astrazione successiva verso una più astratta
definizione di problema ricorsivamente risolvibile. Questo ci permetterà di studi-
are, analogamente a quanto visto per le funzioni calcolabili, insiemi che risultano
essere effettivamente costruibili, ovvero i cui elementi possono essere determinati
in modo algoritmico. 163
164 17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI
⊆
Consideriamo un insieme Ci chiediamo se è costruibile in modo
I I
N.
algoritmico, ovvero se è possibile generare gli elementi di mediante una funzione
I
che sia effettivamente calcolabile. ⊆
17.1. Un insieme è detto ricorsivamente enumerabile
I
Definizione N
(r.e.) se esiste una funzione ricorsiva (parziale o totale) tale che
ψ I = dom(ψ).
⊆
Nel seguito indicheremo con la classe degli insiemi ricorsivamente
RE ℘(N)
∈
enumerabili. Pertanto sse è r.e. Inoltre, nel seguito indicheremo con:
A RE A
• l’insieme r.e. associato al dominio funzione secondo una oppor-
W ϕ
x x ↓
tuna Gödelizzazione, ovvero essendo
W = dom(ϕ ) = y : ϕ (y)
x x x
l’x-esima MdT nella numerazione fissata.
ϕ
x ↓ ∧ϕ
• ∃z
l’insieme ovvero il codominio
E E = y : ϕ (z) (z) = y
x x x x
della stessa funzione parziale.
∈
Sia La funzione parziale:
A RE.
∈
se
1 x A
ψ (x) =
A ↑ 6∈
se x A
è detta funzione semicaratteristica dell’insieme È chiaro che
A. A = dom(ψ ).
A
∈
Inoltre, essendo per ipotesi r.e. , la verifica della condizione è semide-
A x A
↓.
∈
cidibile, ovvero se è tale che , sse Sia dunque
y A = W x A ϕ (x)
y y
def read write un programma equivalente a . È naturale
P = x; C; z ϕ
While
y y
definire il seguente programma: read(x); write(z). Questo programma
C; z := 1;
corrisponde ad una MdT, ed implementa la funzione . Pertanto abbiamo di-
ψ A
mostrato che un insieme è detto r.e. sse ha una funzione semicaratteristica parziale
ricorsiva.
All’interno della famiglia degli insiemi r.e. , esistono insiemi con caratteristiche
più forti. Per questi insiemi vale la condizione aggiuntiva che la loro funzione carat-
teristica (che è sempre una funzione totale) è ricorsiva, ovvero esiste un algoritmo
in grado di decidere l’appartenenza o meno di un elemento all’insieme.
17.2. Un insieme è detto ricorsivo se esiste una funzione
A
Definizione
ricorsiva (totale) tale che:
f
A
∈
se
1 x A
f (x) =
A 6∈
se
0 x A
17.3. I seguenti sono insiemi ricorsivi:
Esempio {0,
• L’insieme dei numeri pari;
2, 4, 6, . . .}
• e
N ∅;
• Ogni insieme finito (Dimostrare per esercizio);
• Ogni insieme tale che è finito (Dimostrare per esercizio).
A Ā
17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI 165
ℵ
Esisteranno dunque insiemi r.e. di cui una parte di uguale cardinalità sarà
0
ricorsiva. Si nota infatti subito della definizioni che
⇒ ∈
ricorsivo
A A RE
Dato insieme ricorsivo, basta infatti definire la funzione parziale e chiaramente
A
ricorsiva:
se
1 f (x) = 1
A
ϕ(x) = ↑ altrimenti
17.4. Dimostrare che i seguenti insiemi sono ricorsivi:
Esercizio
n
• ∈ ∃n∃p primo ;
x : . x = p
N
4 6
• hx, ∈ × ;
yi : x + y = 1238
N N
• ∈ ∃n. .
x : x = 2n + 1
N
17.5 (Teorema di Post). Un insieme è ricorsivo se solo se e
A A
Teorema
sono r.e.
Ā \
⊆
Sia e
A Ā = A.
Proof. N N
(⇒) Sia ricorsivo e la sua funzione caratteristica (totale) ricorsiva. Defini-
A f A
amo:
se
1 f (x) = 1
A
ψ(x) = ↑ altrimenti
È chiaramente una funzione parziale ricorsiva. Ad esempio il seguente frammento
def
di programma implementa Sia read write
ψ: F = x; C ; y.
A A
read
G : x;
C ;
A
while nil do endw;
y = y := y
write y
ha quindi una funzione semicaratteristica parziale ricorsiva. Analogo discorso
A la corrispondente funzione caratteristica.
si applica a essendo = 1 − f
Ā, f A
Ā
Abbiamo pertanto dimostrato che e sono r.e.
A Ā
(←) Supponiamo e r.e. , con funzioni semicaratteristiche e . Defini-
A Ā ψ ψ
A Ā
amo:
↓
se
1 ψ (x)
A
f(x) = ↓
se
0 ψ (x)
Ā
∈ ∈ ∈
È banale osservare che, dato o o allora eseguendo a turno
x x A x Ā,
N:
un’istruzione della MdT che calcola e un’istruzione della MdT che calcola ,
ψ ψ
A Ā
prima o poi una delle due MdT termina, rendendo la funzione totale ricorsiva.
f
166 17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI
Si osservi come la ricorsività di segua anche dal fatto che sia che
=
N N̄ ∅ N
sono r.e.
Il seguente teorema caratterizza gli insiemi r.e. come la famiglia degli insiemi
che possono essere effettivamente enumerati da un algoritmo, ovvero i cui ele-
menti possono essere “listati” in modo effettivo come “output” di un programma.
Gli insiemi r.e. possono dunque essere visti come liste, eventualmente infinite, di
elementi generabili da un algoritmo.
Il teorema di caratterizzazione fa uso di una metodologia effettiva per esplorare
il campo di convergenza di una funzione parziale, ovvero l’insieme degli elementi su
cui una funzione parziale converge (è definita). Questa metodologia per esplorare il
campo di convergenza di una funzione parziale è detta a coda di colomba (dovetail)
e sarà spesso utilizzata nel seguito. In essa ha un ruolo essenziale il concetto di
passo di calcolo o derivazione. Come abbiamo visto nel Cap. 10 ogni sistema
formale introdotto definisce il concetto di calcolo come sequenza discreta di passi
elementari. Pertanto, il procedimento a dovetail è perfettamente accettabile come
metodo algoritmico per esplorare il campo di definizione (o convergenza) di una
funzione parziale ricorsiva.
Sia dunque una funzione parziale ricorsiva. Applicare la tecnica dovetail a
ϕ x
significa costruire l’insieme in modo induttivo, tale che:
ϕ L
x Passo Si faccia un passo di calcolo per e se termina allora
0: ϕ (0), L :=
x
{ϕ (0)};
x
Passo Si faccia un passo nel calcolo di tutte le funzioni
n + 1: ϕ (0), . . . , ϕ (n)
x x
ove il calcolo non sia già terminato al passo precedente, e per ogni tale
m
{ϕ
∪
che converge, si pone
ϕ (m) L := L (m)}.
x x
In pratica si esplora il grafico della funzione seguendo un andamento a zig-zag,
come evidenziato nella figura 1.
L’insieme è stato dunque effettivamente costruito ed i suoi valori corrispon-
L
dono al codominio definito di . Siamo ora in grado di dimostrare il seguente
ϕ x
teorema di Kleene di caratterizzazione degli insiemi r.e.
17.6 (Caratterizzazione degli insiemi r.e. ). Le seguenti affermazioni
Teorema
sono equivalenti:
∈
(1) A RE; ∈ PR:
(2) esiste ϕ A = range(ϕ); ∈
(3) oppure esiste una funzione tale che
A = f R A = range(f).
∅
Consideriamo una data enumerazione delle MdT (o delle funzioni
Proof. {ϕ }
parziali ricorsive) .
x x∈N
⇒ ∈
(1 Sia Per definizione, esisterà parziale ricorsiva t.c.
2) A RE. ϕ A =
x
Definiamo:
dom(ϕ ).
x ↓
se
y ϕ (y)
x
δ(y) = ↑ altrimenti
è parziale ricorsiva e
δ range(δ) = dom(ϕ ) = A.
x
17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI 167
ϕ (0) ϕ (1) ϕ (2) ϕ (3) Argomenti
x x x x
? ? ? ...
◦ ◦ ◦ ◦
Passi ? ?
◦ ◦ ◦
?
◦ ◦
◦ ↓
ϕ (2)
x
?
◦ •
..
. Dovetail: converge dopo 2 passi
ϕ (2)
Figure 1. x
⇒ 6
(2 Sia (anche detto ) e Applicando il dovetail
3) A = range(ϕ ) E A = ∅.
x x
alla funzione:
↓
se
ϕ (y) ϕ (y)
x x
ψ(y) = ↑ altrimenti
6 ∈
poiché esiste tale che all’n -esimo stadio del dovetail
A = range(ϕ ) = n
∅, N
x 0 0
si osserva una terminazione. Definiamo la funzione induttivamente sullo stadio
f
del dovetail, in modo tale che abbia valori tutti e soli nella lista
n-esimo f L
generata dal dovetail di ψ.
{m }
• ≤ ≤ ∈
Se converge in con allora per ogni
ψ , . . . , m 0 j n i [0, j ]:
0 j 0 0 0
0
f(i) = ψ(m );
i
• Supponiamo che per definire si sia usato lo stadio -esimo del
f(j ) n
p p
dovetail. Possiamo avere i seguenti casi:
– Se nell’n passo del dovetail non si rivelano nuove termi-
+ 1-esimo
p
nazioni, allora f(j + 1) = f(j ).
p p {p }
– Se nell’n passo del dovetail converge con input
+1-esimo ψ , . . . , p
p 0 k
≤ ≤ ∈
con allora per ogni
0 k n + 1, i [0, k]: f(j + 1 + i) = ψ(p ).
p p i
• Iteriamo il precedente punto ponendo j = j + 1 + k.
p+1 p
La procedura che abbiamo descritto è effettiva e definisce una funzione ricorsiva
totale tale che
f A = range(f).
⇒ ↑). ↑∈ PR,
(3 Se allora Sappiamo che e
1). A = A = dom(λx. λx.
∅ ∈ R,
quindi è r.e. Se con basta porre:
A A = range(f) f
ϕ(x) = µz.(f(z) − x = 0)
168 17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI
↓ ⇔
∈ PR ∃z.
ed inoltre è immediato osservare che quindi
ϕ ϕ(x) f(z) = x,
che dimostra che è r.e.
A = dom(ϕ) A
17.7. Nel testo di Rogers [27] la definizione di insieme r.e. viene data
Nota
con la caratterizzazione (3) del Teorema appena visto. Tale caratterizzazione
spiega anche il nome “ricorsivamente enumerabile” ovvero enumerabile mediante
l’impiego di una funzione ricorsiva. Nei testi più recenti (p. es., [14, 6]) si adotta
invece la definizione 17.1. Il Teorema sancisce che le due sono del tutto equivalenti.
∈ R
17.8. è r.e. , poiché e
λx. x = range(λx. x).
Esempio N N
17.9. Esiste una funzione totale ricorsiva tale che
f W =
Corollario x
range(ϕ ).
f(x)
È chiaro che non è detto che sia totale, pur essendolo
ϕ f.
f(x)
17.10. Le seguenti affermazioni sono equivalenti:
Teorema
(1) è ricorsivo;
A ∈ R
(2) oppure con non decrescente.
A = A = range(f) f
∅ 6 ⊆
(→). Sia e ricorsivo. Poiché esiste
A = A A a = min(A)
Proof. ∅ N,
minimo valore tra quelli contenuti in Definiamo:
A.
f(0) = a
∈
se
n + 1 n + 1 A
f(n + 1) = altrimenti
f(n)
È chiaro che è totale ricorsiva non decrescente e che
f A = range(f).
(←). Se è finito, allora è banalmente ricorsivo. Supponiamo che
A A A
∈
sia infinito e con totale ricorsiva non decrescente. Sia e
A = range(f) f x A
È chiaro che un tale esiste (perchè?) e che
z = µy. (f(y) > x). z
x x
⇔ {f(0),
∈ ∈
x A x . . . , f(z)}
È quindi decidibile l’appartenenza di ad ovvero è ricorsivo (definire la
x A, A
funzione caratteristica di
A).
17.11. Ogni insieme r.e. infinito ha un sottoinsieme ricorsivo in-
Teorema
finito. ⊆
Sia tale che con funzione ricorsiva totale e
A A = range(f) f
Proof. N
|A| Definiamo la funzione tale che:
= ω. g
g(0) = f(0)
g(n + 1) = f(µy. f(y) > g(n)).
è dunque il più piccolo elemento di più grande di è crescente,
g(n + 1) A g(n). g
⊆
quindi è ricorsivo per il Teorema 17.10. Inoltre poiché
range(g) range(g) A,
⊆
per definizione di
g: range(g) range(f) = A.
17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI 169
17.12. Si dica se i seguenti insiemi sono ricorsivi o r.e. :
Esercizio
(1) con
A = range(f) f(0) = n
0
f(n + 1) = 2f(n).
(2) con
B = range(g) g(0) = n 0
g(n + 1) = h(n)g(n).
essendo una generica funzione ricorsiva (totale).
h
(3) Data una funzione ricorsiva dimostrare che l’immagine inversa di e
f, f
−1
∈ ∈
, con ovvero l’insieme , è r.e.
W x f (W ) = y : f(y) W
N,
x x x
(4) Sia con:
D = range(ψ) ψ(0) = n
0
ψ(n + 1) = ϕ (n)ψ(n).
n
è ricorsivo?
D
Fino a questo momento abbiamo visto insiemi ricorsivi e r.e. Tuttavia non ab-
biamo ancora visto un esempio di un insieme che sia r.e. ma non ricorsivo. Questo
insieme (se esiste) rappresenta l’insieme che discrimina le due classi di insiemi che
abbiamo definito. È chiaro che un insieme di questo tipo deve essere r.e. ma non
ricorsivo, ovvero l’appartenenza ad esso deve essere un predicato semidecidibile.
È naturale chiedersi se questo insieme possa essere in qualche modo correlato alla
non decidibilità della terminazione. Al solito, fissiamo una numerazione delle MdT
{ϕ }
o delle funzioni parziali ricorsive .
x x∈N
↓
17.13. Definiamo .
K = x : ϕ (x)
Definizione x
1
∈
È chiaro per la definizione sopra che .
K = x : x W
x
17.14. è r.e. ma non ricorsivo.
K
Teorema
1 Questo insieme ricorda l’insieme utilizzato per contraddire la teoria classica degli insiemi,
ovvero il Paradosso di Russell [28]. Se infatti fosse possibile definire un insieme del tipo:
6∈ ∈ 6∈
allora otterremmo immediatamente un paradosso poiché sse
M = x : x x M M M M.
L’idea utilizzata per risolvere questo paradosso nella teoria degli insiemi è quella di non ammet-
tere come insieme, ovvero di definire una “disciplina” per la costruzione di insiemi che vieti
M
una costruzione tipo Si osservi come la teoria della ricorsione è immune da questo tipo di
M.
6∈
paradossi. Infatti , l’insieme dei numeri non appartenenti agli insiemi r.e.
K̄ = x : x W
x
da essi generati, non può essere r.e. , altrimenti, essendolo per il Teorema 17.14, sarebbe
K K
ricorsivo (Teorema di Post) il che per il Teorema 17.14 è assurdo. Quindi gli insiemi r.e. non
includono ovvero non esiste tale che
K̄, y K̄ = W
y
0 0
170 17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI
' $
℘(N) K̄
· $
' r.e. K
· $
'
Ricorsivi N
· $
'
Finiti ∅
·
& %
& %
& %
& %
La gerarchia degli insiemi Ricorsivi
Figure 2.
definiamo la funzione tale che:
ψ
Proof. K
↓
se
1 ϕ (x)
x
ψ =
K ↑ altrimenti
è parziale ricorsiva (perchè?) e semicaratteristica di quindi è r.e.
ψ K, K
K Supponiamo ricorsivo. Allora è r.e. Sia tale che . Segue che:
K K̄ y K̄ = W
0 y 0
⇔
∈ ∈
y W = K̄ y K
0 y 0
0
che è chiaramente assurdo.
17.15.
Esercizio
hx, ∈
(1) Dimostrare che è r.e. ma non ricorsivo;
K = yi : x W
2 y
(2) Dimostrare che le seguenti proprietà caratterizzano gli insiemi finiti;
• tutti i sottoinsiemi sono r.e.
• tutti i sottoinsiemi sono ricorsivi ∩
(3) Dimostrare che esistono funzioni ricorsive (totali) e tali che:
f g W
x
∪
e ;
W = W W W = W
y x y
f(x,y) g(x,y)
(4) Dimostrare che è ricorsivo infinito sse esiste una funzione ricorsiva
A f
∀n.
crescente (i.e. tale che
f(n) < f(n + 1)) A = range(f).
Abbiamo quindi la seguente rappresentazione in “classi” di risolvibilità degli
insiemi di numeri naturali. La classe degli insiemi ricorsivi corrisponde alla classe
degli insiemi decidibili , quella degli insiemi r.e. corrisponde alla classe degli insiemi
semidecidibili, mentre gli insiemi non r.e. (che sono la maggior parte di sono
℘(N))
17. INSIEMI RICORSIVI E RICORSIVAMENTE ENUMERABILI 171
gli insiemi per cui non è possibile dare alcun metodo effettivo per verificare sia
l’appartenenza che la non appartenenza di un elemento a questi insiemi. Valgono
quindi le seguenti inclusioni, mostrate anche in Figura 2, tra le varie classi di
insiemi viste fino ad ora: ⊂ ⊂
ricorsivi r.e. tutti
CHAPTER 18
I Teoremi di Ricorsione
I teoremi di ricorsione, detti anche di punto fisso, sono tra i risultati più
importanti che si incontrano nello studio della teoria della calcolabilità. In questo
capitolo studieremo i teoremi di ricorsione e le loro conseguenze nello studio di
proprietà di programmi.
1. Il primo teorema di ricorsione ∈ R
18.1 (Teorema di ricorsione di Kleene). Sia una funzione
t
Teorema ∈
ricorsiva (totale). Allora esiste tale che .
n ϕ = ϕ
N n t(n)
Sia l’indice di una generica MdT . Definiamo la seguente fun-
u ϕ
Proof. u
zione parziale:
↓
se
ϕ (x) ϕ (u)
u
ϕ (u)
u
ψ(u, x) = ↑ altrimenti
È chiaro che la funzione cosı̀ definita è parziale ricorsiva (si descriva a parole una
MdT che “calcola” Quindi, per il Teorema s-m-n, esiste una funzione ricorsiva
ψ).
(totale) tale che: Sia ora una funzione ricorsiva (totale).
g ψ(u, x) = ϕ (x). t
g(u) ◦
Poiché la composizione di funzioni ricorsive è ricorsiva, è ricorsiva. Quindi
t g
◦ ◦
per qualche Pertanto Vista la genericità di
t g = ϕ v. (t g)(v) = ϕ (v). u,
v v
sostituendo con nella definizione di otteniamo:
u v ψ(u, x)
↓
se
ϕ (x) ϕ (v)
v
t(g(v))
ψ(v, x) = ϕ (x) =
g(v) ↑ altrimenti
↓
◦
Poiché è totale, sempre e dunque Posto
t g ϕ (ν) ϕ (x) = ϕ (x).
ν g(v) t(g(v))
quindi abbiamo che .
n = g(v), ϕ = ϕ
n t(n)
Il significato intuitivo del teorema di ricorsione di Kleene sarà più chiaro in
seguito, in particolare nella Sezione 4. Per ora ci basti utilizzarlo come potente
metodo per dimostrare proprietà di ricorsività sugli elementi di Vediamo
℘(N).
qualche esempio: {n}?
∈
18.2. Esiste un t.c. Utilizziamo il
n E = range(ϕ ) =
Esempio N n n
Teorema di Ricorsione per stabilire ciò. Sia è calcolabile e totale.
g(x, y) = x. g
173
174 18. I TEOREMI DI RICORSIONE
Per il Teorema s-m-n avremo che esiste ricorsiva tale che per ogni
h y:
ϕ (y) = g(x, y)
h(x)
{x}.
Per definizione, Per il Teorema di ricorsione, si ha che esiste
range(ϕ ) =
h(x) {n}.
∈ t.c. Pertanto
n ϕ (y) = ϕ (y). range(ϕ ) = range(ϕ ) =
N n n
h(n) h(n)
{n}?
∈
18.3. Esiste un t.c. Sia definita come:
n W = g(x, y)
Esempio N n
0 y = x
g(x, y) = ↑ altrimenti
è calcolabile. Per il Teorema s-m-n avremo che esiste ricorsiva tale che
g h
per ogni y: ϕ (y) = g(x, y)
h(x)
{x}. ∈
Per definizione, Per il Teorema di ricorsione, si ha che esiste
W = n N
h(x) {n}.
t.c. Pertanto
ϕ (y) = ϕ (y). W = W =
n n
h(n) h(n)
18.4. Sia, per l’i-esimo numero primo (p
i > 0, p = 2, p =
Esercizio i 1 2
{p }
). Si dimostri che esiste un indice tale che e
3, . . . u W = , p , . . . , p
u 1 2 (u!)
{1,
E = 2, . . . , u}.
u ∈
18.5. Si mostri che esiste tale che:
ν
Esercizio N
y ≤
2 y ν
ϕ (y) =
ν 5 y>ν
18.6. Si pensi all’enunciato (e alla dimostrazione) dell’equivalente
Esercizio
del teorema di ricorsione nella While-calcolabilità.
2. Il secondo Teorema di ricorsione
In questo paragrafo enunceremo il secondo teorema di ricorsione che estende il
risultato del primo. Utilizzeremo questo teorema per la dimostrazione del teorema
di Myhill nel Capitolo 19. 2 −→ ∈ R
18.7. Sia una funzione ricorsiva (totale). Allora
f :
Teorema N N
−→ ∈ R
esiste una funzione ricorsiva totale tale che:
ν : N N
∀y ∈ : ϕ = ϕ .
N f(ν(y),y) ν(y)
Definiamo la seguente funzione parziale:
Proof.
↓
se
ϕ (z) ϕ (x)
x
f(ϕ (x),y)
x
ψ(x, y, z) = ↑ altrimenti
Per il Teorema s-m-n applicato ai primi due argomenti, esiste una funzione calco-
↓,
labile totale tale che Si noti che, se allora
s ψ(x, y, z) = ϕ (z) . ϕ (x)
x
s(x,y)
(2.1) ϕ = ϕ
s(x,y) f(ϕ (x),y)
x
3. IL TEOREMA DI RICE 175
Per il Teorema s-m-n applicato al secondo argomento di sappiamo che esiste
s
una funzione calcolabile totale tale che:
t
(2.2) s(x, y) = ϕ (x)
t(y)
Definiamo la funzione def
ν(y) = ϕ (t(y))
t(y)
Poiché sia che sono ricorsive e totali, lo sarà anche Dunque:
t ϕ ν.
t(y) Def di
ϕ = ϕ ν
ν(y) ϕ (t(y))
t(y) (2.2), con
= ϕ x = t(y)
s(t(y),y) ↓
Poiché e (2.1)
= ϕ ϕ (t(y))
f(ϕ (t(y)),y) t(y)
t(y) Def di
= ϕ ν
f(ν(y),y)
3. Il Teorema di Rice
Uno dei risultati più importanti dimostrabili mediante il primo teorema di
ricorsione è il Teorema di Rice. Esso afferma che ogni proprietà non banale che
rappresenti ciò che viene calcolato dalle MdT (o dai programmi, vedi Sezione 4)
non è ricorsiva. Definiamo innanzitutto cosa si intende per proprietà sulle MdT.
{ϕ }
Sia al solito una enumerazione delle MdT.
i i∈N
18.8. Una proprietà sulle MdT è un qualsiasi sottoinsieme di
Definizione
{ϕ } . Con abuso di notazione, intenderemo con proprietà qualsiasi sottoinsieme
i i∈N
di intendendo l’insieme costiuito da indici di MdT.
N,
Una proprietà sulle MdT è pertanto univocamente identificata dall’insieme
degli indici delle MdT in essa contenuti. Nel seguito quindi non faremo distinzione
tra proprietà intesa come insieme di indici (e quindi di numeri) di MdT o pro-
prietà intesa come insieme di MdT. Nel primo caso, ovviamente potremo parlare
di proprietà ricorsive (o decidibili), r.e. (o semidecidibili), e proprietà non r.e.
⊆
18.9. Sia dunque una proprietà sulle MdT, è
Π Π Π
Definizione N.
∈
estensionale (o chiusa per eguaglianza estensionale) se per ogni x, y N:
∧ →
∈ ∈
(x )
Π ϕ = ϕ y Π
x y
Intuitivamente, una proprietà è estensionale quando questa “parla” di cosa
calcolano le MdT in essa contenute, e non di come queste macchine sono “fatte”.
Il seguente risultato sancisce l’esistenza di un numero arbitrario di MdT tra loro
equivalenti. ∧
∀i, ∃j
18.10 (Tecnica del Padding). k. : (ϕ = ϕ j > k).
Lemma j i
176 18. I TEOREMI DI RICORSIONE
Siano dati e e sia l’i-esima MdT. Se allora ponendo
i k ϕ i > k j = i
Proof. i
≤
si ha la tesi. Se allora è sufficiente aggiungere a un numero congruo di
i k ϕ i
quintuple (con stati mai raggiungibili dal calcolo) in modo tale che si ottenga ϕ j
con
j > k. 18.11. Si dimostri una proprietà analoga per i programmi
Esercizio While.
Mediante la tecnica del padding si osserva che esistono infinite MdT equivalenti
ad una MdT data. Pertanto, una proprietà estensionale sulle MdT non può che
essere un insieme infinito.
18.12. Si dimostri che le seguenti proprietà sono estensionali:
Esercizio
• e In particolare, tali proprietà sono dette banali ;
∅ N. ∧
• ⊆ PR, ∈
Dato ;
F i : ϕ = ψ ψ F
i
• ;
i : ϕ = λx. x
i
• ≥
è definitivamente .
i : ϕ 3
i {157}
Al contrario, la proprietà che include solo la MdT di indice non è
157
estensionale. Infatti esistono infinite MdT equivalenti ad una data MdT (Lemma
{157}
18.10), e pertanto l’insieme non può essere estensionale.
18.13 (Teorema di Rice). Sia una proprietà estensionale. è
Π Π
Teorema
ricorsiva sse è banale (ovvero oppure
Π = Π =
∅ N).
La direzione (←) segue per definizione.
Proof.
(→) Sia ricorsivo e la sua funzione caratteristica:
Π g
∈
se
1 x Π
g(x) = 6∈
se
0 x Π ∈
Supponiamo per assurdo che non sia banale. Allora esistono tali che
Π a, b N
∈ 6∈
e Definiamo la funzione
a Π b Π.
se
b g(x) = 1
h(x) = se
a g(x) = 0
Essendo ricorsiva per ipotesi, chiaramente è ricorsiva (e totale). Per il Teorema
g h
di ricorsione di Kleene, esiste tale che . Da questo fatto deriviamo
n ϕ = ϕ
0 n h(n )
0 0
l’assurdo:
• ∈ ∈
Se allora essendo estensionale, ma questo è assurdo
n Π Π h(n ) Π,
0 0
6∈
poiché e
h(n ) = b b Π.
0
• 6∈ 6∈
Se allora essendo estensionale, ma questo è assurdo
n Π Π h(n ) Π,
0 0
∈
poiché e
h(n ) = a a Π.
0
Quindi non può essere ricorsivo e non banale.
Π 3. IL TEOREMA DI RICE 177
Il Teorema di Rice dunque afferma che ogni funzione parziale ricorsiva o MdT
ammette un insieme infinito non ricorsivo di indici di funzioni o macchine equiv-
alenti. In particolare osserviamo che i seguenti problemi, di chiaro interesse infor-
matico, non sono decidibili in seguito al Teorema di Rice.
∈ PR,
18.14. Data ed una MdT non è in generale decidibile
ψ M,
Esempio
se “calcola” Infatti se è l’indice della MdT allora questo problema
M ψ. j M,
∈
equivale a decidere se che è una proprietà estensionale non
j i : ϕ = ψ
i
6
banale ( poiché esiste una MdT che calcola la funzione parziale
i : ϕ = ψ = ∅
i ∈ PR 6
ricorsiva essendo e poiché non tutte le MdT
ψ ψ i : ϕ = ψ = N
i
calcolano la stessa funzione) delle MdT, e quindi per il Teorema di Rice è una
proprietà non ricorsiva.
18.15. Date e , non è decidibile se esse sono equivalenti
M M
Esempio 1 2
(ovvero calcolano la stessa funzione). Dimostrare questo per esercizio applicando
il teorema di Rice.
È necessario fare molta attenzione ad utilizzare il Teorema di Rice. Esso
infatti ha come ipotesi il fatto che l’insieme di cui si vuole studiare la ricorsività
sia estensionale. Alcuni insiemi possono trarre in inganno, come nel seguente
esempio. 18.16. Il seguente esempio, ideato da G. Longo [19], non può essere
Esempio
risolto invocando il Teorema di Rice. Definiamo una nozione debole di equivalenza
tra MdT (o programmi) come segue:
∼ ⇔ ↓ ∧ϕ ↓ ⇒
ϕ ϕ (∀x. (ϕ (x) (x) ϕ (x) = ϕ (x)))
i j i j i j
∼
Ci chiediamo se l’insieme con è ricorsivo.
D = range(ψ) ψ(i) = µj. (ϕ ϕ )
i j
↑
Si osservi che la funzione sempre indefinita è debolmente equivalente
λx. ∼
∈
ad ogni altra funzione parziale ricorsiva, ovvero, per ogni con
i ϕ ϕ
N: i u
{ϕ }
indice della più piccola MdT nella numerazione delle MdT , tale che
u n n∈N
↑. {0,
⊆
Quindi, è un insieme finito e quindi ricorsivo.
ϕ = λx. D . . . , u}
u Tuttavia interpretando erroneamente la proprietà come estensionale, l’utilizzo
del Teorema di Rice porterebbe ad affermare che non è ricorsivo. L’insieme
D D
⇒ ∼, ∈
non caratterizza una proprietà estensionale: infatti, se e
= i D ϕ = ϕ
k i
6∈
con (k è facilmente ottenibile con la tecnica del Padding), allora
k > i k D
(dimostrare per esercizio).
18.17.
Esercizio ⊆
(1) Dire (giustificando formalmente) per quali il seguente insieme
A
N
è ricorsivo.
i : W = A
i ↑
∀x.
(2) Dire (giustificando formalmente) se è ricorsivo, r.e. o
i : ϕ (x)
i
non r.e. ≥
(3) Dimostrare che è definitivamente è non ricorsivo.
i : ϕ 3
i
∃x.
(4) Dimostrare che è non ricorsivo.
i : ϕ (x) = x
i
178 18. I TEOREMI DI RICORSIONE
Il Teorema di Rice è assai disarmante di fronte a proprietà estensionali che
riguardano MdT (quindi programmi). Di fatto, ogni proprietà non banale che
tratti ciò che calcolano le MdT è non ricorsiva (non decidibile). Tuttavia, è possi-
bile rappresentare alcune proprietà estensionali non ricorsive (ma r.e. ) in modo
decidibile, ricorrendo a proprietà su MdT non estensionali decidibili.
⊆ ⊆
18.18. Sia una proprietà. è una rappresentazione
Π A
Definizione N N
∈ ∈ ∈
di se per ogni esiste tale che e, viceversa, per ogni
Π i Π j A ϕ = ϕ j A
i j
∈
esiste tale che .
ϕ Π ϕ = ϕ
i i j
⊆
Ogni insieme può essere esteso in modo estensionale ad una proprietà
A
N
⊆ ∃j ∈
tale che e rappresenta Basta definire
Π(A) A Π(A) A Π(A). Π(A) = i :
.
A. ϕ = ϕ
i j 18.19. Sia un insieme r.e. Allora esiste una rappresentazione
A
Teorema
ricorsiva della proprietà
B Π(A).
Se allora basta porre è chiaramente una rappre-
A = B = A = B
Proof. ∅ ∅. 6
sentazione ricorsiva di Supponiamo che Per il Teorema 17.6, es-
Π(A) = A =
∅. ∅. {f(0), }.
iste una funzione ricorsiva (totale) tale che
f A = range(f) = f(1), f(2), . . .
Definiamo tale che:
g g(0) = f(0) dove e
g(n + 1) = j ϕ = ϕ j > g(n)
n j n
f(n+1)
n
Mostriamo che è ben definita: per il Lemma del Padding cosı̀ costruito esiste
g j n
sempre, basta porre e nel Lemma del Padding. è inoltre
i = f(n + 1) k = g(n) g
crescente e ricorsiva. Quindi per il Teorema 17.10 è ricorsivo.
B = range(g)
Inoltre, è chiaro che è una rappresentazione per (segue banalmente per
B Π(A)
costruzione, verificare per esercizio).
Ad esempio, si consideri l’insieme dei programmi che calcolano la somma
A
di numeri interi per E’ estenzionale e r.e. (dunque Una
x, y < 1000. A = Π(A)).
sua rappresentazione ricorsiva esiste per il Teorema (18.19).
18.20. Si mostri che esiste una rappresentazione ricorsiva della
Esercizio
proprietà per i seguenti insiemi:
Π(A)
{i }
∈
(1) A = : 2 W
i
{i
(2) A = : ϕ (2) = ϕ (4)}
i 2·i
{i }
∃j ≤ ∈
(3) A = : i.j W
i
{i {1900, }
∀j ∈ ∈
(4) A = : . . . , 2100} : j W
i
⊆
Con la notazione si intende la vera inclusione tra le funzioni viste
ϕ ϕ
j i
come relazioni. In termini operazionali,
↓−→ ↓ ∧ϕ
∀x (ϕ (x) ϕ (x) = ϕ (x)).
j i j i
Una ulteriore importante caratterizzazione di proprietà r.e. o delle rappresen-
tazioni è dato dal seguente Teorema:
3. IL TEOREMA DI RICE 179
18.21 (Rice e Shapiro). Sia una proprietà estensionale. Se è
Π Π
Teorema ∈
r.e. allora per ogni i N ∧
∈ ∃j ∈ ⊆
sse è finito
i Π Π.ϕ ϕ W (Φ)
j i j
Assumiamo estensionale e r.e. Dimostriamo, un verso alla volta, il
Π
Proof.
se e solo se.
∈ ∈
Sia Se è finito, si prenda Supponiamo che è
(→) i Π. W j = i. i Π, W
i i
∈ ⊆
infinito, ma ogni qual volta e è finito. Sia la funzione definita
j / Π ϕ ϕ W g
j i j
come segue:
≤
se non termina in passi
ϕ (t) M (z) t
i z
g(z, t) = ↑ altrimenti
Per il Teorema s-m-n esiste ricorsiva tale che: Si osservi che
s g(z, t) = ϕ (t).
s(z)
⊆ per definizione. Ora:
ϕ ϕ i
s(z) • ∈ ⊆ ∈
implica che è finito e . Per ipotesi,
z K W ϕ ϕ s(z) / Π.
i
s(z) s(z)
• ∈ ∈
implica che . Pertanto
z / K ϕ = ϕ s(z) Π.
i
s(z)
Dunque saper decidere l’appartenenza a implicherebbe saper decidere l’appartenenza
Π
a che sappiamo non essere r.e.: assurdo.
K̄ ∈ ∃j.ϕ ⊆
Supponiamo per assurdo che esista tale che: e inoltre
(←) i ϕ
N j i
∈ ∈
è finito, e Sia definita come segue:
W j Π, i / Π. g
j
∈ ∈
se oppure
ϕ (t) t W z K
i j
g(z, t) = ↑ altrimenti
∈ R
Per il Teorema s-m-n esiste tale che Abbiamo che:
s g(z, t) = ϕ (t).
s(z)
• ∈ implica che . Per l’ipotesi su e l’estensionalità di
z K ϕ = ϕ i, Π,
i
s(z)
∈
s(z) / Π. | 1
• ∈ implica che . Dunque è estensionalmente
z / K ϕ = ϕ s(z)
W i
s(z) j ∈
equivalente a e pertanto
ϕ s(z) Π.
j
Anche in questo caso l’appartenenza a implicherebbe l’appartenenza a che
Π K̄
sappiamo non essere r.e.: assurdo.
∈
Il teorema di Rice e Shapiro mostra se r.e. allora per ogni vale la
Π i N
proprietà dell’enunciato. Pertanto può essere utilizzato per mostrare che un
Φ ∈
insieme non è r.e. (basta trovare un per cui è falso).
i Φ
N
18.22. Si mostri che i seguenti insiemi non sono r.e.:
Esercizio
{i
(1) : W = N}
i
{i }
(2) è infinito
: W
i
{i →
∀x ∈ ∈
(3) è pari
: x W )}
N(x i ↑.
1 ∀t ∈ ∀t ∈
Ovvero e
W ϕ (t) = ϕ (t) / W ϕ (t)
j i j i
s(z)
180 18. I TEOREMI DI RICORSIONE
18.23. Si trovi un insieme non r.e. per cui la proprietà dell’enunciato
Φ
Esercizio ∈
del teorema di Rice e Shapiro vale per ogni L’esistenza di tale insieme cosa
i N.
dimostra? 4. Proprietà di programmi
Il Teorema di Rice fornisce un importante risultato per comprendere i limiti
dei sistemi automatici per dimostrare o verificare proprietà di programmi. Con-
L.
sideriamo un linguaggio di programmazione Turing-completo è una proprietà
π
L ⊆ L,
dei programmi di se ovvero è l’insieme dei programmi che verificano
π π
la proprietà. Possiamo distinguere tra proprietà sintattiche e semantiche dei pro-
grammi. Le prime riguardano come i programmi sono scritti, mentre le seconde
riguardano il comportamento. Esempi di proprietà di programmi sono:
∈ L ∀x ∈ termina proprietà semantica
P : P(x)
D.
∈ L contiene un ciclo while proprietà sintattica
P : P
|P|
∈ L proprietà sintattica
P : < 1000
∈ L è un programma sicuro proprietà semantica
P : P
È evidente che le proprietà dei programmi di maggior interesse sono quelle seman-
tiche, ovvero quelle che riguardano il comportamento dei programmi, ovvero ciò
che questi fanno/calcolano.
Il concetto di proprietà estensionale caratterizza le proprietà semantiche dei
⊆ L ∈ L:
programmi. Una proprietà è estensionale se per ogni
π P, G
∧ ⇒
L L
∈ ∈
P π [[P]] = [[Q]] Q π
⊆ L
Data una proprietà è sempre possibile estendere alla più piccola proprietà
π π
∈ L
estensionale che contiene Sia un programma. Definiamo:
π. P
def L L
∈ L
P = Q : [[P]] = [[Q]]
def S
È chiaro che è la più piccola proprietà estensionale che contiene
π = P
P∈π
Una proprietà è estensionale sse . È importante osservare che, per il
π. π π = π
Lemma del Padding, una proprietà estensionale non vuota è infinita.
Il Teorema di Rice afferma dunque che una proprietà estensionale non vuota
di programmi, ovvero in grado di caratterizzare almeno un programma, è ricor-
L.
siva, ovvero decidibile, se e solo se questa è banale, ovvero La proprietà
π =
L corrisponde ad affermare che un programma è un programma. Solo quindi
π =
questa banale affermazione sui programmi è decidibile, ovvero esiste un algoritmo
(programma) in grado di verificarla automaticamente.
Diamo di seguito una dimostrazione alternativa del Teorema di Rice per le
proprietà del linguaggio Questa dimostrazione mette in luce il legame
While.
diretto tra il problema della terminazione e la decidibilità di proprietà estensionali.
4. PROPRIETÀ DI PROGRAMMI 181
6 L
Supponiamo che sia estensionale (π ) non banale (π e
π = π =
Proof.
6 e decidibile. Dimostriamo che questo implicherebbe la decidibilità del
π = ∅)
problema della terminazione.
Consideriamo il programma sempre divergente:
W
read(x); while do endw; write(y)
(nil.nil) x := x
↑.
∈ ∈
È chiaro che per ogni Supponiamo che Poiché è non
d [[W]](d) W π. π
D,
6 L), ∈ L ∈
banale (π esiste un programma tale che
= R R / π:
read(h); write(k)
C ;
R
Consideriamo un generico programma P:
read(x); write(y)
C ;
P
∈
e sia Possiamo assumere che i programmi ed non condividano variabili.
e P R
D.
Costruiamo il seguente programma Q:
read(x); [memorizzo l’input in
h := x; x h]
[ResP
x := e; C ; ResP := y; := [[P]](e)]
P [ResR
C ; ResR := k; := [[R]](x)]
R
write(ResR)
↑ ↑. ↓
∀d ∈ ∀d ∈
Se allora Se allora
[[P]](e) [[Q]](d) [[P]](e) [[Q]](d) = [[R]](d).
D. D.
Pertanto abbiamo che:
↑
• ∈
Se allora che per estensionalità di e poiché
[[P]](e) [[Q]] = [[W]] π W π
∈
implica che Q π.
↓
• 6∈
Se allora che per estensionalità di e poiché
[[P]](e) [[Q]] = [[R]] π R π
6∈
implica che Q π. ↓ ∈
Pertanto, avremo che se e solo se la decidibilità di implicherebbe
[[P]](e) Q π: π
la decidibilità della terminazione di Vista la genericità di e dell’argomento
[[P]](e). P
∈ avremmo dimostrato la decidibilità della terminazione per un linguaggio
e D,
Turing-completo, il che è assurdo. 6∈
Un assurdo analogo si dimostra se [completare per esercizio].
W π
L’indecidibilità delle proprietà estensionali deriva quindi direttamente dalla
indecidibilità della terminazione. È importante osservare che questa indecidibilità
non deriva necessariamente da complicati programmi di raro interesse pratico. La
terminazione del seguente semplice programma, ad esempio, costituisce da anni
un enigma per gli scienziati, enigma che a tutt’oggi non risulta essere stato risolto
182 18. I TEOREMI DI RICORSIONE
(utilizziamo un linguaggio esteso con semplici operazioni aritmetiche e con
While
l’istruzione if-then-else): ≥
while do
(n 2)
n mod 2 = 0 n := n div 2
if then
n := 3n + 1
else
endw
L’impatto del Teorema di Rice sullo sviluppo di strumenti automatici di verifica
non è tuttavia cosı̀ drammatico. Lo sviluppo crescente di software di grandi dimen-
sioni (dell’ordine di 10Mlinee) rende impossibile la verifica manuale di importanti
proprietà quali la correttezza, la sicurezza, l’assenza di guasti, la fault-tolerance,
etc. Queste proprietà, tutte chiaramente estensionali, risultano di vitale interesse
per l’utilizzo del software in ambienti safety-critical, quali i sistemi di controllo del
traffico aereo, delle transazioni bancarie, di centrali per la produzione di energia.
Risulta quindi necessario sviluppare strumenti automatici (programmi) che anal-
izzano altri programmi. Il Teorema di Rice, pur imponenedo severe limitazioni
a ciò che è effettivamente possibile dimostrare sui programmi mediante i pro-
grammi stessi (eventualmente definiti in linguaggi diversi), non deve scoraggiare
la ricerca di strumenti e metodi per verificare proprietà di programmi. Mentre
infatti questo risultato impedisce definitivamente la realizzazione di algoritmi di
verifica automatica per tutti i programmi, esso non impedisce che strumenti di
verifica automatica siano realizzabili per classi significative di programmi, ovvero
che per alcune classi di programmi, proprietà estensionali significative siano de-
cidibili. Il Teorema di Rice stabilisce che non esiste una soluzione universale in
grado di verificare in tempo finito se un generico programma soddisfa o meno una
data proprietà estensionale. Tuttavia esistono potenti strumenti e metodi di anal-
isi statica ovvero a tempo di compilazione, quindi decidibili, per verificare ampie
classi di programmi significativi. Questo ambito di studio è competenza dell’area
dei metodi formali e costituisce uno degli ambiti di ricerca sia teorica che applicata
più attivi in questi anni. CHAPTER 19
Riducibilità funzionale e gradi di risolvibilità
L’inclusione insiemistica, intesa come relazione tra insiemi, non dà nessuna
informazione circa la ricorsività di un insieme. In particolare, il fatto che un
insieme sia contenuto in un dato insieme ricorsivo non implica in alcun modo la
ricorsività del primo: la ricorsività di non implica la ricorsività di ogni suo
N
⊂ ⊂
sottoinsieme (e.g. né la ricorsiva enumerabilità (e.g. In questa
K K̄
N), N).
sezione studieremo il concetto di riducibilità funzionale. Questo concetto permette
di correlare tra loro insiemi in modo tale che la ricorsività (o la non ricorsività) di
un insieme possa essere propagata agli insiemi ad esso correlati mediante riduzione
funzionale.
hx, ∈ hx,
Consideriamo l’insieme . Con si intende in
K = yi : y W yi
2 x
questo contesto una possibile codifica delle coppie di naturali in numero naturale
x y
·
(ad esempio ). In questo modo ci occupiamo solo di relazioni tra insiemi di
2 3
numeri naturali e non di insiemi di tuple generiche di numeri naturali.
19.1. è r.e.
K
Lemma 2 ↓,
hx,
Si definisca nel modo seguente: se e
g g(z) = 1 z = yi ϕ (y)
Proof. x
indefinita altrimenti. è la funzione semicaratteristica di ed è chiaramente
g K 2
calcolabile.
ha una struttura molto simile a che sappiamo essere un insieme non
K K,
2
ricorsivo. Ci chiediamo se anche sia non ricorsivo. Si osservi che rappresenta
K K
2 2
una generalizzazione di K: ∈ hx, ∈
sse
x K xi K 2
Pertanto, se fosse ricorsivo, avremmo un modo per decidere l’appartenenza
K 2
a (ovvero sarebbe ricorsivo) che sappiamo essere assurdo. In altri termini,
K K
l’esistenza di una funzione totale e calcolabile tale che
f
∈ ∈
sse
x K f(x) K 2
ci ha permesso di dire qualcosa (di negativo) su .
K 2
Quello che abbiamo visto è un metodo per ridurre la decidibilità dell’appartenenza
ad un insieme alla decidibilità del’appartenenza ad un altro insieme. Questo es-
empio conduce alla seguente definizione.
183
184 19. RIDUCIBILITÀ FUNZIONALE E GRADI DI RISOLVIBILITÀ
⊆
19.2. Siano è (funzionalmente) riducibile a
A, B A B
Definizione N.
∈
(A se esiste una funzione (totale) ricorsiva tale che per ogni
B) f x N:
⇔
∈ ∈
x A f(x) B
Nel caso con funzione ricorsiva diremo che si riduce a via
A B f, A B
L’ordine fa pensare che non è più difficile di La relazione è
f. A B A B.
denominata (many-one reducibility) nel testo di Rogers [27].
< m
1. La relazione di riducibilità
In questo paragrafo vedremo alcuni esempi e proprietà della nozione di riducibilità
funzionale. {x
19.3. Sia Mostriamo che . Sia se
T = : ϕ = 0}. K T f(x, y) = 0
Esempio x
↓, indefinita altrimenti. è calcolabile e per s-m-n esiste totale ricorsiva
ϕ (x) f g
x ∈ ∈
tale che Si osserva che se e solo se .
ϕ (y) = f(x, y). x K g(x) T
g(x) ⊆ ×
19.4. La relazione è riflessiva e transitiva.
℘(N) ℘(N)
Lemma
Esercizio.
↓
19.5. Si considerino i due insiemi e
K = x : ϕ (x) A = x :
Esempio x
. E’ evidente che i due insiemi non sono uguali (esercizio: perché?).
ϕ (0) = 0
x
Tuttavia, mostreremo che e Ciò implica che è un preordine, ma
K A A K.
non una relazione ordine. Sia
∈
0 x K
ψ(x, y) = ↑ altrimenti
è parziale ricorsiva e calcolabile. Per il Teorema s-m-n esiste ricorsiva totale
ψ g
∈
tale che per ogni fissato x N:
∀y ∈ (ψ(x, y) = ϕ (y))
N g(x)
∈ ∈
Supponiamo allora dunque
x K, ϕ (0) = 0, g(x) A.
g(x)
↑,
∈ ∈
Sia ora Allora dunque
x / K. ϕ (0) g(x) / A.
g(x)
Pertanto, K A.
Sia ora: 0 ϕ (0) = 0
x
η(x, y) = ↑ altrimenti
è parziale ricorsiva e calcolabile. Per il Teorema s-m-n esiste ricorsiva totale
η h
∈
tale che per ogni fissato x N:
∀y ∈ (η(x, y) = ϕ (y)).
N h(x)
∈ ∈
Supponiamo allora dunque
x A, ϕ (h(x)) = 0, h(x) K.
h(x) ↑,
∈ ∈
Sia ora Allora dunque
x / A. ϕ (h(x)) h(x) / K.
h(x)
Pertanto, A K.
1. LA RELAZIONE DI RIDUCIBILITÀ 185
non r.e.
K
r.e.
S
\ {∅,
∈ R
X N}
∅ N
Diagramma della relazione
Figure 1. ≡
Per il Lemma 19.4, possiamo definire una relazione di equivalenza tra insiemi
≡
di numeri, in modo tale che sse e Denoteremo con la
A B A B B A. [A]
≡
⊆ ≡
classe di equivalenza di ovvero l’insieme .
A, B : A B
N
In questa relazione l’insieme vuoto e l’insieme giocano un ruolo particolare
∅ N
e forse inatteso: 6
19.6. (1) Sia un insieme. se e solo se
A A A =
Lemma N ∅.
6
(2) Sia un insieme. se e solo se
A A A =
∅ N. ↔
6 ∈ ∈
(1) Sia sia e sia Si osservi che
A = a A f = λx.a. x
Proof. ∅, N
∈
f(x) A. →
∈ ∈
Viceversa, per assurdo Allora esisterebbe tale che
f x f(x)
N ∅. N ∅.
∈
Ma questo è assurdo in quanto, ad esempio ma non appartiene a
0 f(0)
N, ∅.
\
⊂ ∈
(2) Mostriamo che se allora Sia e sia
A A. b A g = λx.b.
N, ∅ N
↔
∈ ∈
Dobbiamo mostrare che Poiché nessun appartiene a devo
x g(x) A. x
∅ ∅
∈ ∈ ∈
solo mostrare che per (ovvero vale che: Ciò è immediato
x / x g(x) / A.
∅ N)
per la definizione di g.
Viceversa, supponiamo per assurdo che Allora esisterebbe tale che
g
∅ N.
→
∈ ∈ ∈
Dunque dovrebbe valere in particolare per e
x g(x) x = 0: 0 /
∅ N. ∅
∈ ∈
Ma è totale e dunque Assurdo.
g(0) / g g(0)
N. N.
Pertanto e sono degli insiemi minimali rispetto alla relazione ma tra loro
∅ N
incomparabili (si veda Figura 1—l’insieme sarà illustrato nel Teorema 19.26).
S
Vediamo alcune proprietà fondamentali della nozione di riduzione funzionale.
⊆
19.7. Sia A, B
Teorema N.
⇒
(1) A B Ā B̄;
186 19. RIDUCIBILITÀ FUNZIONALE E GRADI DI RISOLVIBILITÀ
⇒
∈ ∈
(2) e
A B B RE A RE.
⇒
(3) e ricorsivo ricorsivo.
A B B A ∈
Il primo punto è banale. Dimostriamo che se e allora
A B B RE
Proof.
∈ Sia la funzione semicaratteristica parziale ricorsiva di e supponiamo
A RE. ψ B
B
che via Consideriamo la funzione parziale ricorsiva definita come:
A B f. ψ A
Allora abbiamo che
ψ (x) = ψ (f(x)).
A B
∈
se
1 f(x) B
ψ =
A ↑ 6∈
se f(x) B
∈ ∈
Poiché sse è la funzione semicaratteristica di e quindi
x A f(x) B, ψ A,
A
∈ Il terzo punto ha una dimostrazione del tutto analoga al secondo punto,
A RE.
considerando la funzione caratteristica di
B.
Abbiamo quindi dimostrato che la proprietà di essere ricorsivo o ricorsivamente
enumerabile si propaga verso il basso secondo l’ordinamento tra insiemi. Il
seguente lemma evidenzia una importante classe di insiemi equivalenti. Si osservi
∈ ∈
inoltre che il punto (2) del lemma dice anche che se e allora
A / RE A B, B / RE.
6 6
19.8. ricorsivo e e implica
B A = A = B A.
Lemma ∅ N
\
∈ ∈
Sia e e sia la funzione caratteristica di
a A b A ψ B.
Proof. N B
Definisco
a ψ (x) = 1
B
g(x) = b ψ (x) = 0
B
∈ ∈
è ricorsiva e totale e vale che se e solo se
g x B g(x) A.
Come corollario, tutti gli insiemi ricorsivi diversi da e da (insiemi ricorsivi
∅ N
-equivalenti.
non banali) sono tra loro
Analizziamo ora gli insiemi r.e.
∈
19.9. Per ogni .
A RE, A K
Teorema 2
∈
Sia Allora esiste tale che . Per definizione di
A RE. y A = W
Proof. 0 y
0
∈ hy ∈ hy
, sse . Definiamo dunque È chiaro
K x A = W , xi K f = λx. , xi.
2 y 0 2 y 0
0 0
∈ ∈
che sse .
x A f (x) K
y 2
0
Pertanto, ogni insieme r.e. è riducibile a . Questo significa che ha un
K K
2 2
ruolo speciale all’interno della classe degli insiemi r.e. : ogni elemento di questa
classe è riducibile a .
K 2 ∈
19.10. Un insieme è completo (più precisamente, r.e.
C RE
Definizione ∈
completo) se per ogni A RE: A C.
DESCRIZIONE DISPENSA
In questa dispensa di Informatica a cura del professore Agostino Dovier si parla dei fondamenti dell'informatica: linguaggi formali, calcolabilità e complessità. In particolare vengono affrontati i seguenti argomenti:
- Introduzione (quadro storico e concetti base della matematica);
- Linguaggi formali;
- Teoria della calcolabilità;
- Teoria matematica della ricorsione;
- Complessità Computazionale.
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Teemo92 di informazioni apprese con la frequenza delle lezioni di Informatica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Udine - Uniud o del prof Dovier Agostino.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato