gerarchia di macchine

8/18/2019 gerarchia di macchine

1/35

Andrea Prevete, UNINA2 2016

ELEMENTI DI PROGRAMMAZIONE

a.a. 2015/16

UNA GERARCHIADI

MACCHINE


2/35


UNA GERARCHIA DI MACCHINE

macchine combinatoriemacchine sequenziali (automi a

numero finito di stati)

...macchine di Turing

Macchine di tipo differente hanno diversa capacità di risolvere problemi.Un problema può essere non risolubile ad un dato livello della gerarchia, marisolubile a quello successivo.Esistono problemi non risolubili in assoluto?


3/35


LE MACCHINE COMBINATORIE

Una macchina combinatoria è formalmentedefinita da una tripla:

dove

I = insieme finito dei simboli di ingressoO = insieme finito dei simboli di uscitaft: I -> O (funzione di trasferimento)Esempio: le porte logiche e le funzioni in genere (half

adder, full adder, etc)

ftI O


4/35



Esempio:z = AND(x, y)

Dove x, y, z sono variabili booleane (0, 1).

Vogliamo che z=1 sse x=y=1.

Avremo:

I={(0,0) (0,1) (1,0) (1,1)}

O={0, 1} ft:

Simbolo per una porta AND:

x y z0 0 0

0 1 0

1 0 0

1 1 1

I O


5/35



Esempio:

Dove x, y, s, r sono variabili booleane (0, 1).Vogliamo che s e r valgano rispettivamentela cifra di peso 0 e quella di peso 1 dellasomma di x ed y.Avremo:I={(0,0) (0,1) (1,0) (1,1)}O={(0,0) (0,1) (1,0) (1,1)} ft:

x y s r

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

I O

HALF-ADDERs

r

x

y


6/35



Risolvere problemi con una macchinacombinatoria comporta enumerare in modoesplicito tutte le possibili configurazionid’ingresso, e indicare in corrispondenza ilvalore di uscita. Essendo un dispositivo puramentecombinatorio è inadatto a risolvere problemiche richiedono una memoria interna

(riconoscimento di sequenze, somme dinumeri forniti in successione, etc.)


7/35


FINITE STATE AUTOMATA

Il modo più semplice per introdurre macchine dotate di“memoria” è definire un automa con un numero finito distati interni.

Un automa a numero finito di stati, nel modello detto diMealy, è definito dalla quintupla:

dove

• I = insieme finito dei simboli di ingresso• O = insieme finito dei simboli di uscita• S = insieme finito degli stati

• fu: I x S -> O (funzione di uscita)• fsp: I x S -> S (funzione di stato prossimo)


8/35



I: 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 …

^ ^ ^

O: 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 …

I={0, 1}

O={0, 1}S={s0, s1}

fu: fps:

S I O

s00 0

1 1

s10 0

1 0

S I S+1

s00 s0

1 s1

s10 s0

1 s1


9/35



DIAGRAMMA DI TRANSIZIONE (MEALY):

I: 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 …

^ ^ ^

O: 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 …

1/0S0 S1

1/1

0/0

0/0


10/35



Un modello alternativo per la definizione diautomi a numero finito di stati è quello detto diMoore, definito ancora da una quintupla:

dove• I = insieme finito dei simboli di ingresso• O = insieme finito dei simboli di uscita• S = insieme finito degli stati

• fu: S -> O (funzione di uscita)• fsp: I x S -> S (funzione di stato prossimo)


11/35



DIAGRAMMA DI TRANSIZIONE (MOORE):

I: 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 …

^ ^ ^

O: 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 …

1

S0/0 S01/1

1

0

0 S11/0

0

1

1

S0/0 S01/1

1

0

0S11/0

0


12/35



Gli automi di Mealy e Moore sono, dal punto di vista della capacità computazionale, del tuttoequivalenti. Quindi ogni problema risolvibile con il modello di Mealy può essere trattato con Moore eviceversa.

Sceglieremo, quindi, di volta in volta, fra Mealy e Moore in base alla loro capacità di modellizzarecon espressività ed immediatezza il problema in parola.

Ad esempio è del tutto evidente che la soluzione del problema precedente è resa con maggioreimmediatezza adottando il modello di Mealy.

Immaginiamo, invece, di voler progettare un automa capace di riconoscere – per esempioemettendo come output un 1 – ogni qualvolta la stringa di 0 ed 1 in input contiene un numero pari di0 ed un numero pari di 1.

E’ naturale pensare ad un automa a quattro stati:

S00 = “ho finora letto un numero pari di 0 e di 1”

S01= “ho finora letto un numero pari di 0 e dispari di 1”

S10 =“ho finora letto un numero dispari di 0 e pari di 1”

S11 =“ho finora letto un numero dispari di 0 e di 1”

E, quindi, definire una funzione di output con argomento solo lo stato dell’automa:O(S00 )= 1 O(S11 )= 0

O(S10 )= 0 O(S01 )= 0


13/35



S00 /1 S01

S10 S11

1

1

1

1

00

00


14/35


FINITE STATE AUTOMATAUn modo alternativo, ma importante di definire gli automi fa riferimento al loroutilizzo come strumento formale per il riconoscimento dei cosiddettiLINGUAGGI REGOLARI.

Ad ogni automa corrisponderà quindi un linguaggio dato da tutte e sole lestringhe riconosciute dall’automa in parola.

Cosa intendiamo per riconosciute? Tali che, a partire da uno stato inizialefissato, l’automa – letto l’ultimo simbolo della stringa – si trovi in uno di un

fissato sottoinsieme di stati detti accettanti.In modo più formale definiremo un automa di questo tipo ancora con unaquintupla:

dove

• I = insieme finito dei simboli di ingresso, di cui uno designato comeiniziale

• O = insieme finito dei simboli di uscita• S = insieme finito degli stati• F = sottoinsieme di S detto degli stati finali o accettanti• fsp: I x S -> S (funzione di stato prossimo)


15/35



L’automa in figura, ad esempio, riconosce/accetta tutte le

stringhe che terminano con la sequenza «01».


16/35



Molti linguaggi sono più succintamente ed intuitivamente

definibili attraverso l’utilizzo dei cosiddetti automi non

deterministici.

Chiariamo subito che gli automi non deterministici non

ampliano la capacità rappresentativa degli FSA!Per cosa si differenziano da un FSA ordinario?

Formalmente per la definizione della funzione di stato

prossimo che si presenta così:

fsp: I x S -> P(S)Quindi il possibile valore di fsp è non più un elemento di

S, ma un sottoinsieme anche vuoto di S!


17/35



Abbiamo a che fare, cioè, con un automa che

esplora più strade in parallelo – ognuna delle quali

collassa/muore in concomitanza con un evento non

previsto.

Di seguito l’automa non deterministico che riconoscele stringhe terminanti con la sequenza «01».


18/35



Un FSA è una macchina dotata di una memoria interna.I suoi output, a differenza di quelli di una macchinacombinatoria, dipendono non solo dell’input attuale,ma anche della sequenza storica degli input giàprocessati.

E’ comunque importante ricordare il limite del numerofinito di stati e quindi di una memoria finita edefinitivamente fissata a livello di progetto.

Un FSA è quindi inadatto a risolvere quei problemi che

non consentono di limitare a priori la lunghezza dellesequenze d’ingresso di cui tenere memoria.


19/35



S0 S1

S00 S11

S/10 1

01

10

10

1

Se volessimo realizzare unautoma capace di tenerconto del numero di 0 ed 1di una stringa in ingresso edi emettere come output un1 quando le occorrenze delle

suddette cifre nella stringaletta si equivalessero,sbatteremmo contro labarriera prima citata.Un FSA non ha la potenzacomputazionale necessaria

per affrontare un problemasimile.


20/35


LE MACCHINE DI TURINGLe macchine di Turing consentono di superare il suddetto limite della memoria.Esistono di esse numerose formalizzazioni tutte equivalenti dal punto di vista dellapotenza computazionale.In una versione fra le più semplici ma molto intuitiva una macchina di Turing puòessere pensata come …- Una memoria lineare potenzialmente infinita (..la metafora del nastro illimitato)- Un insieme Q di quadruple del tipo:

- (si al ak s j)con si e s j appartenti ad un insieme S={s1 .. sn} di stati interni della macchina, al edak ad un insieme A={a1 .. am} di possibili simboli di input/output. Le quadruplepossono anche presentarsi nelle forma (si al ak s j)- o (si al ak s j)+ con il significatoche vedremo di seguito- Due variabili di stato, s ed a, che tengono conto dello stato interno attuale e dellaposizione attuale di lettura in memoria- Un sistema di controllo che cerca di far corrispondere alla coppia la primaparte di una delle quadruple di Q, , modificando lo stato interno e scrivendo

in memoria in ragione di quanto riportato dalla seconda parte della quadrupla,. Se la quadrupla è seguita da un suffisso la posizione di lettura in memoriasarà spostata di una posizione a destra (+) o a sinistra (-).


21/35


Un nastro (illimitatamente espandibile a sinistra ed a destra) rappresenta il deposito dei dati(memoria)

La Macchina di Turing è munita di una testina di lettura/scrittura che può:• leggere un simbolo dal nastro

• scrivere sul nastro il simbolo specificato da una quadrupla

• transitare in un nuovo stato interno, sempre seguendo le specifiche di una quadrupla

• spostarsi sul nastro di una posizione nella direzione indicata dall’eventuale suffisso dellaquadrupla

Quando non ci sono più quadruple per cui esiste un match con lo stato e l’input corrente, lamacchina si ferma.

LA METAFORA DEL NASTRO

TM


22/35


LE MACCHINE DI TURING

Risolvere un problema con la MdT significaquindi:

• definire una opportuna rappresentazione deidati iniziali sul nastro• definire la parte di controllo, cioè l’insiemedelle quadruple, in modo da rendere disponibilesul nastro, alla fine del computo, unarappresentazione della soluzione.


23/35



Consideriamo ilseguente insieme diquadruple:

NOP è uno speciale simbolo ad

indicare che non sarà eseguitaalcuna operazione di scrittura, ƀ è

un altro simbolo speciale che sta

ad identificare una cella vuota.

Allora le quadruple elencatedefiniscono un algoritmo perl’incremento unitario di una

stringa binaria!

s1 0 NOP s1 +

s1 1 NOP s1 +

s1 ƀ NOP s2 -

s2 1 0 s2 -

s2 ƀ 1 s4

s2 0 1 s3 -

s3 0 NOP s3 -

s3 1 NOP s3 -

s3 ƀ NOP s4 +


24/35



S1 S2

S3 S4

0,1 / NOP / +

ƀ / NOP / -

1 / 0 / -

ƀ / 10 / 1 / -

0,1 / NOP / -

ƀ / NOP / +

QUESTO E’ IL GRAFO DI TRANSIZIONE


25/35


LE MACCHINE DI TURINGE questo è un esempio di computo:

1 0 1 1

s1

1 0 1 1

s1

1 0 1 1

s1

1 0 1 1

s1

1 0 1 1

s1

1 0 1 1

s2

1 0 1 0

s2

1 0 0 0

s2

1 1 0 0

s3

1 1 0 0

s3

1 1 0 0

s4


26/35



Esistono macchine “più potenti” delleMacchine di Turing?

TESI DI CHURCH-TURINGNon esiste alcun formalismo capace dirisolvere una classe di problemi piùampia di quella risolta da una Macchina

di Turing.


27/35


Per esempio, si dimostra facilmente che una macchina di Turing multinastro non può fare,

calcolare, riconoscere niente più di quanto non

possa fare, calcolare, riconoscere

una macchina mononastro.

Nell’esempio è mostrata una

macchina a tre nastri.


TM


28/35


ƀƀƀƀƀ ƀ0100011000etc

ƀƀƀƀƀƀ1 ƀƀƀƀƀƀƀƀƀetc

ƀƀƀƀƀƀ0100011000etc

ƀƀƀƀƀ ƀ1ƀƀƀƀƀƀƀƀƀetc







ƀƀƀƀ ƀ ƀ1ƀƀƀƀƀƀƀƀƀetc


ƀƀƀ ƀ ƀƀ1ƀƀƀƀƀƀƀƀƀetc


ƀƀƀƀ ƀ ƀ1ƀƀƀƀƀƀƀƀƀetc





Di seguito un computo di unamacchina binastro che risolve ilproblema posto nella slide 19.


29/35



Una volta definita la parte di controllo, una MdTè in grado di risolvere un dato problema.

E’ specifica per quel problema.

È possibile pensare ad una Macchina di TuringUniversale, applicabile cioè a qualsiasi

problema risolubile?


30/35



Finora, l’algoritmo realizzato da una MdT eracablato nella macchina (DOVE??)

E se invece fosse sul nastro, e lamacchina se lo andasse a prendere?Come dovrebbe essere strutturata unasimile MdT?

Avremmo una Macchina di TuringUniversale


31/35



Dovrebbe essere una Macchina di Turing lacui parte di controllo (cioè l’ algoritmo “cablato”.. quindi l’insieme delle quadruple!) consista nel

leggere dal nastro una descrizione dellospecifico algoritmo richiesto.Una tale macchina può essere adattata perrisolvere un qualunque problema (risolubile)

senza modifiche alla sua struttura.E’, quindi, una macchina programmabile!


32/35



Cosa richiede questo?

Saper descrivere l’algoritmo richiesto.

E per descrivere l’algoritmo?

Occorre un linguaggio...

… e una macchina che lo interpreti.

Conclusione:

la Macchina Universale di Turing è l’interpretedi un linguaggio!


33/35



MACCHINA DI TURING UNIVERSALELa UTM modella il concetto di elaboratore diuso generale (“general purpose”):

una macchina che va a cercare

le “istruzioni” da svolgere… fetchle interpreta... decodee le esegue. execute


34/35



In sintesi …

leggere / scrivere un

simbolo dal / sul nastrocorrisponde a:

lettura / scrittura dalla /

sulla memoria RAM /

ROM

transitare in un nuovo

stato interno

nuova configurazionedei

registri della CPU

spostarsi sul nastro di

una (o più) posizioni

scelta della cella di

memoria su cui operare

(indirizzo contenuto

nell’Address Register)


35/35


THE END

gerarchia di macchine

Documents

Transcript of gerarchia di macchine