informatica.senonsainonsei.org

La macchina di TuringV2.1, 09/03/2014

Bruno Boni Castagnetti, Nicoletta Giorda, Franco Marra

Sindacato Pensionati

Corsi di Informatica per Anziane e Anziani

informatica.senonsainonsei.org 2

Contenuto della lezione

• Il Buddha nel computer: cos’è un programma

informatica.senonsainonsei.org 3

Il Buddha, il Divino, dimora nel circuito di un calcolatore o negli ingranaggi del cambio di una moto con lo stesso agio che in cima a una montagna o nei petali di un fiore(Robert M. Pirsig: Lo Zen e l’arte della manutenzione della motocicletta, gli Adelphi, 1990)

informatica.senonsainonsei.org 4

Forma e Significato

informatica.senonsainonsei.org 5

Il computer di Socrate• Tutti gli uomini sono mortali, Socrate è un uomo, Socrate è mortale• Tutti i cani hanno la coda, Fido è un cane, Fido ha la coda

• Sempre vera, non importa se si parla di Socrate o di cani• Quello che importa sono le regole con cui è costruita la frase, non i

contenuti della frase stessa

• Derivazione di frasi “vere” in base a regole predefinite => Ragionamento automatico

• Tutti i gatti guidano la macchina, Felix è un gatto, Felix guida la macchina

informatica.senonsainonsei.org 6

Socrate e il significato• Una frase “vera” può non avere alcun

significato

Frasi “vere”

Frasi con un

significato

Gatti che guidano

Uomini mortali

Cani e code

informatica.senonsainonsei.org 7

Cos’è “vero”

• “Vero” per le macchine vuol dire “derivato” da “stringhe” (frasi) iniziali (postulati) mediante regole predefinite (algoritmo) eseguite automaticamente• “Vero” per gli esseri umani vuol dire “con

un significato” basato sul consenso generale• Non tutto ciò che vero per la macchine è vero

anche per gli esseri umani

informatica.senonsainonsei.org 8

Un giochino da “Settimana Enigmistica”

CASA cambiare tutte le “A” in “O” =>COSO cambiare tutte le “C” in “T” =>TOSO cambiare tutte le “S” in “R” =>TORO cambiare tutte le “T” in “M” =>

MORO stop

DATI REGOLE DEL GIOCO

informatica.senonsainonsei.org 9

La macchina di Turing “CasaMoro”

CASA

CASA TORO MORO

Testina di lettura / scrittura

Nastro che va avanti e indietroINPUT

OUTPUTRISULTATO INTERMEDIO INMEMORIA

RUN

informatica.senonsainonsei.org 10

Il set di istruzioni di CasaMoro

• Input / Output e controllo periferiche– Leggi_la_lettera <lettera>• Leggi la lettera che è nella posizione corrente del nastro

– Scrivi_la_lettera <lettera>• Scrivi la lettera nella posizione corrente del nastro

– Avanti_di <numero_di_posizioni>• Muovi il nastro verso sinistra di <numero_di_posizioni>

– Indietro_di <numero_di_posizioni>• Muovi il nastro verso destra di <numero_di_posizioni>

informatica.senonsainonsei.org 11

Il set di istruzioni di CasaMoro (2)

• Elaborazione– Cambia_in <nuova_lettera>• Cambia la lettera corrente in <nuova_lettera>

informatica.senonsainonsei.org 12

Il set di istruzioni di CasaMoro (3)

• Logiche e di controllo– Se <condizione> allora <istruzione 1> altrimenti

<istruzione 2>• Se si verifica <condizione> esegui <istruzione 1>

altrimenti <istruzione 2>

– Ricomincia_da_capo• Ricomincia da capo

– Stop• Ferma CasaMoro

informatica.senonsainonsei.org 13

Il problema della fermata• Può capitare che una macchina di Touring non incontri mai l’istruzione Stop e “giri”

all’infinito• In questo caso (ma solo in questo caso) il programma è sbagliato

1 Leggi_la _lettera2 Se “M” allora Stop3 Se “A” allora Cambia_in “O” altrimenti4 Se “C” allora Cambia_in “T” altrimenti5 Se “S” allora Cambia_in “R” altrimenti6 Se “T” allora Cambia_in “M”7 Avanti_di 58 Scrivi_la_lettera9 Indietro_di 5 10 Ricomincia_da_capo

• Ma non è detto che programmi non sbagliati siano “corretti” dal punto di vista umano• Un computer può produrre stringhe “vere” per lui ma non per gli esseri umani, perché

prive di significato• I programmi “corretti” sono quelli che producono stringhe che opportunamente

interpretate hanno significato per l’uomo

ERRORE!!

informatica.senonsainonsei.org 14

Le unità di Input Output• Le unità di Input / Output interfacciano il mondo reale, dando

significato concreto alle stringhe elaborate del computer mediante la loro interpretazione

• Un programma è “corretto” quando produce risultati verificabili nella realtà

?Mondo reale,Significato

Elaborazione del computer

informatica.senonsainonsei.org 15

Stringhe, fotografie e musica• Ad esempio:

– Una stringa viene tradotta dall’altoparlante in musica, che ha significato per l’uomo

– Un’altra stringa viene tradotta dallo schermo in una foto, che ha significato per l’uomo

– Se si manda la stringa della musica sullo schermo si ottiene una figura senza “significato”

– Se si manda la stringa della foto sull’altoparlante si ottengono suoni sgradevoli (senza significato)

• Le stringhe, opportunamente memorizzate in “file” hanno un tipo, che serve proprio alla loro corretta interpretazione. Ad esempio:– Tipo foto: jpg (JPEG: Joint Photographic Expert Group)– Tipo musica: mp3 (MP3: Moving Picture Expert Group audio layer

3)– Tipo documento: doc (indica un file creato da Microsoft Word)

informatica.senonsainonsei.org 16

Il teorema di Gödel

• Tutte le cose “vere” per gli esseri umani sono anche “vere” (derivabili algoritmicamente) per le macchine? • No! (Kurt Gödel)

informatica.senonsainonsei.org 17

Il teorema di Gödel (2)

• “Questa stringa non è dimostrabile ” – È vera perché se fosse dimostrabile sarebbe falsa• Ma, essendo vera, non è dimostrabile, quindi non è

derivabile algoritmicamente da alcuna altra stringa

– Ergo, è “vera ” per l’uomo ma non per le macchine di Turing• Se l’uomo “sa” essere vere cose che non sono derivabili

automaticamente, il cervello umano non è una macchina di Turing (Roger Penrose), quindi non è possibile l’Intelligenza Artificiale nel senso “forte” del termine

informatica.senonsainonsei.org 18

Fare la guerra

• Giulio Cesare– Omnia Gallia est divisa in partes tres– Pnolb Hbiib ftu elzltb lo qbsuft usft

• Terzo Reich: la macchina Enigma

informatica.senonsainonsei.org 19

Alan Turing

• Matematico e logico inglese – in servizio ai servizi crittografici durante la seconda

guerra mondiale a Bletchley Park– i messaggi criptati in base al codice Enigma

vennero decifrati grazie all’antesignano dei computer: “Colossus” costruito secondo il modello della Macchina di Turing

– Tutto ciò contribuì in maniera determinante al successo degli Alleati

informatica.senonsainonsei.org 20

Alan Turing (2)

• Campione di maratona• Membro dal 1951 della Royal Society di Londra• Nel 1952 fu arrestato per omosessualità e

condotto in giudizio• Fu sottoposto alla castrazione chimica, che lo

rese impotente e gli causò lo sviluppo del seno• Nel 1954 si suicidò mangiando una mela

avvelenata con il cianuro, prendendo spunto dal film di Walt Disney “Biancaneve e i sette nani”

informatica.senonsainonsei.org 21

Il logo

informatica.senonsainonsei.org 22

FINE

Esercitazione!