Informatica Teorica

Linguaggi di programmazione e macchine di Turing

• Data una MT è possibile costruire un programma Pascal o C che simuli purché il calcolatore che esegue il programma disponga di una quantità di memoria sufficientemente grande da non causare alcun overflow durante l'esecuzione.

• Dato un programma Pascal o C è possibile costruire una MT che calcoli la stessa funzione calcolata dal programma.

Si è dunque scoperto che le MT hanno la stessa potenza di calcolo non solo delle grammatiche non ristrette, ma anche dei programmi sviluppabili nei consueti linguaggi di programmazione ad alto livello.

Conclusione: tutti i formalismi noti per modellare dispositivi di calcolo discreti hanno, al più, la stessa potenza delle macchine di Turing.

Tesi di Church: non esiste alcun formalismo, per modellare una determinata computazione meccanica, che sia più potente delle MT e dei formalismi ad esse equivalenti.

In base a tale enunciato,

Poiché non esistono formalismi più potenti delle MT, possiamo dire che, se si riesce a dimostrare che un problema può essere risolto da una MT, si può allora dedurre che il medesimo problema può essere risolto da un qualunque modello matematico di calcolo con la stessa potenza delle MT. Viceversa, se si dimostra che un problema non può essere risolto da una MT si può allora dedurre che il medesimo problema non può essere risolto da un qualunque altro modello matematico di calcolo; in altri termini, è inutile cercare di risolvere meccanicamente ciò che non può essere risolto da una MT.

ALGORITMI

Intuitivamente, gli algoritmi si possono intendere come un metodo astratto di descrizione dei programmi eseguibili da un calcolatore; un tale programma è una sequenza di comandi che, una volta eseguita dal calcolatore, può risolvere un determinato problema.

algoritmo rappresenta la sequenza astratta di operazioni

Elementari che risolvono un problema in modo meccanico, indipendentemente dal particolare processore (o linguaggio di codifica) scelto.

• Un algoritmo deve contenere una sequenza finita di istruzioni.
• Deve esistere un agente (processore) che sia in grado di comprendere univocamente le istruzioni e di eseguirle producendo risultati precisi e prevedibili.
• Il processore è dotato di dispositivi di memoria in cui possono essere immagazzinati i risultati intermedi.
• La computazione è discreta e non esiste limite al numero di passi richiesti per effettuare un calcolo.
• Gli algoritmi vengono eseguiti deterministicamente.
• Non esiste un limite finito sui dati di ingresso e di uscita.
• Non c'è limite alla quantità di memoria richiesta per effettuare i calcoli (se la memoria di un calcolatore non è riempita completamente durante un calcolo, si può supporre che sia illimitata rispetto a quel calcolo).

Tesi di Church:

Ogni algoritmo per la soluzione automatica di un problema può essere codificato in termini di una MT (o di un formalismo equivalente).

3. ENUMERAZIONE E MACCHINE DI TURING UNIVERSALI

Finora le MT sono state studiate in qualità di dispositivi che sono in grado di risolvere un particolare problema, definito dalla funzione di transizione. Per questo motivo, le macchine di Turing si possono considerare come calcolatori astratti, specializzati e non programmabili; una volta caricato il programma nella memoria di sola lettura del calcolatore, la macchina può eseguire solo quel programma.

ENUMERAZIONE enumerato algoritmicamente

S, S_N

Dato un qualsiasi insieme può essere se è possibile stabilire una biiezione fra e l'insieme dei numeri naturali

A MT

Fissiamo ora un alfabeto e consideriamo l'insieme delle MT a nastro singolo e senza stati finali, aventi AA MT <-> MT come insieme di simboli. Mostriamo come possa essere enumerato, ovvero definire : .

Ak A kPer ogni intero esiste un numero finito di MT, aventi come insieme di simboli ed esattamente di nastri.Infatti, il numero di modi diversi in cui si può definire la funzione di transizione fissato l'alfabeto e il numero distati risulta finito, poiché ha dominio e condominio finito. dif: D -> R, D R fIn generale, data una funzione con e finiti vi sono esattamente funzioni totali diverse.IRISeguendo lo stesso ragionamento per le MT, poiché la funzione di transizione è definita comeQ A -> Q A L, S},: x x x {R, esisteranno esattamenteo lQlilAIIQI.la1 13 macchine di TuringA Qaventi come insieme dei simboli e come spazio degli stati. n.ieh A, kSe chiamiamo la cardinalità dell'insieme allora esistono MT dotate di stati.h.ie1 3MT kPer poter enumerare le MT in è ora necessario ordinare le MT a stati seguendo un preciso criterio, adAesempio in base all'ordine lessicografico, stabilendoq < q < ... < q blank = a <

a < ... < a R < L < S◦ 0 1 k-1 0 1 h-1(q, a) < (q’, a’) q<q’ q=q’ a<a’se e solo se oppure se allora◦ R.l.SII(q, i) = (q, a, m)funzione indefinita <I EA◦ Hmtao taco e(q, a, m) < (q’, a’, m’) q<q’ q=q’ a<a’ q=q’ a=a’ m<m;.se e solo se oppure se allora oppure se allora◦M M’, M M’ <q, a>< ovvero precede nell’ordine lessicografico se, nella prima coppia in cui le relativefunzioni di transizione differiscono, il valore di risulta minore del valore di .o oA questo punto si può ottenere una enumerazione di tutte le MT ragionando nel modo seguente. Prima sienumerino tutte le MT a un solo stato, secondo l’ordine stabilito, poi si enumerino tutte le MT a due stati eE N <-> MTcosì via. Come risultato si ottiene una biiezione : .AGödelizzazione.Un’enumerazione calcolabile da una MT viene chiamata numero di

Gödel. Il numero naturale biiettivamente associato ad una MT è chiamato N N. Per comodità, si farà riferimento a MT che si comportano come dispositivi che calcolano funzioni da inEM M• indicherà l’i-esima macchina di Turing nella enumerazione ossia = (i)i if M• indicherà la funzione calcolata da .i i MACCHINE DI TURING UNIVERSALI Per macchina di Turing universale (MTU) si intende una MT capace di modellare dispositivi generali di risoluzione di problemi, in cui il problema da risolvere non viene codificato nella struttura del dispositivo, ma viene fornito come ingresso, insieme con i dati su cui operare. g(i, x) = f (x), Possiamo definire una MTU come una MT che calcola la funzione cioè una MT che ricevuti in ingresso due numeri naturali y e x, rappresentano rispettivamente la funzione calcolata dalla i-esima MT e l’ingresso che è l’effettivo ingresso su cui deve operare, calcola il valore della f(x).

funzione applicata ay yfLa MTU così definita non sembra appartenere alla famiglia {MT }, in quanto le funzioni associate alle MT inAg{MT } sono funzioni di una variabile, mentre è una funzione di due variabili; questo problema è risolvibile inA NxN N.quanto esiste una biiezione effettiva tra eN <-> MT g: NxN -> N g(x,y) = f (x).Si considerino l’enumerazione : e la funzione definita daE A yNxN N 411Un esempio di biiezione da a è dato dalla funzione 1dixit 142g i f = gSi osservi che è una funzione MT_computabile, ovvero esiste tale che iASi scelga un alfabeto finito ( |A| > 2 ) per codificare i numeri naturali ed ogni altra informazione◦ possibile richiesta per la computazione.n y).Si traduca la rappresentazione di in un’opportuna rappresentazione della coppia (x, La◦ n x y,rappresentazione decimale di può essere tradotta nelle due rappresentazioni decimali di eseparate da un simbolo $.y MSi traduca il numero in

un’opportuna codifica della MT y-esima nella enumerazione, ossia◦ yM x.

Si simuli la computazione di su◦ y g (x, y) = f (x) y x;

Esiste e si può costruire una MT in grado di calcolare per ogni e per ogni una MT di questoymacchina di Turing universaletipo viene chiamata (MTU) poiché è in grado di simulare il comportamento diqualunque altra MT.

4. PROBLEMI IRRISOLVIBILI

• Quanti e quali sono i problemi risolvibili algoritmicamente?
• f : N->N

Come abbiamo visto, tutte le funzioni computabili si possono enumerare; questo significa che layNcardinalità delle funzioni computabili è pari a .0 NoN N->N}| 2D’altra parte, è noto che la cardinalità della classe delle funzioni su è |{f: =anche chiamata cardinalità del continuo, essendo la medesima cardinalità dell’insieme dei numeri reali.N->N} N N->[0,1]}, N.Infatti, l’insieme {f: contiene la classe delle funzioni da in [0,1], ovvero {f:

poiché [0,1] cNoN->N} N->[0,1]} P (N) | = 2Quindi, poiché | {f: | > | {f: | = | , possiamo dedurre che la cardinalità della classe artN delle funzioni da N in è strettamente maggiore della classe delle funzioni computabili; si può quindi concludere che gran parte delle funzioni di non può essere calcolata. PROBLEMA DELLA TERMINAZIONE DEL CALCOLO Studiando i diversi modelli di calcolo, abbiamo visto che un AF termina la sua computazione per qualsiasi colore in ingresso, mentre gli AP per alcune stringhe in ingresso possono entrare in un cammino formato da una sequenza infinita di ε-mosse, e quindi andare in loop. Tuttavia esiste un teorema che garantisce la possibilità di costruire per ogni AP ciclico un AP aciclico equivalente, privo di cicli infiniti. • Cosa accade per le MT e per i programmi scritti in linguaggi di programmazione senza vincoli? In questi casi non è possibile garantire a priori la terminazione del calcolo.

programma per un generico valore di ingresso, né decidere attraverso un algoritmo se ciò possa avvenire in corrispondenza di uno specifico dato; in termini generali, il problema della terminazione del calcolo automatico è non decidibile.

Teorema: nessuna MT può calcolare la funzione totale definita nel seguente modo:

g(x, y) = if f(x) = M x o se giunge in uno stato finale leggendo una y then 1 (1 se la computazione termina) else 0 (0 se la computazione non termina)

Dimostrazione

Lemma: nessuna MT può calcolare la funzione totale definita da