Macchine di Turing e
ricorsività generale
Esempio di MT
• MT1= (Q, S, d, q1, q0)
• Q = {q1; q0}
• S = { | } con una specifica codifica: ogni
numero n è rappresentato con n+1 “|”
Ta
d(q1,|) = (|,d,q1)
daan!
d(q1,s0) = (|,c,q0)
Altro esempio di MT
• MT2 = (Q, S, d, q1, q0)
• Q = {q1; q0}
• S = { | } con la solita codifica: ogni numero
n è rappresentato con n+1 “|”
Ta
d(q1,|) = (s0,d,q1)
daan!
d(q1,s0) = (|,c,q0)
Altro esempio ancora
d(q1,|) = (|,d,q1)
d(q1,s0) = (s0,d,q2)
d(q2,|) = (s0,d,q2)
MT3
d(q2,s0) = (s0,d,q3)
d(q3,|) = (s0,d,q3)
d(q3,s0) = (s0,c,q0)
Ta
daan!
Esempi di MT speciali
•
•
•
•
MT1 implementa la funzione successore
MT2 implementa la funzione zero
MT3 implementa P31...
...ed è facile vedere come qualunque Pnk
possa essere implementata con una MT
• Si dice che le funzioni base sono Turingcomputabili, o T-computabili
...e le altre funzioni?
• Le altre funzioni si ottengono da quelle
base per mezzo di composizione,
ricorsione, e minimalizzazione
• Se dimostriamo che queste operazioni
conservano la T-computabilità, allora
dimostriamo che tutte le funzioni ottenute
sono T-computabili
La composizione
• h(x) = fg(x) = f(g(x))
• Se f e g sono T-computabili, lo è anche h?
• Ossia: se esistono MTf e MTg, si riesce a
costruire MTh?
• Sì: basta mettere insieme le istruzioni di
MTf e di MTg, con l’unico accorgimento di
porre q1h = q1g, q0g = q1f, q0f = q0h
La ricorsione
•
•
•
•
h(0) = k
h(s(x)) = g(x,h(x))
Se g è T-computabile, lo è anche h?
Ossia: avendo a disposizione MTg, si
riesce a costruire MTh?
Sì: è un po’ più complicato che nel caso
della composizione
S include i simboli $1, $2, $3 che sono
usati come separatori
Ricorsione con MT
• Per calcolare h(x), MTh inizia scrivendo
sul nasto (k* rappresenta k+1 barre):
$1
k*
$2
x*
$3
• MTh cancella una barra da x*
• Se zero barre tra $2 e $3, l’output è tra $1
e $2 (perché h(0) = k)
• Altrimenti configura il nastro così:
$1
|
k*
$2 (x-1)* $3
|
k*
Codifica di (0,k)
Ricorsione con MT
• MTh esegue il programma di MTg sulla
parte a destra di $3:
$1
|
k*
$2 (x-1)* $3
|
k*
$2 (x-1)* $3
j*
k*
ottenendo:
$1
|
dove j* è la codifica di j = g(0,k) = h(1)
h(0) = k
h(s(x)) = g(x,h(x))
Ricorsione con MT
• MTh cancella una barra tra $2 e $3, se
non ci sono più barre vuol dire che x=1 e
quindi l’output è j = g(0,k) = h(1), che si
trova a destra di $3:
$1
|
k*
$2
$3
j*
• Altrimenti nuova configurazione e si ripete:
$1
||
j*
$2 (x-2)* $3
||
j*
codifica di (1,j) = (1,h(1))
• Eseguendo MTg a destra di $3 si calcola
g(1,h(1)) = h(2)...e così via fino a h(x)
La minimalizzazione
• f(x) = il più piccolo y: g(x,y)=0
• Dobbiamo costruire MTf usando MTg
• MTf procede eseguendo iterativamente il
codice di MTg per calcolare g(x,0), g(x,1),
g(x,2),...g(x,y) e restituisce in output il
primo y per cui g(x,y)=0
• Se tale y non esiste MTf non si ferma mai
(e infatti f non è definita per quella x)
Minimalizzazione con MT
• MTf configura inizialmente il nastro così:
$1
x*
|
codifica di (x,0)
$2
$3
• Poi copia i dati tra $1 e $2 nello spazio tra
$2 e $3 e lì usa il codice di MTg per
calcolare g(x,0)
• Se il risultato è zero cancella tutto il resto
e lo lascia come output
Minimalizzazione con MT
• Altrimenti MTf riconfigura il nastro così:
$1
x*
||
$2
$3
codifica di (x,1)
e ripete tutto per calcolare g(x,1)
• ...e così via fino a trovare (eventualmente)
il primo y per cui g(x,y)=0
Riassumendo: RG  T-computabile
Ta
daan!
Riesco a implementare
qualsiasi funzione
ricorsiva generale, ossia
ottenuta dalle funzioni
base con composizione,
ricorsione, e
minimalizzazione.
Dubbio...
Ok: se f è RG, allora esiste
una MT che la implementa.
Ma se scrivo una MT
arbitrariamente complicata,
che tipo di funzione viene
computata?
Uhm...
Risposta: RG  T-computabile
• Non esistono funzioni calcolate da una MT
che non siano ricorsive generali
• Si può dimostrare che il programma di una
qualsiasi MT può essere espresso come
una funzione ottenuta dalle funzioni base
con i soliti tre metodi
In altre parole: sono uno
strumento molto potente ma
non fuoriesco da RG
RG  T-computabile
• Dobbiamo dimostrare che ogni funzione
computata da una MT è una funzione RG
• Visto che le funzioni RG sono aritmetiche,
ossia lavorano con i numeri naturali,
dobbiamo innanzitutto codificare gli stati di
una MT
Gödelizzazione degli stati di MT
• MT con alfabeto Σ = {s1,...,sn} nella
seguente situazione
q6
s3 s0 s2 s2 s1 s4 s7 s2 s7
• u (sinistra) = 22 · 30 · 53 (se nastro vuoto: 1)
• v (destra) = 21 · 34 · 57 · 72 · 117
• w (globale) = 2u · 32 · 56 · 7v
Istruzione di MT come funzione
• w è la codifica di uno stato particolare di
una MT
• Eseguendo un’istruzione, MT passa da
uno stato codificato da w a un altro stato,
a cui corrisponde una codifica w’
• Possiamo definire una funzione
aritmentica totale:
w’ se w codifica uno stato non finale
ρMT(w)= w altrimenti
La funzione ρMT
• Il determinismo di MT garantisce che a un
certo w corrisponda uno e un solo w’,
ossia che ρMT sia una funzione
• Si dimostra (ma non lo vedremo) che ρMT
è una funzione ricorsiva primitiva
La funzione θMT
θMT(w,0) = w
θMT(w,s(z)) = ρMT(θMT(w,z))
• Se w è la codifica di uno stato di MT,
θMT(w,z) è la codifica dello stato che si
raggiunge eseguendo z istruzioni di MT
• La funzione θMT è in RP perché è definita
per ricorsione a partire da P11 e ρMT
Da MT a funzione aritmetica
• Data una MT, come facciamo a ricavare
una funzione aritmetica corrispondente?
• Come definire tale funzione sulla base
della MT?
Da MT a funzione aritmetica
1. Dato l’input numerico per la funzione,
codifichiamo la situazione in cui tale input si
trova sul nastro, la testina è nella posizione
standard, e la MT è nello stato iniziale q1:
otteniamo una codifica w
2. Tramite l’operazione di minimalizzazione,
ricaviamo il più piccolo z tale che θMT(w,z)
codifica una situazione finale w’
3. Da w’ ricaviamo lo stato del nastro, su cui è
presente l’output computato dalla MT, che
corrisponderà all’output della funzione
aritmetica
Da MT a funzione aritmetica
• Si dimostra che la procedura nel passi 1,
2, e 3 permette di esprimere la funzione
computata da una MT tramite tutte e sole
le operazioni che generano funzioni
ricorsive generali
• Quindi: a ogni MT corrisponde una
funzione RG
• Ossia: T-computabile  RG
Altro dubbio...
Parlando di me, ci siamo
concentrati sulla
T-computabilità...
...ma come si rapporta la
T-computabilità, che è la
caratteristica di tutte le funzioni
da me computate col concetto
più generale di computabilità?