Pigreco-day 14 marzo 2014
Matematica e Incertezza
Indecidibilità
Limiti della calcolabilità
Prof. Antonio Iarlori
Mathesis Lanciano-Ortona
Esempio di funzione effettivamente calcolabile:
• dato un polinomio di grado n a coefficienti interi
determinare il numero dei suoi zeri interi.
• Trovare, cioè, il numero di soluzioni intere dell’equazione
a 0 x n  a1x n 1  ...  a n 1x1  a n  0 
x  (a 0 x n 1  a1x n 2  ...  a n 1 )  a n
• Un procedimento meccanico ben determinato per
risolvere il problema si ottiene osservando che una
soluzione intera deve essere un
divisore del termine noto.
Trovare le soluzioni intere dell’equazione lineare
a coefficienti interi ax  by  c
*
c  (a , b)q
* * ha  kb  (a , b)
* * * x  qh , y  qk ,
b
* * * *x  x 
n
(a , b )
.
a
y  y
n
(a , b )
c deve essere un multiplo di (a,b)
si trovano con l’algoritmo euclideo del MCD
due interi h, k tali che valga **
Una soluzione particolare
dell’equazione.
Tutte le soluzioni al variare di nZ ottenute
aggiungendo le soluzioni dell’equazione
omogenea associata ax+by=0.
Trovare le soluzioni intere delle terne pitagoriche
a 2  b2  c2
(a , b, c)  1
cerchiamo le terne primitive
* a 2  c 2  b 2  (c  b)(c  b) c,b sono di opposta parità; c-b, c+b coprimi.
Supponiamo a dispari, quindi la scomposizione
a  (m  n)  (m  n)
* *a  (m  n )  (m  n )
2
2
c  b  (m  n ) 2
c  b  (m  n )
b  2mn
c m n
2
2
2
2
sempre possibile. Siano m,n coprimi.
Dal confronto tra * e **
somma e differenza tra ° e °°
è
•Per ciascuno di questi problemi abbiamo diversi
algoritmi risolutivi.
•In matematica si desidera trovare algoritmi per
classi di problemi sempre più ampie.
•Negli esempi citati la classe comune è:
-Soluzioni intere di un’equazione
a coefficienti interi.
•Il matematico David Hilbert elencò
ventitré problemi di cui il decimo
si può formulare così:
-esiste un procedimento effettivo
(algoritmo) per decidere se,
comunque dato un polinomio
con coefficienti interi,
in un numero finito qualunque di variabili,
esso ha radici intere?*
* Si parla di “ procedura di decisione”. Nel caso di risposta negativa, si
dice che il problema posto è indecidibile.
•Per tentare di rispondere a domande di questo tipo
dobbiamo prima di tutto tentare di dare
una definizione rigorosa
di calcolabilità effettiva ( di algoritmo).
•
•
•
•
•
•
La Macchina di Turing
La Macchina di Turing 1
Sommario
• Codifica dei dati
• Macchina Astratta
• Definizioni
• Esempi
Macchina di Turing: Struttura (1)
• È un apparato costituito da:
– un nastro monodimensionale, di lunghezza
infinita, suddiviso in celle, ognuna delle quali
può essere vuota oppure contenere un solo
simbolo.
1
B
B
0
B
– una testina di lettura/scrittura dei simboli
dalle/sulle celle
La testina oltre a leggere/scrivere, si può
spostare di una cella a sinistra, a destra,
oppure può restare ferma.
1
B
B
B
B
B
– una testina di lettura/scrittura dei simboli
dalle/sulle celle
La testina oltre a leggere/scrivere, si può
spostare di una cella a sinistra, a destra,
oppure può restare ferma.
1
B
B
B
B
B
– una testina di lettura/scrittura dei simboli
dalle/sulle celle
La testina oltre a leggere/scrivere, si può
spostare di una cella a sinistra, a destra,
oppure può restare ferma.
1
B
B
B
B
B
Funzionamento (1)
• In ogni fase del calcolo, la testina è posizionata
su una cella del nastro, contenente un simbolo
si  Σ.
• La TM può svolgere una operazione atomica:
– Leggere il simbolo contenuto della cella.
– Scrivere un simbolo (eventualmente vuoto) nella cella.
– Spostare la testina di un passo (a sinistra o a destra).
– Lasciare la testina ferma.
Funzionamento (2)
• La successione degli eventi precedenti
determina in ogni istante uno e un solo stato della
TM (TM deterministica).
– siano q1, q2, …, qn i possibili stati (finiti) di una TM.
• La configurazione di una TM in un dato istante
è la coppia ordinata definita dallo stato corrente qi e
dal simbolo sj puntato dalla testina C = < qi, sj>
nastro
sj
qi
testina
Funzionamento (3)
• Ogni TM è programmata per eseguire uno
specifico calcolo, cioè dispone delle istruzioni per
eseguire quell’unico compito.
• Le istruzioni hanno la forma:
<configurazione>
<operazione atomica>
Nello stato qi la testina legge
Il simbolo sjnella cella puntata
sj
qi
Passa allo stato qh scrive sulla cella il
simbolosk e si sposta a sinistra, a destra,
oppure rimane sulla cella
sk
qh
Definizione Formale
• Una TM è una 7-pla TM=< Q, Σ, Δ, δ, q0, B, F >
– Q insieme finito e non vuoto di stati
– Σ alfabeto della macchina
– Δ alfabeto di input
– δ funzione di transizione
δ : (Q x Σ) → (Q x Σ x{L, R, S})
(con L spostamento a sinistra, R a destra, S stop)
– q0  Q stato iniziale
– B spazio vuoto (blank) = Σ \ Δ.
–F  Q insieme degli stati finali.
Esempio di macchina che TERMINA (T).
La MDT SUCCESSORE riceve in input una sequenza 01001…
che rappresenta un numero in base 2 e lo incrementa di1.
-All’inizio la testina è posizionata sulla cifra più a sinistra;
-si muove quindi verso destra
finché non trova uno spazio bianco;
-va a sinistra di un passo;
-se trova la cifra 0 scrive 1 e si ferma;
-se trova la cifra 1 scrive 0 e va a sinistra di un passo;
-se trova lo spazio bianco B scrive 1 e si ferma.
Esempio di macchina che TERMINA (T).
La MDT SUCCESSORE
Matrice funzionale
Istruzioni
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0, q2,1,S>
<q1,1, q1,0,L>
<q1,B, q2,1,S>
0
1
B
q0 0 R q0 1 R q1 B L
q1 1 S q1 0 L q2 1 S
q0
q1
q2
B
1
q0
1
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
q0
1
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
1
q0
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
1
B
q0
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
1
q1
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
0
q1
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
1
q1
0
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
0
q1
0
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
B
q1
0
0
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q2,1,S>
<q1,1, q1,0,L>
<q1,B,q2,1,S>
1
q2
0
0
B
B
Esempio di macchina che NON TERMINA (NT).
La MDT CONTATORE riceve in input il simbolo 0 che rappresenta il
numero 0 e lo incrementa di1; quindi incrementa di 1 quest’ultimo e così
via scrivendo i numeri naturali in base 2.
-All’inizio la testina è posizionata sulla cella che contiene 0;
-*si muove quindi verso destra finché non trova uno spazio bianco;
-va a sinistra di un passo;
-se trova la cifra 0 scrive 1 e ripete da *;
-se trova la cifra 1 scrive 0 e va a sinistra di un passo;
-se trova lo spazio bianco B scrive 1 e ripete da *.
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
Matrice funzionale
q0
q1
0
1
B
q0 0 R q0 1 R q1 B L
q1 1 R q1 0 L q0 1 R
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
0
q0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,S>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
0
B
q1
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
0
q1
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
1
B
q0
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
1
q1
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,S>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
B
q1
0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
0
q0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
0
B
q0
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
0
q1
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
1
B
q1
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
1
q1
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
1
q1
0
B
B
B
SUCCESSORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,S>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
B
q1
0
0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
q0
0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
0
q0
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
0
B
q0
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
0
q1
B
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
1
B
q1
B
B
CONTATORE
<q0,0, q0,0,R>
<q0,1, q0,1,R>
<q0,B, q1,B,L>
<q1,0,q0,1,R>
<q1,1, q1,0,L>
<q1,B,q0,1,R>
1
0
1
q1
B
B
B
STOP
Tesi di Turing
Nel 1936 Turing propone la seguente ipotesi di
lavoro, nota come Tesi di Turing.
•Una Logical Computing Machine (Turing Machine)
può eseguire qualunque calcolo
puramente meccanico;
• se esiste una procedura effettiva per ottenere il
valore di una funzione matematica, allora tale
funzione è calcolata da una TM.
• Ogni algoritmo può essere espresso da
un’opportuna TM.
•Tutto ciò che è calcolabile lo è attraverso una TM.
Gödelizzazione (1)
Problema: è possibile trattare una TM1
mediante una TM2?
– Le TM elaborano ( ricevono in input)
codifiche di numeri naturali.
– Se riuscissimo a
codificare in numeri naturali il
comportamento di una TM1, allora si potrebbe
definire una TM2 che elabora la prima.
Gödelizzazione (2)
Per codificare una TM è necessario
codificare opportunamente:
– gli stati (finiti);
– i simboli dell’alfabeto di input (finiti);
– gli spostamenti della testina (finiti);
– il blank.
Gödelizzazione (3)
• Sia una TM provvista:
– degli stati q0, q1, q2, …, qn
– dell‘alfabeto di input con simboli s1, s2, …, sm
– del simbolo di blank s0 (B)
– degli spostamenti L, R, S.
• Associamo ad ogni elemento un numero
dispari nel modo seguente:
L R S s0 q0 s1 q1 s2 q2 s3 q3 …
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 3 5 7 9 11 13 15 17 19 21 …
Gödelizzazione di una Istruzione
• Ogni istruzione I può quindi essere associata al
numero naturale g(I) (numero di Gödel)
I
g(I)
L’istruzione I= <q1,s3,q2,s1,L> è associata a
g(I)=213 319 517 711 111
Gödelizzazione della TM
SUCCESSORE.
• La TM SUCCESSORE è provvista
– degli stati q0, q1, q2
– dell‘alfabeto di input con simboli 0,1
– del simbolo di blank B
– degli spostamenti L, R, S
• Associamo ad ogni elemento un numero
dispari nel modo seguente
L R S B q0 0 q1 1 q2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 3 5 7 9 11 13 15 17
Codificazione delle istruzioni della MdT
SUCCESSORE
L R S B q0 0 q 1 1 q 2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 3 5 7 9 11 13 15 17
I1 <q0,0, q0,0,R>
g(I1) = 29∙311∙59∙711∙113
I2 <q0,1, q0,1,R>
g(I2) = 29∙315∙59∙715∙113
I3 <q0,B, q1,B,L>
g(I3) = 29∙37∙513∙77∙111 *
I4 <q1,0,q2,1,S>
g(I4) = 213∙311∙517∙715∙115
I5 <q1,1, q1,0,L>
g(I5) = 213∙315∙513∙711∙111
I6 <q1,B,q2,1,S>
g(I6) = 213∙37∙517∙715∙115
* g(I3) =1.509.541.073.469.000.000.000
Gödelizzazione di una TM
• Dal momento che una TM è identificata
dall’insieme (finito) delle sue istruzioni, allora è
possibile associare a ogni TM uno specifico
numero di Gödel g(TM), ottenuto nel modo
seguente:
– Sia n il numero di istruzioni della TM
– Si moltiplichino le n potenze aventi come base i
primi n numeri primi, e come esponenti, nell’ordine,
i numeri di Gödel delle n istruzioni della TM.
g(I1)
g( TM) =2
g(I2)
∙3
g(I3)
∙5
g(In)
∙ …… ∙ pn
Gödelizzazione di una TM
• L’insieme infinito di tutte le MT è decidibile
tramite il numero di Gödel g(TM).
Dato n  N, esiste un algoritmo finito ( MT) per decidere
se esso è la codificazione di una MT.
• In altre parole, i codici di tutte le MT possono essere
ordinati in un elenco infinito.
L’insieme di tutte le MT è un insieme enumerabile
( ricorsivamente enumerabile).
Gödelizzazione di SUCCESSORE.
– Il numero di istruzioni è 6.
– Si moltiplicano le 6 potenze aventi come base i
primi 6 numeri primi, e come esponenti, nell’ordine,
i numeri di Gödel delle 6 istruzioni di SUCCESSORE.
g(I1)
g( SUCCESSORE) =2
g(I2)
∙3
∙5
g(I3)
g(I4)
g(I5)
∙ 7 ∙ 11
∙
g(I6)
6
Macchina di Turing Universale (1)
• È possibile definire una particolare TM (la UTM)
capace di simulare il comportamento di
qualsiasi altra macchina di Turing M.
Macchina di Turing Universale (1)
• La UTM è una TM che riceve in input:
– la codifica di M = g(M)
– l‘input di M che denotiamo con la lettera I.
• Per ogni M e per ogni I
– La UTM decodifica le quintuple di M ( le istruzioni di M);
– le applica a I (input di M) ottenendo così lo stesso
output di M con input I.
Macchina di Turing Universale (2)
• La UTM è in grado di simulare qualsiasi TM
• Una TM è una macchina specifica per
l’esecuzione di un unico algoritmo
• La UTM è un’evoluzione della TM in quanto è
programmabile: con essa si può eseguire
qualsiasi TM e, quindi, qualsiasi algoritmo
• La UTM rappresenta il passo dalla semplice
computabilità alla programmazione.
Input
MT
I = 0100..
G(MT) = 100011..
I, G(MdT)
UMT
Output
O =10010
O = 10010
Il problema della Fermata (1)
• Stabilire se per ogni MT M e per ogni input I
l’esecuzione di M con input I
- termina oppure
- prosegue all’infinito.
• Il problema è indecidibile:
– Non esiste alcun ALGORITMO (UTM) che,
prendendo in INPUT
una generica MT e un suo generico input I,
produca in OUTPUT un valore che stabilisce se
l’esecuzione di M su I termina o continua all’infinito.
Il problema della Fermata (2)
• Supponiamo per assurdo che il problema della
fermata sia decidibile
• Allora (tesi di Church) esiste una TM Halt che
riceve in input la codifica g(M) di una generica
TM M e un suo generico input I.
• Halt produce in output
– 1 se il calcolo di M con input I termina (T)
– 0 se il calcolo di M con input I non termina (NT)
Input
M
Output
T
I = 0100..
G(M) = 100011..
NT
1
< I, G(M) >
HALT
0
Il problema della Fermata (3)
• Ma se esiste Halt come quella definita allora è
possibile definire un’altra TM Halt1 che riceve
in input g(M) e produce in output
– 1 se il calcolo di M con input g(M) termina
– 0 se il calcolo di M con input g(M) non termina
• Infatti Halt1 è un caso particolare di Halt
– Non ha più in input la coppia <g(M), I>, ma il solo
elemento g(M)
Input
G(M) = 100011..
Output
T
M
NT
1
< G(M) >
HALT1
0
Il problema della Fermata (4)
• Ma se esiste Halt1 come quella definita allora è
possibile definire un’altra TM CONF che
riceve in input la codifica di una TM g(M) e
– produce in output 0, se
•Halt1con input g(M) è 0,
cioè CONF termina con output 0 se
• M con input g(M) non termina.
• CONF(g(M)) = 0 se g(M) = NT;
– genera un calcolo che non termina se
• Halt1 con input g(M) è 1,
cioè CONF non termina se
• M con input g(M) termina.
• CONF(g(M)) = NT se g(M) =T.
Input
G(M) = 100011..
Output
M
T
NT
< G(M) >
HALT1
1
0
0
< G(M) >
CONF
NT
Input
G(M) = 100011..
Output
T
M
NT
NT
< G(M) >
CONF
0
Il problema della Fermata (5)
• CONF è una macchina assurda.
• Se applicata a se stessa, cioè eseguita con input
uguale alla sua stessa codifica g(Conf)
– CONF termina (con output 0) se e solo se
CONF non termina;
– CONF non termina se e solo se
CONF termina.
Input
G(CONF) = 100011..
Output
T
CONF
NT
NT
< G(CONF) >
CONF
0
MACCHINA
M
input
output
I
T
NT
HALT
<G(M),I>
1
0
HALT1
G(M)
1
0
CONF
G(M)
NT
0
CONF
G(CONF)
NT
0