1
parte 4
7. esempio: controllo parentesi ben formate
per l’ esempio seguente
(macchina di Turing numero sette)
ci servono
alcune definizioni
preliminari
le prossime dieci pagine
sono dedicate a questo...
2
premessa - definizione di un insieme:
un insieme di elementi si puo’ definire in modi diversi,
* elencando tutti gli elementi dell’insieme (se e’ finito...)
es. insieme { 0, 1 }
* fornendo una proprieta’ per gli elementi dell’insieme,
es. insieme degli studenti di ingegneria iscritti al 1.o anno
all’univ. di TS,
* specificando delle regole per produrre gli elementi, ovvero
per costruire (a partire da un elemento dato -uno o piu’)
vediamo un esempio di quest’ ultimo modo di procedere.
3
premessa ... sulle stringhe di caratteri...
(*)
dato un insieme di caratteri C = {a,b,c,d }
definiamo una stringa s come una sequenza di caratteri:
es. s1 = d = stringa di un carattere,
s2 = abba e’ una stringa di 4 caratteri,
s3 = abbccdccbba e’ una stringa di 11 caratteri,
def.: |s| = lunghezza della stringa s = n. di caratteri di s
def.: C * e’ l’insieme di tutte le stringhe che si possono
formare con i caratteri di C
( C * leggi c stellato)
C * = { s | s = stringa di caratteri appartenenti a C }
s1,s2,s3... appartengono a C * , compresa la stringa vuota s0,
n.b.: s0, con |s0| = 0, appartiene a C *
____________________________________
(*){
... } = insieme degli elementi elencati tra le parentesi graffe
4
un primo esempio di un insieme di stringhe:
sia l’insieme di caratteri di partenza
formato dall’unico carattere +
allora
P = { + }
allora l’insieme P stellato
P * = { s | s stringa di caratteri di P }
e’ l’insieme delle stringhe che si possono formare con +
es.:
p0 =
(stringa vuota,
|p0| = 0 )
p1 = +
(stringa di un carattere, |p1| = 1 )
p4 = + + + +
(stringa di 4 caratteri, |p4| = 4 )
p7 = + + + + + + + (stringa di 7 caratteri, |p7| = 7 )
l’insieme P * e’ infinito
5
un secondo esempio di un insieme di stringhe
A = insieme di due caratteri, parentesi aperta e chiusa:
A= { ( ) }
allora l’insieme A stellato ...
A * = { s | s stringa di caratteri di A }
e’ l’ insieme di tutte le stringhe che si possono formare con
le due parentesi, ad es.:
s0 =
(stringa vuota)
sx = (
(stringa di un carattere solo)
sn = ) ) ) )
(stringa di 4 caratteri)
s7 = ( ( ) ( ) ( ) )
(stringa di 8 caratteri)
eccetera...
A * e’ un insieme infinito: il numero di stringhe che si
possono formare con uno o piu’ simboli e’ infinito!
6
continua sugli insiemi di stringhe
consideriamo ad es.: B = { 0 1 } allora l’insieme B stellato
B * = { s | s stringa di caratteri di B } = insieme di tutte
le stringhe che si possono formare con i simboli 0 ed 1:
0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111, ecc
possiamo definire un sottoinsieme X di stringhe di 0 ed 1
aggiungendo una proprieta’ richiesta ad una stringa per
essere considerata un elemento di X ovvero “ben formata”:
X = stringhe s di B *, tali che il numero degli 1 in s e’ pari.
quindi 0, 11, 011, 110, 0011, .., 1111, ... sono elementi di X,
mentre 1, 01, 100, 010, ... , 0010, ... non lo sono;
le stringhe pari 0, 11, .. sono “ben formate”, le altre no.
7
ripetizione ... dei concetti presentati finora
insieme C (finito) di caratteri es { x, y, z } ...
una stringa di caratteri su C es s = xxx ...
|s| = lunghezza della stringa s es |xxx| = 3 ...
C stellato C* = { s con |s| >= 0, e s=stringa di caratt. di C}
da C* definisco altri insiemi X, con X sottoinsieme di C*,
introduco una proprieta’ p che richiedo alle stringhe di X:
l’insieme X e’ caratterizzato dalla proprieta’ p:
definiamo "ben formate" le stringhe di X, cioe’ che sono p,
le stringhe di C* che non sono p non appartengono a X non
sono ben formate. Nell’es. precedente,
B={01}
B *= { s | s stringa di caratteri di B }
X = stringhe s di B *, tali che il numero degli 1 in s e’ pari.
8
cont. stringhe e insiemi e stringhe ben formate ...
es.:
B={01}
B *= { s | s stringa di caratteri di B }
Y = { s | s appart. a B *, |s| = 3 } ovvero:
Y = { 111, 110, 101, 011, 100, 010, 001, 000 }
es.:
D={1}
D *= { s | s stringa di caratteri di D }
W = { s | s appart. a D *, e |s| = 4 }
allora:
W = { 1111 }
e basta: l’insieme W ha un solo elemento.
9
avevamo detto che ...
un insieme di elementi si puo’ definire in modi diversi,
* elencando tutti gli elementi dell’insieme (se e’ finito...)
es. insieme { 0, 1 }
* fornendo una proprieta’ per gli elementi dell’insieme,
es. insieme degli studenti di ingegneria iscritti al 1.o anno
all’univ. di TS,
... abbiamo visto alcuni esempi...
ma si puo’ definire un insieme anche in modo “costruttivo”
o “generativo”,
* specificando delle regole per produrre gli elementi, ovvero
per costruire (a partire da elementi dati) dei nuovi elementi
dell’insieme...
vediamo
10
schema generativo (cont. premesse per la m.d.T nr. 7)
defin.di un insieme di stringhe di parentesi “ben formate”:
base:
[pbf = parentesi ben formate ]
( ) sta in PBF /*/
1.a regola:
se E sta in PBF allora (E) sta in PBF
(es. se ( ) ( ) e’ PBF, allora ( ( ) ( ) ) e’ PBF)
2.a regola:
se E ed F stanno in PBF allora EF sta in PBF
(es. se ( ) e ( ( ) ) sono PBF, allora ( ) ( ( ) ) e’ PBF)
limitazione:
null’altro sta in PBF.
_____________________
/*/ nota: la base ( ) e’ stringa di 2 caratteri, la parentesi aperta “(“ e la “)”
11
cont. schema
generativo (7.es:contr. parentesi ben formate)
12
base: ( ) sta in PBF [ pbf = parentesi ben formate ]
1.a regola: se E sta in PBF allora (E) sta in PBF
2.a regola: se E ed F stanno in PBF allora EF sta in PBF
limitazione: null’altro sta in PBF.
da questo schema generativo possiamo ricavare [fabbricare]
tutte le PBF che vogliamo, partendo dalla stringa di base:
( ) ->1 ( ( ) ) ->1 ( ( ( ) ) ) ->1 ( ( ( ( ) ) ) ) ecc
oppure:
( ) ->2 ( ) ( ) ->1 ( ( ) ( ) ) ->1 ( ( ( ) ( ) ) ) ecc
oppure:
( ) ->2 ( ) ( ) ->2 ( ) ( ) ( ) ->1 ( ( ) ( ) ( ) ) ecc
oppure: ...
( ) ->2 ( ) ( ) ->2 ( ) ( ) ( ) ( ) ->2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )..
parentesi ben formate ... problema:
13
data una stringa di parentesi p , decidere se e’ ben formata
oppure no;
ad es.:
( ), ( ) ( ) ( ), ( ( ( ) ) ), ecc
sono p.b.f.,
( (, ( ( ) ) ( (, ) (, ecc
non sono p.b.f.
un metodo potrebbe essere:
1) calcola la lunghezza della stringa data p, |p|,
2) fabbrica un insieme L di tutte le stringhe ben formate di
lunghezza minore o uguale a |p|
(a partire dalla base, con le regole di derivazione viste),
3) vedi se la stringa data p sta in questo insieme L:
4) se p appartiene a L, allora p e’ ben formata,
altrimenti no
parentesi ben formate - problema di decisione
lo stesso problema puo’ essere risolto in modo piu’ breve,
osservando una proprieta’ fondamentale che hanno tutte le
p.b.f.:
ogni parentesi chiusa e’preceduta da una parentesi aperta
( ), ( ) ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ) ecc
sono p.b.f.,
( (, ( ( ) ) ( (, ) (,
( ) ( ) ( ) ) ecc non sono p.b.f.
es.:
1) cerco la prima ) nella stringa data
(() ())
2) sostituisco la prima parentesi ) con un 1: ( ( 1 ( ) )
3) cerco la prima ( che precede la ) appena cancellata:
4) sostituisco questa ( con un uno:
(11 ())
5) ripeto da 1, e ottengo via via le stringhe
(11 11)
111111
14
parentesi ben formate - problema di decisione
15
questo procedimento [elimina le coppie di parentesi ben
formate, la prima “)” e la “(“ corrispondente davanti ] dara’
0)
1)
1)
1)
1)
1)
1)
(
(
(
(
(
(
1
(
(
1
1
1
1
1
)
1
1
1
1
1
1
(
(
(
(
1
1
1
)
)
)
1
1
1
1
)
)
)
)
)
1
1
-->> la p e’ una p.b.f.
questo procedimento si puo’ formulare in forma di m.d.T.
alla fine scriveremo il risultato su nastro in forma di S (si’)
oppure N (no).
due esempi con stringhe non ben formate:
1) cerco la prima ) nella stringa data
( ) ) )
2) sostituisco la prima parentesi ) con un 1: ( 1 ) )
3) cerco la prima “(“ che precede la “)” appena cancellata:
4) sostituisco questa ( con un uno:
1 1 ) )
5) ripeto da istruzione 1, e ottengo
1 1 1 )
6) torno indietro per cancellare una “(“ - ma non la trovo,
7) fine: la stringa non e’ ben formata - troppe “)”
1) cerco la prima ) nella stringa data
( ( ( )
2) sostituisco la prima parentesi ) con un 1: ( ( ( 1
3) cerco la prima “(“ che precede la “)” appena cancellata:
4) sostituisco questa ( con un uno:
( ( 1 1
5) ripeto da istruzione 1, e non trovo piu’
( ( 1 1
6) nessuna “)”, torno indietro per vedere se
7) vi sono “(“ rimaste: ci sono -> fine, non e’ ben formata
16
7.o esempio di m.d.T.
.. A (
a
a ( a
a ) b
b ( a
a 1 a
b 1 b
1) A (
a
2) A (
[...finalmente...]
( ) ( ) ) A ..
(
1
1
1
1
(
+
+
+
) (
;ricerca della prima )
;trovata,cancella,cerca ( corrisp.
;ripeti... se trovi 1 ignora:
;
; ... avremo la successione:
) ) A .
5) A ( 1 1 ( ) ) A ..
a
( ) ( ) ) A .
6) A ( 1 1 ( ) ) A ..
a
a
3) A ( ( ) ( ) ) A .
7) A ( 1 1 ( ) ) A ..
a
a
4) A ( ( 1 ( ) ) A .
8) A ( 1 1 ( 1 ) A ..
b
b
17
m.d.T.: controllo par.ben form.
.. A (
a
a ( a
a ) b
b ( a
a 1 a
b 1 b
1) A (
a
7) A (
[elimina coppie ( ) ]
( ) ( ) ) A ..
(
1
1
1
1
(
+
+
+
) (
1 1 (
8) A ( 1 1 (
b
9) A ( 1 1 1
;ricerca della prima )
;trovata,cancella,cerca ( corrisp.
;ripeti... se trovi 1 ignora:
;scorri a destra se in a,
;a sin.se in b ... avremo:
) ) A .
10) A ( 1 1 1 1 ) A ..
a
) ) A .. 11) A ( 1 1 1 1 1 A ..
a
b
1 ) A .. 14) A ( 1 1 1 1 1 A ..
b
1 ) A .. 15) A ( 1 1 1 1 1 A ..
a
b
18
7.o esempio di m.d.T.
a
a
b
a
b
1)
[eliminazione coppie ( ) ]
( a ( +
;ricerca della prima )
) b 1 ;trovata,cancella,cerca ( corrisp.
( a 1 +
;ripeti... se trovi 1 ignora:
1 a 1 +
;scorri a destra se in a,
1 b 1 ;a sin.se in b
A ( ( ) ( ) ) A .. situazione iniziale ...
a
15) A ( 1 1 1 1 1 A .. ho elim. l’ultima ), e
b
16) A 1 1 1 1 1 1 A .. elim.anche la ( corrisp.
a
ora cerco se c’e’ancora qualche ) da eliminare
19
m.d.T.: controllo par.ben form.
a
a
b
a
b
(
)
(
1
1
a
b
a
a
b
(
1
1
1
1
+
+
+
-
[elimina coppie ( ) ]
;ricerca della prima )
;trovata,cancella,cerca ( corrisp.
;ripeti... se trovi 1 ignora:
;
; ... avremo la successione:
1) A ( ( ) ( ) ) A ... 14) A ( 1 1 1 1 ) A ..
a
b
15) A ( 1 1 1 1 1 A .. 16) A 1 1 1 1 1 1 A ..
b
a
17) A 1 1 1 1 1 1 A .. 20) A 1 1 1 1 1 1 A ..
a
a
ho finito le ), arrivo fino al delimitatore A
->devo prevedere anche questo caso...mi rimane
da controllare se e’rimasta qualche ( “orfana”
20
es. numero 7 di m.d.T.
a
a
a
a
c
c
1)
(
)
1
A
1
A
A
[controllo finale]
a ( + ;ricerca della prima )
b 1 - ;trovata,cancella,cerca ( corrisp.
a 1 + ;ignoro gli 1 in mezzo...
c A - ;da controllare se e’rimasta una (
c 1 - ;scorri verso sinistra ...
h S 0 ;se non hai trovato nessuna ( ->ok
( ( ) ( ) ) A .
22) A 1 1 1 1 1 1 A ..
a
c
15) A 1 1 1 1 1 1 A .. 26) A 1 1 1 1 1 1 A ..
a
c
20) A 1 1 1 1 1 1 A .. 27) A 1 1 1 1 1 1 A ..
a
c
21) A 1 1 1 1 1 1 A .. 28) S 1 1 1 1 1 1 A ..
c
h
ho esaminato il dato, la risposta e’ si’.
21
es. numero 7 di m.d.T.
situazioni stringa NON ok
.. A ( ( ) ( ) A situazione non ok:
a
applico le regole, arrivo a:
.. A ( 1 1 ( ) A ..cancello la prima ) e la
a
.. sua ( corrispondente ..
.. A ( 1 1 1 1 A ..via la seconda ) e la sua (
a
.. corrispondente
.. A ( 1 1 1 1 A ..cerca ancora qualche )
a .. non c’e’- vai in stato c
.. A ( 1 1 1 1 A ..a controllare se c’e’ una (
c
.. c’e’ !! :
.. A ( 1 1 1 1 A .. se in c trovo una ( allora
c
.. la stringa non e’ok:
c ( h N 0 ;caso di stringa errata / prima era:
c 1 c 1 - ;scorri verso sinistra ...
c A h S 0 ;se non hai trovato nessuna ( -> ok
22
es. numero 7 di m.d.T.
.. A ( ) ( ) )
a
.. A 1 1 ( ) )
a
.. A 1 1 1 1 )
a
.. A 1 1 1 1 1
b
.. A 1 1 1 1 1
b
.. N 1 1 1 1 1
h
A
A
A
A
A
A
situazioni di stringa NON ok
situazione non ok:
applico le regole, arrivo a:
..cancello la prima ) e la (
.. trovo una ) e cancello..
..cont. a cercare una )..
..trovo una ) e la cancello,
.. cerco la sua ( corrispond.
.. che pero’ non trovero’:
..finora avevo: b ( a 1 +
.. e la
b 1 b 1 .. se in stato b trovo A->err
.. agg.quintupla b A h N 0
23
rivediamo le quintuple finora definite
; stato a cerca una ) e cancella
a
a
a
a
(
)
1
A
a
b
a
c
(
1
1
A
+
+
-
;
;
;
;
;
ricerca di una ) - ignora (
trovata,cancella,cerca ( corrisp.
ricerca di una ) - ignora 1
non ho trovato una ), rimane da
controllare se e’rimasta una (
;stato b cerca ( corrispond. a ) gia’cancellata
b
b
b
b
( a 1 +
1 b 1 A h N 0
)
?
;
;
;
;
se
se
se
un
trovi ( cancella e ripeti
trovi 1 ignora:
non trovi ( allora non ok!
caso che NON si puo’presentare
;stato c controlla se c’e’ una ( singola..
c
c
c
c
( h N 0
1 c 1 A h S 0
)
?
;c’e’ una ( orfana-> stringa errata!
;scorri verso sinistra ...
;non ho trovato nessuna ( allora ok
24
25
versione grafica
Stop Si
;a cerca/cancella )
a
a
a
a
(
)
1
A
a
b
a
c
(
1
1
A
+
+
-
;
;
;
;
;b cerca/canc. (
b
b
b
b
( a 1 +
1 b 1 A h N 0
)
?
;
;
;
;
S
b (
A
1
1
a
) + A
A
c
-
(
N
N
;c contr.( rimaste
c
c
c
c
( h N 0
1 c 1 A h S 0
)
?
;
;
;
stop No
stop No
start
7.o esempio di m.d.T. conclusione
L’esempio visto pero’ distrugge i dati:
esercizio: modificare l’algoritmo in modo che la macchina
NON distrugga i dati
(suggerimento: nella verifica delle coppie “)” e “(“ invece
di sostituire entrambe le parentesi con un simbolo, si
cambi la “)” in un simbolo e la “(“ in un simbolo diverso,
per cui alla fine e’ facile ripristinare la situazione iniziale.
26
fine parte 4
fine parte 4
27
parte 5
parte 5
28
due esempi di operazioni di base: 1) muovi uni
dato un nastro: .. 0 0 0 0 0 * 1 1 1 0 0 0 ..
a
spostare gli uni dall’altra parte
cioe’ produrre
.. 0 0 1 1 1 * 0 0 0 0 0 0 ..
h
devo trovare una procedura per ottenere il
risultato voluto..
29
cont. esempio muovi gli uni (m.d.T num.8)
dato un nastro: .. 0 0 0 0 0 * 1 1 1 0 0 0 ..
a
produrre
.. 0 0 1 1 1 * 0 0 0 0 0 0 ..
h
una procedura puo’ essere:
cerco l’ultimo 1 a destra, lo cancello e
scrivo un 1 a sinistra
dopo l’ asterisco;
.. e se inizio a cancellare il primo 1 che
trovo a destra dell’ asterisco?
30
muovi uni: una strategia errata:
la strategia di cancellare il 1.o 1 a destra dell’* e poi riscrivere a
sinistra da’ luogo alla sequenza:
.. 0 0 0 0 0 *
a
.. 0 0 0 0 1 *
a
.. 0 0 0 1 1 *
a
.. 0 0 1 1 1 *
a
.. 0 0 0 0 0 *
1 1 1 0 0 0 .. stato a = cerca 1 a
destra dell’ *
0 1 1 0 0 0 .. scavalco 0 e
cerco 1 a destra
0 0 1 0 0 0 ..
0 0 0 0 0 0 .. vado a cercare 1
0 0 0 0 0 0 .. cerco 1
a
non mi fermo piu’ ...
31
cont. esempio muovi gli uni
dato un nastro: .. 0 0 0 0 0 * 1 1 1 0 0 0 ..
produrre
a
.. 0 0 1 1 1 * 0 0 0 0 0 0 ..
h
cerco l’ultimo
1 a destra:
a
b
b
c
c
*
1
0
1
*
b
b
c
d
h
*
1
0
0
*
+
+
0
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
applicando queste, ho
.. 0 0 0 0 0 * 1 1 0 0 0 0 .. cancellato 1,
d
riscrivo a sin.
32
cont. esempio muovi gli uni
a
b
b
c
c
d
d
d
*
1
0
1
*
*
1
0
b
b
c
d
h
d
d
a
*
1
0
0
*
*
1
1
+
+
0
+
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 (ho spostato un 1) e ripeto
.. 0 0 0 0 0 * 1 1 0 0 0 0 ..
d
.. 0 0 0 0 0 * 1 1 0 0 0 0 ..
d
.. 0 0 0 0 1 * 1 1 0 0 0 0 ..
a
33
a
b
b
c
c
d
d
d
*
1
0
1
*
*
1
0
b
b
c
d
h
d
d
a
*
1
0
0
*
*
1
1
+
+
0
+
;
;
;
;
;
;
;
;
scorri a destra; stato b indica
che sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 e ripeto ...
.. 0 0 0 0 1 * 1 1 0 0
a
.. 0 0 0 0 1 * 1 1 0 0
b
.. 0 0 0 0 1 * 1 1 0 0
c
.. 0 0 0 0 1 * 1 0 0 0
d
0 0 .. cerca ultimo 1..
0 0 .. fine dato a dest
0 0 .. cancella
0 0 .. riscrivi
34
a
b
b
c
c
d
d
d
a
*
1
0
1
*
*
1
0
1
b
b
c
d
h
d
d
a
a
*
1
0
0
*
*
1
1
1
+
+
0
+
+
;
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 e ripeto
se in stato a trovo 1 ignoro ...
.. 0 0 0 0 1 * 1
d
.. 0 0 0 0 1 * 1
d
.. 0 0 0 1 1 * 1
a
.. 0 0 0 1 1 * 1
b
0 0 0 0 0 .. vai a sinistra
0 0 0 0 0 .. riscrivi
0 0 0 0 0 .. e ripeti
0 0 0 0 0 .. di nuovo..
35
a
b
b
c
c
d
d
d
a
*
1
0
1
*
*
1
0
1
b
b
c
d
h
d
d
a
a
*
1
0
0
*
*
1
1
1
+
+
0
+
+
;
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 e ripeto ...
se in stato a trovo 1 ignoro ...
.. 0 0 0 1 1 * 1 0
b
.. 0 0 0 1 1 * 1 0
c
.. 0 0 0 1 1 * 0 0
d
.. 0 0 1 1 1 * 0 0
a
0 0 0 0 .. limite dato
0 0 0 0 .. cancella 1 e poi
0 0 0 0 .. riscrivi 1 a sin.
0 0 0 0 .. ripeti: cerco 1 a des
36
a
b
b
c
c
d
d
d
a
*
1
0
1
*
*
1
0
1
b
b
c
d
h
d
d
a
a
*
1
0
0
*
*
1
1
1
+
+
0
+
+
;
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 e ripeto ...
se in stato a trovo 1 ignoro ...
.. 0 0 1 1 1 * 0 0
a
.. 0 0 1 1 1 * 0 0
b
.. 0 0 1 1 1 * 0 0
c
.. 0 0 1 1 1 * 0 0
h
0 0 0 0 .. ripeti: cerca 1 a des
0 0 0 0 .. limite dato,
0 0 0 0 .. non c’e’ 1 da cancellare, quindi
0 0 0 0 .. stop
37
esempio muovi gli uni ... versione grafica ?
dato un nastro: .. 0 0 0 0 0 * 1 1 1 0 0 0 ..
a
date le quintuple:
a
b
b
c
c
d
d
d
a
*
1
0
1
*
*
1
0
1
b
b
c
d
h
d
d
a
a
==>>
*
1
0
0
*
*
1
1
1
+
+
0
+
+
;
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
non c’e’ nessun 1 a destra->stop
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 e ripeto ...
se in stato a trovo 1 ignoro ...
esercizio !
38
39
versione grafica:
..0 0 0 * 1 1 0 0..
a
date le quintuple:
a
b
b
c
c
d
d
d
a
*
1
0
1
*
*
1
0
1
b
b
c
d
h
d
d
a
a
*
1
0
0
*
*
1
1
1
+
+
0
+
+
;
;
;
;
;
;
;
;
;
a +
1
*
1
1
*
+
b
d 0
1
1
h -
0
1
0
*
0
1
* c
-
due esempi di operazioni di base: 2) test se a=b
ipotesi sulla rappresentazione di dati: in unario, separati da
un *, posiz. iniziale testina in mezzo:
..0 0 1 * 1 1 0 0..
a
schema di soluzione:
fintanto che a>0 e b>0 sottrai 1 ad entrambi
cioe’ fai b <= b-1 e poi fai a <= a-1
quando o a=0 e/o b=0 controlla se entrambi sono zero,
se si’ il test risponde S, se no risponde N.
40
test se a=b
es. con
;
a
b
b
c
;
;
d
d
d
e
a
;
;
(m.d.T num.9)
a=1, b= 2: ..0 0 1 * 1 1 0 0..
sottrai 1 a b:
a
* b * + ; vai a destra
1 b 1 + ; scorri il dato b
0 c 0 - ; oltre il limite di b
1 d 0 - ; cancella un 1 di b (come muovi 1)
ora abbiamo:
..0 0 1 * 1 0 0 0..
ora sottrai 1 ad a:
d
1 d 1 - ; scorri a sinistra
* d * - ; scavalca *,vai a vedere dato a
0 e 0 + ; sei oltre a, ritorna a destra
1 a 0 + ; fatto b-1 e anche a-1 : ripeti
1 a 1 + ; scorri il dato a ... fino all’ *
ora abbiamo:
..0 0 0 * 1 0 0 0..
a
41
test se a=b
b
b
c
d
d
d
e
a
a
*
1
0
0
1
*
0
0
1
+
+
+
+
+
;
;
;
;
;
;
;
;
;
(m.d.T num.9) situazioni finali:
a
b
b
c
d
d
d
e
a
*
1
0
1
1
*
0
1
1
stato iniziale:
0 0 1 * 1 1 0 0..
a
;
;
;
;
e
da fare b-1 (se b=1, dopo b=0),
e poi ancora a-1;
ma dopo aver fatto b-1 trovo che a=0 !
allora era b>0, a=0 quindi aggiungo quintupla
* h < 0 ; scrive risultato a<b
oltre b
b-1
quindi ho: 0 0 1 * 1 0 0 0..
scorri 1 di b
d
scavalca *,
oltre a,
a-1 : quindi ho: 0 0 0 * 1 0 0 0..
scorri a destra
a
42
test se a=b
(m.d.T num.9)
se invece ho stato iniziale: 0 1 1 * 1 0 0..
allora dopo aver fatto
a
b-1 e a-1 avro’la situazione: 0 0 1 * 0 0 0..
ripeto,
a
vado a fare b-1, cioe’
0 0 1 * 0 0 0..
b 0 c 0 - ;per fare b-1
b
c 1 d 0 - ;ma non trovo 1 -> 0 0 1 * 0 0 0..
c * f * - ;trovo * (b=0!)
c
;ora devo controllare se anche a=0 -> stato f:
f 0 h = 0 ;trovo 0 a sin dell’*: anche a=0!
f 1 h > 0 ;c’e’1 a sin.dell’*: allora a>0,b=0
; e abbiamo finito...
43
test se a=b
a
b
b
c
d
d
d
e
a
;
e
c
f
f
(m.d.T num.9) - elenco quintuple
* b * + ;
1 b 1 + ; scorri dato b a destra
0 c 0 - ;
1 d 0 - ; b-1 se possibile
1 d 1 - ; scorri indietro
* d * - ;
0 e 0 + ; fino allo zero a sin. di a
1 a 0 + ; a-1 se possibile
1 a 1 + ; scorri a fino a *
casi finali:
* h < 0 ; scrive risultato a<b
* f * - ;trovo * (b=0!)
c
0 h = 0 ;trovo 0 a sin dell’*: anche a=0!
1 h > 0 ;c’e’1 a sin.dell’*: allora a>0,b=0
44
test se a=b
(m.d.T num.9) - elenco quintuple
a * b * + ; vai a vedere dato b
a 1 a 1 + ; scorri a destra dato a
b 1 b 1 + ; scorri dato b
b 0 c 0 - ; sei oltre b
c 1 d 0 - ; fai b-1 se si puo’
c * f * - ; non si puo’se trovo *, controlla
d 1 d 1 - ; scorri 1 di b
d * d * - ; scavalca *,
d 0 e 0 + ; oltre a,
e 1 a 0 + ; a-1 :
e * h < 0 ; scrive risultato a<b
f 0 h = 0 ; trovo 0 a sin di * -> anche a=0!
f 1 h > 0 ; 1 a sin.dell’*, allora a>0,b=0
si osservi che le quintuple con la coppia s,q=
f * a 0 c 0 e 0 non possono presentarsi
45
cosa si puo’ fare con una m.d.T.
abbiamo cosi’ verificato che
esistono m.di T. per
fare n+1
fare a=b?
fare copia valore di a in altra parte
...
sono le operazioni fondamentali per fare aritmetica intera..
non e’ difficile definire m.d.T. per fare altri “conti”
...
vediamo 2*n
46
calcola 2 * n
dato n calcola r = 2 * n ;
ipotesi: n e’ dato in unario; ad es.
0 0 0 1 1 0 0 0 0 0 0
a
cancello 1 e lo sostituisco con due 1 a destra,
devo avere un simbolo di separazione tra n e r,
ad es. dopo il primo ciclo (fatto n-1, r+2)
0 0 0 0 1 0 1 1 0 0 0
a
dopo il secondo ciclo
0 0 0 0 0 0 1 1 1 1 0
h
abbiamo finito...
47
cont. calcolo di 2 * n ... prima versione
;
;
a
b
b
c
c
d
0 0 1
a
1 b 0
1 b 1
0 c 0
1 c 1
0 d 1
0 e 1
1 0 0 0 0 0 0
;
;
e
e
f
g
g
0 0 0 1 0 1 1 0 0 0
ho cancellato 1 di n e
e
aggiunto due 1 a r;
1 e 1 - ignora 1 di r, scorri verso sinist.
0 f 0 - sullo zero di separazione tra n e r
1 g 1 - se n>0 cerca primo 1 di n, se n=0->fine
1 g 1 - scorri 1 di n a sinistra, fino al 0
0 a 0 + e ripeti ...
+
+
+
+
+
-
cancello 1 e aggiungo
due 1 a destra,
fai n-1 e poi vai a destra a fare r+2
ignora 1 di n, scorri fino a 0 in mezzo
e cambia stato: sto esaminando r
scorri 1 se vi sono gia’(r>0) fino a 0
stato c fai r+1 e poi stato d fai r+1,
quindi r+2; ora ritorna a sinistra:
48
49
cont. prima versione di 2 * n
vers. grafica:
1
+
a
0
+
0
b
+
c
0
1
-
1
g
d
h
0
f
1
0
-
e
0
1
-
+
0
un altro modo di calcolare di 2*n, con - stati e + simboli est.
schema: cambio 1 di n in una x e poi aggiungo a n una x;
alla fine se non vi sono piu’ 1 allora trasformo gli x in 1...
1)0 0 0 1 1 0
a
3)0 0 0 1 1 0
a
4)0 0 0 1 1 0
b
5)0 0 0 1 x 0
c
6)0 0 0 1 x x
d
7)0 0 0 1 x x
d
0 0
0 0
0 0
0 0
0 0
0 0
8)0 0 0 x x x 0 0
c
10)0 0 0 x x x 0 0
c
11)0 0 0 x x x x 0
d
14)0 0 0 x x x x 0
d
15)0 0 0 x x x x 0
e
a=cerca limite 0 a destra
b=cambia 1 in x; c=aggiungi 1
d=cerca a sin.1(cont.)o 0(fine)
50
cont. seconda versione di 2 * n
1)0 0 0 1 1 0 0 0
a
2)0 0 0 1 1 0 0 0
d
14)0 0 0 x x x x 0
d
15)0 0 0 x x x x 0
e
16)0 0 0 1 x x x 0
e
19)0 0 0 1 1 1 1 0
e
20)0 0 0 1 1 1 1 0
h
a=cerca limite zero a destra
b=cambia uno in x,
c=aggiungi 1
d=va a sinistra e controlla:
se trovi 1 continua ->in c
se trovi 0 hai finito-> in e
e=cambia alla fine x in 1
51
cont. seconda versione di 2 * n
esercizi suggeriti:
scrivere le quintuple della seconda versione di 2 * n
disegnare la versione grafica della seconda versione
fine esercizio 2 * n
52
fine parte 5
fine parte 5
53
esercizi da fare
54
altri esercizi suggeriti:
1) m.d.T per fare la somma di due numeri:
ad es. con il dato:
...x 1 1 1 y 1 1 w 0 0 0 0 0 0 0 ...
a
ottenere il risultato:
...x 0 0 0 y 0 0 w 1 1 1 1 1 0 0 ...
h
2) macchina per fare il prodotto di due numeri - si usi ad
esempio una codifica simile a quella suggerita per la somma;
cont. esercizi da fare
3) macchina per compattare una stringa di zeri e uni,
delimitata dal simbolo x. Ad es. dato
...x 1 1 1 0 1 0 1 0 1 1 0 0 1 x 0 0 ...
a
ottengo il risultato (le celle su nastro non sono numerate!) :
... x 1 1 1 1 1 1 1 1 x 0 0 ...
4) macchina elimina (azzera) le coppie di uni su un nastro;
ad esempio a partire da un nastro del tipo:
...x 1 1 1 0 1 1 0 1 1 0 0 1 x 0 0 ...
a
ottengo :
...x 0 0 1 0 0 0 0 0 0 0 0 1 x 0 0 ...
55
cont. esercizi da fare
56
4) macchina che conta le stringhe contenenti una coppia di
zeri, ad es. dal nastro dato:
..x 1 1 1 x 0 0 1 x 0 0 0 x 0 1 0 y 0 0 0..
a
produce:
... y 1 1 z 0 0 0 ....
5) macchina somma due numeri in base dieci; ad esempio a
partire dal nastro
..x 0 9 8 x 1 2 3 x 0 0 0 ..
produce il nastro:
..x 0 9 8 x 1 2 3 x 2 2 1 x
(nota: per calcolare a+b con a,b codificati in base 10 si usi
il procedimento ripeti a<-a+1; b<-b-1 fino_a_che b=0 )
una memoria a indirizzo
Il nastro esterno di una macchina di Turing
e’ composto da celle adiacenti non numerate
per individuare un dato si devono introdurre dei simboli
speciali di marcatura (“delimitatori”):
“cancella il dato che sta tra due celle contenenti w
. . . 0 0 0 w 1 1 1 1 1 1 w 0 0 0 0...
^
^
57
continua la memoria a indirizzo
... la nostra tesi e’ che con le m.d.T. si puo’ fare di tutto:
in particolare,
vediamo ora una m.d.T. che simula il comportamento di
una memoria con celle numerate,
individuabili dal numero di cella di memoria o indirizzo:
cioe’ un “dispositivo” che sa fare le due operazioni di base
per ogni dispositivo di memoria:
scrivi (registra) in memoria un dato DDD all’ indirizzo III
leggi dalla memoria il valore che c’e’ all’indirizzo III
58
continua la memoria a indirizzo
m.d.T. che simula una memoria con “celle” numerate, cioe’
con memoria con dati accessibili specificando un indirizzo:
“cancella il dato nella “cella” di numero 22”:
date tre “celle” di memoria di indirizzo
21, 22 e 23 (con valori 4, 1 e 0 rispett.)
... w 2 1 w 4 w 2 2 w 1 w 2 3 w 0 ...
^ ^
^valore=1, indirizzo=22
dopo l’istruzione detta avremo:
... w 2 1 w 4 w 2 2 w 0 w 2 3 w 0 ...
^
riportiamo di seguito solo parte della soluzione
59
continua la memoria a indirizzo
60
prima parte del problema della memoria a indirizzo:
dato un insieme di stringhe di tre caratteri separate da x e
delimitate da y trovare la stringa uguale alla stringa data:
.. y 0 1 0 x 0 1 1 x 0 1 0 x 1 0 1 y ..
^ ^ ^
| | |
dato
str. a valore coincid.
procedimento: esamino i caratteri della stringa data uno
dopo l’altro, ricordando sia su nastro sia con uno stato di
scorrimento diverso se ho letto un 0 oppure un 1:
cerco poi a destra la prima stringa non ancora esaminata e
vedo se ha gli stessi caratteri:
se si, e’ la stringa cercata, se no, continuo (fino al
delimitatore delle stringe y)
parte della 1.a parte della memoria a indirizzi
per il problema “cerca stringa data tra piu’ stringhe”
vediamo prima come si risolve il sotto-problema (test):
determinare se i = k (con i,k stringhe di tre 0 e 1) :
i
k
.. y 0 1 0 x 0 1 1 y ...
a
all’inizio cambio il dato i a sinistra: gli 0 in A, gli 1 in B:
.. y A B A x 0 1 1 y ...
b
poi vado a confrontare i caratteri di i e di k uno dopo l’altro:
y A B A x 0 1 1 y // y A B A x 0 1 1 y //
^
^
//
^
^
//
y A B A x 0 1 1 y //
^
^
// vediamo...
61
cont. memoria a indirizzi / test i = k ?
confronto i caratteri di i e di k uno dopo l’altro: il primo:
.. y A B A x 0 1 1 y..
b
leggo A, scrivo 0 (per ricordare che l’ho gia’ esaminato),
passo in stato di scorr. a destra c (indica che devo trovare 0),
vado su stringa k a vedere se inizia con uno zero:
.. y 0 B A x 0 1 1 y..
c
la stringa k inizia con 0 (ok), memorizzo (cambio 0 in A), e
poi vado indietro a vedere il secondo carattere:
.. y 0 B A x A 1 1 y.. trovo B, cioe’ 1, memorizzo
b
con lo stato di scorrimento
.. y 0 1 A x A 1 1 y.. a destra “d” -> cerco un 1
d
corrispondente a destra ..
62
cont. mem. a indir. / test i = k ?
confronto i caratteri di
.. y 0 B A x A 1
b
.. y 0 1 A x A 1
d
.. y 0 1 A x A 1
d
.. y 0 1 A x A B
e
.. y 0 1 A x A B
b
.. y 0 1 0 x A B
i (010) e di k (011) uno dopo l’altro:
1 y.. trovo B, cioe’ 1, memorizzo
con lo stato di scorrimento
1 y.. a destra “d” -> cerco un 1
corrispondente a destra ..
1 y.. => secondo caratt.di k = 1
ok: registra (1->B), ripeti
1 y.. e=stato ritorno a sinistra
dopo un test ok;
1 y.. terzo carattere di i ?
trovo A =0, cerco a destra
1 y.. terzo carattere di k ...
c
3.a cifra di k -> non e’ 0!! ->
risposta: le stringhe i e k
non
sono uguali; fine test.
63
cerca stringa “i” data tra piu’ stringhe “kn“
64
procedimento: esamino str. kj sulla destra, fino a che trovo
una kn coincidente a stringa i data, oppure arrivo a y:
y A B A x 0
b
y 0 B A x 0
d
y 0 B A x A
e
y 0 B A x A
b
y 0 1 A x A
1 1 x 0 1 0 x 1 1 1 y
inizio: trovo A cioe’ 0
1 1 x 0 1 0 x 1 1 1 y
cerca 0 corrisp ->trovato
1 1 x 0 1 0 x 1 1 1 y ..ritorna
a sinistra al limite y
1 1 x 0 1 0 x 1 1 1 y ..ripeti
test 2.o car.B cioe’ 1
1 1 x 0 1 0 x 1 1 1 y ..in k1
c
trovo 1 -> ok, registro,
cerca stringa “i” data tra piu’ stringhe “kn“
65
procedimento: esamino str. kj sulla destra, fino a che trovo
una kn coincidente a stringa i data, oppure arrivo a y:
y A B A x 0 1 1 x 0 1 0 x 1 1 1 y
b
situazione di inizio
...trovo le prime due cifre coincidenti:
y 0 1 A x A B 1 x 0 1 0 x 1 1 1 y
e
ritorno a sinis.e vedo la
y 0 1 A x A B 1 x 0 1 0 x 1 1 1 y
terza
b
cifra di i: e’ A cioe’ 0
y 0 1 0 x A B 1 x 0 1 0 x 1 1 1 y ma la 3.a
d
cifra di k1 non e’0-> i#k1
y A B A x A B B x 0 1 0 x 1 1 1 y
rimetto
b
la stringa i come prima,e
segue test i = k2
cerca stringa “i” data tra piu’ stringhe “kn“
66
ho fatto il test i=k1, esito NO, segue i=k2
si noti che k1 risulta marcata “gia’vista”
y A B A x A B B x 0 1 0 x 1 1 1 y
b
si ripete:
i primi due caratteri di i sono 0 1, cerca
i corrisp. caratteri di k2 , sono 0 1 -> ok,
stato dopo il confronto di 2 cifre di i e k2
y 0 1 A x A B B x A B 0 x 1 1 1 y
ora
b
vedo se le 3.e
y 0 1 0 x A B B x A B 0 x 1 1 1 y
cifre
c
sono uguali..
trovo che 3.a(i) = 3.a(k2), e ritorno a sin
y 0 1 0 x A B B x A B A x 1 1 1 y per test
e
su pross. cifra
67
cerca stringa “i” data tra piu’ stringhe “kn“
abbiamo:
y A B A x 0 1 1 x 0 1 0 x 1 1 1 y
b
situazione di inizio
...
y A B A x A B B x 0 1 0 x 1 1 1 y
b
dopo il primo test, i<>k1
y 0 1 0 x A B B x A B A x 1 1 1 y dopo il
test di 3 cifre di i e k2
riprovo con la prossima [4.a] cifra - che non c’e’: in stato b
y 0 1 0 x A B B x A B A x 1 1 1 y
trovo x ->
b
-> concludo che i = k2
mdT(a): cerca stringa “i” tra piu’ stringhe “kn“
start
A
0
a 1
B
1
ccerca 0
y
+
x
A
B
0
+ 0
trovato
A
B
1
1
+
non
trovato
B
y
b test
0
68
x
-
fnok
eok
A
dcerca 1
.. y 0 1 0 x 0 0 0 x 0 1 1 x 0 1 0 x ..y..
grafo della m.d.T che cerca j tale che i = kj con
i = str. data a sin. e kj una delle str. date a destra
+
y
cerca stringa “i” data tra piu’ stringhe “kn“
69
la macchina di turing vista risponde (con qualche modifica)
al problema:
dato un nastro dove c’e’ un archivio di indirizzi (stringhe di
0 e 1 memorizzate con opportuni separatori)
e dato un particolare indirizzo (stringa di 0 e 1)
trovare nell’archivio la posizione con indirizzo uguale (cioe’
marcare tale indirizzo); ad es. da situazione iniziale:
y 0 1 0 x 0 0 0 x 0 0 1 x 0 1 0 x...1 1 1 y
a
situazione finale (caso di indirizzo trovato):
y 0 1 0 x A A A x A A B x A B A x...1 1 1 y
x
da cui..
cerca stringa “i” data tra piu’ stringhe “kn“
la macchina di turing ha per definizione
la memoria esterna ad accesso sequenziale,
(per il nastro, ho a disposizione solo i comandi: sposta la
testina rispetto al nastro di una posizione a destra o a sinistra)
per accedere ad un dato sul nastro devo scorrere (leggere)
tutti i dati tra la posizione corrente della testina ed il dato
richiesto.
la m.d.T. vista (cerca j tale che i = kj con i, k stringhe date)
e’ la premessa per relizzare con la m.d.T. una
“memoria ad accesso diretto”, ovvero per poter avere una
memoria capace di leggere/scrivere un valore in una “cella”
di indirizzo specificato:
70
memoria ad accesso diretto:
71
= memoria capace di leggere / scrivere un valore in una
“cella” di indirizzo specificato:
leggi: x <-- MEM[ indirizzo ]
scrivi: x --> MEM[ indirizzo ]
dove la MEM e’ una memoria di n “celle” numerate,
ciascuna in grado di memorizzare un valore:
123
1
313
001
2
3
MEM[ 4 ] = 313 =>
il valore contenuto
nella cella 4 e’ 313
313
4
456
5
006
6
199
7
995
8
indirizzo del valore 313
contenuto della cella di indirizzo 4
memoria ad accesso diretto:
72
= memoria capace di leggere/scrivere un valore in una “cella”
di indirizzo specificato;
con una m.d.T. simulo una memoria ad accesso diretto con
una codifica del tipo:
y 0 1 0 x 0 0 0 1 1 1 x 0 1 0 1 0 1 x 0 1 1 0 0 1 x
dove 010 = indirizzo del dato richiesto alla “memoria”, e
dove le celle di memoria hanno il formato seguente:
x 0 0 0 1 1 1 x
le prime tre cifre sono l’ indirizzo (qui 000) e le seconde tre
cifre sono il valore (qui 111);
ad es. la cella di indirizzo 010 ha (contiene) il valore 101,
e la cella di indirizzo 011 contiene il valore 001.
m.d.T. “memoria ad accesso diretto”
73
con la memoria di formato visto,
y 0 1 0 x 0 0 0 1 1 1 x 0 1 0 1 0 1 x 0 1 1 0 0 1 x
a
possiamo rispondere alla domanda: qual e’ il valore del dato
di numero (o di indirizzo) 010? (qui e’ 101):
procedimento: dato un indirizzo i (010) cerca tra gli indirizzi
un kj tale che kj = i, con la m.d.T. vista prima:
y 0 1 0 x A A A B B B x A B A 1 0 1 x 0 1 1 0 0 1 x
a
poi copia il dato (cioe’ la stringa 1 0 1) al posto dell’indirizzo i :
y B A B x A A A B B B x A B A B A B x 0 1 1 0 0 1 x
i
mdT (b)/mem.accesso diretto/ parte copia il valore trovato
da m.d.T.(a)
j
-
A
g
+
y
k
1
fine copia
+ 0
1
0
A (copia 0!)
A
x
B
h
y
+
i
74
+
l
B
0
1
B (copia 1!)
fine copia
g cerca primo 0 /1; stati j,h vai a sinist. fino a y (j ricorda 0, h ricor.1);
stati k, i scrivono (k scrive A cioe’0, i scive B cioe’ 1); l scorre fino x limite dell’indir.a
sin.; poi g scorre a dest. fino 0 /1 del dato da copiare;
fine parte 6
fine parte 6
75
La macchina di Turing “U”
ogni macchina di Turing esegue sempre la stessa procedura
per interpretare le istruzioni (le quintuple):
ripeti quanto segue:
1) leggi s da nastro
2) dati s (nastro) e q (stato interno) cerca tra le quintuple
quella che ha questa coppia s,q e ricava s1, q1, d1
[nota: s,q e’ l’indirizzo della quintupla]
3) sostituisci ad s il simbolo s1;
4) cambia stato interno (al posto di q metti q1)
5) sposta la testina secondo la direzione d1
per sempre
questa lista di 5 istruzioni e’ la “procedura di imitazione”
o l’ “algoritmo di imitazione” --->>
76
cont. “U”, una m.d.T. speciale ...
e’ possibile definire una m.d.T. ”U” che sia
in grado di eseguire questo algoritmo di imitazione
cioe’
di imitare il funzionamento di una m.d.T. generica “X”
inoltre
e’ possibile codificare sul nastro di questa m.d.T. ”U”
* sia le quintuple di una (generica) m.d.T. “X”
* sia la situazione su nastro esterno di “X”
ovvero avere una situazione del tipo: (q = stato di “U” )
..nas..M..tro.yqqssxqqssxqqssxqqssxqqssxy
q
77
cont. “U”, una m.d.T. speciale ...
vediamo l a codifica di una m.d.T. generica X sul nastro
della m.d.T. speciale U ; ad es.:
..nas..M..tro.yqqssxqqssxqqssxqqssxqqssxy
q
la porzione yqqssx rappresenta
lo stato corrente della macchina X, ovvero
qq rappresenta lo stato interno q
(di X, rappresentato con qualche codifica, es. in binario),
e ss rappresenta il simbolo letto s dal nastro (di X);
la cella corrente (del nastro di X) e’marcata da un simbolo
apposito M;
il contenuto originale di questa cella (che ora e’ M) e’ salvato
nella codifica ss nella porzione yqqssx del nastro di U;
78
cont. “U”, una m.d.T. speciale ...
cont. codifica di m.d.T. X
79
sul nastro della m.d.T. U :
..nas..M..tro.yqqssxqqssxqqssxqqssxqqssxy
q
qq codifica uno stato di X - ad es. se X ha 4 stati, a,b,c,d, la
codifica puo’ essere:
(a,01; b,10; c,11; d,00)
ss codifica un simbolo esterno di X; - ad es. se X ha 4 simboli
esterni 0,1,*,x, posso avere la codifica:
(0,00; 1,11; *,01; x,10)
con sei stati posso definire ad es. la codifica:
(a,000; b,001; c,010; d,011; e,100; f,101)
ecc
cont. “U”, una m.d.T. speciale ...
80
la m.d.T. “U” o “Universale”
e’ una macchina che in effetti sa eseguire un solo algoritmo,
(come del resto ogni m.d.T., per definizione)
e cioe’
la procedura di imitazione della m.d.T. “X” che e’
codificata sul suo nastro:
“dato stato q corrente e simbolo s corrente [di X!]
codificati subito a destra della cella y sul nastro [di U!]
cerca tra le quintuple [di X] codificate su nastro [di U]
quella che comincia con la coppia q,s uguale; a questo
punto sostituisci q1 al posto di q [sul nastro U, a dest.di y]
e s1 al posto di M [sul nastro di U, dove prima era s], e poi
“sposta” M a destra o a sinistra [sul nastro di U], ovvero
copia s che trovi nella nuova “cella corrente” di X a destra
di y, e metti al suo posto M.
osservazione
di seguito e’ riportata la versione grafica di
una m.d.T. universale,
si lascia come esercizio l’analisi di tale grafo:
si noti che due parti del grafo sono state gia’ esaminate,
e sono rispettivamente la parte
“cerca indirizzo” (mdT(a) a pag. 15 della parte Turing.6)
[locate name nel grafo seguente] e la parte
“copia dato” (mdT(b) a pag 21 della parte Turing.6),
[copy item nel grafo seguente]
...
[vedi M.L. Minsky: "Computation: Finite and Infinite
Machines", Prentice Hall 1967,
(bibl. del DEEI o del Centro Calcolo , ) cap. 6,7,8.]
81
82
locate name (quintuple)
da m.d.T.(a)
start
1
B
a
0
-
B
A
trovato
+
dcerca 10
g
eok
A
non
trovato halt
A
A
B
fnok
y
S +
x
0
-
+
y
i
M 1
-
B
to start (repeat)
1
1
M
1
0
0 +
Replace s with s1,
move position, repeat
A
M
+
-
0
1 B
S
1
0
S
B
0 A
B
B
1
B
B (copa 1!)
fine copia
M
A
+
l
B
0
0
A
A
A
x +
B
- restore machine
condition region
M
A (copia 0!)
M 0
S +
-
+
COPY item, replace name
0 ccerca 0
y
y
1
h
+
0 1
+
+
X
1
B
-
k
0
1
1 b
test
j
A
y
+
fine copia
-
A
1
23 stati, 5 simboli
La macchina di Turing Universale - vers. grafica
applicabile ( mdT applicabile ad un dato)
83
definizione di applicabile
diremo che
una mdT “T” e’ applicabile al dato D
se fatta partire T con un nastro su cui e’ codificato D da’
luogo ad una computazione che finisce in un numero finito di
passi,
ovvero
T e’ applicabile a D se produce in un numero finito di passi
un risultato R.
calcolabile
84
Un algoritmo puo’ essere pensato come una funzione f che a
partire da dei dati (*) produce dei risultati (*) quindi come:
y = f(x) con x (dato) e y(risultato) interi,
diremo che f e’ T calcolabile se esiste una m.d.T. T tale
che fatta partire con un nastro su cui e’ codificato x produce
in un numero finito di passi un nastro su cui e’ codificato y;
diremo che f e’ P calcolabile se esiste un Programma C++
P tale che fatto partire con il dato x produce in un numero
finito di passi il risultato y;
____________________________________________________________________
(*)n.b: un dato (ad es. formato da 1000 numeri in virgola mobile di 10 cifre ciascuno)
puo’ esser sempre pensato codificato come UN UNICO intero ... di 10000 cifre !
-> posso sempre pensare y = f(x) come una funzione da num. intero a num. intero
mdT “T” <=> f(intero) -> intero parziale
85
diremo che f(x)->y e’ T (o P) calcolabile se esiste una m.d.T.
(o un programma C++) applicabile a x e che produce (in un
numero finito di passi) il risultato y;
nota: una mdT “T” puo’ essere applicabile ad alcuni dati,
che chiameremo Da = insieme dati per cui T si ferma,
Da = {d, T(d) si ferma}, ma
non applicabile ad altri: Dn = ins.dati per cui T non ferma:
Dn = {d, T(d) non si ferma}:
Associo ad ogni dato d della mdT “T” un intero k ->
l’insieme degli interi I risulta suddiviso in due sottoinsiemi,
Ka che corrisponde ai dati Da (su cui T e’ applicabile), e
Kn che corrisponde ai dati Dn (su cui T non e’ applicabile)
Ad ogni mdT “T” corrisponde una f(k) che e’ definita per k
appartenenete a Ka, ma non e’ definita per k di Kn.
le m.d.T sono meno potenti del C++?
Si puo’ dimostrare che l’insieme delle funzioni T-calcolabili,
coincide con l’insieme delle funzioni C++ - calcolabili,
cioe’ per ogni mdT esiste un programma C++
corrispondente, e viceversa...
ovvero: i due formalismi sono altrettanto potenti!
Definiamo una procedura effettivamente computabile una
procedura che si puo’ esprimere con una m.d.T. oppure con
un programma C++
algoritmo = procedura effettivamente computabile =
= mdT ( tale che si ferma !! )
= programma C++ ( tale che si ferma !! )
(oppure con uno dei molti formalismi definiti da vari autori,
o con uno dei moltissimi linguaggi di programmazione).
86
tesi di Church:
linguaggi di programmazione...
Ada, Basic, C++, Cobol, Java, Logo, Euclid, Lisp, Modula,
Oberon, Pascal, PL/I, Smalltalk, ... e altri 10000 linguaggi...
formalismi...
di Church, di Kleene, di Markov, di McCarthy, di Post,
di Turing, ...
tesi di Church: sono tutti formalismi di pari potenza
(ipotesi fondamentale della teoria degli algoritmi)
per i formalismi finora costruiti e’ stato dimostrato che
l’insieme delle funzioni calcolabili da ciascuno di essi e’ lo
stesso - anche se non e’ stato dimostrato che non esiste un
formalismo piu’ potente
87
limite ... cosa si puo’ fare con una m.d.T?
88
esistono problemi
(esprimibili in forma adatta per una m.d.T./un progr C++)
non risolubili per via algoritmica, ovvero per i quali non esiste
una m.d.T. (o un programma C++)
osservazione molto semplice:
1) si noti che l’insieme delle funzioni da intero a intero F i ( N ) -> N
{ dove ogni F i fa corrispondere
ad un generico numero intero k un (altro) numero intero m,
se F i e’ definita su k, altrimenti non fa corrispondere nulla }
[ -->> quante sono le possibili coppie (intero - intero) ? ]
cioe’ di TUTTE le possibili funzioni che fanno corrispondere
un numero intero m ad un altro numero intero k
non e’ numerabile!
mdT -> f(i)
// f(i) ->? mdT
l’insieme di TUTTE le funzioni da intero a intero
F i ( N ) -> N non e’ numerabile,
mentre:
l’ insieme delle m.d.T.(o dei progr. C++) e’ numerabile
quindi:
la gran parte delle funzioni da intero a intero NON sono
esprimibili con una m.d.T., ovvero gran parte delle f(i)->i
non ha una mdT corrispondente!
molti problemi NON hanno soluzione algoritmica;
vediamo un esempio di problema non risolubile per via
algoritmica.
89
problema dell’ arresto (halting problem)
90
dato un programma qualunque (data una m.d.T. qualunque)
precisato un dato iniziale (una situazione su nastro)
e’ possibile sapere - analizzando il programma / la mdT se
il processo di calcolo che avra’ luogo - fatto partire il
calcolatore (fatta partire la m.d.T) su quel dato produrra’ un risultato entro un numero finito di passi ?
cioe’ se si fermera’?
cioe’ -se il programma (la m.d.T.) e’ applicabile a quei dati?
91
problema dell’ arresto (halting problem)
problema: “data una mdT X e un nastro dati D, se faccio
partire X con i dati D la mdT X si fermera’ dopo un numero
finito di passi (cioe’ e’ X applicabile a D)?
...000313008x82y1000...
f
(dati D su nastro)
(a,0,...) quintuple
(a,1,...) della
(b,8,...) mdT. X
risposta “ingenua”:
... faccio partire il programma:
se dopo un po’ si ferma allora la m.d.T.X e’ applicabile a quei
dati D, se non si ferma allora X non e’ applicabile a D.
ma ... non e’ una buona risposta! in effetti non posso sapere
se una MdT che lavora da 7531 giorni magari si ferma dopo
il 7532.mo giorno ...
forse si puo’ avere la risposta solo ispezionando, analizzando
problema dell’ arresto (halting problem)
92
problema: “data una mdT X e un nastro dati D, se faccio
partire X con i dati D la mdT X si fermera’ dopo un numero
finito di passi (cioe’ e’ X applicabile a D)?
forse si puo’ avere la risposta solo ispezionando, analizzando
la m.d.T. (chiamiamola mdT”X”) ed i relativi dati ?
esprimiamo il problema cosi’: “ dati una mdT X e un nastro
dati D, e’ possibile sapere
- solo analizzando X e D, senza far partire la macchina se la mdT X, fatta partire con i dati D, si fermera’ dopo
un numero finito di passi ? (cioe’ se X e’ applicabile a D ?)
risposta: non e’ possibile.
segue dimostrazione
93
problema dell’ arresto (halting problem)
il problema dell’arresto non ha soluzione algoritmica,
dimostrazione per assurdo: ipotizzo che esista la soluzione, e
poi dimostro che cio’ porta ad una contraddizione.
ipotizziamo esista una procedura E (magica) ovvero una mdT
E (magica) tale che sappia rispondere alla domanda:
dati macchina di Turing X e dato D, X e’applicabile a D?
cioe’se faccio partire X su D il processo di calcolo sara’ finito?
quindi abbiamo E tale che se codifico X e D sul nastro di E
(abbiamo visto come si codificano X e D per il caso della mdT Universale)
e faccio partire E ottengo la risposta si/no per la domanda se
X e’ applicabile a D.
(n.b.: applico E al nastro dati (di E) dove sono codificati X e D)
problema dell’ arresto (halting problem)
(cont.dim.per assurdo)
94
ipotesi :
esiste una mdT E tale che risponda alla domanda:
X [mdT generica] e’ applicabile a D [dato generico per X]?
E tale che se codifico X e D sul nastro di E
(abbiamo visto come si codificano X e D per il caso della mdT Universale)
e faccio partire E allora ottengo come risultato di E
la risposta si/no per la domanda se X e’ applicabile a D
(si noti che applico E al nastro dati (per E) dove sono codificati X e D) :
(quintuple di E)
(nastro)
...XXXX...DDDD...
problema dell’ arresto (halting problem)
(cont.dim.per assurdo)
95
ipotesi : esiste una mdT E tale che se codifico X e D sul
nastro di E e faccio partire E allora ottengo la risposta si/no
per la domanda se X e’ applicabile a D
(quintuple di E)
(nastro di E)...XXXX...DDDD...
ora, per non avere il fastidio dei doppi dati D,X sul nastro di E
consideriamo il problema piu’ limitato: al posto di un generico
dato D per la mdT X considero un solo dato particolare C,
anzi, scelgo per dato D la rappresentazione stessa di X ...
quindi il problema (piu’ limitato) e’:
X aplicata a X si fermera’?
--------------------------------------------------(*)dal Minsky: applicare X a X ... si immagini la situazione di un tizio che contempla l’
immagine del proprio cervello...
problema dell’ arresto (halting problem)
96
ora la domanda e’: data una mdT X se faccio partire X sul
dato particolare che e’ la codifica stessa di X su un nastro di
una mdT, la X si fermera’?
la situazione iniziale e’: quintuple di X e, sul nastro di X, la
rappres. stessa di X:
...000313008x82y1000...
f
(dati su nastro=codifica di X)
(a,0,...) quintuple
(a,1,...) della
(b,8,...) mdT. X
se faccio partire X sui dati X(= rappresentazione di X) la X si
fermera’?
abbiamo sostituito al problema dell’applicabilita’
<< X e’ applicabile a D ? >> un problema meno generale:
<< X e’ applicabile a X ? >>
cioe’ X applicato a [descrizione di] X si ferma?:
97
problema dell’ arresto (halting problem)
quindi invece della E (magica) di prima,
esiste una mdT E tale che sa rispondere alla domanda:
X [mdT generica] e’ applicabile a D [dato generico per X]?
(1)
E
(mdT) con
...XXX...DDD....
(nastro di E)
ipotizzo l’esistenza di una mdT F (meno potente - ma
sempre “magica” ) in grado di rispondere alla domanda:
X [mdT generica] e’ applicabile a X ?
[X dato particolare per X, cioe’ il dato X e’ la desrizione della stessa X]
(2)
F
(mdT) con
...XXX...FFF....
(nastro di F)
anzi, consideriamo la mdT G tale che basta fornirle la sola
descrizione di X:
(3)
G
(mdT) con
...XXX..........
(nastro di G)
sara’ poi la G stessa a copiare X per avere la situazione (2)
98
problema dell’ arresto (halting problem)
(cont) ipotesi : esiste G tale che
(3)
G
(mdT) con
...XXX..........
(nastro di G)
a partire dal dato XXX e’ in grado di rispondere alla
domanda (con XXX mdT generica):
XXX e’ applicabile al dato XXX ?
per ipot. (da dimostrare assurda) esiste G tale che
o G si ferma nello stato s scrivendo “S” se XXX e’
applicabile a XXX (ovvero XXX si ferma),
o G si ferma in stato n scrivendo “N” se XXX non e’
applicabile a XXX (ovvero XXX non si ferma)
99
problema dell’ arresto (halting problem)
E risponde a: X [mdT qque] e’ applicabile a D [dato qque] ?
(1)
E
(mdT) con
...XXX...DDD....
(nastro di E)
F risponde a: X [mdT generica] e’applicabile a X[un dato] ?
(2)
F
(mdT) e
...XXX...FFF....
(nastro di F)
G copia da X il dato X, poi risponde a: X e’ applicabile a X?
(3)
G
(mdT) e
...XXX..........
(nastro di G)
ora modifichiamo la G un po’: sia K la mdT G modificata
nel senso seguente:
al posto dello stato finale s dove la G scrive “S” [ XXX e’
applicabile a XXX] introduciamo una coppia di stati s,t e
due transizioni tra s e t in ciclo infinito : la K e’ una G ... un
po’ rovinata, nel senso: dove G si fermava per scrivere S,
la K va in ciclo infinito e non si ferma piu’...
problema dell’ arresto (halting problem)
quindi abbiamo una K tale che: se fornisco come dato una
descrizione di una mdT generica X allora K fa:
se X non e’ applicabile a se’ stessa [X non si ferma su X]
allora K si ferma e scrive “N”,
se invece X e’ applicabile a se’ stessa [X si ferma su X]
allora K non si ferma...
[nota: la K NON e’ applicabile alle X che si fermano...]
cosa succede se applico K a se’ stessa?
per ipotesi:
se K applicata a se’ stessa si ferma [K sta ora per X di prima]
allora K applicata a K non si ferma;
se K applicata a se’ stessa NON si ferma [K sta per X di prima]
allora K applicata a K ... si ferma ...
100
problema dell’ arresto (halting problem)
quindi abbiamo: se fornisco a K come dato la descrizione di
una generica X allora K fa: se X non e’ applicabile a se’
stessa allora K si ferma e scrive “N”, se invece X e’
applicabile a se’ stessa [X si ferma su X] allora K non si
ferma; cioe’ la K NON e’ applicabile alle X che si fermano.
cosa succede se applico K a se’ stessa?
per ipotesi:
se K applicata a se’ stessa si ferma [K sta ora per X di prima]
allora K applicata a K non si ferma;
se K applicata a se’ stessa NON si ferma [K sta per X di prima]
allora K applicata a K ... si ferma ...
siamo in contraddizione !!!
101
problema dell’ arresto (halting problem)
102
partendo dall’ipotesi dell’esistenza della macchina magica G
che risponde si o no al problema dell’arresto di una mdT
generica X su un dato particolare (la descriz.della X stessa),
siamo poi passati alla G modificata K (che non e’ applicabile
alle XXX che si fermano), e siamo arrivati ad una
contraddizione: quindi
non puo’ esistere K e quindi non puo’ esistere G ... quindi
il problema dell’arresto NON e’ risolubile per via
algoritmica!
___________________
dal Minsky:
“we have only the deepest sympathy for those readers who have not
encountered this type of simple yet mind-boggling argument before”
problema dell’ arresto (halting problem)
ovvero: dato un generico programma P non e’ possibile
determinare con un programma “magico” G se il
programma P e’ applicabile ad un dato generico D
ovvero: il problema dell’arresto non e’ risolubile per via
algoritmica
ovvero: non c’e’ una procedura effettiva (un algoritmo, una
mdT, un programma C++...) per stabilire se una procedura
X e’ realmente effettiva (algoritmo che si ferma in un
numero finito di passi) oppure no.
ovvero: non e’ possibile costruire un programma G tale che
esso solo leggendo il testo di un generico programma X
risponda: si’, questo programma funziona, oppure non,
questo programma non funziona ...
103
problema dell’ arresto (halting problem)
ma attenzione - se e’ vero che:
dato un generico programma P non e’ possibile determinare
con un programma “magico” G se il programma P e’
applicabile ad un dato generico D cioe’ se si fermera’ questo non significa che non esistano particolari tipi di
programmi / dati per i quali invece esiste la soluzione
ovvero: il problema dell’arresto per un programma
qualunque applicato ad un dato qualunque e’ troppo
generale per avere una soluzione algoritmica, ma ...
esistono casi particolari per i quali esiste una soluzione
algoritmica.
104
problema dell’ arresto (halting problem)
nota:
il fatto che esistono problemi non risolubili per via
algoritmica pone un limite a quello che si puo’ fare con gli
algoritmi (e con i calcolatori);
questo tipicamente succede per problemi di natura troppo
generale;
rimane da stabilire di volta in volta se un particolare
problema e’ risolubile...
sara’ oggetto del nostro corso lo studio della soluzione di
alcuni problemi ben delimitati ...
105
riassumiamo alcuni concetti:
106
procedura di calcolo=lista di istruzioni=progr.C++=mdT
mdT: stato iniziale: nastro con dati D, stato q e posiz.testina.
istruzioni: quintuple; mdT applicabile a D se si ferma;
processo di calcolo = procedimento di calcolo =
insieme degli stati di una mdT,
dal primo (stato iniziale, con il dato di partenza)
all’ultimo (stato finale, con il risultato)
riassumiamo alcuni concetti:
algoritmo = discrizione completa, eseguibile, finita, non
ambigua di un procedimento di calcolo che a partire da
dei dati D da’ luogo ad un procedimento di calcolo finito,
che in un numero finito di passi produce un risultato R.
algoritmo = una mdT X che a partire da dei dati D si
ferma e produce un risult. R in un n.ro finito di passi
(X e’ applicabile a D);
algoritmo = una mdT applicabile
= procedura effettivamente computabile
107
fine parte 7
e con questo concludiamo
questo capitolo sugli
algoritmi e sulle
macchine di Turing
108
109
fine parte 7