1 ALGORITMI E MACCHINE DI TURING. 2 algoritmo: funzione da intero a intero... date codifiche...

1ALGORITMI

E

MACCHINE DI TURING

2

algoritmo:

funzione da intero a intero

...

date codifiche opportune ;-)

quanti programmi ?

quante funzioni da intero a intero ?

3traccia di UNA esecuzione:

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)=7oppure 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)

4formalismi

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, ...)

5... ancora sulla definizione di algoritmo...

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 ...

6qualche es. di problemi (..procedimenti) di calcolo:

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 = 05) 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);


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;


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 Porpetto15) traduzione automatica delle poesie di Saba in urdu16) scrivere tutti gli n per cui l' equazione x n + y n = z n ha soluzioni x,y,z intere;


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.

10- 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.

11talvolta 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

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

13Un 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!

15

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.

BIBLIOGRAFIA per questa parte:(ma solo per chi sia molto interessato all’argomento

16cont. 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.

17parte 2

parte 2:

18Macchina di Turing

• 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.230-265

presentato qui per due scopi:• un modello teorico di tutti i calcolatori “convenzionali” modello Von Neumann• un formalismo usabile per dimostrare un teorema importante

19cosa e’ necessario per fare calcoli?

... 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...

20calcolo automatico ?

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)

22un’ istruzione della macchina di Turing

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

23Alcune osservazioni sulla macchina di Turing

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

24limite per gli stati interni Qil 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.

25l’esecutore (l’unita’ di elaborazione) ?

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? )

26e 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

27macchina = automa

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"

28ricorda i componenti della macchina di Turing:

* una memoria esterna per i simboli S

* 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”

29m.di T. - schema:

... (ri-) vediamo in dettaglio le singole parti ...

30ipotesi 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 }

31la memoria esterna : testina di lettura/scrittura

* 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

32memoria interna e unita’ di elaborazione

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:

33come si esegue un’istruzione della m.d.T:

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).

34notazione piu’ breve:

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)

351) 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

362) una m.di T. molto semplice “riempi nastro”: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 ... a2) 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

37continua 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 ... aal 2.o passo (cioe’ prima del secondo passo, dopo il primo) : ... 0 0 1 0 0 0 0 0 ... aal 3.o passo : ... 0 0 1 1 0 0 0 0 ... aal 4.o passo : ... 0 0 1 1 1 0 0 0 ... aal 5.o passo: ... 0 0 1 1 1 1 0 0 a eccetera ....

38cont. es. nr. 2 “riempi nastro”

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

39definizione di applicabilita’

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.

40una 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 .. a2)..1 0 0 0 0 0 1 .. a3)..1 0 0 0 0 0 1 .. a

4)..1 0 0 0 0 0 1 .. a5)..1 0 0 0 0 0 1 .. a6)..1 0 0 0 0 0 1 .. a

.. 1 0 0 0 0 0 1 .. a

( a 0 a 1 -> )( a 1 h 1 -> )

41cont. variante 2.o es. “riempi nastro”

1)..1 0 0 0 0 0 1 .. 2)..1 0 0 0 0 0 1 .. a a3)..1 0 0 0 0 0 1 .. 6)..0 0 0 0 0 0 1 .. a ae 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 ...

423)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 1rappresento il numero due con 11rappresento il numero tre con 111, rappresento il numero quattro con 1111 rappresento il numero cinque con 11111 eccrappresento il numero dodici con 111111111111che e’ la rappresentazione piu’ antica: il sistema “unario”

43continua terzo es. di m.di T.: calcolo di N+1

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) .. 0 0 1 1 0 0 0..situazione finale nastro (N=3) .. 0 0 1 1 1 0 0..

stato iniziale a


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 ... apasso 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 ? ...


per calcolare N+1 devo aggiungere un 1: quindi da .. 0 0 1 1 0 0 0 0 ... ala 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

46continua 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)

47esercizio:

scrivere una m.di T. che calcola n+2

-> provare ora !

48fine parte 2

fine parte 2

49rappresentazione grafica della macchina di Turing

la quintupla (q,s, q1,s1,direz) si rappresenta graficamente:

s

s1

q q1

direz

n.b.: la direzione di spostamento della testina e’ riportata nello stato di arrivo.e il nastro? cioe’ la memoria esterna ? ... separatamente !

50continua rappresentazione grafica

la m.di T. che calcola n+1, ovvero la matrice funzionale con le quintuple:

(a 1, a 1 + ) (a 0, z 1 0 ) (z 1, z 1 0 )

a z

START1

1

0

1 1

1

0

due stati: a (scorri a destra) e z (arresto)

51esercizio (4.o es. di m.di T.)

dato il nastro esterno:

... 0 0 0 0 0 0 0 0 0 ...

con tutte le celle con simbolo zero, e date le istruz.:

(che quintupla e’? / sono? ovvero: cosa fa questa macchina se fatta partire con il nastro riportato qui sopra? )

11

a h

0

start

0 0->

52cont. esercizio: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

( 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 ->

11

a h

0

start

0 0->

53possiamo 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

( 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 !!

11

a h

0

start

0 0->

542.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.

a 1 a 1 + a 0 b 1 - b 1 b 1 - b 0 a 1 +

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 (-)

55

data situazione iniziale su nastro:

... 0 0 0 0 0 0 0 0 0 ...

(nastro inizialmente tutto a zero) e le quintuple a fianco :

cont. il secondo esercizio (5.o es.)

a 1 a 1 + a 0 b 1 - b 1 b 1 - b 0 a 1 +

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...

56cont. il secondo esercizio (5.o es.)dati nastro: e quintuple: a 1 a 1 +... 0 0 0 0 0 0 0 0 ... a 0 b 1 -(tutto a zero) b 1 b 1 - b 0 a 1 +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 ... adopo il 1.o passo: ... 0 0 0 0 1 0 0 0 0 ... bdopo il 2.o passo: ... 0 0 0 1 1 0 0 0 0 ... a

57cont. il 2.o esercizio: (5.o es.)dati nastro: e quintuple: a 1 a 1 +... 0 0 0 0 0 0 0 0 ... a 0 b 1 - a b 1 b 1 - a=mette 1 a des.,b=mette 1 a sin. b 0 a 1 +

situazione iniziale ... 0 0 0 0 0 0 0 0 0 ... adopo il 1.o passo: ... 0 0 0 0 1 0 0 0 0 ... bdopo il 2.o passo: ... 0 0 0 1 1 0 0 0 0 ... adopo il 3.o passo: ... 0 0 0 1 1 0 0 0 ... adopo il 4.o passo: ... 0 0 0 1 1 1 0 0 ... b

58cont. il 2.o esercizio: (5.o es.)0).. 0 0 0 0 0 0 0 0 .. a 1 a 1 + a a 0 b 1 - b 1 b 1 - 1).. 0 0 0 0 1 0 0 0 .. b 0 a 1 + b2).. 0 0 0 1 1 0 0 0 .. 6).. 0 0 0 1 1 1 0 0 .. a b3).. 0 0 0 1 1 0 0 0 .. 7).. 0 0 1 1 1 1 0 0 .. a a4).. 0 0 0 1 1 1 0 0 .. 10)..0 0 1 1 1 1 0 0 .. b a5).. 0 0 0 1 1 1 0 0 .. 11)..0 0 1 1 1 1 1 0 .. b b

59cont. il 2.o esercizio: (5.o es.)dati nastro: e quintuple: a 1 a 1 +0)... 0 0 0 0 0 0 0 0 ... a 0 b 1 - a b 1 b 1 - al passo undici lo stato e’: b 0 a 1 +11)..0 0 1 1 1 1 1 0 .. b

quindi questa m.d.T. fatta partire su un nastro vuotolo 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 )

60cont. il 2.o esercizio: (5.o es.)

dati nastro: e quintuple: a 1 a 1 +0)... 0 0 0 0 0 0 0 0 ... a 0 b 1 - a b 1 b 1 - b 0 a 1 +

0

1

a b <-

start

11

->

11

0

1

616.o es. di m.di T: “controllo parita’ ”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’ noancora:

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

626.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):


S = { 0, 1, x, D, P } Q = { p, d, ...? , h } situazione iniziale: ... x 1 1 1 0 0 x .. pleggo 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 destraper 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


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 .. p2)..x 1 1 1 0 0 x .. d3)..x 1 1 1 0 0 x .. p4)..x 1 1 1 0 0 x .. d

5)..x 1 1 1 0 0 x .. d6)..x 1 1 1 0 0 x .. d7)..x 1 1 1 0 0 D .. he basta: risposta “D”


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

666.a m.di T: “controllo parita’-vers.grafica ”( p 0 p 0 + ) ( p 1 d 1 + ) * ( d 0 d 0 + ) ( d 1 p 1 + ) @ ( d x h D 0 ) ( p x h P 0 )

... rappresentazione grafica delle stesse quintuple: (nota: nel grafo degli stati [sotto] sono marcate due quintuple, * e @ )

+

0

+

start

p

halt

d

x x

11

1

1

P D

*

@0

000

676.a m.di T: “controllo parita’ - vers.grafica”

( p 0 p 0 + ) ( p 1 d 1 + ) * ( d 0 d 0 + ) ( d 1 p 1 + ) @ ( d x h D 0 ) ( p x h P 0 )

nota: non riporto le transizioni di stato che lasciano lo stato immutato e che riscrivono lo stesso simbolo (transizioni (p,0, ...), (d,0, ... )

+

0

+

start

p

halt

d

x x

1

1

1

1

P D

*

@

686.o es., m.d.T. <<controllo di parita’ >>, nota:

una variante dell’es.6:( p 0 p 0 + ) ( p 1 d 0 + ) * ( d 0 d 0 + ) ( d 1 p 0 + ) @ ( d x h D 0 ) ( p x h P 0 )sono cambiate le istr. * @

erano (p,1,d,1 ,+) (d,1,p,1 ,+)

ho lo stesso risultato, macancello 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 .. p2).. x 0 1 1 0 0 x .. d3).. x 0 0 1 0 0 x .. p4).. x 0 0 0 0 0 x .. d...6).. x 0 0 0 0 0 x .. d7).. x 0 0 0 0 0 D .. h

69parte 3 - fine

fine parte 3

1 ALGORITMI E MACCHINE DI TURING. 2 algoritmo: funzione da intero a intero... date codifiche...

Documents

Transcript of 1 ALGORITMI E MACCHINE DI TURING. 2 algoritmo: funzione da intero a intero... date codifiche...