Macchine di Turing - University of Cagliari€¦ · Alan M. Turing (1912-1954) Francesco Paoli...

Macchine di Turing

Francesco Paoli

Istituzioni di logica, 2016-17

Francesco Paoli (Istituzioni di logica, 2016-17) Macchine di Turing 1 / 29

Alan M. Turing (1912-1954)


Cos’è un algoritmo?

Un algoritmo è una procedura P effettiva o meccanica:

1 P dev’essere formulata mediante un numero finito di istruzioni esatte,ognuna delle quali deve contenere un numero finito di simboli.

2 P deve produrre il risultato in un numero finito di passi.3 P deve poter essere eseguita – in linea di principio! – da un essereumano, con carta e matita, senza l’aiuto di una macchina.

4 P, per poter essere eseguita, non deve presupporre alcun ricorsoall’intuizione o all’ingegno.


L’algoritmo euclideo per il MCD


La subroutine “resto”


L’algoritmo euclideo esteso


Turing: l’attività di calcolo

Il calcolo, per Turing, ha tre caratteristiche essenziali:

1 Ci si serve di un numero finito di simboli disposti su un supporto; talisimboli possono essere scritti o cancellati un numero finito di volte.

2 Si può modificare il proprio campo visivo un numero finito di volte.3 Ricordando un numero finito di istruzioni e atti già compiuti, si passada una combinazione iniziale di simboli (gli argomenti della funzioneda calcolare) a una combinazione finale (il valore della funzione perquegli argomenti).


Componenti di una macchina di Turing

1 Alfabeto2 Nastro3 Lettore4 Memoria


Funzionamento di una macchina di Turing

La macchina funziona per passi elementari successivi. In ciascun passo delcalcolo, la macchina può:

stampare o cancellare un certo simbolo, eventualmente passando daun certo stato interno a un altro stato interno;

spostare il nastro di una cella a sinistra o a destra rispetto al lettore,eventualmente passando da un certo stato interno a un altro statointerno;

fermarsi.


Alcune convenzioni

L’alfabeto contiene due soli simboli, 0 e 1.

Le celle contenente il simbolo 0 si considerano vuote.

Prima dell’avvio del calcolo, il lettore si trova sulla prima cella vuota adestra dell’ultimo simbolo 1 presente sul nastro.

Alla fine del calcolo (se la macchina si ferma), il lettore si trovasull’ultima cella vuota a sinistra del primo simbolo 1 presente sulnastro.


Macchina di Turing (definizione formale)

Una macchina di Turing sull’alfabeto {0, 1} a stati in S = {1, ..., n} è uninsieme M di quintuple ordinate (dette istruzioni) della forma

I =⟨S ],R,W ,M,N ]

⟩tale che:

1 S ],N ] ∈ S ;2 R,W ∈ {0, 1};3 M è uno dei simboli L, R, H.

La coppia⟨S ],R

⟩si dice testa dell’istruzione

⟨S ],R,W ,M,N ]

⟩.


Macchina di Turing deterministica

Una macchina di Turing M sull’alfabeto {0, 1} a stati in S = {1, ..., n} sidice deterministica se per ogni stato m ∈ S esiste una e una sola istruzioneI ∈M con testa 〈m, 0〉 ed una e una sola istruzione J con testa 〈m, 1〉.Tutte le macchine di Turing che considereremo sono deterministiche.


Esempi stupidi

Macchina cancellatrice1 0 0 H 11 1 0 H 1

Macchina cerca cella vuota a sinistra e macchina cerca 1 a destra

1 0 0 R 21 1 1 R 22 0 0 H 22 1 1 R 2

1 0 0 L 21 1 1 L 22 0 0 L 22 1 1 H 2


La macchina per l’addizione

1 0 0 R 11 1 0 R 22 0 1 R 32 1 1 R 23 0 0 L 43 1 1 R 34 0 0 H 44 1 0 H 4


Struttura di una computazione

Supponiamo che la macchina M a stati in S = {1, ..., n} debba calcolarela funzione numerica k-aria F k per gli input n1, ..., nk .All’inizio del calcolo:

la macchina si trova nello stato 1;

sul nastro sono stampati gli input n1, ..., nk , in notazione romanasemplificata;

il lettore si trova sulla cella vuota immediatamente a dx dell’ultimosimbolo 1 nella rappresentazione di nk .

Alla fine del calcolo (se la macchina si ferma!):

la macchina si trova nello stato n;

sul nastro è stampato l’output F k (n1, ..., nk ), in notazione romanasemplificata;

il lettore si trova sulla cella vuota immediatamente a sx del primosimbolo 1 nella rappresentazione di F k (n1, ..., nk ).


Verso il concetto di configurazione

Come si presenta una macchina di Turing M a un determinato passo t diun calcolo? Tutte le informazioni pertinenti sono racchiuse in treparametri:

1 la cella su cui è posizionato il lettore al passo t;2 ciò che è scritto sul nastro al passo t;3 lo stato in cui si trova M al passo t.


Configurazione

Sia M una macchina di Turing a stati in S = {1, ..., n}. Unaconfigurazione di M è una tripla ordinata K = 〈p,C , s〉, dove:

1 p è un numero intero, detto posizione di K ;2 C è una funzione da Z (insieme dei numeri interi) a {0, 1}, dettacondizione di K (C (x) = 1 per almeno un x ∈ Z e per al più unnumero finito di x ∈ Z);

3 s ∈ {1, ..., n} ed è detto stato di K .


Come si calcola la configurazione successiva

Sia K = 〈p,C , s〉 una configurazione di M. La configurazione successivadi K è la configurazione K ′ = 〈p′,C ′, s ′〉 determinata come segue:

1 Si prende l’istruzione I ∈M con testa 〈s,C (p)〉 (si noti che esiste edè unica!); siano

⟨W ,M,N ]

⟩le rimanenti componenti di I .

2 p′ =

p + 1 se M = L;p − 1 se M = R;p se M = H.

; C ′(x) =

0 se x = p e W = 0;1 se x = p e W = 1;C (x) se x 6= p.

3 s ′ = N ].


Computazione

Sia M una macchina di Turing a stati in S = {1, ..., n}. Una computazionedi M a partire dalla posizione p1, dalla condizione iniziale C1 e dallo statoiniziale 1 è una successione finita di configurazioni K1, ...,Km tale che:

K1 = 〈p1,C1, 1〉;per ogni i < m, Ki+1 = (Ki )

′;

lo stato di Km occorre come prima e quinta componente diun’istruzione I ∈M che contiene il simbolo H.


Funzione Turing-computabile

Una funzione numerica k-aria F k si dice Turing-computabile se esiste unamacchina di Turing M tale che per ogni possibile input n1, ..., nk esiste unacomputazione K1, ...,Km con le seguenti caratteristiche:

la condizione di K1 è la funzione (da numeri di celle a simboli) checorrisponde alla rappresentazione romana semplificata dell’inputn1, ..., nk ;

la condizione di Km è la funzione (da numeri di celle a simboli) checorrisponde alla rappresentazione romana semplificata dell’outputF k (n1, ..., nk ).


Macchina di Turing universale

Sia M una macchina di Turing in grado di calcolare il valore della funzionek-aria F k per ogni possibile input n1, ..., nk . Una macchina di Turing M′

simula M se, ricevendo come input gli argomenti n1, ..., nk e una codificanell’alfabeto {0, 1} delle istruzioni di M, restituisce come outputF k (n1, ..., nk ).

Una macchina di Turing U si dice universale se può simulare ogni altramacchina di Turing M.


Esistenza delle macchine universali

TheoremEsiste una macchina di Turing universale.

Dimostrazione.(schema)

Si mostra che è possibile enumerare in modo sistematico tutte lemacchine di Turing e codificarne la tavola delle istruzioni nell’alfabeto{0, 1}.Ogni macchina di Turing è identificata dal suo indice n, ossia dalposto che occupa in questa enumerazione.

Si mostra che esiste una macchina U, la quale, ricevuti in input inumeri n1, ..., nk , j , inizia a computare e calcola dapprima la codificadella tavola delle istruzioni di Mj , poi il risultato della funzioneF k (n1, ..., nk ), dove F k è la funzione calcolata da Mj .


Problemi Turing-decidibili

Un problema P che ammette risposte sì-no è Turing-decidibile se esisteuna macchina di Turing M la quale, ricevuta in input la codifica di unaqualsiasi istanza I di P, si ferma dopo un numero finito di passi stampandol’output 1 se la risposta ad I è affermativa, 0 se la risposta ad I è negativa.Per esempio, il problema P di stabilire se un numero naturale è pari èTuring-decidibile. Ogni istanza I di P è costituita da un numero naturale.


Problema della fermata: enunciazione

Consideriamo il problema P che consiste nello stabilire se una genericamacchina di Turing si fermerà o no quando riceve un certo input.

Le istanze di P saranno coppie ordinate 〈n,m〉, dove n è l’indice dellamacchina di Turing Mn e m la codifica del suo input.

Ci chiediamo se P è un problema Turing-decidibile.


Problema della fermata: conseguenze

NB Se lo fosse, avremmo una procedura di decisione per il problemaQ che consiste nello stabilire se una generica formula α del primoordine è un teorema del calcolo della deduzione naturale. Non èdiffi cile costruire una macchina di Turing M che esamina tutte lepossibili dimostrazioni di α e si ferma stampando l’output 1 quandone ha trovata una.

Se P fosse un problema Turing-decidibile, basterebbe avviare lamacchina H che lo decide e chiederle se M si fermerà o no seapplicata alla codifica di α. In questo modo Q risulterebbeTuring-decidibile.


Indecidibilità del problema della fermata (1)

L’idea intuitiva è porre alla macchina la domanda: Ti fermerai se ti vienechiesto se non ti fermerai?. Se la macchina fosse in grado di rispondere aquesta domanda si determinerebbe una contraddizione.

TheoremNon esiste nessuna macchina di Turing H che, ricevuto l’input 〈n,m〉,stampa l’output 1 se la macchina di Turing Mn si ferma quando ricevel’output m, e stampa l’output 0 altrimenti.

Dimostrazione.(Cenni!)

Supponiamo per assurdo che H esista.

Essendo una macchina di Turing, H avrà un certo indice i .


Indecidibilità del problema della fermata (2)

Dimostrazione.Si può definire una nuova macchina di Turing K che, se applicataall’input n, produce l’output 1 se H produce l’output 0 se applicataall’input 〈n, n〉, mentre non si ferma se H produce l’output 1 seapplicata all’input 〈n, n〉.Essendo una macchina di Turing, K avrà un certo indice j .Cosa succede se a K viene fornito l’input j?Darà l’output 1 se H produce l’output 0 se applicata all’input 〈j , j〉,non si ferma se H produce l’output 1 se applicata all’input 〈j , j〉.Contraddizione!


Il teorema di Church-Turing (1)

Sia Σ = {σ1, ..., σ7} l’insieme finito di enunciati corrispondenteall’aritmetica di Robinson.

Consideriamo la relazione su N

R ={〈m, h〉 : la macchina diTuring di indice m, applicata

all’input m, si ferma entro h passi.

}Il problema di decidere se una coppia ordinata 〈m, h〉 appartiene a Rè Turing-decidibile (si costruisce una macchina che stabilisce se m èindice di una macchina di Turing e, in caso affermativo, ne spacchettala tavola delle istruzioni, esegue h passi di calcolo e vede se lamacchina si ferma).

Per il teorema di rappresentabilità, esiste una formula del primoordine β (x , y) tale che β (x/pmq, y/phq) è derivabile da Σ quando〈m, h〉 ∈ R.


Il teorema di Church-Turing (2)

Consideriamo la formula ∃yβ (pmq, y) e supponiamo di poterdecidere se è derivabile da Σ.Allora saremmo in grado di decidere il problema della fermata!Contraddizione.

Se adesso per ogni formula α del primo ordine esistesse una macchinadi Turing che decide se è un teorema del calcolo della deduzionenaturale, ciò varrebbe in particolare per

σ1 ∧ ...∧ σ7 → ∃yβ (pmq, y) .

Ma allora saremmo in grado di decidere se ∃yβ (pmq, y) è derivabileda Σ. Contraddizione.


Macchine di Turing - University of Cagliari€¦ · Alan M. Turing (1912-1954) Francesco Paoli...

Documents

Transcript of Macchine di Turing - University of Cagliari€¦ · Alan M. Turing (1912-1954) Francesco Paoli...