contenuto:
1
MdT - parte seconda
ancora alcune macchine di Turing
per risolvere semplici problemi :
8) controllo parentesi ben formate (slide 14)
9) sposta un dato su nastro (slide 27)
10) confronto di due valori interi e test <, =, > (slide
39)
11) dato un numero n calcola il valore 2*n (slide 48)
12) cerca stringa di simboli s2 uguale a una stringa
data s1
(slide 57)
13) una "memoria ad accesso diretto" (slide 65)
xx) la macchina di Turing programmabile o universale
8. esempio: controllo parentesi ben
formate
per l’ esempio seguente
(macchina di Turing numero otto)
ci servono
alcune definizioni
preliminari
le prossime dieci pagine
sono dedicate a questo...
2
premessa - definizione di un
insieme:
3
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’) sistema "generativo"
premessa ... sulle stringhe di caratteri...
4
(*)
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,
definiz: |s| = lunghezza della stringa s = n. di caratteri
di s
definiz: 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 }
anche la stringa vuota s0 appartiene a a C * :
s0, con |s0| = 0, appartiene a C *
____________________________________
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| =
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 }
e' l' 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
posso definire un X sottoinsieme di B* (di stringhe di 0
ed 1) aggiungendo una proprieta’ richiesta ad una
stringa per essere considerata un elemento di X ovvero
“ben formata”:
es.: 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
7
ripetizione ... dei concetti presentati
finora
8
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*,
introducendo una proprieta’p che chiedo 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}
*
cont. stringhe e insiemi e stringhe ben formate
...
es.:
B={01}
B *= { s | s qualunque stringa di caratteri di B }
Y = { s | s appart. a B * e tale che |s| = 3 }
ovvero:
Y = { 111, 110, 101, 011, 100, 010, 001, 000 }
9
es.:
D={1}
D *= { s | s stringa di caratteri di D }
D * = { 1, 11, 111, 1111, 11111, 111111, 1111111, ... }
W = { s | dove s appartiene a D *, e dove |s| = 4 }
allora:
W = { 1111 }
avevamo detto che ...
10
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... sistema generativo ...
schema generativo (cont. premesse per la m.d.T nr. 8)
defin.di un insieme di stringhe di parentesi “ben
formate”:
base:
( ) sta in PBF
/*/
[pbf = parentesi ben
formate ]
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)
11
cont. schema
generativo
(sistema formale generativo)
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
( a ->1 b significa: applico la regola 1 alla stringa a, e ricavo la
stringa b)
oppure:
( ) ->2 ( ) ( ) ->1 ( ( ) ( ) ) ->1 ( ( ( ) ( ) ) ) ecc
oppure:
( ) -> ( ) ( ) -> ( ) ( ) ( ) -> ( ( ) ( ) ( ) ) ecc
12
parentesi ben formate ... problema:
13
data una stringa di parentesi p , decidere se e’ ben
formata oppure no, ovvero decidere se appartiene
all'insieme PBF
ad es.:
( ), ( ) ( ) ( ), ( ( ( ) ) ), ecc
sono p.b.f.
( (, ( ( ) ) ( (, ) (, ecc
non sono p.b.f.
un metodo per decidere 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.
questo metodo funziona perche' vi sono solo regole che allungano
parentesi ben formate - problema di
decisione
14
MA - 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
e ogni parentesi aperta e' seguita da una chiusa:
( ), ( ) ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ) 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 ())
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).
se alla fine rimangono delle parentesi aperte oppure non
due esempi con stringhe non ben formate:
16
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) ora torno indietro per cancellare una “(“ -ma non la
trovo,
7) allora 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
8.) m.d.T.: controllo parentesi ben formate
.. A ( ( ) ( ) ) A ..
a
a ( a ( + ; ricerca della prima ), scorri le
(
a ) b 1 - ; trovata ),cancella,cerca (
corrisp.
b ( a 1 + ; trovata ( ...
a 1 a 1 + ; se trovi 1 ignora:
b 1 b 1 - ; se trovi 1 ignora:
avremo la successione:
1) A ( ( ) ( ) ) A .
5) A ( 1 1 ( ) ) A ..
a
a
2) 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 ..
17
8.) m.d.T.: controllo par.ben form.
[elimina coppie ( )
]
.. A ( (
a
a ( a (
a ) b 1
corrisp.
b ( a 1
cercato!
a 1 a 1
b 1 b 1
1) A ( (
a
7) A ( 1
) ( ) ) A ..
+
-
;ricerca della prima )
;trovata,cancella,cerca (
+
;se in b trovi ( e'il paio
+
;scorri a destra se in a,
;a sin.se in b ... avremo:
) ( ) ) A .
10) A ( 1 1 1 1 )
a
1 ( ) ) A ..
11) A ( 1 1 1 1 1
a
b
8) A ( 1 1 ( 1 ) A ..
14) A ( 1 1 1 1 1
b
b
9) A ( 1 1 1 1 ) A ..
15) A ( 1 1 1 1 1
a
b
A ..
A ..
A ..
A ..
18
8.) m.d.T.: controllo par.ben form.
[elimina coppie ( )
19
]
a
a
b
a
b
b
a
(
)
(
1
1
A
A
a
b
a
a
b
h
c
(
1
1
1
1
N
A
+
+
+
0
-
;ricerca della prima )
;trovata,cancella,cerca ( corrisp.
;ripeti... se trovi 1 ignora:
;
; ... avremo la successione:
; se non trovi ( allora non ok!
;
1) A ( ( ) ( ) ) A ...
..
a
15) A ( 1 1 1 1 1 A ..
b
16) A 1 1 1 1 1 1 A ..
..
a
17) A 1 1 1 1 1 1 A
a
...
20) A 1 1 1 1 1 1 A
a
8.) m.d.T.: controllo par.ben form. [controllo finale]
a ( a (
a ) b 1
a 1 a 1
a A c A
trovata
+
+
-
c 1 c 1 c A h S 0
;
;
;
;
20
ricerca della prima )
trovata,cancella,cerca ( corrisp.
ignoro gli 1 in mezzo...
stato a,va a destra, nessuna )
; da controllare se e’rimasta una (
; scorri verso sinistra ...
; se non hai trovato nessuna ( -> ok
1) A ( ( ) ( ) ) A .
a
15) A 1 1 1 1 1 1 A ..
a
20) A 1 1 1 1 1 1 A ..
a
21) A 1 1 1 1 1 1 A ..
c
22) A 1 1 1 1 1
c
26) A 1 1 1 1 1
c
27) A 1 1 1 1 1
c
28) S 1 1 1 1 1
h
1 A ..
1 A ..
1 A ..
1 A ..
8) m.d.T. controllo par.ben form. situazioni stringa
NON
ok
quintuple:
c 1 c 1 c A h S 0
c ( h N 0
;scorri verso sinistra ...
;se non hai trovato nessuna ( -> ok
;caso di stringa errata
esempio di stringa non ben formata:
.. A ( ( ) ( ) A
a
.. A ( 1 1 ( ) A
a
.. A ( 1 1 1 1 A
a
.. A ( 1 1 1 1 A
a
.. A ( 1 1 1 1 A
c
)
.. A ( 1 1 1 1 A
situazione non ok:
applico le regole, arrivo a:
..cancello la prima ) e la
.. sua ( corrispondente ..
..via la seconda ) e la sua (
.. corrispondente
..cerca ancora qualche )
.. non c’e’- vai in stato c
..a controllare se c’e’ una (
.. c’e’ una ( e non c'e'piu'
.. se in c trovo una ( allora
21
8) m.d.T. par.ben formate - 2 caso di stringa
NON ok
altro esempio di stringa non ben formata:
.. A ( ) ( ) )
a
a:
.. A 1 1 ( ) )
a
.. A 1 1 1 1 )
a
.. A 1 1 1 1 1
corrispond.
b
.. A 1 1 1 1 1
b
.. N 1 1 1 1 1
>err
A
A
A
A
A
A
situazione non ok:
applico le regole, arrivo
..cancello la prima ) e la (
.. trovo una ) e cancello..
..cont. a cercare una )..
..trovo una ) e la cancello,
.. cerco la sua (
.. che pero’ non
..finora avevo:
.. e la
.. se in stato b
trovero’:
b ( a 1 +
b 1 b 1 trovo A-
22
8) m.d.T. par.ben formate
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. ad una ) 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 ( h N 0
errata!
c 1 c 1 c A h S 0
;c’e’ una ( orfana-> stringa
;scorri verso sinistra ...
;non ho trovato nessuna ( allora ok
23
24
versione grafica di questa MdT:
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
(
1
A
)
a 1 + ;
b 1 - ;
b
h N 0 ;
;caso imposs.
1
(
-
S
A
1
A
) + A
a
c
(
N
N
;c contr.( rimaste
c ( h N 0 ;
c 1 c 1 - ;
c A h S 0 ;
c ) ; caso
imposs.
stop No
stop No
start
nel grafico non sono segnate le
transizioni a1 a1 +; b1 b1 -; c1 c1-
8.o esempio di m.d.T. osservazione finale:
L’esempio visto pero’ distrugge i dati:
esercizio: modificare l’algoritmo in modo che la
macchina NON distrugga i dati
(provare da soli...)
(suggerimento: nella verifica delle coppie “)” e “(“
invece di sostituire entrambe le parentesi con un
simbolo, si cambi la “)” in un simbolo x e la “(“ in un
simbolo diverso y, e alla fine sara' facile ripristinare
la situazione iniziale.
25
Macchine di Turing
26
Abbiamo visto che una MdT puo' realizzare alcune
procedure di calcolo semplici,
riempi il nastro di uni,
come incrementa un numero n di uno,
controlla se il numero di uni in una stringa di zeri e uni e'
pari
controlla se una stringa di ( e di ) e' ben formata;
vediamo ancora qualche esempio di MdT che realizzano
alcune operazioni tipiche di tutti i calcolatori:
sposta un dato,
test se un due numeri sono uguali,
ecc
MdT numero 9 : sposta (muovi) uni
due esempi di operazioni di base:
MdT numero 9 : sposta (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..
27
MdT numero 9 : sposta (muovi) uni
28
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 il primo 1 che trovo a destra dell’
asterisco, lo cancello e scrivo un 1 a
sinistra dopo l’ asterisco:
.. 0 0 0 0 1 * 0 1 1 0 0 0
prossimo
a
*
.. 0 0 0 1 1 * 0 0 1 0 0 0
a
poi cerco il
uno a destra dell'
lo cancello e lo
scrivo a sinistra
MdT numero 9 : sposta (muovi) uni
29
una strategia: cancello il primo 1 a destra dell’ * e riscrivo 1 a
sinistra
.. 0 0 0 0 0 *
dell'*
a
trovo
.. 0 0 0 0 0 *
sinistra
c
.. 0 0 0 0 0 *
d
d
.. 0 0 0 0 1 *
poi
e
all' *,
.. 0 0 0 0 1 *
1 1 1 0 0 0 .. stato a cerca 1 a destra
cancello il primo uno che
0 1 1 0 0 0 .. sono in stato c, vai a
e cerca l' *
0 1 1 0 0 0 .. scavalco *, passo in stato
cerco 0 a sinistra dell'*
0 1 1 0 0 0 .. in stato d cambio 0 in 1,
in stato e a destra fino
0 1 1 0 0 0 .. ripeto: cerca 1, cancella e
a
porta 1 a sinistra:
.. 0 0 0 1 1 * 0 0 1 0 0 0 .. in stato d il 1.o zero a
sinist
MdT numero 9 : sposta (muovi) uni
30
una strategia: cancello il primo 1 a destra dell’ * e riscrivo 1 a
sinistra
.. 0 0 0 0 0 *
dell'*
a
una x
.. 0 0 0 0 0 *
c
.. 0 0 0 0 0 *
c
c
.. 0 0 0 0 1 *
poi
e
di *
.. 0 0 0 0 1 *
1,cancella,
1 1 1 0 0 0 .. stato a cerca 1 a destra
sostituisco il primo 1 con
x 1 1 0 0 0 .. stato c vai a sinistra
e cerca l' *
x 1 1 0 0 0 .. scavalco 0, sempre in stato
cerco 0 a sinistra dell'* e
x 1 1 0 0 0 .. in stato c cambio 0 in 1,
in stato e scorri 1 a sin
x 1 1 0 0 0 .. ripeto: in a, cerca
a
e porta 1 a sinistra:
.. 0 0 0 1 1 * x x 1 0 0 0 .. in stato c il 1.o zero a
sinist
MdT numero 9 : sposta (muovi) uni
31
meglio: cercare l’ultimo 1 a destra:
a * b * +
che
b 1 b 1 +
cerca 0
b 0 c 0 sinistra
c 1 d 0 -
; scorri a destra e vai in b; stato b indica
; sono a destra del *; in stato b ignora 1
; vai oltre gli uni, allo zero torna a
; in stato c cancella 1; stato d=cancellato 1
dato il nastro qui sotto applico le quintuple scritte sopra:
.. 0 0 0 * 1 1 1 0 0
a
.. 0 0 0 * 1 1 1 0 0
b
uni
.. 0 0 0 * 1 1 1 0 0
b
.. 0 0 0 * 1 1 1 0 0
b
0 .. 1) passo, iniziale
0 .. 2) in stato b scorri a destra
e cerca lo zero = fine degli
0 .. 4) scorrimento a destra
0 .. 5) zero limite degli 1 a destra
MdT numero 9 : sposta (muovi) uni
a
b
b
c
d
d
d
*
1
0
1
*
1
0
b
b
c
d
d
d
a
*
1
0
0
*
1
1
+
+
+
;
;
;
;
;
;
;
32
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1 (ho spostato un 1) e ripeto
.. 0 0 0 * 1 1
d
.. 0 0 0 * 1 1
d
.. 0 0 0 * 1 1
d
.. 0 0 1 * 1 1
a
0 0 0 0 .. 8) vado a sinistra scorrendo
gli uni a destra dell' *
0 0 0 0 .. 9) sono in mezzo, ancora a sin
0 0 0 0 ..10) cerca 0 a sinistra di *
trovato 0 a sinistra di *
0 0 0 0 ..11) e scrivo un 1, e ripeto
MdT numero 9 : sposta (muovi) uni
a
b
b
c
d
d
d
*
1
0
1
*
1
0
b
b
c
d
d
d
a
*
1
0
0
*
1
1
+
+
+
;
;
;
;
;
;
;
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
d aggiunge 1 a sinistra...
ignorando 1
scrivo 1, passo in stato a, e ripeto
.. 0 0 0 0 1 * 1 1 0 0 0
a
.. 0 0 0 0 1 * 1 1 0 0 0
b
.. 0 0 0 0 1 * 1 1 0 0 0
b
.. 0 0 0 0 1 * 1 1 0 0 0
sinistra,cancella
c
.. 0 0 0 0 1 * 1 0 0 0 0
d
0 .. 12) passa l' *
0 .. 13) in b cerca ultimo 1..
0 .. 15) in b fine dato a dest
0 .. 16) ritorna a
0 .. 17) e scrivi 1 a sinistra
33
MdT numero 9 : sposta (muovi) uni
a
b
b
c
d
d
d
a
*
1
0
1
*
1
0
1
b
b
c
d
d
d
a
a
*
1
0
0
*
1
1
1
+
+
+
+
;
;
;
;
;
;
;
;
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
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..
34
MdT numero 9 : sposta (muovi) uni
a
b
b
c
d
d
d
a
*
1
0
1
*
1
0
1
b
b
c
d
d
d
a
a
*
1
0
0
*
1
1
1
+
+
+
+
;
;
;
;
;
;
;
;
scorri a destra - b indica che
sono a destra del *; ignora 1
oltre gli uni - torna a sinistra
cancella 1; stato d=cancellato 1
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:
ripeto, cerco 1 a destra dell'asterisco - ma ora non c'e' piu'
35
MdT numero 9 : sposta (muovi) uni
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
+
+
;
;
;
;
;
;
;
;
;
36
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
c'e' 1
.. 0 0 1 1 1 * 0 0
da
c
fermo:
.. 0 0 1 1 1 * 0 0
0 0 0 0 .. ripeti: cerca 1 a des
0 0 0 0 .. sono sul limite dato,torno
a sinistra in c, ma non
0 0 0 0 .. trovo un *, non vi sono 1
cancellare, quindi mi
0 0 0 0 .. stop
MdT numero 9 : sposta (muovi) uni
esempio muovi gli uni ... provare a scrivere la
versione grafica come esercizio
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 ...
37
38
MdT numero 9 : sposta (muovi) uni
versione grafica
della MdT num. 9 :
..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
-
10) MdT: test se due dati hanno valore uguale
10) esempio:
una macchina di Turing per il
confronto di due valori numerici,
ovvero test
se a<b oppure se a=b oppure se a>b
39
10) MdT: test se due dati hanno valore uguale
2.o esempio di operazioni di base:
40
test se a=b
ipotesi sulla rappresentazione di dati: in unario, separati
da un *, posizione iniziale testina in mezzo:
. . .
0 0 1 * 1 1 0 0..
a
schema di soluzione (algoritmo in notazione informale) :
fintanto che a>0 e b>0
{ sottrai 1 ad entrambi
cioe’ fai b-1 e poi fai a-1 }
ora, se a=0 oppure b=0
{ controlla se entrambi sono zero,
se si’ il test risponde S, se no risponde N }
10) MdT : test se a=b
es. con
41
a=1, b= 2:
dato a
;
a
b
b
c
;
;
d
d
d
e
a
;
;
dato b
sottrai 1 a b:
..0 0 1 * 1 1 0 0..
* b * + ; vai a destra
a
1 b 1 + ; scorri il dato b cerca ultimo 1
0 c 0 - ; sono oltre il limite di b, torna a sin
1 d 0 - ; cancella un 1 di b (come nella muovi 1)
ora abbiamo:
..0 0 1 * 1 0 0 0..
ora sottrai 1 ad a:
d
1 d 1 - ; scorri a sinistra per fare a-1
* 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
10) MdT: test se a=b vediamo avanti ... caso
a<b :
42
; sottrai 1 a b:
..0 0 1 * 1 1 0 0..
a * b * + ; vai a destra
a
b 1 b 1 + ; scorri il dato b cerca ultimo 1
b 0 c 0 - ; sono oltre il limite di b, torna a sin
c 1 d 0 - ; cancella un 1 di b (come muovi 1)
; ora sottrai 1 ad a:
d 1 d 1 - ; scorri a sinistra
d * d * - ; scavalca *,vai a vedere dato a
d 0 e 0 + ; sei oltre a, ritorna a destra
e 1 a 0 + ; fatto b-1 e anche a-1 : ripeti
a 1 a 1 + ; scorri il dato a ... fino all’ *
; ora abbiamo:
..0 0 0 * 1 0 0 0..
;
a
; il ciclo si ripete finche o a oppure b vanno a zero:
; se dopo aver fatto b-1 non trovo alcun 1 in a, ovvero
; se dopo d0 e0+ (torna a destra dopo trovato 0 a sin di
a)
; cioe' se dopo aver fatto b-1 trovo che a=0 ?
; allora e' b>0, a=0 quindi aggiungo quintupla che
e * h < 0 ; "scrive" il risultato, ovvero "minore" a<b
10) MdT : test se a=b
se lo stato iniziale e' come a destra
(a>b) allora si procede a cancellare
un uno a destra (dal dato b, eseguo
b-1) e anche a sinistra (dato a,
eseguo a-1), come riportato nella
traccia di esecuzione qui a destra:
traccia gia' seguita prima, ripeto:
in stato b cerco fine dato b, quindi uno
zero, con (b 0) siamo sul limite destro,
torno a sinistra di una posizione in stato c
e cancello l'uno piu' a destra di b
poi in stato d cerco lo zero limite di a a
sinistra, torno indietro in stato e e cancello
l'uno piu' a sinistra di a, e ritorno nello
stato a;
43
. . 0 1 1 * 1 0
a
. . 0 1 1 * 1 0
b
. . 0 1 1 * 1 0
b
. . 0 1 1 * 1 0
c
. . 0 1 1 * 0 0
d
. . 0 1 1 * 0 0
d
. . 0 1 1 * 0 0
d
. . 0 1 1 * 0 0
d
. . 0 1 1 * 0 0
e
. . 0 0 1 * 0 0
a
0..
0..
0..
0..
0..
0..
0..
0..
0..
0..
10) MdT : test se a=b, caso a>b
dopo aver cancellato un 1 da b e e
anche da a, avro’la situazione in
rosso,
vado a fare b-1, al solito cerco zero
dopo gli uni di b, qui trovo subito
zero, torno a sinist. in stato c per
cancellare un 1 di b, ma trovo *
(non 1) caso b=0;
se in c trovo asterisco, passo in stato
f
c * f * - ; ora so che il dato b e' zero
devo controllare se anche a=0, passo
in stato f, vado a sinistra sul dato a:
se in stato f trovo un uno a sinistra
di *
44
.. 0 1 1 * 1 0 0..
a
...
.. 0 1 1 * 0 0 0..
e
.. 0 0 1 * 0 0 0..
a
.. 0 0 1 * 0 0
a
.. 0 0 1 * 0 0
b
.. 0 0 1 * 0 0
c
.. 0 0 1 * 0 0
f
.. 0 0 > * 0 0
h
0..
0..
0..
0..
0..
10) MdT : test se a=b, caso a==b
a * b * +
b 1 b 1 +
b 0 c 0 -
;situazione iniziale
;scorri b a destra
;quando trovi 0 in b,
;vai in stato c e
c 1 d 0 - ;fai b-1 se possibile
d 1 d 1 - ;scorri a sinistra dopo b-1
d * d * - ;scavalca asterisco in mezzo
d 0 e 0 + ;fino allo zero a sin. di a
e 1 a 0 + ;fai a-1 se possibile
a 1 a 1 + ;scorri uni di a fino *
; restano da vedere i casi finali:
; se dopo fatto b-1 trovo che a=0,cioe'
e * h < 0 ;scrive risultato a<b
c * f * - ;se cerco di fare b-1, trovo
; * allora b=0, vado controllare a :
f 0 h = 0 ;trovo 0 a sin dell’*: anche
a=0!
f 1 h > 0 ;c’e’1 a sin.di *: allora
a>0,b=0
si osservi che le quintuple con la coppia
45
..0 1 *
a
....
..0 1 *
e
..0 0 *
a
..0 0 *
1 0 0..
0 0 0..
0 0 0..
0 0 0..
b
..0 0 * 0 0 0..
c
..0 0 * 0 0 0..
f
..0 = * 0 0 0..
h
10) MdT : test se a=b, caso a<b
a * b * +
b 1 b 1 +
b 0 c 0 -
;situazione iniziale
;scorri b a destra
;quando trovi 0 in b,
;vai in stato c e
c 1 d 0 - ;fai b-1 se possibile
d 1 d 1 - ;scorri a sinistra dopo b-1
d * d * - ;scavalca asterisco in mezzo
d 0 e 0 + ;fino allo zero a sin. di a
e 1 a 0 + ;fai a-1 se possibile
a 1 a 1 + ;scorri uni di a fino *
; resta da vedere i casi finali:
; se dopo fatto b-1 trovo che a=0,cioe'
e * h < 0 ;scrive risultato a<b
c * f * - ;se cerco di fare b-1, trovo
; * allora b=0, vado controllare a :
f 0 h = 0 ;trovo 0 a sin dell’*: anche
a=0!
f 1 h > 0 ;c’e’1 a sin.di *: allora
a>0,b=0
46
..0 1 * 1 1 0..
a
cancella uno:
dopo b-1, a-1 ho:
..0 0 * 1 0 0..
a
e
ripeti..
..0 0 * 1 0 0..
b
..0 0 * 1 0 0..
b
..0 0 * 1 0 0..
c
..0 0 * 0 0 0..
d
..0 0 * 0 0 0..
d
..0 0 * 0 0 0..
e
..0 0 < 0 0 0..
10) MdT : test se a=b; rivediamo le
quintuple:
47
a * b * + ;situazione iniziale
b 1 b 1 + ;scorri b a destra in cerca dello zero di
fine b
b 0 c 0 - ;quando trovi 0 dopo b, vai in stato c, vai a
sin
c 1 d 0 - ;se trovi 1 allora fai b-1 e poi in stato d,a
sin
d 1 d 1 - ;dopo b-1 scorri a sinistra gli 1 di b e/o di
a
d * d * - ;scavalca asterisco in mezzo
d 0 e 0 + ;fino allo zero a sinistra di a
e 1 a 0 + ;c'e' almeno un 1 di a, faccio a-1 se
possibile
a 1 a 1 + ;scorri a destra gli 1 di a fino *
; casi finali:
; (e,*) e'il caso a=0 dopo fatto b-1 cioe':
e * h < 0 ;dopo b-1 e senza a-1, scrive risultato a<b
; (c,*) e'il caso b=0, si deve controllare se a e'zero o
no:
c * f * - ;devo controllare a: in stato f (b=0) ho:
esercizio
11) dato un numero n calcolare il valore 2*n
48
49
esercizio
11) dato un numero n calcolare il valore 2*n
dobbiamo prima specificare la codifica, ad es.:
0 0 0 A 1
a
dato n=3;
destra di
0 0 0 A 0
a
0 0 0 A 0
a
0 0 0 A 0
a
0 0 0 A 0
1 1 B 0 0 0 0 0 0 0 0 0 0 0
per ogni 1 del dato n scrivo due 1 a
B:
1 1 B 1 1 0 0 0 0 0 0 0 0 0
0 1 B 1 1 1 1 0 0 0 0 0 0 0
0 0 B 1 1 1 1 1 1 0 0 0 0 0
0 0 B 1 1 1 1 1 1 0 0 0 0 0
h
si lascia allo studente l'esercizio ...
cosa si puo’ fare con una m.d.T.
abbiamo cosi’ verificato che
esistono m.di T. per
fare n+1
fare test se a=b?
fare copia del valore di a in un altra parte
...
sono le operazioni fondamentali per fare aritmetica
intera..
non e’ difficile definire m.d.T. per fare altri “conti”
vedremo che con le MdT si possono risolvere molti
problemi
anche piu' complicati ...
50
esercizi suggeriti
51
1) m.d.T per fare la somma di due numeri A e B:
ad es. con il dato (A e B in unario, delimitati da x,y,w) :
...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
(i dati originali qui non vengono conservati)
esercizi suggeriti
2) macchina per fare il prodotto di due numeri
ad es. con il dato A=3, B=2 codificato ad es. con:
..x111y11w0000000...
a
ottengo il risultato:
..x000y00w111111111111111111z0000...
h
52
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 ...
h
nota che una cella della memoria a nastro esterna non
53
cont. esercizi da fare
54
4) macchina azzera le coppie di uni sul nastro esterno;
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 ...
h
cont. esercizi da fare
5) 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 ....
h
55
cont. esercizi da fare
56
6) 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
)
cont. esercizi da fare
57
7) macchina che cerca una stringa uguale ad una
stringa data, tutte le stringhe sono composte da soli 0 e 1
e sono delimitate da un simbolo x
.. z 0 0 z 1 1 x 1 0 x 1 0 x 0 0 x ..
a
la stringa data 0 0 sta tra due z, ed e' uguale alla
quarta stringa dopo la z; il problema dovra' essere
scomposto in problemi piu' semplici; lo stato interno (o
la sequenza di stati interni) ricordera' il simbolo letto
dopo z, che sara' ad es sostituito con un simbolo diverso,
ad es. 0 diventa a, 1 diventa b, di seguito in stato q dopo
avere riconosciuto che
il primo simbolo dopo x e' uguale al 1.o simbolo dopo il
3.o x
.. z a 0 z 1 1 x 1 0 x 1 0 x a 0 x ..
cosa si puo’ fare con una m.d.T.
abbiamo cosi’ verificato che
esistono m.di T. che sanno risolvere alcuni problemi :
n+1, test se a=b?,
(si potrebbe vedere anche le operazioni di
somma a+b, e prodotto a*b ),
copia del valore di a in un altra parte (a := b) ...
...
queste sono alcune delle operazioni fondamentali
per fare aritmetica intera..
non e’ difficile definire m.d.T. per fare altri “conti”
58
59
cosa si puo’ fare con una m.d.T. ?
si puo' simulare un calcolatore con una MdT
?
si puo' dimostrare che e' possibile simulare un
calcolatore digitale con una M.di T.;
in particolare, si possono costruire MdT per simulare i
singoli componenti del calcolatore, come la memoria
centrale, l' unita' centrale, una memoria a disco ...
vediamo un cenno sul problema di simulare la memoria
centrale del calcolatore con una MdT
60
si puo' simulare un calcolatore con una MdT
?
61
problema:
simulare la memoria centrale del calcolatore con una
MdT
la memoria centrale del calcolatore e' molto diversa
dalla memoria a nastro di una MdT;
la memoria centrale e' un dispositivo HW fatto di celle
di memoria (di formato fisso) ciascuna con un indirizzo
ed e' in grado di fare due operazioni: memorizza D e
leggi D
"scrivi un dato D nella cella di memoria di indirizzo A"
"leggi un dato D dalla cella di memoria di indirizzo A"
memoria ad accesso diretto:
= memoria capace di leggere / scrivere un valore (un
dato) x in una “cella” di indirizzo specificato indiri :
leggi:
x <-- MEM[ indiri ]
scrivi:
x --> MEM[ indiri ]
dove la MEM e’ una memoria di n “celle” numerate,
con indirizzi (numeri cella) da zero a n, e con ciascuna
cella 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
62
995
8
indirizzo del valore 313
contenuto della cella di indirizzo 4
una memoria a indirizzo? ma la m.di T. non lo e'
!
La memoria nastro esterno di una macchina di Turing
e’ composta da celle adiacenti non numerate,
l'accesso ad una cella e' sequenziale,
passando prima per tutte le celle intermedie..
per individuare un dato si introducono dei simboli
speciali di marcatura (“delimitatori”), ad es.:
“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...
^
^
63
una memoria a indirizzo
Es: una MdT con un po'di dati sul nastro esterno,
separati dal simbolo x,
00x01011x00x111x1001x0101x00
a
(=posizione testina e stato interno)
allora per arrivare al 4.o dato 1001 devo scorrere
(leggere / riscrivere) i primi tre;
... ma:
una MdT puo' simulare la memoria a indirizzi con un
sistema di codifica del tipo seguente
(A,B,C sono simboli delimitatori) :
. . . A 01011 B 1001001000111 C . . .
dove la parte 01011 tra A e B e' l'indirizzo,
e la parte 1001001000111 tra B e C e' il dato
64
continua la memoria a indirizzo
65
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
continua la memoria a indirizzo
66
m.d.T. che simula una memoria con “celle” numerate,
cioe’ con memoria con dati accessibili specificando un
indirizzo:
“azzera 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.)
. 2 2 x 2 1 w 4 w 2 2 w 1 w 2 3 w 0 ...
^ ^
^valore=1,
indirizzo=22
dopo l’istruzione detta avremo:
. 2 2 x 2 1 w 4 w 2 2 w 0 w 2 3 w 0 ...
^
riportiamo di seguito solo parte della soluzione; nota:
continua la memoria a indirizzo
67
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)
m.d.T. “memoria ad accesso diretto”
68
formato codifica della memoria con indirizzi e dati a tre
cifre:
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
si puo' fare una MdT per rispondere alla domanda: qual
e’ il valore del dato di numero (o di indirizzo) 010? (qui
e’ 101)
con il procedimento: 1) dato un indirizzo i (010) cerca tra
gli indirizzi un kj tale che kj = i, (m.d.T. cerca stringa=), e
ho ad es
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
2) poi copia il dato (la stringa 1 0 1) al posto dell’indirizzo
i:
memoria a indirizzi su supporto fisico a memoria
sequenziale
69
negli anni 60 sono stati realizzati sistemi di memoria a
nastro magnetico
formattato a zone di memoria di ampiezza fissa e con
indirizzo registrato accanto il dato;
il sistema era in grado di trovare il dato di indirizzo k
cercando su nastro (con ricerca sequenziale) la zona con
indirizzo k e quindi il dato corrispondente (memoria
associativa,
ogni dato ha registrato anche l'indirizzo che
lo individua (o chiave) )
questo sistema non ha avuto successo ...
una macchina di Turing
"programmabile"
70
tutte le M.di T "sanno" (per definizione) eseguire solo
un algoritmo, cioe' quello "prefissato" nella memoria
delle quintuple (che e' a sola lettura, non modificabile); e
quindi una M di T ha UN programma;
ma:
e' possibile codificare una qualunque macchina di
Turing (quintuple, nastro, memoria dello stato, posizione
testina)
su un nastro esterno di una particolare m.d.T., che
chiameremo m.d.T Universale;
si puo' costruire un insieme di quintuple per realizzare
le azioni richieste per una qualunque m.d.T., cioe'
l'algoritmo di imitazione
a questo punto abbiamo una m.d.T. "programmabile",
cont. “U”, una m.d.T. speciale ...
71
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
osservazione
per chi e' interessato all'argomento vedere ad es.
M.L. Minsky: "Computation: Finite and Infinite
Machines", Prentice Hall 1967, cap. 6,7,8.,
questi argomenti saranno ripresi in altri corsi
di seguito e’ riportata la versione grafica di
una m.d.T. universale, solo a titolo di curiosita' !!
72
73
locate name (quintuple)
start
a
0
1 -
B
trovato
y
B
+
+
dcerca 01
eok
A
non
trovato
-halt
A
y
B
fnok
y
S +
x
0
A (copia 0!)
B
-
+
y
i
M 1
-
B
to start (repeat)
M
A
M
1
1
B (copa 1!)
A
B
M
+
-
0
1 B
0 A
B
1
-
fine copia
1
0
A
+
l
B
0
- restore machine
M condition region
A
A
x +
M 0
S +
-
+
COPY item, replace
name
0 ccerca 0
A
y
1
h
+
0 1
+
+
X
1
B
g
k
0
1
1 b
test
-
A
A
fine copia
da m.d.T.(a) j
S
0
0 +
B
Replace s with s1,
move position, repeat
1
0
S
B
A
1
23 stati, 5 simboli
La macchina di Turing Universale - vers.
grafica
m.d.T e algoritmi
segue un discorso generale sulle M.d.T.,
sull'applicabilita',
sugli algoritmi e
sulle funzioni effettivamente calcolabili
74
applicabile ( mdT applicabile ad un
dato)
75
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
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
76
mdT “T” <=> f(intero) -> intero parziale
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
77
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!
cioe' se si puo' risolvere un problema con il linguaggio
C++
(con un calcolatore digitale) lo stesso problema si puo'
risolvere con il formalismo delle MdT
(e in particolare i diversi linguaggi di programmazione
procedurali (o imperativi) hanno la stessa potenza:
quello che si puo' risolvere in Visual Basic si puo'
78
le m.d.T sono meno potenti del C++?
Si puo’ dimostrare che
per ogni mdT esiste un programma C++
corrispondente, e viceversa...
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).
79
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, ...
ogni algoritmo si puo' scrivere in uno qualunque di
questi
formalismi :
tesi di Church:
sono tutti formalismi di pari potenza
(ipotesi fondamentale della teoria degli algoritmi)
80
tesi di Church:
tesi di Church:
i formalismi definiti finora per scrivere algoritmi
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
( ma - non e’ stato dimostrato che non esiste un
formalismo piu’ potente )
81
limiti
infine,
ancora un dubbio:
... cosa si puo’ fare con una m.d.T?
ovvero: cosa si puo' risolvere con un algoritmo?
si puo' formulare un problema in modo che si possa
cercare di risolverlo per via algoritmica
(ad es. con un programma in C++)
e poi scoprire che non si puo' risolvere?
esistono problemi non risolubili per via algoritmica?
esistono problemi per cui non si potra' mai scrivere un
programma che li risolva?
82
limite ... cosa si puo’ fare con una m.d.T?
83
si puo' dimostrare che 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
m,
ad un generico numero intero k un (altro) numero intero
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
per ogni mdT c'e' una f(i) ,
ma per ogni f(i) c'e' mdT ?
e' sufficiente osservare che
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 problema non risolubile per via
algoritmica.
84
problema dell’ arresto (halting problem)
85
dato un programma qualunque (data una m.d.T.
qualunque)
con un dato iniziale fissato (una situazione su nastro)
ci si chiede se
solo analizzando il programma / la mdT - (senza
esecuzione)
e’ possibile sapere 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’ --
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’ X e’ applicabile a D)?
...000313008x82y1000...
quintuple
f
(dati D su nastro)
X
(a,0,...)
(a,1,...) della
(b,8,...) mdT.
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 75301 giorni magari si
86
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)?
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: si puo' dimostrare che non e’ possibile
87
problema dell’ arresto (halting problem)
88
quindi : dato un generico programma P con i suoi dati
D non e’ possibile determinare ( con un programma
“magico” G ) se il programma P e’ applicabile al dato
generico D
quindi: 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 (un
compilatore magico) tale che esso solo leggendo il testo
di un generico programma X risponda: si’, questo
programma funziona, oppure no, questo programma
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.
89
problema dell’ arresto (halting problem)
90
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 abbastanza semplici e ben delimitati ...
riassumiamo alcuni concetti:
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)
91
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
= un programma che produce
un risultato in un numero finito di passi
92
93
e con questo concludiamo questo capitolo sugli
algoritmi e sulle
macchine di Turing
94
fine