ALGORITMI
E
MACCHINE DI TURING
1
2
algoritmo:
funzione da intero a intero
...
date codifiche opportune ;-)
quanti programmi ?
quante funzioni da intero a intero ?
traccia di UNA esecuzione:
3
nota: un algoritmo ed un particolare insieme di dati
in ingresso o di partenza
definiscono un particolare processo di calcolo
come questo visto per il calcolo del MCD di 18 e 12,
oppure per i due esempi MCD(1996 ,768)=4 e MCD(2310, 203)=7
oppure come quello visto prima per il calcolo del capitale
con interesse composto con capitale iniziale 1000
interesse annuo 4 e numero anni 5,
oppure come l’ esempio iniziale di calcolo della somma di
due numeri interi a=1991 e b=2309 con s= 4300...
NOTA: un algoritmo puo’ essere applicabile a un dato solo,
oppure a un numero finito di dati, oppure a un numero
infinito di dati, oppure a nessun dato (senza dati iniziali)
formalismi
4
Esistono moltissimi formalismi per definire (esprimere,
specificare) algoritmi:
formalismi astratti:
Macchina di Turing, (vedremo nel prossimo capitolo)
Lambda Calcolo,
linguaggi per calcolatori:
linguaggi macchina, ...
ling. di programm. imperativi o procedurali, come ad es.:
Algol 59, Basic, C, C++, C#, Cobol, Fortran 57,
Fortran 90, Java, Modula, Pascal, , Smalltalk, ...
ling. di progr. funzionali (Lisp,Scheme, ...),
ling. di progr. logici (Prolog, ...)
... ancora sulla definizione di algoritmo...
5
la nozione di algoritmo o procedura effettivamente
computabile e' del 1935, ed e’ stata ripresa da piu' autori
con diversi formalismi negli anni 30, 40 e 50.
oggi si puo’definire un algoritmo come un programma
eseguibile da un calcolatore che a partire da un dato valido
produce in un tempo finito e sempre lo stesso risultato (*)
esistono algoritmi (programmi) per risolvere un enorme
quantita’ di problemi
ma ATTENZIONE: non esistono algoritmi risolutivi per tutti i
problemi [vedremo un esempio in dettaglio]
----------------------------------------------
(*) implicita l’ipotesi che il linguaggio di programmazione in
cui scrivo il programma sia non ambiguo,deterministico e
eseguibile dal calcolatore ...
qualche es. di problemi (..procedimenti) di calcolo:
6
in questo elenco alcuni problemi sono semplici, altri difficili
fino a “praticamente intrattabili”, altri impossibili ...
1) problema della somma di due interi di 4 cifre (abbiamo
visto prima un procedimento)
2) dati due numeri, trovare il maggiore;
3) calcolo del capitale maturato dopo dieci anni, con dati l’
interesse composto e il capitale iniziale;
4) dati tre valori numerici a,b,c calcolare le radici
dell’equazione di secondo grado a * x2 + b * x + c = 0
5) dato un elenco di nomi e relativi numeri di telefono (in
rubrica o elenco telefonico o nel cellulare della zia), trovare
il num.o di telefono di una persona (ad. es. Mario Rossi);
qualche es. di problemi (..procedimenti) di calcolo:
7
6) scrivere una lettera di sollecito di pagamento alla ditta
“Sgraffigna,Nonpaga,Fuggi&co”.
7) calcolo della mossa migliore per ogni possibile situazione
del gioco del filetto / della dama / degli scacchi
8) data una rete stradale di una citta' e le informazioni sui
flussi di veicoli (per ogni strada e per ogni istante) trovare il
percorso ottimo (tempo o consumo o altro) da casa propria
all' universita';
9) calcolo del percorso ottimo di un robot semovente in
ambiente con ostacoli (ad es.durante una partita di calcio
del campionato internazionale per squadre di robot);
10) calcolo dei comandi per il controllo di una macchina
operatrice di un impianto industriale;
qualche es. di problemi (..procedimenti) di calcolo:
11) calcolo delle tasse per gli studenti del primo anno
della facolta' di ingegneria;
12) calcolo del comando da trasmettere sull' interfaccia
MIDI nell'ambito di un programma che produce
musica da partitura memorizzata da/di Buxtehude;
13) calcolo dell’immagine da inviare sullo schermo
sinistro relativo al gioco virtuale Destroyer71;
14) scrittura automatica da parlato di Porpetto
15) traduzione automatica delle poesie di Saba in urdu
16) scrivere tutti gli n per cui l' equazione
x n + y n = z n ha soluzioni x,y,z intere;
8
qualche es. di problemi (..procedimenti) di calcolo:
9
17) scrivere un programma per comprimere una sequenza di
immagini video codificate in versione digitale in modo da
poter memorizzare dieci filmati su un disco da 10 Mega byte
18) scrivere un programma che controlla se un qualunque
programma scritto in C++ e’ sintatticamente corretto e se
si ferma dopo un numero finito e limitato di passi
19) trovare una procedura per decidere per ogni x intero e
per ogni f(x) (f funzione da intero a intero) se f(x) e' o
meno una funzione costante;
20) scrivere un programma per decidere per ogni matricola
del corso di Fondamenti di Informatica se passera’ l’esame
entro la prossima sessione.
- ancora sui procedimenti di calcolo:
specifica del problema: in ogni caso si chiede di ottenere a
partire da certe informazioni iniziali (dati di ingresso del
problema) informazioni nuove, o risultati del problema.
la formulazione del problema non da' alcuna indicazione su
come risolvere il problema;
talvolta il problema e’ ambiguo:
cerco ad es. il nome di Furlan Giuseppe nella guida
telefonica di Trieste oppure di John Brown nella guida
telefonica di Manchester e trovo molti nomi uguali.
10
talvolta il problema e’ praticamente intrattabile, perche’
richiede un numero di passi troppo grande
(un esempio: per calcolare la funzione di Ackermann
A(4,2) ci vuole un po’ di tempo (circa 10 secondi), il
risultato e’ un numero intero di 19729 cifre:
A(4,2) = 2,00352 ...6733 x 10 +19728 ;
(H.J.Smith, programma VPCalc per calcoli con dati fino a
114.639 cifre e con valori di grandezza fino a
10^15.032.385.525, da: ModulaTor nr.11, vol.1, dec 91)
per il calcolo A(4,3) ci vorrebbero piu’ di A(4,2)
secondi [n anni, dove n ha piu’di 10000 cifre...]
e un calcolatore con piu’ di A(4,2) byte di memoria [k
Gbyte, dove k ha piu’di 10000 cifre...] ... e’ un
problema non risolubile in pratica
11
12
talvolta si dimostra che un problema non ha soluzione
ad es. il problema di decidere per ogni x intero e ogni
funzione f(x) da intero a intero se f(x) e' costante o no,
ovvero trovare una F tale che
F(f) = 1 se f(x) e’ costante per tutti gli x e
F(f) = 0 se f(x) non e’ costante
si puo’ dimostrare che il problema NON ha soluzione
13
Un altro problema che non ha soluzione (come si puo’
dimostrare) e’ il seguente “Halting Problem” :
scrivere (il testo di) un programma (un “super-compiler”) SC
che sia in grado di leggere un testo di un programma
generico P e di un dato generico D per il programma P, e
poi, analizzando il testo P e i dati D, sia in grado di
rispondere se
* il programma P con questo dato generico D una volta
avviata l’esecuzione si ferma in un tempo finito (si arresta
dopo aver eseguito un numero finito di istruzioni)
* oppure no, e in questo secondo caso ha luogo una
computazione infinita.
Nota che NORMALMENTE un compilatore analizza il teso
di un programma generico e per prima cosa decide se la
sintassi e’ corretta oppure no;
14
nota: si osservi che il numero di algoritmi e’ infinito ma
numerabile ...
vi sono tanti algoritmi quanti i numeri naturali
(si pensi ad es. che un programma in C e’ un testo; posso
immaginare di costruire una sequenza di tutti i programmi
in C, iniziando dal piu’ piccolo - il programma vuoto
“main(){}” e poi “allungando” in ordine lessicografico con
costrutti che mantengano la sintassi legale;
un algoritmo puo’ essere considerato come una funzione da
intero a intero (l’insieme dei dati “ e’ “ un intero (formato
appunto da tutti i dati codificati), l’insieme dei risultati e’ un
intero);
il numero di funzioni da intero a intero non e’ numerabile solo una piccola parte delle f(int)->int e’ un algoritmo!
BIBLIOGRAFIA per questa parte:
(ma solo per chi sia molto interessato all’argomento
M.A. Arbib, A.J. Kfoury, R.N. Moll: "A Basis for
Theoretical Computer Science", Springer Verlag 1981
(BIBL.FAC.ING)
R.Y.Kain, "Automata Theory, Machines and
Languages", McGraw Hill,72. (BIBL.FAC.ING)
M.L. Minsky: " Computation: Finite and Infinite
Machines", Prentice Hall 1967, (Centro Calcolo ,
DEEI) cap. 6,7,8.
C.Ghezzi, D.Mandrioli: "Informatica Teorica", Clup,
Milano, 1989.
15
cont. BIBLIOGRAFIA per questa parte:
D.E.Knuth: "The Art of Computer Programming",
vol. 1, "Fundamental Algorithms", Addison Wesley
1968, (FAC./5/XXIIc/41a/I)
B.A. Trakhtenbrot: "Algoritmi e macchine
Calcolatrici", Ed. Progresso tecnico, 1964,
(FAC/5/Cont.3/7)
J.E.Hopcroft, J.D.Ullman: “Introduction to Automata
Theory, Languages and Computation”, Addison
Wesley, Reading, Mass., 1979.
16
parte 2
parte 2:
17
Macchina di Turing
18
• Formalismo molto semplice per descrivere algoritmi
• definito da Alan Turing, matematico inglese, nel 1935
A.M.Turing, “ On Computable numbers with an application to the
entscheidungsproblem ” Proc. London Math. Soc. 2:42, 1936, pp.230265
presentato qui per due scopi:
• un modello teorico di tutti i calcolatori “convenzionali”
modello Von Neumann
• un formalismo usabile per dimostrare un teorema
importante
cosa e’ necessario per fare calcoli?
19
... da Turing: un generico processo di calcolo ridotto alla
forma piu' semplice diventa:
• devo avere a disposizione un po' di carta per scrivere i
risultati intermedi:
• cioe', semplificando, tanti foglietti di carta quanto basta,
messi in fila, che leggo o scrivo uno alla volta (tenendo un
"dito" sul "foglietto corrente");
• da qualche parte ho una lista di istruzioni che mi dice cosa
fare ad ogni passo.
...
le azioni richieste sono molto semplici...
calcolo automatico ?
20
si noti che il formalismo di Turing si basa sull’idea di un
procedimento meccanico, automatico, dove si immagina che
e’:
• data una lista di istruzioni molto semplici
(scritta su una memoria accessibile all’esecutore,
che deve essere solo letta dallo stesso)
• dato un insieme di dati iniziali scritti su una “memoria”
accessibile all’esecutore (probabilmente diversa dalla
precedente, perche’ destinata anche a contenere i dati
intermedi e i risultati -> deve essere riscrivibile)
• data una memoria per ricordarsi a che punto siamo, quindi
lo stato corrente della computazione
vediamo meglio...
21
Le azioni richieste sono semplici:
*) dato il valore letto "S" da un foglio (foglio corrente,
individuato da un “dito segnafoglio” ),
*) dato "Q", stato del processo [ anzi dell’ esecutore - e’ lo
stato interno dell' elaboratore o esecutore, memorizzato da
qualche parte, in una memoria "interna" ],
*) si (ri)scrive sullo stesso foglietto un nuovo simbolo "S1"e si
passa (l’esecutore!) nello stato nuovo "Q1",
*) si puo' quindi cambiare il "foglio corrente", passando a
esaminare il foglietto adiacente a destra oppure a sinistra
(specifico una direzione)
un’ istruzione della macchina di Turing
22
un’istruzione per la macchina di Turing dice:
se hai letto dal foglietto il simbolo S e se sei nello stato Q (la
computazione e’ nello stato Q) allora ti dico
quale simbolo nuovo S1 scrivere su quel foglietto,
quale stato nuovo Q1 assumi ora (cioe’ la computazione),
e quale foglietto esaminare (a sinistra, a destra, o lo stesso ->
Direzione) per la prossima istruzione:
la quintupla (Q, S, Q1, S1, Direz) e' un' istruzione della
macchina di Turing -> l'insieme delle quintuple
("memorizzate a sola lettura" nella macchina di Turing) e'
la descrizione del procedimento di calcolo che questa
macchina realizza
Alcune osservazioni sulla macchina di Turing
23
Cosa scrivo sui foglietti? Che simboli uso?
c’ e' un numero finito di simboli S "esterni",
l’insieme (finito) di questi simboli e’ detto alfabeto esterno
Nota: il numero di simboli utilizzabili sui fogli di carta della
memoria esterna deve essere finito con un numero infinito di simboli non sarei piu' in grado
di distinguerli uno dall'altro- avrei un insieme continuo di
simboli! (si noti che la dimensione dei fogli di carta e'
fissa).
c’e’ ancora una ragione per avere un insieme finito di S, che e’ la
stessa per Q - vediamo
limite per gli stati interni Q
24
il procedimento di calcolo e' specificato dall' insieme
delle "istruzioni" cioe’ delle quintuple (Q, S, Q1, S1, Direz)
Le istruzioni sono individuate dai dati correnti per ogni
istruzione, che sono S (simbolo letto dal foglietto) e Q (stato
della macchina) quindi la coppia
S,Q individua l’istruzione, ovvero determina cosa fare al
passo corrente.
il numero delle istruzioni deve essere finito, quindi anche il
numero di S e di Q distinti deve essere finito ->
il numero degli stati interni "Q" deve essere finito ->
l’insieme degli stati interni Q e’ finito.
nota che durante una computazione (un processo di calcolo o
di elaborazione) ad ogni passo del processo abbiamo uno
stato Q ben determinato (uno solo in ogni istante) - questo
stato cambia di passo in passo.
l’esecutore (l’unita’ di elaborazione) ?
25
nell' unita' di elaborazione :
1) c’e una “memoria congelata” dove e’ memorizzata
(fisssata in modo “indelebile”) la funzione di
trasformazione (= la matrice funzionale = le quintuple);
la memoria dove sono memorizzate le istruzioni e’ finita:
2) c’e’ una memoria interna (“riscrivibile”) in cui e'
memorizzato lo stato corrente della macchina Q
anche questa memoria e’ finita,
3) l’esecutore poi anche “legge” dal nastro, “trova” la
quintupla corrispondente, “riscrive” la cella su nastro,
“sposta” la testina di lett/scritt, “cambia stato”.
...
l' unita' di elaborazione e' finita
( questo vale anche per un esecutore umano?
la memoria di una persona e’ finita? )
e i foglietti?
i foglietti sono la memoria di lavoro del procedimento di
calcolo “alla Macchina di Turing”,
sono la memoria esterna (in contrasto con le memorie
interne per lo stato corrente Q e per le quintuple)
per evitare problemi di limiti della memoria di lavoro:
supponiamo di avere un numero di fogli grande quanto
basta - ovvero illimitato:
la memoria esterna e' illimitata, ed e' formata da celle
adiacenti accessibili in modo strettamente sequenziale;
una cella corrisponde al ( e’ il ) foglietto
26
macchina = automa
27
con termini piu’ precisi:
la macchina di Turing e' un automa a stati finiti dotato di
memoria esterna illimitata.
... per noi la definizione sara’ nel senso inverso: una volta
capito cos’e’ la m.di T. avremo anche capito cos’e’ un
automa a stati finiti.
Vediamo uno schema grafico del modello della "macchina"
ricorda i componenti della macchina di Turing:
* una memoria esterna per i simboli S
28
* una memoria interna dove tenere lo "stato" Q
* un' unita' di elaborazione dove e'memorizzata (fisssata) la
funzione di trasformazione (la matrice funzionale -le
quintuple) e che esegue ciclicamente un’istruzione, cioe’:
•leggi dal nastro un simbolo s
•dati s (dal nastro) e q (stato corrente) determina, in
base alle quintuple date una terna di simboli s1, q1, d1
•scrivi s1 al posto di s,
•memorizza q1 al posto di q = nuovo stato della
macchina
•sposta la testina in direzione d1
... ripeti dal punto “leggi .. s”
m.di T. - schema:
... (ri-) vediamo in dettaglio le singole parti ...
29
ipotesi sugli insiemi di simboli usati
insieme dei simboli su nastro
(varia da macchina a macchina)
S = { a, b, c, d, ... }
es.:
S = { 0, 1, * }
insieme degli stati:
(varia da macchina a macchina)
Q = { x, y, z, w, p, q, .. }
es.:
Q = { a, b, c, h }
30
la memoria esterna : testina di lettura/scrittura
31
* una memoria esterna = un insieme di celle ciascuna delle
quali contiene uno (e uno solo) dato s (scelto dall’ alfabeto
di simboli esterni finito S);
la memoria esterna e' accessibile una cella alla volta
mediante una "testina" di lettura/scrittura;
la testina di accesso puo' spostarsi di una cella per volta
rispetto la posizione corrente. In ogni istante e' individuata
la cella corrente (dove sta la testina), e inoltre sono
individuate le celle a sinistra e a destra, accessibili (alla fine
di ogni ciclo di esecuzione) con un comando "sposta la
testina sulla cella a destra" oppure "sulla cella a sinistra".
le celle NON sono numerate
<=== ATTENZIONE
il numero di celle non e' limitato
<=== ATTENZIONE
memoria interna e unita’ di elaborazione
32
una memoria interna -- dove tenere lo stato interno del
processo di calcolo, individuato da un simbolo "q" scelto da
un insieme finito di simboli Q (stati interni possibili),
(serve per ricordare “sto facendo questo” )
un' unita' di elaborazione -- dove e'memorizzata (fisssata) la
funzione di trasformazione (l’insieme delle quintuple detto
anche la matrice funzionale)
e che esegue ciclicamente le seguenti cose:
come si esegue un’istruzione della m.d.T:
33
Passo generico della macchina (o algoritmo di esecuzione):
1) leggi dal nastro il simbolo s
(valore contenuto nella cella corrente)
2) dati s e q (s= simbolo letto dal nastro, q= stato corrente
della macchina) determina, in base alla matrice funzionale
MF, una terna di simboli s1, q1, d1 (nuovo simbolo esterno
s1, nuovo stato della macchina q1 e direzione di
spostamento della testina d1) [cioe’si cerca, nell’insieme delle
quintuple (q,s,q1,s1,d1) quella che ha q,s coincidenti ]
3) scrivi s1 al posto di s,
4) memorizza q1 al posto di q (stato nuovo della macchina)
5) sposta la testina in direzione d1
6) ripeti da 1).
notazione piu’ breve:
34
Di seguito useremo la notazione seguente per specificare lo
stato corrente di un processo di calcolo con la MdT:
... 0 0 0 0 0 * 1 1 1 0 0 0 0 ...
a
dove si specifica quanto basta:
il nastro (= memoria esterna)
lo stato corrente di valore a (stato indicato con il simbolo Q)
simbolo corrente * (simbolo letto dalla cella corrente, che e’
quella marcata dallo stato corrente)
1) la m.d.T piu’ semplice: “non fare nulla”
la macchina piu’ semplice non fa nulla, cioe’ rimane nello
stato di fermo o di arresto “z” fin dal primo passo;
“z” significa: qualunque cosa leggi dalla cella corrente del
nastro riscrivila uguale, rimani nello stesso stato e non
spostare la testina. ip.: insieme simboli esterni: S = { 0,1 }
insieme degli stati : Q = { z }
devo dare: situaz. iniziale e insieme istruzioni:
... 0 1 0 0 1 1 1 0 ...
questa macchina ha
z
due istruzioni:
( z 0 z 0 0 ) ... se sei nello stato z e se hai letto 0
dalla cella corrente allora riscrivi 0
e non spostare la testina
( z 1 z 1 0 ) ... sei nello stato z, hai letto 1, allora
riscrivi 1 e non spostare la testina
35
2) una m.di T. molto semplice “riempi nastro”:
36
per descrivere una computazione (diciamo pure “un conto”) devo fornire: la situazione
iniziale e le istruzioni cioe’le quintuple ( q, s, q1, s1, d1 ) ...
1) situazione di partenza:
a) un nastro (mem.esterna) vuoto,
b) stato iniziale = a [il nome e’ arbitrario, uso “a” per brevita’]
... schematicamente:
... 0 0 0 0 0 0 0 0 ...
a
2) le istruzioni: qui ho un' unica quintupla, composta da:
( q s q1 s1 d1 ) se sei nello stato a e leggi da nastro 0,
( a 0 a 1 -> ) allora scrivi su nastro un 1 al posto di
0, sposta la testina a destra e infine
vai nello stato a : fine del 1.o passo
... 0 0 1 0 0 0 0 0 ... situaz. dopo il 1.o passo
a
=situaz.all’iniz. 2.o passo
continua m.d.T. “riempi nastro”:
situazione di partenza, al 1.o passo , istruz.: ( a 0 , a 1 -> ) :
... 0 0 0 0 0 0 0 0 ...
a
al 2.o passo (cioe’ prima del secondo passo, dopo il primo) :
... 0 0 1 0 0 0 0 0 ...
a
al 3.o passo :
... 0 0 1 1 0 0 0 0 ...
a
al 4.o passo :
... 0 0 1 1 1 0 0 0 ...
a
al 5.o passo:
... 0 0 1 1 1 1 0 0
a
eccetera ....
37
cont. es. nr. 2 “riempi nastro”
38
attenzione allo stop: lo stato di stop “h” di norma
non viene esplicitamente descritto; si intende che
nello stato “h” la macchina qualunque cosa legga
riscrive lo stesso simbolo e rimane nello stesso stato
e non sposta la testina:
(h$h$0)
la macchina appena vista, fatta partire su un nastro pieno di
zeri da’ luogo ad un processo di calcolo che non si ferma
mai ... lo stato di arresto non si raggiunge mai (anzi, non e’
stato neanche definito)
vedremo ancora qualche esempio di macchine di questo tipo
definizione di applicabilita’
39
Se una MdT fatta partire da una situazione iniziale [nastro,
posizione testina, quintuple] si ferma dopo un numero
finito n di passi allora diremo che tale MdT e' applicabile
ai dati iniziali;
se invece una MdT fatta partire con certi dati iniziali non si
ferma mai allora diremo che la MdT non e' applicabile a tali
dati.
Si noti che in generale "e' difficile" determinare QUANDO
si fermera' una MdT, e anzi SE si fermera'. Ritorneremo
in seguito su questo punto.
una macchina “cerca uno”
modifichiamo un po’:
il nastro inizialmente non e’
tutto vuoto,
le istruzioni: aggiungo
un’istruzione-> ho due
quintuple:
1)..1 0 0 0 0 0 1 ..
a
2)..1 0 0 0 0 0 1 ..
a
3)..1 0 0 0 0 0 1 ..
a
.. 1 0 0 0 0 0 1 ..
a
(a 0
(a 1
a 1 -> )
h 1 -> )
4)..1 0 0 0 0 0 1 ..
a
5)..1 0 0 0 0 0 1 ..
a
6)..1 0 0 0 0 0 1 ..
a
40
cont. variante 2.o es. “riempi nastro”
41
1)..1 0 0 0 0 0 1 .. 2)..1 0 0 0 0 0 1 ..
a
a
3)..1 0 0 0 0 0 1 .. 6)..0 0 0 0 0 0 1 ..
a
a
e a questo punto la macchina si ferma...
naturalmente, se l’uno appare dopo 1.0 E +500 celle, allora il
numero di passi eseguiti prima di fermarsi sara’ molto piu’
grande... ma lo stesso finito;
se invece l’uno a destra non c’e’, la macchina non si fermera’
mai ...
3)es.: calcolo del numero n1 successore a n
n1 =succ(n) = n+1;
ipotesi sulla rappresentazione di n per il calcolo di n+1
rappresento il numero uno con
1
rappresento il numero due con
11
rappresento il numero tre con
111,
rappresento il numero quattro con 1111
rappresento il numero cinque con 11111
ecc
rappresento il numero dodici con 111111111111
che e’ la rappresentazione piu’ antica: il sistema “unario”
42
continua terzo es. di m.di T.: calcolo di N+1
43
devo fornire la situazione iniziale:
sul nastro rappresento N, numero intero positivo, con la
codifica (scelta mia!) semplice:
scrivo N in unario ovvero rappresento il numero n
riportando n volte un 1 (ipotesi: l’ insieme dei simboli su
nastro esterno e’ S = { 0,1 }.
per cui per passare da N (scritto con N simboli 1) a
N+1 basta aggiungere un 1:
situazione iniz. nastro (N=2)
situazione finale nastro (N=3)
stato iniziale a
.. 0 0 1 1 0 0 0..
.. 0 0 1 1 1 0 0..
continua terzo es. di m.di T.: calcolo di N+1
per passare da N a N+1 devo aggiungere un 1: quindi dalla
situazione iniziale (la posiz. iniz. testina e’ una mia scelta):
... 0 0 1 1 0 0 0 0 ...
a
passo alla situazione finale:
... 0 0 1 1 1 0 0 0 ...
z
(indico con z lo stato finale)
non vi sara’ difficile immaginare le istruzioni:
se leggi 1 e se sei nello stato a ? ...
44
continua terzo es. di m.di T.: calcolo di N+1
45
per calcolare N+1 devo aggiungere un 1: quindi da
.. 0 0 1 1 0 0 0 0 ...
a
la situazione finale sara’: (indico con z lo stato finale)
... 0 0 1 1 1 0 0 0 ...
z
le istruzioni:
se leggi 1 e se sei nello stato a allora scrivi 1 (cioe’ lascia
l’uno senza cambiarlo) e sposta la testina a destra,e ripeti
(finche’ non leggi uno zero)
se leggi 0 e sei nello stato a, allora scrivi 1 (appunto il +1 !) e
hai finito - passa nello stato di fine o di arresto ... quindi:
(a 1, a 1 +) indico con + uno spostamento a destra
(a 0, z 1 0) indico movimento zero se la testina
non si sposta
continua terzo es. di m.di T.: calcolo di N+1
(a 1, a 1 + ) (a 0, z 1 0 ) (z 1, z 1 0 )
(provare a leggere le istruzioni!)
situazione inziale
(posiz. iniz. testina e’una mia scelta):
... 0 0 1 1 0 0 0 0 ...
a
applico (a 1, a 1 ->)
passo due:
... 0 0 1 1 0 0 0 0 ...
a
applico (a 1, a 1 ->)
passo tre:
... 0 0 1 1 0 0 0 0 ...
a
applico (a 0, z 1 0)
situazione finale:
... 0 0 1 1 1 0 0 0 ...
z
applico (z 1, z 1 0)
46
esercizio:
scrivere una m.di T. che calcola n+2
-> provare ora !
47
fine parte 2
fine parte 2
48
rappresentazione grafica della macchina di Turing 49
la quintupla (q,s, q1,s1,direz) si rappresenta graficamente:
s1
s
direz
q
q1
n.b.: la direzione di spostamento della testina e’ riportata
nello stato di arrivo.
e il nastro? cioe’ la memoria esterna ? ... separatamente !
continua rappresentazione grafica
la m.di T. che calcola
matrice funzionale
(a 1, a 1 + )
n+1, ovvero la
(a 0, z 1 0 )
con le quintuple: (z 1, z 1 0 )
1
START
1
a
0
0
1
1
1
due stati: a (scorri a destra) e z (arresto)
z
50
esercizio (4.o es. di m.di T.)
51
dato il nastro esterno:
... 0 0 0 0 0 0 0 0 0 ...
con tutte le celle con simbolo zero, e date le istruz.:
1
1
->
a
0
0
start
0
h
(che quintupla e’? / sono?
ovvero: cosa fa questa
macchina se fatta partire
con il nastro riportato qui
sopra? )
cont. esercizio:
52
la domanda era: cosa fa la macchina di Turing seguente?
... 0 0 0 0 0 0 0 0 0 ...
nastro esterno = tutte le celle con simbolo zero
1
1
->
a
0
0
start
0
h
( a, 0, a, 0, + )
( a, 1, h, 1, 0 )
se sei nello stato a e
se leggi zero, allora
lascia 0 e vai a destra,
se trovi uno allora
scrivi 1 e fermati
questa macchina cerca sul nastro un 1 per fermarsi ->
possiamo rispondere all’ esercizio “cosa fa l a macchina di
Turing seguente”?
... 0 0 0 0 0 0 0 0 0 ...
nastro esterno = tutte le celle con simbolo zero
1
1
->
a
0
0
start
0
h
53
( a, 0, a, 0, + )
( a, 1, h, 1, 0 )
se sei in a e leggi 0 allora
lascia 0 e vai a destra,
se in stato a e se trovi 1
allora scrivi 1 e fermati
questa macchina cerca sul nastro un 1 per fermarsi, ma sul
nastro ci sono solo zeri: la macchina non si fermera’mai!
e’facile definire una macchina di T. che non si ferma mai una M.di T. che non si ferma NON e’ un algoritmo !!
2.o esercizio (5. es) cosa fa la m.d.T seguente:
data la situazione iniziale su
nastro (inizialmente tutto a 0):
... 0 0 0 0 0 0 0 0 0 ...
e date le quintuple a fianco
(un + indica la direzione di
spostamento a destra,
un - indica la direzione di
spostamento a sinistra e uno
0 indica un non spostamento.
a1
a0
b1
b0
a1+
b1b1a1+
leggi: nello stato a se
trovo 1 riscrivo 1,
rimango nello stato a
e vado a destra (+)
se in a trovo 0 riscrivo 1
e cambio stato, vado
nello stato b, e mi sposto
a sinistra (-)
54
cont. il secondo esercizio (5.o es.)
data situazione iniziale su nastro:
... 0 0 0 0 0 0 0 0 0 ...
a1
a0
b1
b0
a1+
b1b1a1+
(nastro inizialmente tutto a zero)
e le quintuple a fianco :
a e’ lo stato di scorrimento a destra fino alla cella con uno
zero; questo zero viene cambiato in uno, poi si va in b:
lo stato b e’ uno stato di scorrimento a sinistra , fino alla
prima cella con uno zero, che viene cambiato in un 1 e poi
si ritorna nello stato a...
quindi...
55
cont. il secondo esercizio (5.o es.)
dati nastro: e quintuple: a 1 a 1 +
... 0 0 0 0 0 0 0 0 ...
a0 b1(tutto a zero)
b1 b1b0 a1+
stato a = scorri a destra, fino a 0; riscrivi 1, vai in stato b:
stato b = scorri a sinistra, fino 0; riscrivi 1, ritorna in st. a:
questa macchina riempie il nastro di uni: appende un 1 ad
ogni ciclo di esecuzione (formato da uno o piu’ passi);
situazione iniziale ... 0 0 0 0 0 0 0 0 0 ...
a
dopo il 1.o passo: ... 0 0 0 0 1 0 0 0 0 ...
b
dopo il 2.o passo: ... 0 0 0 1 1 0 0 0 0 ...
a
56
cont. il 2.o esercizio: (5.o es.)
dati nastro:
e quintuple: a 1 a 1 +
... 0 0 0 0 0 0 0 0 ...
a0 b1a
b1 b1a=mette 1 a des.,b=mette 1 a sin. b 0 a 1 +
situazione iniziale ... 0 0 0 0 0 0 0 0 0 ...
a
dopo il 1.o passo: ... 0 0 0 0 1 0 0 0 0 ...
b
dopo il 2.o passo: ... 0 0 0 1 1 0 0 0 0 ...
a
dopo il 3.o passo: ... 0 0 0 1 1 0 0 0 ...
a
dopo il 4.o passo: ... 0 0 0 1 1 1 0 0 ...
b
57
cont. il 2.o esercizio: (5.o es.)
0).. 0 0 0 0 0 0 0 0 ..
a1 a1+
a
a0 b1b1 b11).. 0 0 0 0 1 0 0 0 ..
b0 a1+
b
2).. 0 0 0 1 1 0 0 0 .. 6).. 0 0 0 1 1 1 0 0 ..
a
b
3).. 0 0 0 1 1 0 0 0 .. 7).. 0 0 1 1 1 1 0 0 ..
a
a
4).. 0 0 0 1 1 1 0 0 .. 10)..0 0 1 1 1 1 0 0 ..
b
a
5).. 0 0 0 1 1 1 0 0 .. 11)..0 0 1 1 1 1 1 0 ..
b
b
58
cont. il 2.o esercizio: (5.o es.)
dati nastro:
e quintuple: a 1 a 1 +
0)... 0 0 0 0 0 0 0 0 ...
a0 b1a
b1 b1al passo undici lo stato e’:
b0 a1+
11)..0 0 1 1 1 1 1 0 ..
b
quindi questa m.d.T. fatta partire su un nastro vuoto
lo riempie di uni per ipotesi il nastro e’ illimitato -> la m.d.T. non si fermera’
mai...
( disegnare per esercizio la versione grafica delle
quintuple )
59
cont. il 2.o esercizio: (5.o es.)
dati nastro:
e quintuple: a 1 a 1 +
0)... 0 0 0 0 0 0 0 0 ...
a0 b1a
b1 b1b0 a1+
1
0
a
->
1
start
1
1
1
<1
0
b
60
6.o es. di m.di T: “controllo parita’ ”
61
problema: costruire una m.d.T. che risponde alla domanda:
data una sequenza di zeri e uni, delimitati da una x,
determinare se il numero degli uni presenti e’ pari.
es. con il dato: .. x 0 0 1 1 x ..
la risposta e’ si’
es. con il dato: .. x 1 1 1 0 x ..
la risposta e’ no
ancora:
con il dato:
.. x 1 0 1 0 1 0 1 0 0 x ..
la risposta e’ si’
es. con il dato: .. x 1 1 1 0 0 1 1 1 1 x ..
la risposta e’ no
6.o es. di m.di T: “controllo parita’ ”
ipotesi sugli insiemi di simboli usati:
S = { 0, 1, x, D, P }
Q = { p, d, ...? , h }
suppongo di fornire la risposta nella cella dove mi fermo,
scrivendo P se il numero degli 1 era pari, D se era dispari.
non so ancora quanti stati mi servono;
procedimento:
esamino a partire dal primo tutti i dati da sinistra a destra,
e ad ogni uno letto sul nastro cambio stato:
stato “pari” sara’ “p” , stato dispari sara’ “d”;
inizialmente mi metto nello stato pari (zero 1 incontrati):
62
6.o es. di m.di T: “controllo parita’ ”
63
S = { 0, 1, x, D, P } Q = { p, d, ...? , h }
situazione iniziale:
... x 1 1 1 0 0 x ..
p
leggo i dati da sinist a dest, ad ogni 1 cambio stato: stato “p”
pari , stato “d” dispari; stato iniziale “p”;
per lo stato pari:
( p 0 p 0 + ) ; se nello stato p leggo zero rimango in p,
; riscrivo zero e vado a destra
( p 1 d 1 + ) ; se in p leggo un 1 -> riscrivo 1,vado
; in stato dispari e mi sposto a destra
per lo stato dispari:
( d 0 d 0 + ) ; in d ho 0 -> riscrivo 0, resto in d, a destra
( d 1 p 1 + ) ; in d ho 1 -> riscrivo 1, vado in p, a destra
6.o es. di m.di T: “controllo parita’ ”
situazione iniziale: ... x 1 1 1 0 0 x ..
p
( p 0 p 0 + ); in p leggo 0, riscrivi 0 ,resto in p, dest.
( p 1 d 1 + ); in p leggo 1; vado in d; scrivo 1; a dest
( d 0 d 0 + ); in d ho 0; riscrivo 0; resto in d, a dest;
( d 1 p 1 + ); in d ho 1; riscrivo 1; vado in p; a dest.
segue la “traccia di esecuzione”
1)..x 1 1 1 0 0 x ..
p
2)..x 1 1 1 0 0 x ..
d
3)..x 1 1 1 0 0 x ..
p
4)..x 1 1 1 0 0 x ..
d
5)..x 1 1 1 0 0 x ..
d
6)..x 1 1 1 0 0 x ..
d
7)..x 1 1 1 0 0 D ..
h
e basta: risposta “D”
64
6.o es. di m.di T: “controllo parita’ ”
mancano ancora le quintuple per le due situazioni finali:
6).. x 1 1 1 0 0 x ..
d
(e quella simmatrica dove arrivo alla cella limite x in stato p)
quindi oltre alle gia’ viste:
( p 0 p 0 + ) ; in p leggo 0, riscrivi 0 ,resto in p, destra.
( p 1 d 1 + ) ; in p leggo 1; vado in d; scrivo 1; a destra
( d 0 d 0 + ) ; in d ho 0; riscrivo 0; resto in d, a destra;
( d 1 p 1 + ) ; in d ho 1; riscrivo 1; vado in p; a destra.
aggiungo:
( d x h D 0 ) ; in d ho x; scrivo risultato D e mi fermo
( p x h P 0 ) ; in p ho x: scrivo risultato P e mi fermo
65
6.a m.di T: “controllo parita’-vers.grafica ”
(p0p0+)
(p1d1+)*
(d0d0+)
(d1p1+)@
(dxhD0)
(pxhP0)
66
... rappresentazione grafica
delle stesse quintuple:
(nota: nel grafo degli stati [sotto] sono
marcate due quintuple, * e @ )
start
0
x
0
0
+
p
P
1
D
halt
1
x
+
*
1
@
1
d
0
0
6.a m.di T: “controllo parita’ - vers.grafica”
nota: non riporto le transizioni
di stato che lasciano lo stato
immutato e che riscrivono lo
stesso simbolo (transizioni
(p,0, ...), (d,0, ... )
(p0p0+)
(p1d1+)*
(d0d0+)
(d1p1+)@
(dxhD0)
(pxhP0)
halt
start
x
p
+
P
1
0
D
1
1
x
+
*
@
1
d
67
6.o es., m.d.T. <<controllo di parita’ >>, nota:
una variante dell’es.6:
(p0p0+)
(p1d0+)*
(d0d0+)
(d1p0+)@
(dxhD0)
(pxhP0)
sono cambiate le istr. * @
erano (p,1,d,1 ,+) (d,1,p,1
,+)
ho lo stesso risultato, ma
cancello i dati; si provi a
scrivere la traccia di
esec. con
(p,1,d,A,+),(d,1,p,B,+)
la variante dara’:
1).. x 1 1 1 0 0 x ..
p
2).. x 0 1 1 0 0 x ..
d
3).. x 0 0 1 0 0 x ..
p
4).. x 0 0 0 0 0 x ..
d
...
6).. x 0 0 0 0 0 x ..
d
7).. x 0 0 0 0 0 D ..
h
68
parte 3 - fine
fine parte 3
69