1 MACCHINE DI TURING e ALGORITMI *) definizione, relazione tra MdT e algoritmi, - esempi nella prima...

transcript

MACCHINE DI TURING

e ALGORITMI *) definizione, relazione tra MdT e algoritmi, - esempi nella prima parte : 1) la MdT che non fa nulla 2) riempi nastro 3) cerca uno 4) incrementa un numero di uno (n+1) 5) cerca uno, 6) riempi nastro simmetrica 7) controllo parita' su un dato di zeri e uni

2Macchina di Turing

(attenzione: la Macchina di Turing NON e' una macchina (non e' Hardware, non ha un' unita' centrale come tutti i calcolatori di oggi) NON e' un oggetto ...

e' un formalismo - ovvero un sistema formale -

molto semplice per descrivere algoritmi

3Macchina di Turing

La Macchina di Turing e' un formalismo per descrivere algoritmi

Fu definita 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 perche' e' un ..

esempio di automa modello teorico dei calcolatori “convenzionali” (VonNeumann)buona introduzione ad alcuni algoritmi formalismo usabile per dimostrare un teorema importante

(*) problema della decisione

4calcolo automatico

alcuni calcoli possono essere eseguiti seguendo delle istruzioni in maniera del tutto meccanica;

negli anni trenta il matematico inglese Alan Turing si e' occupato dei limiti dei procedimenti di calcolo

e a tal fine ha definito un formalismo per ridurre un procedimento di calcolo a sequenze di azioni molto semplici

5cosa e’ necessario per fare calcoli?

devo avere a disposizione un po' di carta per scrivere i dati di partenza, intermedi e i risultati finali :

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:

il repertorio di istruzioni e' il piu' semplice possibile, le azioni richieste sono molto semplici...

---Proposta di Turing: cosa diventa un generico processo di

calcolo ridotto alla forma piu' semplice...

6calcolo automatico

la macchina di T e' un formalismo per un procedimento meccanico automatico di

"fare conti", dove si immagina di avere a disposizione

una lista di istruzioni molto semplici (scritta su una memoria accessibile all’esecutore, che deve essere (solo) letta dallo stesso, oggi si dice una ROM)

un insieme di dati iniziali scritti su una “memoria” accessibile all’esecutore (diversa dalla precedente memoria per le istruzioni, perche’ destinata anche a contenere i dati intermedi e i risultati -> deve essere riscrivibile)

una memoria per ricordarsi a che punto siamo, cioe' per memorizzare lo stato corrente della computazione

vediamo meglio...

7cosa fa una macchina di Turing

Le azioni semplici richieste dalla "macchina di Turing":

*) dato un simbolo letto "S" da un foglio (foglio corrente, individuato da un “dito” o posizione corrente pc ),

*) dato "Q", stato del processo [ anzi dell’ esecutore - e’ lo stato interno dell' elaboratore o esecutore, memorizzato da

qualche parte, in una memoria "interna", e' un simbolo ],

*) 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) -> cambia posizione corrente pc

8un’ 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:

un' istruzione della macchina di Turing e' una quintupla :

(Q, S, Q1, S1, Direz) l'insieme delle quintuple ("memorizzate a sola lettura" nella

macchina di Turing) e' la descrizione del procedimento di calcolo che questa macchina realizza

(detta matrice funzionale)

9Alcune 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

10limite per gli stati interni Q

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 - e: il numero di simboli S "esterni" e' finito il numero degli stati interni "Q" e' finito nota che durante una computazione (un processo di calcolo di elaborazione) ad ogni passo del processo abbiamo uno stato Q ben determinato (uno solo in ogni istante) - questo stato puo' cambiare di passo in passo.

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

nell' unita' di elaborazione : 1) c’e una memoria dove e’ memorizzato il procedimento di calcolo (congelato, fisssato in modo “indelebile”) (= 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,

... l' unita' di elaborazione e' finita ( questo vale anche per un esecutore umano? la memoria di una persona e’ finita? )

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

l' "unita' di elaborazione" della Macchina di Turing ha:

1) una memoria con le quintuple della matrice funzionale (dove sono memorizzate le istruzioni), finita, a sola lettura 2) una memoria interna (“riscrivibile”) con lo stato corrente della macchina Q, anche finita,

3) una "testina di registrazione" con cui si "legge" dal nastro,

4) una unita' di "controllo" che data la coppia S,Q "trova" la quintupla corrispondente, e quindi i nuovi S1, Q1, Direz, e poi “riscrive” S1 nella cella corrente su nastro, “sposta” la testina di lett/scritt come da Direz, e infine “cambia stato” da Q a Q1 .

13e 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, ==>> una macchina di Turing e' piu' "potente" di un calcolatore reale ...ma la memoria esterna (il nastro) e' formata da celle adiacenti accessibili in modo strettamente sequenziale;una cella corrisponde al ( e’ il ) foglietto

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

15notazione piu’ breve:

Useremo la seguente notazione piu' concisa 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)

la posizione corrente e' indicata dalla posizione dello stato corrente, qui il simbolo corrente e' * (simbolo letto dalla cella corrente, che e’ quella marcata dallo stato corrente)

161) esempio, M.d.T che non fa nulla, stato di arresto

la macchina piu' semplice non fa nulla, cioe’ rimane nello stato di fermo o di arresto “z” fin dal primo passo;stato “z” significa: qualunque cosa leggi dalla cella corrente del nastro riscrivila uguale, rimani nello stesso stato e non spostare la testina. ipotesi: 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

172) una m.di T. riempi nastro:per descrivere una computazione (“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

182) una m.di T. riempi nastro:

1) situazione di partenza: ... 0 0 0 0 0 0 0 0 ... a2) le istruzioni: un' unica quintupla, composta da: ( q s q1 s1 d1 ) ( a 0 a 1 -> ) se sei in stato a e leggi da nastro 0,allora scrivi su nastro un 1 al posto di 0, sposta la testina a destra e vainello stato a : fine del 1.o passo ... 0 0 1 0 0 0 0 0 ... a =situaz. dopo il 1.o passo=situaz.all’iniz. 2.o passo

unica istruzione: ( a,0, a,1,-> ) situazione iniziale: ... 0 0 0 0 0 0 0 0 ...

aal 2.o passo:( dopo il 1.o, prima del 2.o passo,) : ... 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 .... ma ... non si ferma mai !!

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

attenzione allo stop: lo stato di stop “h” di norma non viene esplicitamente descritto; si intende che nello stato di stop “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

203) una macchina “cerca uno”

modifichiamo un po’: il nastro inizialmente non e’ tutto vuoto,

nastro e posiz. iniziale:.. 0 0 0 0 0 1 .. adue istruzioni (quintuple) :

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

al passo 6 la macchina va nello stato h e si ferma - passo 7 a fianco

1).. 0 0 0 0 0 1 .. a2).. 0 0 0 0 0 1 .. a3).. 0 0 0 0 0 1 .. a

4).. 0 0 0 0 0 1 .. a5).. 0 0 0 0 0 1 .. a6).. 0 0 0 0 0 1 .. a7).. 0 0 0 0 0 1 .. h

213) una macchina “cerca uno”

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

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 si ferma ... ma 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 ...

224)esempio: MdT per il calcolo del numero successore a n

n1 =succ(n) = n+1;

ipotesi: rappresentiamo n in unario, ovvero:

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”

23continua 4.o es. di m.di T.: calcolo di N+1

situazione iniziale: (scelta mia!) sul nastro rappresento N, numero intero positivo, con codifica piu' semplice unaria :

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 astato finale (halting state) h

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 ... h (indico con h 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 ... adevo arrivare alla situazione finale: (h = lo stato finale)... 0 0 1 1 1 0 0 0 ... h 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, h 1 0) indico movimento zero se la testina non si sposta

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

a questo punto abbiamo finito (situazione di fermo, dove la posizione testina non cambia e lo stato interno non cambia)

27esercizio:

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

-> provare ora !

28esercizio : una m.di T. che calcola n+2: n codificato in unario, tutto il resto del nastro e' a zero;la macchina, posizionata all' inizio sull'uno a sinistra, scorre gli uni verso destra come prima; arrivata allo zero a destra deve aggiungere due uni: quindi da stato a, leggo zero, scrivo 1 e passo nello stato b (lo stato b "ricorda" che ho gia' aggiunto un uno e che devo aggiungere ancora uno) e vado a destra, in stato b leggo 0, scrivo 1 e ho finito ...

inizio:... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... afine scorrimento: +1

... 0 0 1 1 1 1 0 0 ... be ancora +1, ... 0 0 1 1 1 1 1 0 ... h e ho finito

29macchina = automa

con termini piu’ precisi:

la macchina di Turing e' un automa a stati finiti dotato di memoria esterna illimitata

... vedremo tra poco uno schema grafico del modello della "macchina"

la m.d.t. puo' essere costruita con un po' di circuiti elettronici (tranne il nastro illimitato)

esistono molti programmi (disponibili su rete) per simulare una macchina di Turing ...

30ricorda i componenti della macchina di Turing:

* una memoria esterna per i simboli S (testina lett/scritt)

* 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’:

il ciclo di esecuzione di un'istruzione di una M.di T.: * leggi un simbolo s dalla posizione corrente su nastro * dati s (dal nastro) e q (stato corrente) determina dalle quintuple date una terna di simboli s1, q1, d1 * scrivi s1 al posto di s, * memorizza q1 al posto di q q1 = nuovo stato della macchina * sposta la testina in direzione d1 ripeti dall'inizo, da “leggi s dal nastro ”

31m.di T. - schema:

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

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

33la 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 e di 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 : le celle sono senza indirizzo! il numero di celle non e' limitato <=== ATTENZIONE la MdT ha una memoria di lavoro illimitata

34memoria interna e unita’ di elaborazioneuna 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, ho fatto quello” )

un' unita' di elaborazione -- dove e'memorizzata (fisssata) la funzione di trasformazione (l’insieme delle quintuple detto anche la matrice funzionale, il "programma" della MdT

l'insieme delle quintuple che descrive la sequenza delle azioni da fare che e' l'algoritmo in notazione come richiesto dalleMdT si chiama anche "MATRICE FUNZIONALE": semetto le quintuple in colonna ho una matrice dove una riga e' una quintupla, e dove una quintupla e' individuata dai primi due valori (Q,S) e mi da' con i tre valori successivi i nuovi simboli (Q1, S1, Direz)

35ciclo di un' istruzione

la MdT esegue ciclicamente le seguenti cose (ripetiamo) :

il ciclo di esecuzione di un'istruzione di una M.di T.:

* leggi un simbolo s dalla posizione corrente su nastro * dati s (dal nastro) e q (stato corrente) determina dalle quintuple della MdT una terna di simboli s1, q1, d1 * scrivi s1 al posto di s, s1 sostituisce s nella cella del nastro esterno * memorizza q1 al posto di q q1 = nuovo stato della macchina * sposta la testina in direzione d1 alla fine, dopo avere riscritto la cella con s1

ripeti dall'inizo, da “leggi s dal nastro ”

36la MdT cha fa n+2 :

inizio:... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... a ... 0 0 1 1 1 0 0 0 ... afine scorrimento: +1

... 0 0 1 1 1 1 0 0 ... be ancora +1, ho finito:... 0 0 1 1 1 1 1 0 ... h

la matrice funzionale:

( a, 1, a , 1, + ) vai a destra finche' trovo 1( a, 0, b, 1, +) se trovo 0 cambia in 1 (n+1)( b, 0, h, 1, 0) secondo zero cambia in 1 (n+2)( h, $, h, $, 0) halt: qual.que cosa leggi non cambiare( b,1, b, 1, ??) quintupla non possibile ...

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

fine parte introduttiva alle M.di T.

rappresentazione grafica della matrice delle quintuple

39rappresentazione grafica della macchina di Turing

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

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

40rappresentazione grafica della 4.a macchina di Turing

la 4.a 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 )

START1

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

41esercizio (5.o esempio di M.di T.)

dato il nastro esterno:

... 0 0 0 0 0 0 0 0 0 ... a

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

che quintuple sono ?e cosa fa questa macchina se fatta partire con il nastro riportato qui sopra?

42cont. esercizio (5.a MdT) :la domanda era: cosa fa la macchina di Turing seguente?... 0 0 0 0 0 0 0 0 0 ... a nastro esterno = tutte le celle con simbolo zero

dal grafo a sinistra:( 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 sei in stato a, e trovi uno allora scrivi 1 e fermati

questa macchina cerca sul nastro un 1 per fermarsi ->

43risposta a “cosa fa la macchina di Turing seguente (5.a) ”? ... 0 0 0 0 0 0 0 0 0 ... il nastro esterno ha tutte le a 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 sei in stato a, e trovi uno 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!

44relazione tra M.di T. e algoritmi:

una macchina di Turing che si ferma dopo un numero finito di passi e' un algoritmo

una macchina di Turing che non si ferma mai NON e’ un algoritmo !!

45ancora un esercizio: cosa fa la m.d.T seguente (6.a MdT) :

data la situazione iniziale su nastro (inizialmente tutto a 0):

... 0 0 0 0 0 0 0 0 0 ... a

e date le quintuple:

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

(+ indica spostamento a destra, - indica spostamento a sinistra, 0 indica un non spostamento)

leggi: se nello stato a trovo 1 riscrivo 1, resto 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 sinis. (-)se in b trovo 1 riscrivo 1, resto in stato b e vado a sinistrase in stato b trovo 0 scrivo 1 vado in stato a e a destra...

data situazione iniziale su nastro:

... 0 0 0 0 0 0 0 0 0 ... a

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

cont. il secondo esercizio (6.a MdT)

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

47cont. il secondo esercizio (6.a MdT)

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

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

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, simmetricamente a destra e a sinistra ...

per ipotesi il nastro e’ illimitato -> la m.d.T. non si fermera’ mai...

( disegnare per esercizio la versione grafica delle quintuple )

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

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 uni 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” : al passo iniziale 1) stato p, sono sulla cella a sinistra (la prima dopo delimitatore x); qui trovo 1: quintupla p,1

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

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

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

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

- fine prima parte delle MdT

1 MACCHINE DI TURING e ALGORITMI *) definizione, relazione tra MdT e algoritmi, - esempi nella prima...

Documents