Teoria della Computazione - Libero.it · 2003. 1. 27. · _ Teoria della Computazione _ 1...

____________________________ Teoria della Computazione ____________________________

1

Teoria della Computazione

Introduzione La questione principale sulla quale la teoria della computazione cerca di fare luce è la seguente:

“Comprendere i limiti e le possibilità teoriche del calcolo automatico”

L’aggettivo teorico è utilizzato per specificare che i limiti della computazione sono esplorati senza fare particolare riferimento ad una precisa macchina. Teorico, inoltre, implica che non viene presa in considerazione alcuna limitazione per le risorse di spazio e di tempo disponibili per il calcolo. In breve, l ’aspetto essenziale che si cerca di investigare è se un dato compito può essere portato a termine con l’utilizzo di risorse finite, senza interessarsi a quante esse siano . Questo approccio è differente dalla pratica informatica, ove molti problemi, risolvibili in tempo o spazio finito, risultano intrattabili poiché richiedono più risorse di quelle disponibili . Per calcolo automatico si intende l ’esecuzione di procedure effettive che producono, a partire da certi dati, in tempo finito, un risultato. Una buona descrizione di una procedura effettiva può essere data attraverso l ’uso dei diagrammi di flusso . Un diagramma di flusso è costituito da:

• blocchi rettangolari che racchiudono le operazioni che devono essere eseguite nell ’ordine specificato;

• blocchi rettangolari con una speciale etichetta di INIZIO e di FINE;

• blocchi romboidali che racchiudono la descrizione di un test che deve essere eseguito sui dati in corso di elaborazione;

• frecce direzionali che connettono tra loro i vari blocchi, indicando la sequenza di accesso ad essi. Dai blocchi rettangolari può uscire una ed una sola freccia. Dai blocchi romboidali escono tante frecce quanti sono i possibili esiti del test eseguito nel blocco. Non c’è limite al numero di frecce che giungono ad un blocco di qualsiasi


2

tipo. Nessuna freccia parte dal blocco rettangolare etichettato FINE.

Esempio Si consideri la funzione

1 se ∃z: xz=y con z∈Ζ divide(x, y)= 0 altrimenti

La computazione di tale funzione può essere descritta dal seguente diagramma di flusso:

Esempio Si consideri la funzione

1 se l’espansione decimale di π ha x cifre pi(x)= consecutive uguali 0 altrimenti

La computazione di tale funzione può essere descritta dal seguente diagramma di flusso:

si

no

no

si

START

y=0

y>x

y := y-x

OUTPUT 1

OUTPUT 0


3

Questo diagramma di flusso è sintatticamente corretto, presenta però degli inconvenienti:

1) per conoscere il valore della funzione in un dato punto x sembra necessario conoscere tutta l ’espansione decimale di π a priori, operazione non realizzabile;

2) non si avrà mai l ’output 0 . Dunque questo diagramma non descrive una procedura effettiva.

Limiti dei diagrammi di flusso Gli esempi e le definizioni date rendono l ’ idea di ciò che è calcolabile, ma nello stesso tempo mostrano con evidenza i limiti di un diagramma di flusso:

visto come procedura, non è sempre effettiva; non è ottimale per problemi molto complessi; non è stato specificato quali operazioni sono lecite

all ’ interno di un blocco. Si abbandonerà perciò tale modello e se ne considereranno altri che, partendo da alcuni assiomi, di genere differente, i quali catturano gli aspetti essenziali del fenomeno computazione, conducono sempre a caratterizzare quale computabile la medesima classe di funzioni.

si

no

START

n=0

z=π fino alla n-esima cifra

n=n+1

X cifre consecutive

uguali?

OUTPUT 1


4

Primo modello: la macchina a registri illimitati La struttura dati fondamentale manipolata dalle URM è quella degli interi positivi o nulli. La teoria classica della computazione si interessa infatti delle funzioni del tipo f: ℵ0 ℵ0 . L’hardware della macchina URM è costituito da un vettore infinito di registri , ognuno dei quali è in grado di contenere un intero maggiore o uguale a 0. In ogni istante della computazione solo un numero finito di registri avrà contenuto non nullo. I registri sono etichettati con le lettere maiuscole Ri , mentre quando si fa riferimento al contenuto dei registri si usano le lettere minuscole ri . Per quanto riguarda il software , i programmi di una URM sono liste finite e numerate di istruzioni del tipo: 1) ISTRUZIONE ZERO: Z(n)≡”rn:=0”

2) ISTRUZIONE SUCCESSORE: S(n)≡”rn:=rn+1”

3) ISTRUZIONE DI TRASFERIMENTO: T(m, n)≡”rn:=rm”

4) ISTRUZIONE DI SALTO CONDIZIONATO: J(m, n, q)≡”if rm=rn goto q” Lo stato di una URM viene descritto da una struttura dati finita, detta configurazione . Essa è costituita dalla l ista dei registri della URM con contenuto non nullo, insieme al loro contenuto , dalla l ista numerata delle istruzioni che compongono il programma in esecuzione e dall ’indice dell’istruzione che deve essere eseguita nell’istante successivo . La configurazione iniziale , per convenzione, è la stessa per tutte le URM ed è così fatta: i registri sono tutti nulli, eccetto i primi k , che costituiscono l ’input del programma da eseguire, e l ’ indice dell ’ istruzione da eseguire è pari a 1 . Ad ogni istante il programma in esecuzione specifica come cambia la configurazione della URM . La lista delle configurazioni raggiunte a partire da quella iniziale costituisce una computazione della URM . Se la URM perviene ad una configurazione in cui l ’ indice della successiva istruzione da eseguire eccede gli indici delle istruzioni del programma dato, la macchina si arresta e si avrà una computazione finita , altrimenti si avrà una computazione infinita . Nel caso di computazione finita, il contenuto del primo registro nella configurazione finale è convenzionalmente assunto come l ’output del programma.


5

Esempio Data la funzione

x-1 se x>0 f(x)= 0 altrimenti

il programma URM che la computa è il seguente: I1: J(0, 1, END) I2: S(1) I3: J(1, 0, OUTPUT) I4: S(1) I5: S(2) I6: J(0, 0, I3) OUTPUT: T(2, 0)

Osservazione Dall ’esempio precedente si nota che la semantica di un programma URM è spesso difficile da determinare leggendo la lista delle istruzioni. È spesso assai utile, quindi, passare da un programma URM ad una sua rappresentazione come diagramma di flusso, come segue:

a) ogni istruzione corrisponde ad un blocco; b) le istruzioni di salto condizionato corrispondono ai

blocchi romboidali e le frecce direzionali indicano le relazioni logico-temporali tra le istruzioni stesse;

c) si aggiungano il blocco START , da cui esce una sola freccia verso il blocco che rappresenta l ’ istruzione indicizzata con 1, ed il blocco END , in cui giungono tante frecce quante sono le istruzioni che rimandano ad istruzioni con indice eccedente il numero di istruzioni del programma a partire dai corrispondenti blocchi.

Osservazione È possibile ridurre il numero di istruzioni base per le URM a 3 , in funzione del fatto che l ’ istruzione T(m, n) può essere simulata dal seguente programma:

I1: Z(n) I2: J(m, n,5) I3: S(n) I4: J(1, 1, 2)


6

Definizioni Nella teoria della computazione si concentra l ’attenzione sulle funzioni f:Χ ℵ con Χ⊆ℵk . Se Χ≠ℵk , allora la funzione f si dice parziale , perché non definita per alcune k-uple, altrimenti si dice totale.

Definizione Il programma P computa la funzione f:Χ ℵ se sono soddisfatte le seguenti condizioni:

1) P(x1, … , xk)↓b e f(x1, … , xk)=b ∀(x1, … , xk)∈Χ 2) P(x1, … , xk)↑ ∀(x1, … , xk)∉Χ

Se esiste un programma P che computa la funzione f , allora la f si dice URM-computabile .

Definizione Una funzione totale che assume solo i valori 0 oppure 1 si dice predicato . Un predicato computabile si dice decidibile .

Secondo modello: modello funzionale

Funzioni iniziali 1) FUNZIONE NULLA: n(x)=0 . Essa è computabile tramite il

programma: I1: Z(0); 2) FUNZIONE SUCCESSORE: s(x)=x+1 . Essa è computabile tramite

il programma: I1: S(0); 3) FUNZIONE PROIEZIONE: pi(x1, … , xn)=xi . Essa è computabile

tramite il programma: I1: T(i, 0).

Composizione Abbiamo visto come è possibile scrivere programmi per calcolare le funzioni. La costruzione ex novo di un programma per una funzione risulta però poco conveniente. Per tale motivo, accade spesso che programmi per il calcolo di una certa funzione si ottengano combinando tra loro programmi scritti per funzioni più semplici. Comporre due programmi P1 e P2 vuol dire combinarli in un nuovo programma P3 in modo tale che l ’output di P1 venga fornito come input a P2 . Basta a tal proposito scrivere le istruzioni di P2 di seguito a quelle di P1 , aggiornando gli indici delle istruzioni del


7

secondo programma ed i riferimenti ad essi nelle istruzioni di salto condizionato. Si incontrano però due problemi:

1) un primo problema è legato alla presenza di salti condizionati a istruzioni con indice eccedente il numero di istruzioni di un dato programma . Si è convenuto che tale situazione determina l ’arresto della computazione del programma. Ma se concateniamo P1 e P2 la computazione non si arresterà come, invece, dovrebbe ed il suo esito è imprevedibile. Una soluzione a tale problema è data dalla standardizzazione .

Definizione Un programma P si dice standard se le sue istruzioni sono indicizzate da interi consecutivi a partire da 1 e, se esso è costituito da s istruzioni, ogni salto condizionato in esso presente si deve riferire ad un indice minore o uguale ad s+1 . È immediato osservare che esiste un algoritmo che dato un programma P ne restituisce uno P’ , che computa la medesima funzione, ma è in forma standard.

Ritornando al nostro problema, se P1 è standard e nel corso dell ’esecuzione raggiunge un punto di arresto, allora il controllo verrà senz’altro trasferito all ’ istruzione (s+1)-esima, cioè alla prima istruzione di P2 , realizzandosi in tal modo la corretta concatenazione desiderata.

2) un secondo problema è quello della collisione dei registri: potrebbe accadere che il medesimo registro sia usato da P1 e da P2 per il mantenimento di differenti variabili, e che un corretto funzionamento di P2 assuma che ogni registro che non contenga l ’ input abbia inizialmente contenuto nullo, condizione che non viene assicurata alla terminazione di P1 .

Osservazione Un’analisi della lista finita delle istruzioni di un programma consente, facilmente, di determinare quali dei registri della URM saranno utilizzati e quali no.


8

Notazione Dato il programma, in forma standard, P(x1, … , xk) , sia ρ(P) il massimo indice dei registri utilizzati dal programma P , allora il programma P[e1, … , ek e] è quello che si ottiene come segue: si premetta alle istruzioni di P il seguente blocco di istruzioni T , che serve a copiare l ’ input dei registri R1 , … , Rk nei registri di indice e1 , … , ek con ei>ρ(P) ∀ i:

T(1, e1) T(2, e2) M T(k, ek)

Si faccia seguire alle s istruzioni di P la seguente istruzione S , che copia l ’output, che per convenzione è posto nel registro R1 , nel registro di indice e>ρ(P) ed e>ei ∀ i=1, … , k:

T(1, e) Tra T e P si esegua il seguente blocco N , che pulisce i registri di lavoro:

Z(1) M Z(ρ(P))

Si può garantire che la computazione guidata dal programma Q=(T, N, P, S) sarà identica a quella guidata da P .

Teorema Se f(y1, … , yk), g1(x1, … , xn) , … , gk(x1, … , xn) sono funzioni computabili, allora la funzione

h(x1, … , xn)=f(g1(x1, … , xn) , … , gk(x1, … , xn)) è pure computabile. Dim.: basta esibire un programma che computi h . Siano Pf, Pg1 , … ,

Pgk i programmi che computano rispettivamente f , g1, … , gk . Sia m=max{ρ(Pf), ρ(Pg1), … , ρ(Pgk)}+1 . Il programma voluto è il seguente:

T(1, m) T(2, m+1) M T(n, m+n-1) Z(1) M Z(n)


9

Pg1[m, m+1, … , m+n-1 m+n] Z(1) M Z(n) Pg2[m, m+1, … , m+n-1 m+n+1] M Z(1) M Z(n) Pgk[m, m+1, … , m+n-1 m+n+k-1] Z(1) M Z(n) Pf[m+n, m+n+1, … , m+n+k-1 1]

C.V.D.

Corollario Se f(x1, x2) è computabile anche la funzione f(x2, x1) è computabile. Dim.: f(x2, x1)=f(p2(x1, x2), p1(x1, x2)) che è computabile per il

teorema precedente. C.V.D.

Corollario Se f(x,y) è computabile anche la funzione g(x)=f(x,x) è computabile. Dim.: g(x)=f(p1(x, y), p1(x,y))=f(x, x) che è computabile per il

teorema precedente. C.V.D.

Corollario Se f(x1, x2) è computabile, tale è anche la funzione h(x1, x2, x3)= =f(x1, x2) . La variabile x3 non svolge alcun ruolo attivo, ma è a volte utile nelle dimostrazioni. Per tale motivo essa è detta dummy . Dim.: h(x1, x2, x3)=f(p1(x1, x2, x3), p2(x1, x2, x3)) che per il

teorema precedente è computabile. C.V.D.


10

Osservazione La composizione è uno strumento buono quando è noto il numero di volte che si deve applicare le funzioni di partenza computabili, ad esempio la funzione f(x)=kx è computabile per composizione perché

f(x)=somma(…(somma(x, x), x)…, x) con la funzione somma, ripetuta k volte, computabile. Essa però non è utile per definire funzioni del tipo f(x, y)=xy , dove y non è costante. Occorre quindi un nuovo strumento.

Ricorsione (primitiva) Si considerino le due funzioni f(x1, … , xn) e g(x1, … , xn, y, z). La funzione h(x1, … , xn, y) definita come segue:

f(x1, … , xn) se y=0 h(x1, … , xn, y)= g(x1, … , xn, y, h(x1, … , xn, y-1)) se y>0

si dice definita per ricorsione primitiva .

Esempio La funzione h(x, y)=xy è definita così:

0 se y=0 h(x, y)= x+h(x, y-1)) se y>0

In tal caso sono f(x)=0 e g(x, y, z)=x+z .

Teorema Se h(x1, … , xn, y) è ottenuta per ricorsione primitiva da f(x1, … , xn) e g(x1, … , xn, y, z), con f e g URM-computabili, allora anche h è URM-computabile. Dim.: occorre costruire un programma per una macchina URM che

computi h . Siano Pf e Pg i programmi per computare f e g . Sia m=max{ρ(Pf), ρ(Pg), n+2} . Il programma per h è il seguente:

T(1, m+1) T(2, m+2) M T(n+1, m+n+1) Z(1) M


11

Z(m) Z(m+n+2) rm+n+2=risultati parziali Z(m+n+3) rm+n+3=contatore Pf[m+1, … , m+n m+n+2] COND: J(m+n+1, m+n+3, END) Pg[m+1, … , m+n, m+n+3, m+n+2 m+n+2] S(m+n+3) J(1, 1, COND) END: T(m+n+2, 1)

C.V.D.

Osservazione Con l ’introduzione della composizione e della ricorsione si può vedere se una funzione è computabile in un modo più astratto, evitando di scrivere programmi da far girare sulle URM.

Definizione Una classe di funzioni C si dice PRC se soddisfa le seguenti due proprietà:

1) la classe C è chiusa rispetto agli operatori di composizione e ricorsione;

2) le funzioni iniziali appartengono a C .

Teorema La classe delle funzioni URM-computabili, CURM, è una classe PRC .

Definizione La più piccola classe PRC (rispetto all ’ inclusione insiemistica) è la classe delle funzioni primitive ricorsive PR , cioè

PR=∩PRC e si ha che la classe PR è formata dalle funzioni ottenute per composizione e ricorsione a partire dalle funzioni iniziali.

Osservazione La classe delle funzioni URM-computabili contiene strettamente PR. Infatti, si osservi che gli operatori di ricorsione e composizione, se applicati a funzioni totali, costruiscono ancora funzioni totali, e, siccome le funzioni iniziali sono totali, allora tutte le funzioni


12

appartenenti a PR sono funzioni totali. In CU R M, invece, si hanno anche funzioni non totali e ciò che è più interessante è che si hanno funzioni totali non PR.

L’operatore di minimalizzazione Abbiamo detto che esistono funzioni computabili non PR. Per ottenere tutte le funzioni CU R M a partire dalla classe PR si ha, quindi, bisogno di un nuovo operatore, detto di minimalizzazione , che denoteremo con la lettera µ .

Definizione Sia M(x1, … , xn, y) una funzione parziale che assuma solo i valori (dove definita) 0 o 1 . Definiamo il numero intero µyM(x1, … , xn, y) come il miny:((M(x1, … , xn, y)=1) ∧ (M(x1, … , xn, z)=0 ∀z


13

m+n+1 , e di mantenere nel registro di indice m+n+2 i l valore 1 con cui confrontare il risultato di ogni computazione di M al crescere di y .

C.V.D.

Osservazione La classe Cf delle funzioni funzionalmente computabili, ottenibili dalle funzioni iniziali per ricorsione, composizione e minimalizzazione è contenuta in CURM

Cf⊆CURM

Funzione definita per casi Siano Mi=(x) ∀ i=1, … , n predicati mutuamente esclusivi, e siano fi=(x) ∀ i=1, … , n funzioni computabili. Allora la funzione

f1(x) se M1(x) f2(x) se M2(x) f(x)= M M fn(x) se Mn(x)

definita per casi è URM-computabile. Dim.: la funzione f(x) può essere scritta come segue

f(x)=Σ i=1..nMi(x)fi(x) allora è possibile scrivere un programma che la calcoli.

C.V.D.

Osservazione Spesso l ’operatore di minimalizzazione si dice non limitato, perché il range nel quale si cerca la y che rende vera M è non limitato.

Definizione Sia M(x1, … , xk, y) una funzione a valori in {0, 1} , allora la funzione

f(x1, … , xk, a,b)=miny∈ [a, b]y:M(x1, … , xk, y)=1 si dice ottenuta per minimalizzazione limitata a partire da M . Se y non esiste, allora f(x1, … , xk, a,b)=0 .


14

Osservazione Dalla definizione appare evidente che la classe PR è chiusa rispetto a tale operatore.

La funzione di Ackermann Tale funzione è un esempio di funzione totale, computabile, non primitiva ricorsiva. La funzione di Ackermann è così definita:

y+1 se x=0 A(x, y)= A(x-1, 1) se y=0∧x≥1 A(x-1, A(x, y-1)) se y,x≥1

I valori assunti da questa funzione possono essere trascritti in una tabella infinita, di cui riportiamo il seguente frammento:

Come si è costruita questa tabella? È banale ricavare la prima colonna e la prima riga; i valori nelle colonne successive si ottengono come segue: si legge anzitutto il valore contenuto nella casella sottostante alla casella in cui si vuole computare la funzione; tale valore fornisce l ’ indice, nella colonna precedente, della casella che contiene il valore cercato. Questa osservazione ci fornisce un’intuizione di come si possa effettivamente computare A(x,y) . Si tratta di computare ‘a ritroso’ i valori necessari fino ad arrivare ad uno dei casi che potremo definire iniziali. Questo metodo potrebbe essere implementato in un programma per una URM, anche se risulterebbe un programma molto complesso. Allora A(x, y) è computabile ed, inoltre, è anche totale, perché A(x, y) è definita per ogni coppia (x, y) . Si ha che A(x, y) non è primitiva ricorsiva. La dimostrazione consiste nel provare che la funzione di Ackermann cresce più rapidamente di quanto possa crescere una qualunque funzione

L

L

LL

LL

LLL

LLL

LLL

MMMMMMM

432101353210

135321277432

95431165413765

xy


15

primitiva ricorsiva, e non verrà riportata qui. Per accertarsi, però, di tale vertiginoso tasso di crescita, si verifichi come

A(x, y)=Ax(y) Sia soluzione dell ’equazione di ricorsione funzionale

Fi(y)=Fi-1(Fi(y-1)) Se sono fissate le condizioni iniziali c’è, ovviamente, un numero infinito di possibili soluzioni a tale ricorrenza. Una famiglia di possibili soluzioni è la seguente:

f0(y)=y+1 f1(y)=2y f2(y)=2y f3(y)=22…2 } y+1 vo lte

M è, dunque, evidente che la crescita della funzione di Ackermann deve essere vertiginosamente rapida, superiore a quella di ciascuna delle funzioni fi .

Terzo modello: le macchine di Turing Una TM è data da:

1) un insieme finito di simboli Σ . Esso contiene il simbolo speciale di “blank” o “spazio vuoto”, che si denota con B;

2) un array infinito di celle inizialmente tutte blank, tranne un numero finito di esse contenenti l ’ input;

3) una testina in grado di leggere nella cella in cui è posizionata, di scrivere oppure di muoversi a sinistra o a destra, passando ad esaminare una delle celle adiacenti;

4) un insieme finito Q di stati in cui la macchina può via via trovarsi;

5) un insieme finito di quadruple del tipo (s1, a, b, s2) , dove s1 ,s2∈Q , a∈Σ e b∈Σ∪{L, R} . La semantica di queste quadruple, che costituiscono il cosiddetto ‘controllo finito ’ della macchina, è la seguente: se la macchina si trova nello stato s1 e la testina sta leggendo il simbolo a , se b è un simbolo dell ’alfabeto si deve cancellare a e scrivere b, altrimenti la testina deve muoversi a destra o a sinistra a seconda del valore di b , ed infine si deve assumere il nuovo stato s2 . Non ci sono più quadruple che cominciano con la medesima coppia s1 , a .


16

La definizione, fornita al punto 5) ,del controllo finito di una TM come insieme di quadruple, può essere sostituita da altre equivalenti: a) funzione di transizione: δ: Q×Σ → Σ∪{L, R}×Q; b) tabella , le cui righe sono indicizzate con gli stati, e le cui colonne

vengono indicizzate dai simboli dell ’alfabeto. Nella casella [q1, a] avremo un b∈Σ∪{L, R} ed uno stato q2.

La configurazione di una TM consiste nello stato in cui la macchina si trova assieme al contenuto delle caselle del nastro diverse dal blank, e la posizione della testina. Per la configurazione iniziale adottiamo la seguente convenzione: lo stato iniziale è q0 e la testina è posta sul simbolo non blank più a sinistra. Eseguendo le mosse prescritte dal controllo finito, la macchina passa da una configurazione all ’altra fino a quando viene raggiunto lo stato finale qf . La configurazione raggiunta in uno stato finale è interpretata come configurazione finale . Il contenuto dei registri in una configurazione finale è l ’output della computazione. È ovviamente possibile che una TM non si arresti mai o si arresti solo su determinati input.

Osservazione Risulta spesso conveniente descrivere le TM, soprattutto quando esse sono costituite da pochi stati e operano su un piccolo alfabeto, mediante l ’espediente grafico dei cosiddetti diagrammi di transizione . In essi ogni nodo rappresenta uno stato, e da ognuno di essi si dipartono degli archi, etichettati da un simbolo dell ’alfabeto e da un altro simbolo che rappresenta l ’azione (scrittura o movimento) che la testina deve intraprendere nel passaggio da uno stato ad un altro.

Le funzioni T-computabili Nel seguito assumeremo di rappresentare i numeri in notazione decimale. L’input verrà fornito alla TM sotto forma di stringhe di numeri decimali separati da un blank, e, inizialmente, la testina sarà posizionata sul primo simbolo non blank più a sinistra. L’output sarà ottenuto leggendo la stringa composta di simboli non blank più a sinistra sul nastro, nel momento in cui la macchina si arresta.


17

Una TM, che obbedisce a queste convenzioni, stabilisce una funzione (generalmente parziale) tra le n-uple di numeri naturali ed i numeri naturali; tale funzione è naturalmente associata alla macchina. Una funzione f(x) si dice T-computabile se esiste una TM la cui funzione associata coincide su tutti gli input con f . In particolare, se f(m)↑ per qualche m, la macchina non si arresta sull ’ input m .

Proposizione Le funzioni iniziali sono T-computabili. Dim.: costruiamo le TM corrispondenti ad ognuna delle funzioni

iniziali: 1) la funzione successore è calcolata tramite la

seguente TM: (q0, 0, R, q0) (q0, 1, R, q0)

M (q0, 9, R, q0) (q0, B, L, q1) (q1, 0, 1, qf) (q1, 1, 2, qf)

M (q1, 8, 9, qf) (q1, 9, 0, q2) (q2, 0, L, q1)

2) la funzione nulla è calcolata dalla seguente TM: (q0, 0, B, q1)

M (q0, 9, B, q1) (q1, B, R, q0) (q0, B, R, q2) (q2, B, 0, qf) (q2, 0, B, q1)

M (q2, 9, B, q1)

3) la funzione proiezione m-esima è calcolata dalla seguente TM:

(q0, 0, B, qh0) M

(q0, 9, B, qh0)


18

(qh0, B, R, q0) (q0, B, R, q1) (q1, 0, B, qh1)

M (q1, 9, B, qh1) (qh1, B, R, q1) (q1, B, R, q2)

M (qm-1, 0, R, qhm-1) (qm-1, 1, R, qhm-1)

M (qm-1, 9, R, qhm-1) (qhm-1, B, R, qf)

C.V.D.

Teorema Le funzioni ottenute per composizione, ricorsione e minimalizzazione a partire da funzioni T-computabili sono T-computabili

Cf⊆CT

Teorema Come vedremo, la configurazione di una TM si può codificare con un numero intero, allora passare da una configurazione alla successiva corrisponde ad una funzione f: ℵ → ℵ . Si ha poi che tale funzione è URM-computabile, cioè ogni TM può essere simulata da una URM,

CT≡CURM

Variazioni sulle TM Il modello classico descritto precedentemente per le TM può subire diverse variazioni. Esse risultano tutte equivalenti al modello di calcolo classico, dove per equivalenti si intende che tutto ciò che è computabile in un modello , con le opportune convenzioni, può essere computato in un altro modello .

TM a più nastri Anziché supporre che la macchina operi su un unico array per mezzo di un’unica testina, si può supporre che vi siano k nastri infiniti capaci di contenere simboli dell ’alfabeto e che la macchina possa, in ogni istante della computazione, leggere contemporaneamente su


19

ciascuno di essi, per mezzo di k testine. Le mosse della macchina richiederanno nuovi simboli L ed R per descrivere il comportamento delle testine, ma per il resto la struttura della macchina sarà invariata. È immediato osservare che tali macchine sono in grado di computare tutte le funzioni che una TM normale può computare. Essa infatti può sempre immaginarsi come una TM con k nastri, di cui se ne adoperi sempre e soltanto uno. Viceversa una TM normale può simulare una TM a k nastri. Basta suddividere il suo unico nastro in 2k tracce . Le tracce di posto dispari simuleranno le posizioni delle testine sui k nastri e quelle di posto pari il contenuto dei nastri.

Nastro semi-infinito Anziché supporre che il nastro su cui la macchina opera sia infinito in entrambe le direzioni, si supponga che questo sia illimitato solo in una di esse. È chiaro che una TM standard può eseguire tutte le computazioni effettuabili su un nastro semi-infinito: essa si limiterà a non utilizzare le caselle a sinistra di un certo limite fissato. Viceversa una TM a nastro semi-infinito può simulare una TM a nastro infinito, infatti

nastro semi-infinito ⇓

nastro infinito

⇓

…… ……

……

……


20

Input read-only machine o TM off-line Esse sono TM a più nastri, di cui uno speciale che contiene l ’ input e sul quale la macchina può effettuare solo operazioni di lettura. Esse sono utili quando è necessario manipolare molto i dati in input. Anche questo tipo di macchine è equivalente al modello standard. Una TM off-line si può simulare con una TM a k nastri con il primo nastro limitato a destra e a sinistra con due simboli marcatori. Una TM a k nastri può essere simulata da una TM off-line a k+1 nastri: il nastro extra viene usato per l ’ input e su esso si può solo leggere.

TM non deterministiche Nella descrizione del controllo finito di una TM, riportata precedentemente, si è esplicitamente richiesto che non ci fossero due quadruple (q1, s1, s2, q2) e (q1’, s1’, s2’, q2’) tali che q1=q1’ e s1=s1’ . Tale richiesta è motivata dal fatto che si desidera che lo stato ed il simbolo letto in un dato istante determinino in maniera univoca lo svolgimento successivo della computazione. Presenteremo ora una speciale variazione di TM.

Definizione Una TM non deterministica (NTM) è una TM che nel controllo finito contenga qualche coppia di quadruple con i primi due termini identici. Una NTM giunta in un passo di computazione in cui più di una quadrupla specifica i possibili comportamenti si clonerà in un numero di copie pari al numero (finito) di possibilità offerte, e ciascuna copia continuerà la computazione seguendo una possibile scelta differente da quella operata dalle altre copie. Si tratta, in un certo senso, di molte computazioni condotte contemporaneamente ed ognuna indipendente dalle altre. Un diagramma che voglia rappresentare la computazione condotta da una NTM assume la forma di un albero . L’output di una NTM potrebbe essere definito, in tal caso, come il contenuto del nastro quando uno dei possibili rami della computazione si arresta. Se nessuna scelta porta la macchina ad arrestarsi, l ’output non è definito. C’è però una difficoltà: seguendo diversi percorsi si può pervenire ad output differenti. Una NTM, quindi, non potrebbe più essere considerata


21

come una descrizione di funzione computabile uno-a-uno, ma piuttosto come descrizione di una funzione computabile uno-a-molti. Questo è perfettamente accettabile, ma non si inquadra con l ’ indagine sulle funzioni uno-a-uno computabili, condotta precedentemente. Tale difficoltà può essere superata facilmente se ci si restringe allo studio di TM che riconoscono linguaggi , cioè tali che, esaminata una stringa data in input di simboli di un dato alfabeto, siano in grado di decidere se tale stringa appartiene o meno ad una data collezione di stringhe ( l inguaggio). In tal caso, l ’output della macchina è soltanto 1 o 0 , a seconda che la stringa venga accettata o meno. Si assumerà che una NTM accetti una data stringa se c’è almeno un ramo della computazione che da in output 1 . Una stringa viene rigettata se tutti i rami della computazione terminano e danno come output 0 . Se tutti i rami finiti danno come output 0 e ci sono rami infiniti, non si può dire niente sulla stringa. Restringere l ’attenzione a queste particolari macchine riconoscitrici di linguaggi non è assolutamente limitativo. Infatti, ogni computazione si può riformulare in termini di riconoscimento di linguaggi: se si ha una funzione computabile, f , computare il suo valore in un punto x è equivalente a decidere quale delle stringhe f(x)=0 , f(x)=1 , … , f(x)=n , … ‘appartiene’ al linguaggio associato alla funzione

Gf={(n, f(n)) ∀n∈Ν} Anche decidere se una particolare istanza di un problema abbia o meno una soluzione, si può riformulare in termini di riconoscimento di un linguaggio: la stringa che codifica l ’ istanza del problema viene accettata se esiste una soluzione, rifiutata altrimenti.

Teorema I linguaggi riconoscibili da una DTM sono riconoscibili anche da una NTM e viceversa. Dim.: ⇒) banale, perché una DTM può essere considerata come una

speciale NTM ⇐) può essere provato in due modi:

1°metodo: sappiamo che una NTM genera un albero di differenti computazioni. Se si vuole vedere se c’è un ramo che conduce ad uno stato di accettazione della stringa in input, in


22

maniera deterministica, si tratta di “costruire”, livello per livello, l ’albero e “visitare” la parte di albero costruita fino a quel punto, verificando se si è raggiunta una foglia , ed esaminando, in tal caso, l ’output. Poiché ogni nodo dell ’albero ha grado finito, una costruzione abbinata ad una visita nel modo appena descritto si può certamente portare avanti in maniera deterministica, per esempio con una BFS a partire dalla radice (si esclude la DFS per la possibile presenza di rami infiniti).

2°metodo: si tratta di costruire una DTM con k=3 nastri che simuli una NTM. Sul primo di essi viene scritto l ’ input che può essere riletto più volte, ma non verrà mai alterato. Inoltre, posto r uguale al numero massimo di alternative differenti che sono presenti ad ogni passo della computazione della NTM in esame , si introduca un modulo nella DTM capace di generare via via, secondo un ordine lessicografico, tutte le stringhe composte da interi compresi tra 1 ed r , e di scriverle ad una ad una nel secondo nastro. Tali stringhe saranno le “guide” nella simulazione deterministica dell’evoluzione di una macchina non deterministica. Il terzo nastro è quello di lavoro ed il controllo finito della DTM sarà uguale a quello della NTM che si vuole simulare. Ogni volta che viene offerta una biforcazione nelle transizioni, si “consuma” un simbolo nella stringa guida generata in precedenza e si sceglie la transizione indicata da quel simbolo. Se tale computazione giunge ad uno stato di accettazione e di arresto, si è raggiunta una conclusione. Se si giunge ad un rifiuto, si ricomincia la simulazione dopo aver generato una nuova stringa guida. Se per tutte le stringhe guida di una data


23

lunghezza si giunge, arrestandosi, ad un rifiuto, è chiaro che non ci sono computazioni che portano all ’accettazione dell ’ input, ed anche in questo caso si è raggiunta una conclusione. Se la stringa guida si esaurisce prima di essere giunti all ’arrestarsi di una computazione, si passa a generare la successiva stringa guida e si ricomincia la simulazione dall ’inizio. Questo meccanismo tiene automaticamente conto del caso in cui si sia imboccata la strada di qualche computazione che non si arresti. La simulazione proposta è deterministica e questo prova il teorema.

C.V.D.

Corollario La classe delle funzioni computabili deterministicamente coincide con la classe delle funzioni computabili non deterministicamente.

Il problema del castoro indaffarato Presenteremo una funzione che non è T-computabile, nel senso che non esiste una TM in grado di calcolarla. Essa, quindi, non sarà neanche URM-computabile (visto che CT≡CURM) e Cf-computabile (visto che Cf⊆CT e Cf⊆CURM). Il problema del castoro indaffarato o busy beaver problem è il seguente. Si consideri l ’ insieme Mn di tutte le DTM che computano sull ’alfabeto {1, B} e che hanno esattamente n stati. Si definisce produttività , prod(M) , di una M∈Mn i l numero di simboli 1 consecutivi che la macchina lascia sul nastro quando, e se, si arresta dopo essere partita con nastro vuoto. Se la macchina M non si arresta, allora prod(M)↑ . Si definisce la funzione

p(n)=max(M∈Mn)∧ (prod(M)↓ ){prod(M)}

Teorema La funzione p(n) non è T-computabile.

Lemma 1 Si ha che ∀n∈ℵ


24

p(n+1)>p(n) Dim.: sia M una macchina ad n stati che abbia produttività pari a

p(n) . A partire da essa, aggiungendo un unico stato allo stato finale, si può certamente riuscire a scrivere un’ulteriore simbolo 1 . La macchina M’ , così costruita, ha n+1 stati e produttività pari a p(n)+1 . Dunque

p(n+1)≥p(n)+1>p(n) C.V.D.

Lemma 2 La funzione f(n)=2n è T-computabile, dunque esiste una macchina M a k stati che la computa. Dim.: per esercizio.

Lemma 3 Se k è il numero degli stati della macchina nel Lemma 2 si ha

p(n+k)≥2n Dim.: è semplice disegnare una macchina Mn’ ad n stati, che abbia

produttività uguale ad n . Se lo stato finale di questa macchina si concatena con lo stato iniziale della macchina a k stati del Lemma 2 , otterremo una nuova macchina M’ con n+k stati e produttività pari a 2n .

C.V.D.

Dimostrazione del teorema Per ASSURDO si supponga che la funzione p(n) sia computabile e sia computata dalla macchina Mp ad h stati. Se concateniamo la macchina Mn’ e due copie di Mp , si possono scrivere, a patire dal nastro vuoto, p(p(n)) simboli 1 , e la macchina così ottenuta ha n+2h stati, da cui ∀n

p(n+2h)≥p(p(n)) n+2h≥p(n) .

Con n’=n+k avremo che n+k+2h≥p(n+k)

con k del Lemma 2 n+2h+k≥p(n+k)≥2n

2h+k≥n i l che è ASSURDO perché non c’è nessuna limitazione su n .


25

Si ha quindi che p(n) non è T-computabile . C.V.D.

Sistemi di Post-Markov Sia Σ={a1, … , ak} un alfabeto finito. Indichiamo con Σ* l ’ insieme delle stringhe costruite con i simboli di Σ . Sia ε la stringa vuota.

Manipolazione di stringhe

Definizione Si definisce Post-produzione la seguente:

g0s1g1s2…gh-1shgh h0si1h1si2…hm-1simhm essendo g0, … , gh, h0, … ,hm stringhe fissate e i1 , … , im∈{1 , … , n} . Sia σ∈Σ*, se applichiamo ad essa una Post-produzione, come quella illustrata precedentemente, avremo

σ=g0σ1g1σ2…gh-1σngh τ=h0σ i1h1σ i2…hm-1σ imhm

Esempio Sia Σ={a, b} e (π) as1bs2 s2as2a la Post-produzione, allora da σ=aεba si ottiene τ così

σ=aεba (π) aaaa=τ .

Osservazione 1) Esistono stringhe a cui non è possibile

applicare determinate regole di produzione; 2) Esistono stringhe alle quali si può applicare la

stessa produzione in diversi modi.

Definizione Un sistema canonico di Post S consiste di :

1) un alfabeto finito Σ; 2) un sottinsieme finito di assiomi A di Σ*; 3) un insieme finito Q di produzioni.

Definizione Si dice che la stringa τ è generata o generabile in un sistema di Post, S , (⊢Sτ) se ∃σ∈A:

σ⇒Qτ


26

Si indichi a tal proposito con TS={τ∈Σ*:⊢Sτ}

l ’ insieme dei teoremi di S .

Esempio Siano Σ={a, b} , A={ε, a, b} e Q={(π1), (π2)} con

(π1) s1 as1a (π2) s1 bs1b

Si ha allora che ε⇒π2bεb=bb⇒π1abba

da cui si ha che TS={w: w è palindroma su A}

Definizione Sia Σ un alfabeto e sia X⊆Σ* . X è Post-generabile se esiste un alfabeto Σ1 , tale che Σ⊆Σ1 , e un sistema di Post S sull ’alfabeto Σ1 , tale che X=TS∩Σ* .

Osservazione Usando insiemi Post-generabili è possibile sostituire produzioni del tipo presentato precedentemente con produzioni del tipo

gs sh dette produzioni normali .

Teorema Ogni insieme X Post-generabile può essere generato a partire da un sistema normale di Post, ossia un sistema formato da produzioni normali.

Osservazione Dato l ’alfabeto Σ={a1, … , ak} si desidera poter definire una funzione che trasformi stringhe di Σ* in numeri naturali. Consideriamo per tale motivo la funzione seguente

∧: Σ* ℵ così definita

∧(σ=ai0ai1…ain)=i0+i1k+i2k2+ … +inkn con k base. Ovviamente ∧(ε)=0 . L’inversa di tale funzione è


27

∼: ℵ Σ* Essa prende un n∈ℵ , lo trasforma in base k e i coefficienti danno la sequenza di simboli nella stringa. Si ha quindi una corrispondenza biunivoca tra Σ* e ℵ .

Definizione Sia X⊆Σ* . Definiamo l ’ insieme

X^={x^: x∈X} come l ’ insieme dei numeri corrispondenti alle stringhe di X .

Teorema Dato Σ alfabeto finito, sia X⊆Σ*, allora X è Post-generabile se e solo se X^ è ricorsivamente enumerabile.

Funzioni Post-calcolabili Tali funzioni sono del tipo:

1) f: Σ* Σ* con f non necessariamente totale. Definiamo l ’ insieme

G(f)={σ⋅f(σ): σ∈Dom(f)} con ⋅∉Σ , e si ha che σ⋅τ∈G(f) se σ∈Dom(f) e τ=f(σ) . Si ha quindi che f è Post-calcolabile se G(f) è Post-generabile .

2) f: (Σ*)n Σ* Essa è Post-calcolabile . La dimostrazione di ciò si opera considerando un Gn(f) , ottenuto combinando in modo opportuno la definizione G(f) .

3) g: ℵn ℵ Consideriamo, inoltre, la funzione

g∼: (Σ*)n Σ* così definita:

g∼(m1∼, … , mn∼)=(g(m1, … , mn))∼ Si ha allora che g è Post-calcolabile se e solo se g∼ è Post-calcolabile .

Esempio Sia Σ={a} e sia f: Σ* Σ* tale che

1………1 f 1………1 123 123 n volte n2 volte


28

In tal caso G(f)={1………1 ⋅ 1………1 ∀n∈Ν}

123 123 n volte n2 volte

Consideriamo il seguente sistema di Post S: • Σ1={1, ⋅} • A={ ⋅} • Q={(π)} con (π): s1 ⋅s2 s11 ⋅s2s1s11

Questa sola produzione basta a generare tutte le stringhe di G(f) dall ’assioma “ ⋅”, infatti

ε⋅ε ε1 ⋅εεε1 = 1 ⋅1∈G(f) 1 ⋅1 11 ⋅1111∈G(f)

infatti 1………1 ⋅ 1………1 1………11 ⋅ 1………11………1………1 1 123 123 123 123123123 n n2 n+ 1 n2+ n+ n+ 1=

=n2+2n+1=(n+1)2 da cui G(f) è Post-generabile da S , e, dunque, f è Post-calcolabile.

Teorema La classe delle funzioni Post-calcolabili coincide con la classe delle funzioni T-calcolabili .

Definizione Un insieme di produzioni su un alfabeto Σ si dice monogenico se per ogni stringa σ∈Σ* esiste al più una produzione ad essa applicabile.

Definizione Un sistema di Post si dice monogenico se ogni sua produzione è monogenica.

Teorema Sia f: Σ* Σ* una funzione parziale, e siano x,y∉Σ . Allora le seguenti affermazioni sono equivalenti: (a) f è Post-calcolabile; (b) esiste un insieme Q di produzioni monogeniche su un alfabeto

Σ1 con Σ∪{x, y}⊆Σ1 tale che ∀σ∈Σ*, τ∈(Σ1)* si abbia Xσ⇒Qτ se e solo se σ∈Dom(f) e τ=yf(σ) , ed il simbolo “”, indica che dopo aver prodotto τ non si può più applicare nessuna produzione.


29

Algoritmo normale di Markov Sia dato Q tale che

1) tutte le produzioni s1gs2 s1hs2 sono normali 2) T⊆Q sono tutte le produzioni terminali.

Un algoritmo normale di Markov si applica a σ∈Σ* secondo le seguenti regole: a) se più di una produzione può essere applicata a σ , si usa la prima

nella lista Q , che si suppone ordinata; b) se una stessa produzione s1gs2 s1hs2 si può applicare a σ in più

di un modo, allora vuol dire che g compare in più posti in σ , dunque la si applica alla prima occorrenza di g;

c) i l processo termina avendo generato la stringa τ se non si può più applicare alcuna regola di produzione, oppure appena si utilizza una regola di produzione terminale di T .

Teorema Una funzione è Markov-computabile se e solo se è Post-computabile .

La tesi di Church Le classi di funzioni computabili ottenute usando i tre modi alternativi di assiomatizzare il procedimento del calcolo:

1) approccio funzionale; 2) URM; 3) TM

sono equivalenti, e ciò spinse Church a dire che “ogni funzione computabile, secondo il concetto intuitivo del termine, è computabile”. Allora tutte le volte che siamo in grado di fornire un argomento rigoroso per dimostrare che una funzione è computabile, si farà uso della tesi di Church per concludere che esiste sicuramente una TM (o un programma URM, o una serie di ricorsioni, composizioni e minimalizzazioni) che la computa.

Osservazione Si è usata tale tesi per affermare che la funzione di Ackermann è computabile, esibendone solo la tabella.

Definizione Una funzione g: ℵ0 X si dice enumerazione di X se è suriettiva.


30

Se g non è iniettiva si dice enumerazione con ripetizioni . Se g può essere descritta con un preciso algoritmo si dice effettiva enumerazione di X .

Definizione Un insieme X si dice enumerabile se esiste f: ℵ0 X enumerazione senza ripetizioni (cioè f è biettiva). Se f può essere descritta con un preciso algoritmo X si dice effettivamente enumerabile .

Lemma Sono effettivamente enumerabili (e.e.), i seguenti insiemi:

1) (ℵ0)2 2) (ℵ0)k 3) U i=0..∞(ℵ0)i 4) ℵ0∪ℵ0∪…∪ℵ0

Dim.: definiamo Pairing function la seguente funzione π: (ℵ0)2 ℵ0

così definita π(x, y)=2x(2y+1)-1

1) per provare che (ℵ0)2 è e.e. bisogna provare che π è biettiva. SURIETTIVITÀ: sia m∈ℵ0, se m=0 , allora

(x, y)=(0, 0) è tale che

π(0, 0)=0 se, invece, m≠0 allora sia x la massima potenza tale che 2x divida m+1 . Si ha che (m+1)/2x è sempre dispari, da cui (m+1)/2x-1 è sempre pari, allora sia

y=((m+1)/2x-1)/2 Con tali x e y si ha che

π(x, y)=m . INIETTIVITÀ: siano

π(x1, y1)= π(x2, y2) allora

2x1(2y1+1)-1=2x2(2y2+1)-1 da cui x1=x2 e y1=y2 .

2) la proprietà si dimostra per induzione su k . Per k=1 è banale. Per k=2 è vera per la 1) . Si supponga la


31

proprietà vera per k-1, e si osservi che (Ν0)k= =(Ν0)k×Ν0=Ν0×Ν0=(Ν0)2 che è e.e. La codifica che permette enumerare (Ν0)k è

z(n1, … , nk)=π(nk, π(nk-1, π(…, π(n2, n1)…)) cioè è ottenuta componendo k volte la funzione π .

3) per U i=0..∞(Ν0)i potremmo essere tentati, per dimostrare che è e.e. , a scegliere come effettiva enumerazione la funzione z(n1, … , nk) . Nella codifica non ci sarebbero problemi, ma nella decodifica, dal momento che k è variabile, potrebbe capitare che uno stesso numero n∈ℵ0 venga decodificato in maniera non univoca. Per tale motivo si usa una codifica più opportuna:

τ(n1, … , nk)= =2n1+2n1+n2+1+2n1+n2+n3+2+…+2n1+n2+…+nk+k-1-1

Per la decodifica si opera così: dato n’∈ℵ , si consideri n’+1 e si trasformi tale numero in base binaria e da ciò si ottiene la k-upla. Poiché è ben noto che per ogni numero naturale esiste una ed una sola espressione binaria, allora la decodifica è non ambigua, da cui la funzione τ è biettiva ed è effettiva, dunque U i=0..∞(ℵ0)i è e.e.

4) per l ’unione di h copie distinte di ℵ0 si usa come enumerazione la funzione βh , che è tale che ni → hni+i-1 , dove ni è l ’i-esima componente della h-upla.

C.V.D.

Teorema Sia I l ’ insieme di tutte le istruzioni sintatticamente accettabili per una URM. L’insieme I è e.e. Dim.: le possibili istruzioni per una URM sono:

1. I1=Z(n) n∈ℵ0 2. I2=S(n) n∈ℵ0 3. I3=T(i, j) π(i, j)∈ℵ0 4. I4=J(m, n, q) π(π(n, m), q)∈ℵ0

Si ha che I=U i=1..4Ii è e.e. tramite la funzione β4 relativa al caso 4) del Lemma precedente.

C.V.D.


32

Teorema della codifica di Godel L’insieme ℘ di tutti i possibili programmi per macchine URM è e.e. Dim.: dato un programma P∈℘ , esso consiste di una lista di

istruzioni {I1, … , Ih} . Consideriamo la funzione γ(P)=τ(β4(I1), … , β4(Ih))

Essa è tale che P≡(I1, … , Ih) β4 (i1, … , ih) τ γ(P)∈ℵ0

Si ha che γ è composizione di biezioni computabili, da cui γ è una biezione computabile , anzi è addirittura primitiva ricorsiva .

C.V.D.

Teorema L’insieme di tutte le TM è e.e.

Definizione Il simbolo Φa(n) indica la funzione n-aria computata dal programma di codice a . Il suo dominio è Wa(n) , mentre il suo codominio è Ea(n) .

Osservazione Le definizioni date riflettono la più utile conseguenza dell ’aver numerato i programmi, cioè non c’è sostanziale differenza tra dati di input per le URM ed i programmi , dunque è possibile scrivere programmi in grado di manipolare altri programmi (passati come input tramite codice).

Osservazione Consideriamo i tre seguenti insiemi

Si ha che f è suriettiva (ad ogni funzione corrisponde un programma), ma non è iniettiva, visto che più di un programma potrebbe calcolare la stessa funzione, da cui ℘≥C

FUNZIONI COMPUTABILI PROGRAMMI CODICI

f

γ-1

γ

ℵ0

℘

C


33

e ℵ0=℘ dunque C≤ℵ0 Una funzione f: ℵ0 ℵ0 si può definire così

0, 1, … , n, … f=[ f(0), f(1), … , f(n), …]={fn}

dove {fn} è una successione, anche se non nel vero senso della parola, dal momento che potrebbe capitare che f(n)↑, per qualche n . Le stringhe infinite di interi hanno la cardinalità di ℜ , dunque le funzioni f: ℵ0 ℵ0 sono tante quanti sono i numeri reali dunque, essendo ℜ>>ℵ0 , si ha che esistono infinite funzioni non computabili . Per dimostrare ciò faremo uso di una tecnica, detta diagonalizzazione di Cantor , che permette di scrivere infinite funzioni non computabili. Essa è stata utilizzata in Analisi per dimostrare che ℵ⊂ℜ nel seguente modo: si supponga per ASSURDO che non lo sia, allora ha senso dire che esiste {sn} , successione di tutti i numeri reali dove

s1=parte intera,s11s12s13… s2=parte intera,s21s22s23… M

Consideriamo, poi, il numero 0,p11p22p33… con pi i≠si i ∀ i . Questo è un numero reale che è diverso per costruzione da ogni si ∀ i , e ciò è ASSURDO perché avevamo supposto che {sn} fosse la successione di tutti i numeri reali.

Teorema Esiste una funzione unaria totale non computabile. Dim.: si consideri la seguente funzione definita per casi

Φx(x)+1 se Φx(x)↓ f(x)= 0 altrimenti

Essa non è computabile. Per ASSURDO si supponga che f(x) sia computabile e sia Pf un programma che la computi, con xf codice di tale programma. Si ha che ∃xf:

• f(x)= Φxf(x) per ipotesi assurda • f(x)= Φx(x)+1 per definizione

da cui, posto x=xf , si ha che f(xf)= Φxf(xf)= Φxf(xf)+1


34

i l che è ASSURDO . Da ciò si evince che f(x) non è computabile .

C.V.D.

Osservazione Lo schema di definizione usato per f(x) non è corretto perché il predicato Φx(x)↓ è indecidibile.

Diagonalizzazione È stato detto che la tecnica dimostrativa del teorema precedente si chiama diagonalizzazione . Infatti la costruzione della funzione f si può descrivere come segue: si immagini di scrivere la seguente tabella infinita:

LL

LL

LL

LL

LMMMMMM

LL

NMMMMMM

iinputcodici

iii

ij jjjj

210)()2()1()0(0)()2()1()0(1)()2()1()0(2

)()2()1()0(

0000

1111

2222

ΦΦΦΦΦΦΦΦΦΦΦΦ

ΦΦΦΦ

Per i casi in cui la funzione non è definita la tabella contiene un simbolo convenzionale “↑”, oppure “∞”. La funzione f è stata costruita prendendo i valori sulla diagonale di questa tabella e sommando a ciascuno di essi 1 , se Φ j(i)↓ con j=i . Se Φ j(i)↑ con j=i , la f prenderà come valore la 0 . Si è così ottenuta una nuova sequenza [f(0), f(1), f(2), … , f(n), …] che non può, per costruzione, coincidere con nessuna delle sequenze che costituiscono le righe della tabella, corrispondente alle funzioni computabili.

Osservazione Infinite altre funzioni non computabili si possono costruire variando la scelta della costante.


35

Teorema dei parametri o “s-m-n” La codifica dei programmi che calcolano funzioni, le quali dipendono da parametri, varia in maniera primitiva ricorsiva , al variare dei parametri stessi.

Caso di un solo parametro Se {fα} è una famiglia di funzioni computabili del tipo f(x1, … , xm, α) , con α∈ℵ parametro, allora esiste una funzione h(α) primitiva ricorsiva tale che

f(x1, … , xm, α)=Φh(α )(x1, … , xm) Dim.: poiché la funzione f(x1, … , xm, α) è computabile, esiste un

programma Pf che la computa. Esso prende in input m+1 valori

esegue le istruzioni e da l ’output sulla prima casella. Si fissi il parametro α con α ’ e si facciano variare solo le m variabili xi . A tal proposito si prenda un programma

Pf’=(N, Pf) dove N è il seguente programma

T(m, m+1) T(m-1, m) M T(1, 2) Z(1) S(1) M α ’ volte S(1)

ottenendo

dove si fa girare Pf . Si osservi che N non dipende ne dall ’ input ne dal programma. Si ha quindi un programma Pf’ che prende in input solo gli m valori x1, … , xm e che può essere codificato così

γ(Pf’)=k(γ(Pf), α ’, m) con k funzione PR (visto che tutte le operazioni di codifica sono PR).

xm …x2 x1 α

xm …x2 x1 α’


36

Quindi la funzione computata da Pf’ è f(α ’, x1, … , xm)=Φk(m) (e, α ’ ) (x1, … , xm)=Φh(α ’ ) ( x1, … , xm)

poiché e=γ(Pf) è costante. C.V.D.

Osservazione Si ha che al variare di α l ’output dipende solo da x1, … , xm (input) e che i codici dei programmi che via via si ottengono variano in maniera primitiva ricorsiva.

Caso generale Sia f(x1, … , xm, y1, … , yn) una funzione computabile, allora esiste una funzione PR s(t, x1, … , xm) tale che se f è computata da P e γ(P)=e si ha che

f(x1, … , xm, y1, … , yn)= =Φe(x1, … , xm, y1, … , yn)= =Φs(e, x1, … , xm)(y1, … , ym)

Morale del teorema “s-m-n” Funzioni simili sono computate da programmi simili, e più precisamente funzioni che differiscono per uno o più parametri hanno codici legati da funzioni PR.

Corollario Esiste una funzione PR h(n) tale che Φh(n )(x)=xn ∀n . Dim.: sia g(x, n)=xn . Essa è computabile, dunque

g(x, n)=Φk(e, n )(x)=Φh(n)(x) visto che e è fissato.

C.V.D.

Corollario Esiste una funzione PR h(n) tale che Φh(n )(x)=x mod n ∀n . Dim.: analoga alla precedente.

Osservazione Abbiamo visto che We={x∈ℵ: Φe(x)↓} . Generalizzando si ha che

We(m)={(x1, … , xm)∈ℵm: Φe(x1, … , xm)↓}


37

Corollario Esiste una funzione PR h(n) tale che Wh(n) (m)={(y1, … , ym)∈ℵm: y1+…+ym=n} ∀n . Dim.: lo si dimostri per m=2 . Si consideri la funzione

1 se n=y1+y2 g(n, y1, y2)= ↑ altrimenti

che è computabile, da cui g(n, y1, y2)=Φe(n, y1, y2)=Φk(e, n)(y1, y2)=Φh(n )(y1, y2)

i l cui insieme di definizione è Wh(n)(2)={(y1, y2)∈ℵ2: y1+y2=n}

C.V.D.

Definizione Fissato n , definiamo funzione universale di arietà n la seguente funzione:

Ψn=(e, x1, … , xn)=Φe(x1, … , xn) Essa comprende tutte le funzioni computabili di arietà n .

Osservazione Se si riuscisse a dimostrare che la funzione universale di arietà n è computabile, si avrà in mano un programma in grado di simulare qualsiasi altro programma assegnato mediante il codice, cioè un programma universale .

Teorema universale La funzione universale Ψn=(e, x1, … , xn)=Φe(x1, … , xn) è computabile ∀n . Dim.: per provare tale teorema, occorre costruire un programma in

grado di decodificare il codice di un programma e di simularne l ’esecuzione. Tale programma universale non è altro che un interprete che deve tradurre un assegnato codice di Godel, estraendo da esso, passo per passo, le successive istruzioni adatte per una URM. Il piano generale che un programma siffatto deve seguire è il seguente:

1) CODIFICARE UNA CONFIGURAZIONE 2) DECODIFICARE LA CONFIGURAZIONE STESSA


38

3) ESTRARRE LA SUCCESSIVA ISTRUZIONE DA ESEGUIRE 4) COMPUTARE LA SUCCESSIVA CONFIGURAZIONE E

PASSARE AL PASSO 1) . C.V.D.

Lemma La configurazione di una URM, durante l ’esecuzione di un fissato programma, può essere codificata in maniera primitiva ricorsiva da un unico numero non negativo. Dim.: la configurazione di una URM è nota una volta che siano noti i

contenuti dei suoi registri e l ’ indice dell ’ istruzione che deve essere eseguita al passo successivo. Se ρ(P) è il massimo indice dei registri utilizzati da P , i l contenuto dei registri può essere codificato da un unico numero come segue:

c=p1r1p2r2… pρ (P )rρ ( P ) dove pi è l ’i-esimo numero primo. Questa corrispondenza biunivoca, tra tutti i possibili contenuti dei registri e gli interi non negativi, è computabile e, quindi, costituisce un’effettiva codifica. Se j è l ’ indice della successiva istruzione da eseguire, si avrà che:

σ=π(c, j)∈ℵ0 è la codifica computabile della configurazione della URM in ogni istante. Si ha che σ è una codifica che coinvolge solo operazioni primitive ricorsive, quali il prodotto e la pairing function, dunque σ è PR .

C.V.D.

Osservazione A noi interessa sapere, al variare del tempo, come varia la configurazione interna della URM, per eseguire il ciclo presentato nel teorema universale , dunque bisogna considerare la funzione σ(t)=π(c(t), j(t)) , così definita

π(c(0), 1) se t=0 σ(t)= f(σ(t-1)) se t>0

dove


39

π(c(t+1), j(t)+1) se πy-1(σ) è l’indice di una istruzione S, Z o T f(σ(t))= π(c(t), j(t+1)) se πy-1(σ) è l’indice di una istruzione J

È banale verificare che è possibile passare da una configurazione all ’altra in maniera PR.

Istruzione di arresto Per conoscere l ’output del programma universale si ha bisogno di un’istruzione di arresto . Consideriamo il predicato step(t, e, x) . Esso è computabile, si vuole dimostrare che è PR . Per convenzione, se il programma è giunto all ’ istruzione di fine programma nell ’ istante t’ , allora

j(t’)=0 e, inoltre, ∀t≥t’

j(t)=0 e c(t)=c(t’)

da cui σ(t)=σ(t’)

Per sapere, quindi, se step(t, e, x)=1 , bisogna controllare il valore del predicato “ is_null?(j(t))”. Si ha che j(t) è PR, “is_null?” è PR, da cui “is_null?(j(t))” è PR , per composizione di funzioni PR , da cui l ’equivalente step(t, e, x) è PR . Considerata la funzione

arresto(e, x)=min t: step(t, e, x) essa è computabile, ma non PR .

Notazione 1) πx-1(n) restituisce la coppia (x, y) tale che π(x, y)=n 2) exp2(n) restituisce il massimo k tale che n/2k∈ℵ

Esse sono funzioni PR . Si ha che l ’output del programma universale è il seguente

Ψ(e, x)=exp2(πx-1(σ(t’)))= =exp2(πx-1(σ(min t: step(t, e, x))))

e restituisce il contenuto del primo registro.

PR PR PR NON PR PR


40

Osservazione È giusto che Ψ(e, x) abbia qualcosa di non PR, perché essendo un programma universale deve essere in grado di computare tutte le funzioni computabili , che sono più delle funzioni PR.

Corollario (teorema della forma normale di Kleene) Ogni funzione computabile si può ottenere per composizione, ricorsione e l ’applicazione di una sola occorrenza dell ’operatore di minimalizzazione, a partire dalle funzioni iniziali. Dim.: se f(x) è computabile, allora

f(x)=Φe(x)=Ψ(e, x) che, per il teorema universale , si è ottenuta per composizione e ricorsione a partire da funzioni PR, più una sola applicazione dell ’operatore di minimalizzazione.

C.V.D.

Osservazione Dal corollario segue che

CURM⊆Cf da cui, sapendo che

Cf⊆CURM si ha che

Cf=CURM

Funzioni non primitive ricorsive Si è visto che la funzione di Ackermann è un esempio di funzione computabile, totale e non primitiva ricorsiva. Usando il teorema universale si dimostra che esistono infinite funzioni non PR . A tale scopo è necessario osservare meglio in che modo si possono costruire le funzioni PR. Esse possono essere ottenute mediante la combinazione delle operazioni di composizione e ricorsione, a partire dalle funzioni iniziali. L’applicazione di tali operatori, per ottenere una data funzione PR, avviene secondo un piano che si può schematizzare con un diagramma ad albero. Le foglie dell ’albero sono le funzioni iniziali. I nodi interni, a livello superiore, rappresentano le funzioni ottenute per composizione o ricorsione a partire dalle funzioni costruite nei nodi sottostanti. La radice dell ’albero rappresenta la funzione PR desiderata.


41

Esempio Considerata la funzione PR

f(x)=2x+3 si ha che

S(S(Z(n))) se x=1 2x= S(S(2(x-1))) se x>1

e che 3=S(S(S(Z(x)))

e che S(p1(x, y) se y=1 x+y= S(x+(y-1)) se y>1

da cui il piano di costruzione della funzione f potrebbe essere rappresentata da seguente albero:

È abbastanza semplice codificare un albero di costruzione con un intero. Si può, ad esempio, elencare i nodi secondo una procedura

composizione

Z(.)

S(.)

S(.)

S(.)

S(.)

S(.)

Z(.)

S(.)

S(.)

2x

p1(. , .)

S(.)S(.)

2x+3

ricorsione


42

BFS , a partire dalla radice, assegnando a ciascun nodo un codice che indichi che tipo di operazione viene effettuata in tale nodo (scelta della funzione iniziale, composizione o ricorsione). Tale elenco di codici può essere successivamente codificato in un unico numero tramite la funzione τ . Data una funzione PR f , e, quindi, un piano p per la sua computazione, si può introdurre una funzione computabile θ(f, p), che restituisce l ’ intero che codifica tale piano. Dunque, preso n∈ℵ0 , si considera la funzione θ-1(n) , che restituisce la funzione PR, il cui piano di definizione è codificato da n .

Osservazione Così come non esiste un unico programma URM per la computazione di una funzione computabile, non esiste un unico piano per la definizione di una funzione PR. Una funzione PR è comunque computabile ed ha, quindi, diritto ad un programma per la sua computazione. Si ha quindi la seguente catena di funzioni:

ℵ0 →θ-1 {FUNZIONI PR} →γ ℵ0 da cui si definisce la funzione

p(n)=γ(θ-1(n)) che è computabile, per la tesi di Church, visto che è stato descritto un metodo per computarla.

Osservazione La funzione p(n) da il codice di un programma della funzione PR, il cui piano di definizione è n .

Teorema Esiste una funzione computabile e totale che non è PR. Dim.: sia g(x)=Φp(x)(x)+1 .

Si ha che Φp(x)(x) è una funzione totale, perché p(x) è il codice di un programma che calcola una funzione PR, e ogni funzione PR è totale, dunque anche g è totale. Si ha poi che g è computabile, infatti

g(x)=Φp(x)(x)+1= Ψ(p(x), x)+1 { comp. 14243 comp 1442443 comp.


43

Se per ASSURDO g(x) fosse PR, allora esisterebbe un piano di definizione ad essa associato di codice h , da cui

• g(x)=Φp(h)(x) per ipotesi assurda • g(x)=Φp(x)(x)+1 per definizione

Allora in x=h si ha che g(h)=Φp(h)(h)=Φp(h)(h)+1

i l che è ASSURDO , da cui g(x) non è PR . C.V.D.

Corollario Esistono infinite funzioni computabili e totali che non sono PR, al variare della costante che nel teorema aveva valore 1.

Catalogo di predicati indecidibili

1) tot(x) Il predicato

1 se Φx(y)↓ ∀y tot(x)= 0 altrimenti

è indecidibile. Dim.: si supponga per ASSURDO che tot(x) sia decidibile e

consideriamo la funzione: Φx(x)+1 se tot(x)=1 g(x)= 0 altrimenti

Essa è definita per casi e, per ipotesi ASSURDA, il suo predicato discriminante è computabile, dunque g è computabile. Sia e il codice del programma che la computa. Si ha dunque che

• g(x)=Φx(x)+1 per definizione • g(x)=Φe(x) per ipotesi assurda

da cui, posto x=e , si ha che g(e)=Φe(e)+1=Φe(e)

i l che è ASSURDO, dunque il predicato tot(x) è indecidibile.

2) “x∈Wx” Tale predicato equivale al predicato “Φx(x)↓”, ed è indecidibile.


44

Dim.: si supponga per ASSURDO che “x∈Wx” sia decidibile, e sia data

0 se x∉Wx g(x)= ↑ altrimenti

Tale funzione è computabile, perché è definita per casi ed il suo predicato discriminante è decidibile (per ipotesi assurda). Sia m il codice di un programma che computa g , da cui

g(x)=Φm(x) Se m∈Wx, allora, per definizione, si ha che

g(m)=Φm(m)↑ da cui m∉Wx . Se, invece, m∉Wx , allora

g(m)=Φm(m)=0 da cui m∈Wx . Dunque, in ogni caso, si perviene ad un ASSURDO , da cui il predicato “x∈Wx” è indecidibile.

3) halt(x, y) Il predicato

1 se Φx(y)↓ halt(x, y)= 0 altrimenti

è indecidibile. Dim.: si consideri halt(x, x) , che è equivalente a “x∈Wx”, che

è indecidibile, allora halt(x, x) è indecidibile, da cui halt(x, y) , che è più difficile di halt(x, x) , è sicuramente indecidibile. Si è così fatto uso della tecnica della riduzione .

4) “x∈Ey” Tale predicato è indecidibile. Si ricordi che Ey={w: ∃z|Φy(z)↓w} . Dim.: si consideri la funzione

x se x∈Wx f(x)= ↑ altrimenti

Essa è computabile, per la tesi di Church; sia m il codice del programma che la computa, cioè

f(x)=Φm(x) da cui


45

codom(f)=Em Ovviamente, si ha che

x∈Em x∈Wx Se si sapesse decidere “x∈Ey”, si saprebbe decidere anche un suo caso particolare, quale “x∈Em”, e, quindi, anche “x∈Wx”, i l che è ASSURDO, da cui il predicato “x∈Ey” è indecidibile.

5) “Φx≡0” Tale predicato è indecidibile. Dim.: si consideri la funzione

0 se x∈Wx f(x,y)= ↑ altrimenti

Essa è computabile, per la tesi di Church, dunque ∃m: f(x, y)=Φm(x,y)=Φk(x)(y)

Si ha allora che 0 ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

dunque “x∈Wx” “Φk(x)(y)=0 ∀y”

Se M(x)=”Φx≡0” fosse decidibile, allora lo sarebbe anche M(k(x))=”Φk(x)≡0”, visto che k(x) è una funzione PR, dunque anche ”x∈Wx” lo sarebbe, il che è ASSURDO, da cui il predicato “Φx≡0” è indecidibile.

6) P(x, y)=”Φx≡Φy” Tale predicato è indecidibile. Dim.: sia a i l codice di un programma che computa la funzione

identicamente nulla Φa≡0

da cui P(x, a)=”Φx≡0”

Se si sapesse decidere P(x, y), si saprebbe decidere anche il suo particolare caso P(x, a), cioè il caso “Φx≡0”, i l che è ASSURDO, dunque il predicato P(x,y)=”Φx≡Φy” è indecidibile.

7) P(x, y)=”Wx≡Wy” Tale predicato è indecidibile.


46

Dim.: sia y’ il codice di una funzione totale, da cui Wy’≡ℵ

Se si sapesse decidere P(x, y), allora si saprebbe decidere anche P(x, y’)=”Wx≡ℵ”=tot(x) , i l che è ASSURDO, da cui P(x, y)=”Wx≡Wy” è indecidibile.

Osservazione Non è vero che se A è indecidibile lo è pure A∧B . Infatti se consideriamo A∧F , esso è sempre falso, e, quindi, sempre decidibile, a prescindere da A . Ciò vale anche per A∨B .

8) P(x, y)=”Φx(y)=a” Tale predicato è indecidibile. Dim.: sia data la funzione

a se x∈Wx f(x, y)= ↑ altrimenti

che è computabile, per la tesi di Church, allora ∃m: f(x, y)=Φm(x, y)=Φk(x)(y)

e si ha che a ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui “x∈Wx” “Φk(x)(y)=a”

Dunque, se P(x,y) fosse decidibile, allora lo sarebbe anche P(k(x),y) , e quindi anche x∈Wx , il che è ASSURDO, da cui il predicato P(x,y)=”Φx(y)=a” è indecidibile.

9) R(x)=”Φx(x)=0” Tale predicato è indecidibile. Dim.: sia data la funzione

0 se x∈Wx f(x, y)= ↑ altrimenti


e si ha che


47

h ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui, posto y=k(x) , “x∈Wx” “Φk(x)(k(x))=h”

Dunque, se R(x) fosse decidibile, allora lo sarebbe anche R(k(x)) , e quindi anche “x∈Wx”, i l che è ASSURDO, da cui il predicato R(x) è indecidibile.

10) P(x)=”Φx(y) è costante ∀y” Tale predicato è indecidibile. Dim.: si hanno due metodi di dimostrazione

a) sia data la funzione h se x∈Wx f(x, y)= ↑ altrimenti


e si ha che 0 ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui “x∈Wx” “Φk(x)(y)=h”

Dunque, se P(x) fosse decidibile, allora lo sarebbe anche P(k(x)) , e quindi anche “x∈Wx”, il che è ASSURDO, da cui il predicato P(x) è indecidibile.

b) sia data la funzione f(x)=Φx(y)-h

che è computabile, e si ha che “Φx(y)=h ∀y” “f(x)≡0”

da cui il predicato “Φx(y)=h ∀y” è indecidibile.

11) P(x)=”Φx assume solo valori pari” Tale predicato è indecidibile. Dim.: sia data la funzione

2x se x∈Wx f(x, y)= ↑ altrimenti

che è computabile, per la tesi di Church, allora ∃e:


48

f(x, y)=Φe(x, y)=Φk(x)(y) e si ha che

2x ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui “x∈Wx” “Φk(x)(y)=2x”

Dunque, se P(x) fosse decidibile, allora lo sarebbe anche P(k(x)), e quindi anche “x∈Wx”, il che è ASSURDO, da cui il predicato P(x) è indecidibile.

Proprietà A è indecidibile se e solo se ¬A è indecidibile.

12) P(x)=”Wx≠φ” Tale predicato è indecidibile. Dim.: sia data la funzione

1 se x∈Wx f(x, y)= ↑ altrimenti

che è computabile, per la tesi di Church, allora ∃e: f(x, y)=Φe(x, y)=Φk(x)(y)

e si ha che 1 ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui, posto y=k(x) , “x∈Wx” “Wk(x)≠φ”


13) P(x)=”Wx≡φ” Tale predicato è indecidibile. Dim.: dal momento che P(x)=¬”Wx≠φ” , che è indecidibile, per

la proprietà vista precedentemente, il predicato dato è indecidibile.

14) P(x)=”Ex=ℵ” Tale predicato è indecidibile.


49

Dim.: sia data la funzione y se x∈Wx f(x, y)= ↑ altrimenti

che è computabile, per la tesi di Church, allora ∃e: f(x, y)=Φe(x, y)=Φk(x)(y)

e si ha che y ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

dunque ℵ se x∈Wx codom(Φk(x))=Ek(x)= φ se x∉Wx

da cui “x∈Wx” P(k(x))


15) Q(x)=”Ex è infinito” Tale predicato è indecidibile. Dim.: analoga alla precedente.

16) R(x)=”Wx è infinito” Tale predicato è indecidibile. Dim.: analoga alla precedente.

Definizione Sia A⊆B , A si dice sottinsieme non banale di B , se A≠B e A≠φ .

Teorema di Rice Hp.: sia p una proprietà di una funzione computabile unaria. Sia R

l ’ insieme dei codici dei programmi che calcolano le funzioni computabili che godono della proprietà p . Sia R un sottinsieme non banale di ℵ .

Ts.: la proprietà p è indecidibile. Dim.: dal momento che R è non banale, si può supporre che la

funzione fΦ(y)↑ ∀y non goda della proprietà p (se così non


50

fosse si potrebbe considerare la proprietà ¬p , e ripetere lo stesso discorso con il complementare di R in ℵ). Sia g(y) una funzione che goda della proprietà p . Si consideri la funzione

g(y) se x∈Wx f(x, y)= ↑ altrimenti

che è computabile, per la tesi di Church, dunque ∃e: f(x, y)=Φe(x, y)=Φk(x)(y)

e si ha che g(y) ∀y se x∈Wx Φk(x)(y)= ↑ ∀y se x∉Wx

da cui “Φk(x) gode della proprietà p” “x∈Wx”

Dunque, se si potesse decidere P(x)=”x è il codice di una funzione che gode della proprietà p”, si potrebbe decidere anche P(k(x)), e quindi anche “x∈Wx”, il che è ASSURDO, dunque la proprietà p è indecidibile, cioè P(x)=”Φx gode della proprietà p” è un predicato indecidibile.

C.V.D.

Osservazione Il teorema di Rice è utile, perché tramite esso basta portare solo un esempio positivo ed uno negativo di funzione computabile rispetto al predicato in esame per affermare che questo è indecidibile.

Esempio Considerato il predicato P(x)=”Ex è infinito” , sia R={x: P(x)=1} . Sia x’ il codice di un programma che computa la funzione

g1(y)=2y ∀y che ha codominio infinito, si ha allora che

x’∈R Sia poi x’’ il codice di un programma che computa la funzione

g2(y)=2 ∀y che ha codominio {1} , si ha allora che

x’’∉R Da ciò ne viene che R è non banale, dunque, per il teorema di Rice, si ha che il predicato P(x)=”Ex è infinito” è indecidibile.


51

Definizione Il predicato P(x) si dice estensionale quando assume lo stesso valore (V o F) coerentemente su tutti i codici x che computano la medesima funzione.

Teorema di Rice – nuovo enunciato Se P(x) è estensionale, allora è anche indecidibile.

Osservazione Esistono problemi indecidibili in ogni branca della matematica, e, quindi, in ogni scienza moderna di cui la matematica è linguaggio.

Problema della parola nei gruppi Dato un insieme G ed un’operazione associativa binaria

•: G×G → G se

1) esiste un elemento neutro e , tale che a•e=e•a ∀a∈G 2) esiste un unico elemento b, tale che a•b=e ∀a∈G

allora (G, •) si dice gruppo .

Esempio Sia G l ’ insieme dei moti rigidi di un esagono su se stesso:

Si ponga: - a la rotazione di 60° - b la rotazione di 120° - c la rotazione di 180° - d la rotazione di 240° - e la rotazione di 300° - f la rotazione di 360° , cioè f è l ’ identità


52

- g , h , i i ribaltamenti rispetto ai 3 assi Definiamo l ’operazione x•y come “eseguire l’operazione y, e poi l’operazione x”. Quello definito è un gruppo tale che: - a•a=b, cioè a2=b - a3=c - a4=d - a5=e - a6=f - d•e=c - g•g=f Dunque, (G, •) è un gruppo dotato della proprietà di essere generato da un elemento a:

∃m: am=f

Osservazione Il fatto che G è infinito, induce a dire che esistono gruppi infiniti, anche se generati da un numero finito di elementi.

Proposizione Quando in un gruppo esistono un numero finito di generatori ed un numero finito di assiomi (relazioni), allora esso si dice finitamente generato .

Problema “ Dato un gruppo G finitamente generato e data una stringa finita di operazioni (una parola) W=a1a2…an, dove ogni ai è un elemento generatore del gruppo, decidere se W è l ’elemento neutro o no.”

È stato provato nel ’70 da Boom e Nabokov che questo problema è indecidibile.

Osservazione Se (G, •) è un gruppo abeliano, cioè tale che

a•b=b•a allora il problema diventa decidibile.


53

Problema delle equazioni diofantee Le equazioni diofantee sono equazioni polinomiali a coefficienti interi di cui si cercano soluzioni intere.

Problema “Data un’equazione diofantea, vedere se ha soluzioni intere.”

Questo è un problema indecidibile. Vi è un problema diofanteo particolare

Xn+Yn=?Zn EQUAZIONE DI FERMAT per cui solo l ’anno scorso è stato dimostrato che

∄x,y,z∧n>2: Xn+Yn=Zn

Osservazione Se consideriamo il problema dell ’esistenza di radici reali in equazioni polinomiali a coefficienti reali, si ha che esso è decidibile.

Osservazione Finora ci siamo occupati solo della distinzione tra decidibilità e indecidibilità:

Adesso considereremo pure la parziale decidibilità, e si ha che:

Definizione Diremo che il predicato P(x) è parzialmente decidibile se e solo se la funzione

1 se P(x)=1 χ ’P(x)= ↑ altrimenti

INDECIDIBILITÀ DECIDIBILITÀ

INDECIDIBILITÀ DECIDIBILITÀ

PARZIALE DECIDIBILITÀ


54

è computabile.

Osservazione La parziale decidibilità è una generalizzazione della decidibilità. Infatti si ha che un predicato è decidibile se e solo se la funzione

1 se P(x)=1 χP(x)= 0 se P(x)=0

è computabile. Si ha che χP(x) è un caso particolare di χ ’P(x) . In pratica ogni predicato decidibile è anche parzialmente decidibile, ma, in generale, non vale il viceversa.

Esempio Sia P(x)=“x∈Wx”. Si ha che

1 se x∈Wx χ ’P(x)= ↑ altrimenti

è computabile, da cui il predicato P(x)=“x∈Wx” è parzialmente decidibile, ma sappiamo che non è decidibile.

Osservazione Esistono predicati indecidibili che non sono parzialmente decidibili.

Esempio Sia P(x)=”x∉Wx”. Tale predicato è indecidibile, perché P(x)=¬”x∉Wx”. Supponiamo per ASSURDO che sia parzialmente decidibile, allora la funzione

1 se x∉Wx χ ’P(x)= ↑ altrimenti

è computabile, dunque ∃e: χ ’P(x)=Φe(x)

Sia x=e , se e∈We , allora Φe(e)↓

da cui χ ’P(x)=1

da cui e∉We

Se, invece, e∉We , allora


55

Φe(e)↑ da cui

χ ’P(x)↑ da cui

e∈We In ogni caso si perviene ad un ASSURDO, da cui il predicato “x∉Wx” non è parzialmente decidibile.

Esempio Sia “y∈Wx’” con x’ fissato. Esso è indecidibile perché è una generalizzazione di “x’∈Wx’”, che è indecidibile. Inoltre, “x’∈Wx’” è parzialmente decidibile, ma ciò non dice nulla sulla parziale decidibilità di “y∈Wx’”. Il caso vuole comunque che “y∈Wx’” è anche parzialmente decidibile. Infatti, la funzione

1 se y∈Wx’ χ ’P(y)= ↑ altrimenti

è computabile.

Osservazione Questo esempio mostra che la tecnica di riduzione non può essere utilizzata per dimostrare la parziale decidibilità. Si ha però che se si riduce un predicato P(x) ad un altro che non è parzialmente decidibile, allora anche P(x) non è parzialmente decidibile.

Proprietà Il predicato P(x) è parzialmente decidibile se e solo se esiste una funzione g(x) computabile tale che

P(x)=1 g(x)↓ Dim.: ⇒) sia P(x) parzialmente decidibile, allora

1 se P(x)=1 g(x)=χ ’P(x)= ↑ altrimenti

è computabile e si ha che P(x)=1 g(x)↓

⇐) supponiamo che P(x)=1 g(x)↓

con g(x) computabile. Si consideri la funzione


56

1 se P(x)=1 1 se g(x)↓ χ ’ P (x)= = ↑ altrimenti ↑ altrimenti

Siccome g(x) è computabile, allora ∃e: g(x)=Φe(x)

da cui 1 se x∈We χ ’P(x)= ↑ altrimenti

che è una funzione computabile, dunque il predicato P(x) è parzialmente decidibile.

C.V.D.

Proprietà Il predicato P(x) è parzialmente decidibile se e solo se esiste un predicato decidibile R(x, y) tale che

P(x)=1 ∃y: R(x, y) Dim.: ⇒) sia P(x) parzialmente decidibile, allora la funzione

1 se P(x)=1 χ ’P(x)= ↑ altrimenti

è computabile, dunque ∃e: χ ’P(x)=Φe(x)

Si consideri 1 se step(y, e, x) R(x, y)= ↑ altrimenti

che è decidibile. Si ha allora che χ ’P(x)=Φe(x)↓ P(x)=1 ∃y: R(x, y)

⇐) sia R(x, y) computabile e sia P(x)=1 ∃y: R(x, y)

Consideriamo la funzione 1 se P(x)=1 1 se ∃y: R(x, y) χ ’P(x)= = ↑ altrimenti ↑ altrimenti

che è computabile, tramite un algoritmo del tipo: “ Dato x , si prenda y=0 e si verifichi se R(x,0)=1 . Se sì allora OK , altrimenti si


57

consideri y=1 e si ripeta lo stesso ragionamento su R(x,1) , e via dicendo.”

Se ∃y: R(x, y), sicuramente lo si trova con questa ricerca di tipo esaustivo, dunque χ ’P(x) è computabile, e il predicato P(x) è parzialmente decidibile.

C.V.D.

Osservazione Siano A e B predicati decidibili, allora si ha che

• A∧B , A∨B e ¬A sono decidibili; • ∃y: A(x,y) è parzialmente decidibile; • ∀y: A(x,y) è indecidibile.

Proprietà Se A(x, y) è parzialmente decidibile, allora “∃y: A(x,y)” è parzialmente decidibile. Dim.: si consideri la funzione

1 se ∃y: A(x,y) χ ’A(x, y)= ↑ altrimenti

Per vedere se essa è computabile bisogna esibire un algoritmo. Si potrebbe riconsiderare l ’algoritmo della dimostrazione precedente e provare ∀y , in maniera esaustiva, se il predicato A(x, y) è vero o falso. Si noti, però, che il predicato A(x, y) non è decidibile, ma solo parzialmente decidibile, per ipotesi, dunque tale algoritmo, per qualche y , potrebbe non fermarsi. Si consideri allora un nuovo metodo, detto dovetailing:

“ Si consideri il programma che implementa χ ’A(x, y) e lo si esegua sulla coppia (x, 0) per k passi. Se A(x, 0)=1 allora OK , altrimenti si esegua il programma sulla coppia (x, 1) sempre per k passi. Se A(x, 1)=1 allora OK , altrimenti si riconsideri la coppia (x, 0) e si esegua il programma su di essa per 2k passi. Si ripeta il ragionamento fino ad ottenere una risposta positiva. Se ciò non avviene si avrà χ ’A(x, y)↑ .”


58

Questo metodo si può rappresentare anche con la seguente

tabella: dove nella casella [(x, y), nk] si mette 1 se il programma che computa χ ’A(x, y) si è arrestato in nk passi, • altrimenti. Scelta una casella si può decidere in tempo finito qual è il suo contenuto. Per sapere se ∃y: A(x,y) bisogna trovare un 1 in tale tabella, scorrendola in diagonale. Se tale 1 vi è, lo si troverà sicuramente, perché questo è un metodo esaustivo, altrimenti si andrà avanti all'infinito, dunque χ ’A(x, y) è computabile, perciò il predicato ”∃y: A(x,y)” è parzialmente decidibile.

C.V.D.

Proprietà Il predicato P(x) è decidibile se e solo se i predicati P(x) e ¬P(x) sono parzialmente decidibili. Dim.: ⇒) se il predicato P(x) è decidibile, allora P(x) è anche

parzialmente decidibile. Ma se P(x) è decidibile, allora anche ¬P(x) è decidibile, da cui ¬P(x) è anche parzialmente decidibile.

⇐) se P(x) è parzialmente decidibile, allora la funzione 1 se P(x)=1 χ ’P(x)= ↑ altrimenti

è computabile. Parimenti, se ¬P(x) è parzialmente decidibile, allora la funzione

1 se ¬P(x)=1 χ ’¬P(x)= ↑ altrimenti

è computabile.

M

… (x,2) (x,3)(x,1)(x,0)

•

2k

k

3k


59

Si noti che χ ’p e χ ’¬P non sono mai non definite contemporaneamente, ma una delle due si arresterà prima dell ’altra, e permetterà così di dire che l ’altra è falsa, da cui il predicato P(x) è decidibile.

C.V.D.

Esempio Il predicato Q(x)=”x∉Wx” non è parzialmente decidibile. Dim.: si sa che:

• “x∈Wx“ è parzialmente decidibile • “x∈Wx” è indecidibile

Se per ASSURDO “x∉Wx” fosse parzialmente decidibile, allora, per la proprietà precedente, il predicato “x∈Wx” sarebbe decidibile, il che è ASSURDO, da cui il predicato “x∉Wx” non è parzialmente decidibile.

C.V.D.

Esempio Il predicato “Wx=φ” non è parzialmente decidibile. Dim.: si sa che il predicato “Wx=φ” è indecidibile. Si consideri

¬“Wx=φ” “Wx

Teoria della Computazione - Libero.it · 2003. 1. 27. · _ Teoria della Computazione _ 1...

Documents

Transcript of Teoria della Computazione - Libero.it · 2003. 1. 27. · _ Teoria della Computazione _ 1...

Teoria della Computazione - Libero.it · 2003. 1. 27. · _____ Teoria della Computazione _____ 1...

Documents

Transcript of Teoria della Computazione - Libero.it · 2003. 1. 27. · _____ Teoria della Computazione _____ 1...

Teoria della Computazione - Libero.it · 2003. 1. 27. · _ Teoria della Computazione _ 1...

Transcript of Teoria della Computazione - Libero.it · 2003. 1. 27. · _ Teoria della Computazione _ 1...