Macchine teoriche

• modelli di calcolo teorici
• semplici al punto di poter venire definiti in modo matematico
  (in termini di insiemi, funzioni, ecc.)
• non realistici, però entro certi limiti equivalenti a quelli reali
  es: macchine di Turing e computer reali possono risolvere gli stessi problemi

la macchina di Turing

definita da Alan Turing nel 1936

von neumann

memoria ad accesso casuale di grandezza finita

turing

nastro di lunghezza illimitata

 ---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x | a | z | 3 | 2 | 0 | d | a | 9 | ...
 ---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---

tipo di lettura

von neumann

una locazione qualsiasi

turing

testina che si muove sul nastro
un solo spostamento per volta

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | 9 | ...
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
                               |     |
                          <--  |     |  -->
			       |     |

spostamento a destra (D) di una posizione
oppure a sinistra (S)

schema della macchina

nastro, testina e unità di controllo

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | 9 | ...
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
                               |     |
			+------+     +------+
			|                   |
			|                   |
			|                   |
			|                   |
			|                   |
			|                   |
			+-------------------+

la macchina può:

• leggere il valore sotto la testina
• scrivere un nuovo valore
• spostare la testina a destra (D) o a sinistra (S) di una sola posizione per volta

unità di controllo

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | 9 | ...
 ---+---+---+---+---+---+---+--| | ^ |--+---+---+---+---+---+---+---
                               | | | |
			+------+ V | +------+
			|                   |
			|  +---> (2) ---+   |
			|  |            |   |
			| b/Sa        x/Sb  |
			|  |            |   |
			| (0) -a/D2--> (1)  |
			|              ( )  |
			|             x/Da  |
			|                   |
			+-------------------+

internamente: una macchina a stati finiti dice cosa fare
un po' diversa da quelle viste finora

automa interno

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | ...
 ---+---+---+---+---+---+---+--| | ^ |--+---+---+---+---+---+---+---
                               | | | |
			+------+ V | +------+
			|                   |
			|  +---> (2) ---+   |
			|  |            |   |
			| b/Sa        x/Sb  |
			|  |            |   |
			| (0) -a/D2--> (1)  |
			|              ( )  |
			|             x/Da  |
			|                   |
			+-------------------+

riceve il valore letto dalla testina

fornisce: spostamento della testina D/S e nuovo valore da scrivere

automa interno

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | ...
 ---+---+---+---+---+---+---+--| | ^ |--+---+---+---+---+---+---+---
                               | | | |
			+------+ V | +------+
			|                   |
			|  +---> (2) ---+   |
			|  |            |   |
			| b/Sa        x/Sb  |
			|  |            |   |
			| (0) -a/D2--> (1)  |
			|              ( )  |
			|             x/Da  |
			|                   |
			+-------------------+

esempio: stato 0, valore sotto la testina a

segue la freccia da 0 marcata a/qualcosa

in questo caso, a/D2:

• la testina va a destra (D)
• al posto di a viene scritto 2

automa interno

                               /-----\
 ---+---+---+---+---+---+---+--|     |--+---+---+---+---+---+---+---
... | 2 | a | k | 9 | r | s | x|     |z | 3 | 2 | 0 | d | a | ...
 ---+---+---+---+---+---+---+--| | ^ |--+---+---+---+---+---+---+---
                               | | | |
			+------+ V | +------+
			|                   |
			|  +---> (2) ---+   |
			|  |            |   |
			| b/Sa        x/Sb  |
			|  |            |   |
			| (0) -a/D2--> (1)  |
			|              ( )  |
			|             x/Da  |
			|                   |
			+-------------------+

da stato e carattere letto, fornisce:

• spostamento della testina (destra o sinistra)
• carattere da scrivere al posto di quello letto
• nuovo stato

spostamento e carattere da scrivere dipendono dal carattere letto
per questo vanno sulla freccia e non nello stato

non in figura: l'automa ha anche due stati accetta e rifiuta

cosa fa

risolve solo problemi di decisione (risposta 0/1) su stringhe

si mette la stringa da analizzare sul nastro

l'automa procede

risposta: stato accetta o rifiuta

definizione teorica

⟨alfabeto nastro, insieme stati, stato iniziale e due finali, funzione di transizione e output⟩

funzione di transizione:

dato

stato e carattere letto

fornisce

nuovo stato, spostamento (D o S) e carattere da scrivere

alfabeto

sono i caratteri che possono stare sul nastro

si assume che uno di questi sia il blank: ␣

all'inizio la stringa da analizzare è sul nastro
le posizioni prima e dopo contengono ␣

macchina di Turing: esempio

il nastro e la testina sono uguali per tutte le macchine

a seconda della funzione da calcolare c'è un automa diverso

esempio: macchina che riconosce se la stringa ha un numero pari di uni

  A          R
  ^          ^
  |          |
  _          _
  |          |
  0 --1/D1-> 1 
( ) <-1/D1-- ( )
0/D0         0/D0

spiegazione?

numero pari di uni: spiegazione

  A          R
  ^          ^
  |          |
  _          _
  |          |
  0 --1/D1-> 1 
( ) <-1/D1-- ( )
0/D0         0/D0

si parte dallo stato zero

cappio 0/D0

se arriva 0, si va nello stato 0
la testina si sposta a Destra ma prima scrive 0

cappio 0/D0

se arriva 1, si va nello stato 1
la testina si sposta a Destra ma prima scrive 1

…

omissioni

  A          R
  ^          ^
  |          |
  _          _
  |          |
  0 --1/D1-> 1 
( ) <-1/D1-- ( )
0/D0         0/D0

omettiamo i valori irrilevanti

␣ = ␣/Mc
con M=D o =S e c carattere qualsiasi

programma fisso

la macchina esegue un programma fisso

del resto, anche gli automi
macchina di Turing = automa + nastro

programma = automa interno = funzione di transizione

altro programma?

esempio: macchina che verifica le parentesi

è una diversa macchina

ha un altro automa dentro

macchine con output

input

stringa sul nastro all'inizio

output

stringa sul nastro alla fine

carattere ␣ intorno alla stringa: prima del primo carattere e dopo l'ultimo

esempio di macchina con output

macchina che somma uno

[macchina di Turing che somma uno]

spiegazione…

macchina che somma uno

[macchina di Turing che somma uno]

alfabeto binario

lo stato iniziale fa avanzare la testina fino alla fine della stringa

il secondo stato fa tornare indietro fino al primo zero
nel farlo, cambia uno con zero

il primo zero viene convertito in uno e si termina

sul nastro: il numero aumentato di uno

altro esempio di macchina di Turing

[macchina di Turing che somma uno]

verifica se le parentesi sono bilanciate

solo accetta/rifiuta

spiegazione…

parentesi bilanciate: cerca )

[macchina di Turing che verifica se la parentesi sono bilanciate
evidenziato lo stato iniziale]

avanza fino al primo )

parentesi bilanciate: torna indietro a (

[macchina di Turing che verifica se la parentesi sono bilanciate
evidenziato lo stato che fa tornare a ( cancellando quello che trova]

torna indietro cancellando tutto fino al primo (

in questo modo, ha cancellato le parentesi più interne:

(abcd(erjf(efg)…
       ⇓
(abcd(erjfxxxxx…

ora: ricomincia ad andare avanti

parentesi bilanciate: torna all'inizio

[macchina di Turing che verifica se la parentesi sono bilanciate
evidenziato lo stato che fa tornare a ( cancellando quello che trova]

ci si arriva alla fine della stringa

torna all'inizio: se trova ( rifiuta

semantica della macchina di Turing

macchine 0/1

si mette la stringa sul nastro

risultato:

• accettata
• rifiutata
• la macchina non termina mai

non terminazione

con gli automi non era possibile:

automi: un carattere = una transizione di stato

alla fine, in qualche stato l'automa doveva stare:

• finale = accetta
• non finale = rifiuta

macchine di Turing:

si può ripassare più volte per una stessa posizione del nastro

macchina di Turing non terminante

[macchina di Turing che non termina]

• primo ingresso 0: rifiuta
• secondo ingresso 1: accetta
• primo 1 e secondo 0: non termina

semantica della macchina di Turing

• data la macchina e una stringa
• la semantica dice se la stringa viene accettata, rifiutata, o la macchina non termina

semantica formale della macchina di Turing

⟨alfabeto nastro, insieme stati, stato iniziale e due finali, funzione di transizione e output⟩

data una stringa s

la stringa definisce il nastro all'inizio

la semantica è simile a quella degli automi

dice:

• come cambia lo stato
• come cambia il nastro
• come cambia la posizione della testina

semantica automi e macchina di Turing

automa: stato successivo e uscita

Turing: stato successivo, stato del nastro e posizione della testina

definizione di terminazione e accettazione

terminazione = si arriva allo stato accetta o allo stato rifiuta

non come gli automi: dopo questi non si va oltre

accetta/rifiuta = dipende dallo stato a cui si arriva

differenza macchina di Turing — computer

macchina di Turing:

• nastro infinito
• spostamento testina una sola posizione alla volta

computer:

• memoria finita
• accesso causale
  in qualsiasi momento si può accedere a una qualsiasi locazione

macchine di Turing multinastro

invece di un nastro ne hanno k

[tre nastri]

esempio: tre nastri

il primo nastro ha alfabeto {0,1,&,D,S}

testine

[tre nastri, ognuno con la sua testina]

ogni nastro ha una sua testina di lettura/scrittura indipendente dalle altre

i movimenti dei nastri sono indipendenti:
es: il primo nastro può andare a destra mentre il secondo e il terzo a sinistra

automa multinastro completo

[tre nastri, ognuno con la sua testina, e l'unità di controllo]

la macchina ha il solito automa dentro

riceve

tre caratteri

fornisce

tre comandi destra/sinistra (anche diversi)
tre caratteri da scrivere (anche diversi)

si può andare a destra sul primo e terzo nastro e a sinistra sul secondo

teorema sulle macchine multinastro

per ogni intero k:

k nastri o uno sono la stessa cosa

in termini formali: ogni linguaggio riconosciuto da un macchina di Turing a k nastri è riconosciuto da una macchina di Turing a nastro singolo

la macchina di turing universale

ha in ingresso la descrizione di un'altra macchina di Turing

ne simula il funzionamento

"È possibile inventare una sola macchina che può essere utilizzata per calcolare qualsiasi sequenza computabile. Se questa macchina U è dotata di un nastro in cui all'inizio è fornita la 'descrizione standard' della funzione di transizione di una macchina M, allora U calcolerà la stessa sequenza di M." [Turing, 1936]

la macchina universale, in termini moderni

un computer che non esegue una serie prefissata di passi
lavorare secondo un programma che viene dato in input

adesso sembra ovvio, allora no

definizione della macchina universale

tre nastri:

• nastro con una descrizione della macchina M da simulare
• nastro usato da U
• nastro che si comporta come quello di M

codifica di una macchina di Turing

è uno degli ingressi di quella universale

esempio: macchina del numero pari di uni

stati 0, 1, 10=accetta, 11=rifiuta

codifica della macchina = una sequenza di caratteri da mettere sul primo nastro

codifica della macchina

num_stati && funzione_transizione

nell'esempio:

100 && 0 & 0 & 0 & 0 & D && 0 & 1 & 1 & 1 & D && …
       -----------------    -----------------    ---

0&0&0&D

stato 0, ingresso 0 → vai a stato 0, scrivi 0, sposta D

0&1&1&D

stato 0, ingresso 1 → vai a stato 1, scrivi 1, sposta D

…

lo stesso per tutti gli altri elementi della funzione di transizione

questa è la macchina M
va sul primo nastro di quella universale

secondo nastro della macchina universale

secondo nastro = stato della macchina M
inizialmente 0

macchina universale: funzione di transizione

è l'automa interno di U

a ogni passo:

• secondo nastro = stato attuale di M (s)
• terzo nastro = carattere letto (c)

si cerca sul primo nastro una sequenza &&s&c&A&B&C&& e si scrive:

• secondo nastro: nuovo stato A
• terzo nastro: nuovo carattere B
• spostamento sul terzo nastro: quello specificato da C

simulazione

un passo di M
⇓
una intera ricerca sul primo nastro
⇓
molti passi della macchina U

macchine di Turing non deterministiche

come gli automi non deterministici:

a ogni passo sono possibili più scelte di stato successivo

accettazione se almeno una delle scelte porta allo stato accetta

oppure: a ogni istante di tempo un insieme di stati e un insieme di possibili stati del nastro

equivalenza fra macchine

sono equivalenti:

• macchine di turing, multinastro e non deterministiche
• macchina di Post
• lambda-calcolo
• algoritmi di Markov
• macchine RAM

es: ogni linguaggio riconosciuto da una RAM ha una macchina di Turing che lo riconosce

tesi di Church-Turing

tutto quello che si può calcolare (con un qualsiasi modello di calcolo) si può calcolare con una macchina di Turing

non esiste un modello di calcolo più potente di una macchina di Turing

macchine RAM

sono un modello più realistico

sempre teorico, ma simile ai computer reali

comode per valutazioni di efficienza dei programmi
uguali a Turing per quello che riguarda la calcolabilità

macchina RAM

+--------------------------+              +---+
|   +---+                  |              | 2 | (0)
| +-| 0 | PC               |              | 3 | (1)
| | +---+                  |              | 5 | (2)
| |                        |              | 1 | (3)
| +->   | (2):=5           |              |14 | (4)
|     f | [2]:=(4)/2       |              | 9 | (5) = [2]
|       | (4):=9*[5]       |              | 3 | (6)
|     h | if([2]>4) goto f |              | 7 | (7)
|     i | [2]:=(3)         |              | 2 | (8)
|       | end              |              | 0 | (9)
+--------------------------+              | 0 | (10)
                                          | 0 | (11)
					  |...|

programma

istruzioni numeriche e salti condizionati

memoria

vettore di numeri

macchina RAM: memoria

+--------------------------+              +---+
|   +---+                  |              | 2 | (0)
| +-| 0 | PC               |              | 3 | (1)
| | +---+                  |              | 5 | (2)
| |                        |              | 1 | (3)
| +->   | (2):=5           |              |14 | (4)
|     f | [2]:=(4)/2       |              | 9 | (5) = [2]
|       | (4):=9*[5]       |              | 3 | (6)
|     h | if([2]>4) goto f |              | 7 | (7)
|     i | [2]:=(3)         |              | 2 | (8)
|       | end              |              | 0 | (9)
+--------------------------+              | 0 | (10)
                                          | 0 | (11)
					  |...|

• (2) = secondo elemento del vettore
• [2] = quinto elemento del vettore, dato che (2)=5

input: i valori dei primi registri
quelli non usati per l'input contengono inizialmente zero

macchina RAM: esecuzione

+--------------------------+              +---+
|   +---+                  |              | 2 | (0)
| +-| 0 | PC               |              | 3 | (1)
| | +---+                  |              | 5 | (2)
| |                        |              | 1 | (3)
| +->   | (2):=5           |              |14 | (4)
|     f | [2]:=(4)/2       |              | 9 | (5) = [2]
|       | (4):=9*[5]       |              | 3 | (6)
|     h | if([2]>4) goto f |              | 7 | (7)
|     i | [2]:=(3)         |              | 2 | (8)
|       | end              |              | 0 | (9)
+--------------------------+              | 0 | (10)
                                          | 0 | (11)
					  |...|

esecuzione sequenziale, a parte i salti

PC=program counter

• indica l'istruzione da eseguire
• si parte da 0 (prima istruzione)
• si incrementa, a parte i salti

termina: istruzione end

valore calcolato: cella 0 di memoria

considerazioni sulla macchina RAM

è una macchina teorica:

• memoria ilimitata come numero di celle
• ogni cella contiene un numero naturale qualsiasi

differenza RAM — macchina di turing

nelle RAM:

• accesso casuale
• no alfabeto finito

equivalenza con macchina di Turing

nastro: valori memorizzati nella memoria della RAM
nella forma num:val&num:val&…

il programma non c'è
è codificato nella macchina stessa

a seconda dell'istruzione c'è un "mini-automa" che esegue l'istruzione

poi si passa al successivo a meno che l'istruzione non sia di salto

paragone con certi sistemi embedded, che una volta programmati eseguono
sempre lo stesso programma?