Macchine di Turing e Macchine di Turing e Calcolabilità Calcolabilità

(1)

Macchine di Turing e Macchine di Turing e

Calcolabilità Calcolabilità

Ivan Lanese

Dipartimento di Informatica—Scienza e Ingegneria Università di Bologna

Ivan.lanese@gmail.com

http://www.cs.unibo.it/~lanese/

(2)

Macchine di Turing 2

(3)

Ringraziamenti

●

Parte del materiale presente in queste slide è tratto dalla presentazione Calcolo e Simboli: la scienza

digitale del prof. Simone Martini, Università di Bologna

(4)

Alan Mathison Turing (1912—1954)

●

Nato il 23 giugno 1912

●

OBE

(Order of the British Empire)

●

FRS

(Fellow of the Royal Society)

●

Morto il 7 giugno 1954 per avvelenamento da cianuro,

probabilmente suicidio dovuto

alle persecuzioni per la sua

omosessualità

(5)

Alan Mathison Turing (1912—1954)

●

Criptanalisi

●

Macchine per il calcolo

●

Gioco dell'imitazione

●

Morfogenesi

(6)

Criptanalisi

(7)

Morfogenesi

Turing, A. M. (1952).

The Chemical Basis of Morphogenesis.

Philosophical Transactions of the

Royal Society B: Biological

Sciences 237 (641): 37–64.

(8)

www.turingsunflowers.com

(9)

Il gioco dell'imitazione

●

Cos'è l'intelligenza?

●

Un interrogante è

collegato mediante un terminale con due

stanze: in una di esse si trova una persona,

nell'altra un computer

●

Ponendo domande tramite il terminale, l'interrogante deve

decidere chi è l'essere

umano e chi la macchina

(10)

(11)

Le macchine di Turing

(12)

Cosa significa calcolare?

●

Turing ha iniziato a porsi domande sulla natura e i

limiti dei computer molto prima che questi esistessero!

– Primo calcolatore “universale” elettromeccanico:

Z3, 1941; Konrad Zuse, Germania.

– Primo calcolatore “universale” elettronico:

ENIAC, 1946; University of Pennsylvania’s Moore School of Electrical Engineering

●

Alan M. Turing, On Computable Numbers, with an

Application to the Entscheidungsproblem, Proc. Lond.

Math. Soc. (2) 42 pp. 230-265 (1936)

– Entscheidungsproblem (secondo Problema di Hilbert):

Esiste un metodo definito di calcolo che, data una

proposizione matematica permette di decidere se è o non è dimostrabile?

(13)

Cosa significa calcolare?

1 7 9 2 6

+ 5

= 2

7

(14)

Macchina di Turing

●

Dispositivo astratto che contiene tutti gli elementi essenziali per “calcolare” una qualsiasi funzione

– Un supporto su cui scrivere: un nastro infinito, diviso in caselle

– Un insieme finito di simboli che possono comparire sul nastro

– Un dispositivo di lettura/scrittura

– Un insieme finito di “stati” in cui la macchina si può trovare in ogni istante

– Una “tavola di istruzioni” finita, che dice alla macchina cosa fare in base al simbolo che si trova in quel momento sotto la testina di lettura/scrittura

(15)

Macchina di Turing

● Un insieme finito di stati in cui la macchina può trovarsi

– q0 è lo stato iniziale, in cui la macchina si trova quando viene fatta partire

– halt è lo stato finale: se la macchina raggiunge tale stato, si ferma.

– Nota: gli stati possono avere nomi arbitrari; “q0” e “halt” sono solo una nostra convenzione che useremo qui

● Un nastro infinito diviso in celle

● Un alfabeto finito (insieme di simboli che possono comparire sulle celle del nastro)

– L'alfabeto include un simbolo “spazio” (blank) che compare su tutte le (infinite) celle non inizializzate del nastro.

– Un insieme finito di celle puo' contenere inizialmente simboli diversi da blank, e rappresentano l'input della macchina di Turing

● Una funzione di transizione che determina il comportamento

(16)

Funzione di transizione

●

Una lista di regole che indicano, per ogni possibile

simbolo X che si trovi al momento sotto la testina e per ogni possibile stato P della macchina:

– quale simbolo Y scrivere al posto di X (è possibile riscrivere nuovamente X);

– quale è il nuovo stato Q della macchina (è possibile che lo stato rimanga sempre P);

– se la testina deve essere spostata a destra oppure a sinistra di una casella;

●

Inizialmente la macchina si trova nello stato iniziale, e

la testina è posizionata su una data cella del nastro

(che di solito dipende dal problema da risolvere)

(17)

Esempio

1 1 1 1

Testina di lettura/scrittura con indicato lo stato corrente

Contenuto iniziale del nastro

●

Alfabeto: {1, b}

●

Stati: {q0, halt}

Stato

corrente Simbolo

corrente Nuovo

Simbolo Nuovo

Stato Spostamento

q0 1 1 q0 right

q0 blank 1 halt right

q0

(18)

Esempio

●

Calcolare il “complemento a uno” di un numero espresso in base 2

– In pratica, cambiare gli '1' con '0' e viceversa

– 10010001 → 01101110

●

Inizialmente sul nastro viene scritta la cifra binaria

●

Al termine il nastro deve contenere il risultato al posto degli input

●

Esercizio: come definiamo la funzione di transizione?

1 0 0 1 0 0 0 1

q0

(19)

Esempio

●

Calcolare la somma di due numeri in base 1

– 111 + 1111 = 1111111

●

Inizialmente sul nastro vengono scritti i due numeri da sommare, separati da un blank

●

Al termine il nastro deve contenere il risultato al posto degli input

●

Esercizio: come definiamo la funzione di transizione?

1 1 1 1 1 1 1

q0

(20)

Entscheidungsproblem

●

Esiste un metodo definito di calcolo che, data una

proposizione matematica permette di decidere se è o non è dimostrabile?

●

Turing definisce metodo definito di calcolo come procedura di calcolo realizzabile mediante una macchina di Turing

– Tesi di Church-Turing: le macchine di Turing definiscono con precisione la nozione intuitiva di “procedimento definito di calcolo”

●

Turing dimostra che non esiste alcun metodo definito di calcolo che permette di decidere se una

proposizione matematica è o non è dimostrabile.

(21)

Funzioni calcolabili e Turing-Completezza

●

Tesi di Church-Turing: le funzioni calcolabili sono tutte e sole le funzioni calcolabili da una qualche macchina di Turing

●

Qualsiasi formalismo mediante il quale sia possibile simulare una macchina di Turing si dice Turing-

Completo

– Esempio di formalismo Turing-Completo?

– Esempio di formalismo NON Turing-Completo?

(22)

LEGO Turing Machine

http://www.legoturingmachine.org/

(23)

Formalismo Turing-Completo:

Automi Cellulari

●

Griglia infinita di celle che possono essere “accese” o “spente”

●

Lo stato successivo di ogni cella

dipende dal suo stato corrente, e da quello dei suoi 8 vicini

●

Esempio: Game of Life

– Una cella accesa che ha meno di due vicini accesi, si spegne

– Una cella accesa che ha due o tre vicini accesi, resta accesa

– Una cella accesa che ha più di 3 vicini accesi, si spegne

Una cella spenta che ha esattamente 3 vicini

(24)

Il Game of Life è Turing-Completo

http://rendell-attic.org/gol/tm.htm

(25)

Funzioni non calcolabili:

Halting Problem

●

Esistono funzioni che NON sono calcolabili

●

Esempio (Halting Problem)

“Scrivere una funzione che accetta in input (1) la descrizione di un programma P scritto in una

opportuna notazione, e (2) l'input I da passare a P. La funzione deve restituire TRUE se e solo se il

programma P applicato all'input I termina”

(26)

Halting problem

Dimostrazione semi-formale

●

Supponiamo per assurdo che sia possibile scrivere un metodo Java che accetta in input due stringhe

– P rappresenta il sorgente di un programma Java

– I rappresenta l'input su cui il programma P deve operare

bool Termina(String P, String I) {

if (P applicato a I termina) { return true;

} else {

return false;

} }

Qui dovrebbe essere del codice Java “opportuno”

che decide se P(I) termina o no

(27)

Halting problem

Dimostrazione semi-formale

●

Poiché l'input I puo' essere una qualsiasi stringa di caratteri, nulla ci impedisce di passare al programma P il suo stesso codice sorgente come input!

– Quindi se è possibile scrivere un metodo Termina(), è

possibile scrivere anche il metodo Termina_su_P() seguente

bool Termina_su_P(String P) {

if (Termina(P, P)) { return true;

} else {

return false;

} }

(28)

Halting problem

Dimostrazione semi-formale

●

Se è possibile scrivere un metodo Termina() e

Termina_su_P(), allora è possibile anche scrivere un metodo Bomba() seguente

– Se P(P) termina, Bomba(P) NON termina

– Se P(P) non termina, Bomba(P) ritorna true

bool Bomba(String P) {

if (Termina_su_P(P)) {

while (1) ; // ciclo infinito return false;

} else {

return true;

} }

(29)

Halting problem

Dimostrazione semi-formale

● Che cosa possiamo dire dell'invocazione Bomba(Bomba)?

– Cioé passiamo al metodo Bomba() il suo stesso codice

● Bomba(Bomba) puo' terminare, o andare in loop

– Se Bomba(Bomba) termina, significa che Termina_su_P(Bomba) restituisce false

– Cioé Termina(Bomba, Bomba) restituisce false

– Cioé Bomba(Bomba) NON termina

} else {

return true;

} else {

return false;

}

Assurdo!

(30)

Halting problem

Dimostrazione semi-formale

● Che cosa possiamo dire dell'invocazione Bomba(Bomba)?

– Cioé passiamo al metodo Bomba() il suo stesso codice

● Bomba(Bomba) puo' terminare, o andare in loop

– Se Bomba(Bomba) NON termina, significa che Termina_su_P(Bomba) restituisce true

– Cioé Termina(Bomba, Bomba) restituisce true

– Cioé Bomba(Bomba) termina

} else {

return true;

} }

} else {

return false;

} }

Assurdo!

(31)

Halting problem

Dimostrazione semi-formale

●

Quindi supponendo che fosse possibile scrivere un metodo Termina(), abbiamo ottenuto un assurdo

●

Di conseguenza NON possiamo definire un metodo Termina() che operi come indicato

– Nemmeno se usiamo un linguaggio di programmazione

diverso: tutti i linguaggi di programmazione sono equivalenti ad una macchina di Turing, quindi possono calcolare solo le funzioni che una macchina di Turing puo' calcolare

(32)

Funzioni non calcolabili:

Tassellatura di Wang

● Dato un insieme di tipi di piastrelle di Wang, decidere se esse possono ricoprire il piano

– E' possibile usare un numero illimitato di piastrelle di ciascun tipo

– Esempio: le piastrelle seguenti possono ricoprire il piano (in modo non periodico)

● E' stato dimostrato che è impossibile definire un algoritmo per

decidere se un insieme dato di tipi di piastrelle può ricoprire il piano

By Anomie - Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=3968914

(33)

(34)

...e poi dicono che l'informatica teorica non serve!

Michael F. Cohen, Jonathan Shade, Stefan Hiller, and Oliver Deussen. 2003. Wang Tiles for image and texture generation. In ACM SIGGRAPH 2003 Papers (SIGGRAPH '03). ACM, New York, NY, USA, 287-294. DOI http://dx.doi.org/10.1145/1201775.882265