Dispensa di informatica - Fondamenti: Linguaggi Formali, Calcolabilità e Complessità

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.

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.