LEZIONE Problemi , algoritmi e modelli computazionali Nelle unità precedenti abbiamo parlato della relazione esistente tra algoritmo- linguaggi di programmazione e programma' Tale relazione può essere riassunra dal seguente schema: t:fTfT**"**"***\§\ f:t,Mttooo risolutivo 1 "*§r;-- trroe*to) j Est llr-=< Eap (ki. ffir{, Lne a- M I1r Un pr( ter Tr; (M LU] a In ch (qr a a a a La bl, lndMduazione di un algoritmo Bontà di un algoritrm tcomplessità .compuhazionale) ,ir.t:..it,iBguBgru^ r\ di:$rogrammazione ! \t {eodifica) Dati (input) Il precedente schema puo essere generalizzato nel seguente modo: -**J #iìiliaJ6i*,ri'#r -\ l, _9"r3lgolg1; Dati (input) §celta det linguaggio .Èiù adatto (sintassi e semantica) Risultati (output) Risultati (output) 106 BLOCCO TEMATICO B Teoria della comPutazione
'el!q!^los!r uou eJessa eqqe;lod otsanb 'eualqo"rd un aAIostJ ,,etuel-od nrd,, eurllf,3pru pl eqoueeu es el 'eJeAIosrJ p ef,selJ uou eJlle,l eqc euralqo"rdun eJeAIosrJ e eJlle,un rp ,.e.ro1131u-1,, eJesse aqqe.rtod 'llleJur 'e)lslJ eulr13f,etu eurì'PcrsrJ Pun]cseur PleuruJelep Pun Bp rf,Jelosur^s e ouo^Jes lclleualeu !llepout I
:oclleuoleu ollepou un eluelpet.U .'.olezz\eal aJasse gnd a;olncesa un
'olllnlosrJ olueurrpeoo;d Ir otetuaualdr-ur a tndtno,l otele;d:elul 'lndur,;oletuasa;ddeJ eJasse alep etuof, eJa^rJJSap Qoro eAeC 'lrullJofiIe e"rrn§ese rp op-e;3 ur eleuopepduoc ollspou un euroJ eu; ';alnduro3 elerule.l orduesa.red 'ec-rsrJ eurL{of,pru eun eu;oo alueurerJesseoeu olesuad eJessa e^ep uou aJolnoese.'I
uolncesf
!leuolzelnduoc !llepou e luluoFle Iluelqord
wflr
Un modelloLEZIONE computazionale:
la macchina di Turing
La macchina di ruring fu introdotta una decina di anni prima che fosse realil primo prototipo di elaboratore a "programma mem orizzato" , ed è stataderata un modello, con una struttura molto semplice e facile da percepire,tiene conro di rutre le proprietà logiche di una matchina reale capàce di esegqualunque algoritmo
La macchina di ruring assume un ruolo decisamente molto importante nel.Jooti'r,dnUr,onlpoÉohitttir-rrb srùcr:upra crdu'anarrsl oeglt-algontmt per decideresulla loro computabilità, cioè sul fatto che siano o mendrisoTvibili indipendenre-mente dalla macchina fisica su cui saranno eseguiti.
L'attuale struttura del computer (macchina di Von Neuman) deriva dal formali-smo della macchina di Turing.
La macchina di Turing rappresenta un prototipo astratto di macchina calcolatri-ce, costruito in modo da riprodurre cio che vi è di essenziale nel comportamentocomputistico dell'uomo.
Osserviamo che un computo eseguito da parte di un uomonumero finito di operazioni su un numero finito di simboli.si effetrua la moltiplicazione 31 x 17..
avviene mediante unCosi, per esempio, se
31 x17:
21731
527
si scrivono successivamente dei simboli su un foglio di carta, muovendosi in duedimensioni. Una prima semplificazione sta nelÈosservare che per eseguire uncalcolo è sufficiente disporre i simboli in una sola dimensione su una sriscia dicarta. Cosi l'operazione precedente potrebbe essere scritta nel seguente modo:
31, 17 217, 31, 5ZT
Se consideriamo che, nell'eseguire un'operazione,l'uomo osserva solo un nu-mero finito di simboli alla volta, possiamo effettuare un'ulteriore semplificazioneosservando un solo simbolo per volta.Questa e l'idea essenziale nel concetto di macchina di Turing: la sua condotta èinfluenzata solo dall'informazione locale e non globale. poich?, infine, la memo-ria dell'uomo sembra essere finita, si assume ctré ta macchina di Turing abbia unnumero finito di stati interni.
Da un punto divista informale, una macchina di Turing è costituita da:. un nastro;. una testina di lettura/scrittura;. un'unità di memoria interna;o un'unità di calcolo;o un,unità logica.
BLOCCO TEMATICO B Teoria della computazione108
607I OINSI llONSUddV lO YINn ?Ilqetoctec ellop euoel
'elleo pl ezz\eue e EJlsep e ltetsodg = 6:pllao ?l ez leue e eJlsrurs e llelsods = S
louu;eg = g
:rurpJo lluan§es I eIeq) olprluoc !p etlun,un rp plsrn^o"rd q tpyq el 'S'IJ ?llp rpueì.uoc r a;l1.ledur1
'gb olets ol ote;tsl8e;Q puJelul erJoueì.u elleu e (o.Dseu ps tluase;d IJelleJm Iep eJtsep ezuenbasol-1os pl e eJlsrurs ezuanbesollos el 'lso3 'opuenpr^rput; !x oyoquls II etueueluooellao eun ur e^oJl Is SulJnJ rp eulllf,f,pur ellap eurlsat e1 'lpurnb 'aluptsl IuFo ul
'1 oldu;ase "red'eletcads èJelleJeoun ep 'eJlsep e a eJlsrurs e 'elellullep Q aJeuruesa ep rloquls tp ezuanbes e1
'etureJ eJelseJ o elleo eun Ip EJlsluls e o eJtsep e ls.retsodse 'eur.rd o1els assoJ IJ etuetupnluena eq3 oylenb aJlnltlsos ep opour ul 'oJo^el Ip
Qnd 'ollorluoc !p ptlun,un Ep oleu:eno§ a oJlseu Iap ellespt eun ns oleuotztsodatuaureunuoddo 'aqc ousluerf,eu un a (S1I) etnp;rcs/ernpel !p eullsel P'I
'pJlsruls e ers eJtsep e els olJepuedsa eylqlssod e;du;es Q eqo lsueq 'IPUJ PululJeluou aLIJ ecrglu§ls uou olsenb :ollulJut elueule)IJoel Q oJlsPU II aLIs ouep oLuelqqv
'rleurJ e rpeuJelul Il?llnslJ I a eleJoqele aJesse ouo^ep eLp IuolzeulJoJulel euerluoo 'rpurnb 'oJtseu II 'elon^ eJessa a"rnddo 'oro^el !p oleqetle olpuIelt{)
{u* , ... ,zx,tx,or} = X
orlulJ etuarsul o1Jef, un e atuaueuedde oloquIlsolos un eJeueluoJ gnd lpnb ellep eunoseto 'ellec uI oslllp Q 'olelluJIIII elueuleJ-lJoel 'o^lllsodslp otsan§ 'tuotzeuJoJul el euelluoc eqJ olueu;nJls ol Q orlseu ll
unanl
esun
o1l
-IJ:
-a'.
EJ
el
-$
EJ
at-l!ol
-ca;o:
Y9e9eveeeòere
Y
Fu;rn1!p eulqcceu Bl :eleuolzepduoc ollepou un
a;, Q; - al,al, t
Gomportamento dellaLEZIONE macchina di Turing
L',ultim,a unità componente questa macchina e I'unità logica,preposra atta aeJsione da passi che la macchina dere compiere. rerpren-aeià tu/e dectsbne, o*sta per fornire I'istruzione corrispondente il successiiopasso da eseguire,l,unitàIogica necessita di due ingressi:
o il simbolo a, corrispondente al contenuto della cella sulla quale è posizionatain quell'istante la TLS;o il simbolo q,corrispondente allo stato della macchina in quell,istante.
Le varie combinazio_ni di questi due valori (a,, gJ definiscono univocamente ilcomportamento della Mdr. Infatti, dopo l'introduzione della coppia, l,unità Io-gica fornisce una terna di valori che corrispondono all'istruzione^da eseguire. Inparticolare:
e il simòolo a, che deve essere scritto nella cella su cui è posizionata Ia TLS;o il simbolo q, che indica lo stato q, in cui deve passare la macchina;o il simbolo ni, che rappresenta la àirezione in cui si deve muovere la TLS.
Possiamo concludere che la MdT è definita dalla seguente funzione logicaf:
LE34
St
Piu formalmente, la macchina di Turing (MdT) è una sestupla:
MdT = (Q,x,Y, f, qo, F)
dove:
. Q è I'insieme finito non vuoto degli statidella macchina;o X è l'insieme finito di simboli (alfabeto di lavoro, comprende tutti i simboliutilizzati sia in ingresso sia in uscita). Tale alfabeto comprende anche il simbo-lo speciale 1., precedentemente definito, che indica la cella vuota;
' Y (sottoinsieme di X) è l'insieme finito e non vuoto di simboli detto alfabetodi ingresso;
o f è una funzione, detta funzione di transizione, che mostra come evolvonostato e uscite:
e " y- e * X * {Desra, Sinistra, Fermo}
. go e Q e lo stato iniziale della macchina;o F (sottoinsieme di O è I'insieme degli stati finalidella macchina.
L',in
Qutstril90.chetal r
nes:fina
Costruiamo per esempio una{a,b,c}, scambia ciascun a con
BLOCCO TEMATICO B Teoria della computazione
MdT che, su una stringa costruita sull'alfabetob, ciascun b con c, ciascun c con a.
LLO
TTTI OlNll lloNluddv lo vllNn Pr[qeloclec ellop euoal
otets ollep Q rb'otsenb.red :rb e ayen8nrb otels ol eluesa;d eldntuynb euoluenb ur (puruuel euolzelndu-loc pl) elselJe !s e lb ole1s olyeu essed oserul :(elon^ ellasec) y oloqtuts pp elepuFas eFul.rts ellep eulJ el eJluof,ul uoue ourJ enunuoo e oleJoprsuoc ptF oloqluls Iep pJtsep e1p etsods ls lpurn§ur opueueulJ olsertlf,rJ olqurpos o1 enEese (el?tztut orels) 0b otels olleu '
ellep oloquns ou:ud II eiueueluoJ elleJ ellns puorztsod ts Puttlocetu'rpl l EIIop eurelu! euouoru ellou olezzrJotueur q eldnlulnb ellop etu
7 'u e1dn1u1nb eq opuect;dde
r;-", lIY
g 'u e1dn1u1nb e1 opueclldde
lT;-l +
T 'u eldnlurnb eg opuecgldde
T 'u eldnlulnb e1 opuec;ldde
Z 'u eldnlulnb el opueclldde
:en8es euoc euarlLe euorzelnduoc e1
l-'6-q I+
:eprzrur auorzenlrs aluenBes el eJe^e lp otdu;ese "rad oueluoddng
louJeJ ots e (epur; otets) Ib olels olleu ope^ Y o^lJf,s Y o33et es 0b otets o1leu
S'Ir el eJlsep e otsods e 0b olels olleu olseJ e ollrcs c oF8al as 0b olels olleu
SIJ el eJtsep e olsods a 0b olets olleu olser f, oAIJJS q o8Fet es 0b olels o11au
STJ pl ?Jlsap e olsods a 0b o1els olleu olsal q oAIJcs e oF8al es 0b olels olau
Definisciuna MdT che esegua l'addizione di due numeri naturali
Rappresentazione dell' InPut
I numeri sono rappresentati sul nastro da una sequenza di barre l. Al numeroviene fatta corrispondere una barta, al numero 1 due barre, al numero 5 sei
re e cosi via. Due numeri sono rappresentati da due sequenze di barre sepa
dalla cella vuota.Per esempio, per eseguire 2 + 3 awemo la seguente situazione di pattenza.
Gomputazione
Per effettuare la somma la MdT riempie con una barra la cella vuota che separa i
due numeri e cancella le due barre finali del secondo numero.
Rappresentazione dell'outPut
E la seguente situazione di arrivo o fine computazione:
). 1. l, ),"
À, Q+
MdT = (Q, X,Y, l, qo' F) dove:
e = Ìqo : "rrìi sfi"osto sulprimo numero", q,.: "^i sposto sul secondo numero",
q, = ' ià19"11o la prima barra" , gs = "cancéilo la seéon dabarta" , qo : finale)
r: {À.. l} alfabeto di lavoroY = {I l} alfabeto di ingressoStato iniziale = go
F = {qn}f tfunàiòire di gansizione) e così definita dalle seguenti quintuple:
4 ^ I I n Tr
- ln Qs, s€ leggo l, rimango in qo cioè nello stato che mi fa
*' Yo I I Y0 spostare sul primo numero
2. eo ). I q, D - ll itj?rffi à,ilffi, [:nxlJlt' cioè nerro stato che
ln q, se teggo | , scrivo l, rimango in q, cioè nello stato che
3' 9r I I gr D -
mi fà spostare sul secondo numero
ln q, se leggo 1', vuol dire che ho finito di leggere il secondo
4. gt )" 1, 9z S
- nuniero e quindivado in q2 cioè nello stato che mi dice che
- devo cancellare una barra
5. ez | ), es s - [#',:ìJ:*[ |d,T:[*J"Ì;:;H".'"ffi[t:T: barra e
.lnq3,seteggol,cancellolasecondabarra,vadonellostato6' 9z | )' 9s F
- finaÌe qo e mif"rmo
BTOCCO TEMATICO B Teorla della computazioneLLz
8TTI OINSI ilONIUddV tO V-IlNn P]illqetoctec eilap euoel
eluJol rs e zb eleur1 o]e]s ollou eA
'(,,tr gp greds;p orounu un o$el eq,, ?olc Tb ul ? gqcrod) p o^Ucs
'Ìndur ur ezuanbes ellap oulJ e; eBBe; es Qolc i epFel es ''t ,t -
J
euJe, !s a zb eleurl olels olloueA'(,,T rp ued oreunu un o11al eq" Qotc
ob ul Q qqctod)d enucs \ C'1ndu1 u1 ezuenbas ellop aug e; aFFa; os ?otc l eBFeg es '0b u;
--Q
zbpytb
zbdl%
Iboorb T rp rJedsrp oJatunu un oBol e lsor.lc ocrp or.lc olels ollou qotc rb ur oueuu 'g elFel os 'rb u;
T lp Ued oJaunu un ollq? !s aqc aclp aL{c o}e}s ollou go;c ob ,;
"n'tr eFBel es ''b'ui- C
,S p ued ototilnu un opal Q ts ,ato a?paLlc olels ollau ?olc
ob ul auewp'i rnr,,;;;bb= i- o
ob I I 'b'g
ob o o ob'z
I tp tredslp oJorunu un opel? rs aqc eclp eLlc olels ollou qorc Tb ur e^ 'T eF8eg es 'ob u;
-C Ib t I ob.T
:aydnturnb rtuan8es ellpp ellulJap ISoo q (euorzlsueJt rp euorzunJ) J
:Ups aleurJ euorzentrs el otsr^ euedde orduasa,llap'ossa;§ur ur rloqì.urs rep ezuanbes ellep eJtsep e ellesm euuy.rd elyeu
,,d,, anucs purqocpru ey '(etonn q ezuenbas ey as a;nddo) r.red a I Ip oJeunu Jr eS'ossa"iEur ur rloqurs rep ezuenbes ellep
eJtsep e ellespf, eurud elJeu ,,p,, aATJJS eurLlf,f,eul ey 'uedsrp a I Ip oJeunu Ir aS
pd1no, 1;ep euolzelueserddeg
e7'oln8as Ip eleJlsotu
'e"re§Eel ep eJamerp3 ou-r1.ld 1ns eteuorzrsod g eullsale11anb eresse Qnd IpW el1pp ezual;ed 1p auorzentrs e'I
pdug, 1;ep euolzelueserddeg
'3JOllf,SOu03rJ etuolneo^BeleJ 1r rnb ouer1rodu rnc rp 'nuolne II3 uocolpluoUJe eJesse gnd etuelqo;d ossals otsan§'uedsrp a I Ip oJerunu II 'l e 6 rp ezuenbaseun ur 'es eJe3rJrJen ,red 1pyrl ?un rf,srurJeg
e Oldl,ìl3sf
Fu;rn1 !p eulqcceuJ ellep olueueyodruoC
ob ,p
Y1pTT00T1
0b ,tr
Y1YTT00IY
LEZIONE
6
iStati iai """- ^"
i b,qo,D
:, . :l?p
stato dipende siarealtà questa funzifunzione di ras
, À,q',rStop
Rappresent aztonedella tunzionedi transizione
Consideriamo la MdT della lezione precedente. Il nuovostato in cui ci si trova, sia dal simbolo letto in input. Inincorpora sia la funzione di transizione dello stato, sia lazione delle uscite, usate per lo studio degli automi.
Rappresentazione della funzione di transizioneLe quintuple che descrivono il comportamento di una MdT possono esserepresentate:
o in forma tabellare con una tabella di transizione (o matrice funzionale);o in forma grafica con i diagrammi di stato (che vedremo tra breve).
Rappresentazione con tabella di transizioneIn una matrice funzionale le colonne indicano i possibili input che possono eletti e le righe i differenti stati in cui puo rrovarsi la macchina. In ogni cella è cnuto il nuovo simbolo da scrivere, il nuovo stato e il tipo di movimento da eLa tabella di transizione per la MdT vista nella lezione precedente è:
"'! '-" ""'l'-"-"' -'''
isi"il
c. go, D ,. go,DStop_ Stop
Rappresentazione dell'input e dell'outputRisolvere problemi con la macchina di Turing sisnifica:o definire un'opportuna rappresentazione dei dati inizialisu nastro;o definire la funzione di transizione che mostra il reale processo di calcolo (
nt IfrTi^npl della menrhino.o definire la rappresentazione del risultato finale o dell'output.Consideriamo una MdT che "somm a una unitit a un numeto scritto in notazionedecimale". La rappresentazione dell'input è definita dall,insieme delle seguentiquintuple:
,90.,9r
7. go 6 7 9, F8. 9o 7 B q; F9.90899, F10.9090g0S11.Q0). 1QrF
olels ol .eurel ls o e^onu Lin e'Aunta3e eu 'elJeq ellep au[ elle e^lrJe
- J tb I V
0b
erieq eun eEBe; gqcug elsods rs
- A ob
I I ob
'e1on^ ouels ellef, el el1nl
eJJeq el odop aqc ou;etuoddnS 'eldntupb Ip sulalsul eluen§as I eJezaltn o1nlod
ouruleJ^e oletuasa"rddeJ ISoc oJeulnu p Pllun eun eJeuluJos Jed 'PIA Isof, e eJJeq
eJ1 Z OJeuInu Ip .eJJeq enp I oJaunu p 'eJJeq eun aJepuodst't'toc e1leJ euel^ 0
o,"-n,p.Ie"r,leqlpezuenbesectldueseu]o3etu.epulf,apauolzelouuIuouoJeurnu Ir o11;elluese.rdde; etlon etsenb eLU ',.oJetunu un ? Pllun eun euIulos,, eLIf,
ellecuec aqc eìlo^ quEo) olaunu opuocas 11 e ou:pd l! eD elsods tS
Ib**9b
eb I lebeb+*sb
eb I I eb
.IJ1
-ue
olounu oLuud lep eJleq pun ellocuec C
S
oreunu opuocos lop olzlul,lle eA-S
auorzelnduoc el epnlcuoc e euJro] lS -_0b
eÌro^ u ereraÌ! s
lp ereqrl g erg '(ereq T + u uoc eluesa.lddei ls orolJ.lnu |t gqctod)
olournu opuocas lep ouotzeluesoldde.l ellap ereq eun ellacueC -\ S
eb
hb
eb
Y!Sal
!1eluo
*+bb
" Itb**''blleb**zb
llzbI
,b
zb _ | rb
epnluln§
'olel1nslJ Iep eJJeq pun ns eteuolzlsod eb o1e1s olleu euJeJ Is eulqcceur e'I
Udlno,llop ouoFeluo§etddeg
.EIJPSSEJAU IUOIZ
-pJe1l Ip oJeulnu Iep eJoteluoc ep 'lpurnb 'e^Jes oJeulnu opuoJes Il'eun ellafue)eu e ou;ud InS Blsods IS oJeulnu opuoJes Iep eJJeq tuflo "lad 'oJeuInu opuoJes
