La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek
-
Upload
alumni-mathematica -
Category
Technology
-
view
141 -
download
1
Transcript of La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek
![Page 1: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/1.jpg)
La macchina più geek dell’universo The Turing Machine
Pierpaolo Basile
![Page 2: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/2.jpg)
Macchina di Turing
• Modello astratto di calcolo introdotto nel 1936 da Alan Turing
• Fornire una definizione matematica/formale del concetto di algoritmo
• Risolvere il problema di decisione
![Page 3: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/3.jpg)
Algoritmo
«Procedimento di risoluzione dei problemi per passi successivi, in particolare un
procedimento computazionale ricorsivo determinato per risolvere un problema in
un numero finito di passi»
American Heritage Dictionary
![Page 4: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/4.jpg)
Problema di decisione
«Esiste un «processo meccanico» in grado di stabilire se per un dato
problema esiste un algoritmo risolvibile in
un numero finito di passi?»
![Page 5: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/5.jpg)
La Macchina di Turing (MdT)
![Page 6: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/6.jpg)
Problema di decisione
![Page 7: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/7.jpg)
Problema di decisione
• Costruiamo un algoritmo H che prende in input un altro algoritmo P
• H si comporta nel seguente modo:
vero se P termina falso se P NON termina
H restituisce
![Page 8: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/8.jpg)
Problema di decisione
• Costruiamo un altro algoritmo K che utilizzando H decide se P termina
stampa loop se H(P)=falso va in loop se H(P)=vero
K restituisce
K si comporta in maniera opposta al suo input P!
![Page 9: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/9.jpg)
Problema di decisione
• Supponiamo di dare in input a K lo stesso K
stampa loop se K NON termina va in loop se K termina
K(K) restituisce
Assurdo • K(K) si ferma quando K va in loop • K(K) va in loop quando K si ferma
H non può esistere
![Page 10: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/10.jpg)
La Macchina di Turing
![Page 11: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/11.jpg)
MdT: il nastro
• Nastro potenzialmente infinito diviso in celle (memoria) • ogni cella contiene un simbolo preso da un
alfabeto finito
![Page 12: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/12.jpg)
MdT: la testina…
• Testina di lettura/scrittura • può leggere/scrivere in una cella per volta
![Page 13: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/13.jpg)
MdT: …la testina…
• Testina di lettura/scrittura • può leggere/scrivere in una cella per volta
• può spostarsi a destra o a sinistra di una cella per volta
![Page 14: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/14.jpg)
MdT: …la testina
• Testina di lettura/scrittura • può leggere/scrivere in una cella per volta
• può spostarsi a destra o a sinistra di una cella per volta
![Page 15: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/15.jpg)
MdT: l’unità di controllo
• Unità di controllo • decodifica ed esegue comandi rivolti alla testina
(controlla la testina)
Unità di Controllo
![Page 16: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/16.jpg)
MdT: lo stato
• La macchina può trovarsi in un numero finito di stati
• La macchina può cambiare stato in seguito ad una lettura di un simbolo dal nastro
• Chiameremo configurazione la coppia: <simbolo visibile alla testina, stato corrente>
• Esiste uno stato «speciale» HALT che indica la fine dell’algoritmo
![Page 17: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/17.jpg)
Macchine di Turing (MdT)
L’unità di controllo esegue un algoritmo A sui dati memorizzati sul nastro
Le istruzioni di A sono del tipo:
< simbolo_letto, stato_corrente, simbolo_da_scrivere, sinistra/destra/ferma, nuovo_stato >
configurazione
![Page 18: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/18.jpg)
Algoritmi per MdT: il nastro
• Definire un’opportuna configurazione iniziale del nastro • Codificare i dati
• Es.: nastro iniziale per problema della sottrazione tra interi
4 – 2 operandi codificati con ‘I’ e separati da * blank=^
^ I I I I * I I ^ ^
Configurazione iniziale
![Page 19: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/19.jpg)
Algoritmi per MdT: il nastro
• Definire un’opportuna configurazione finale del nastro che rappresenti la soluzione
^ ^ ^ I I ^ ^ ^ ^ ^
Configurazione finale
![Page 20: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/20.jpg)
Algoritmi per MdT: il controllo
• Definire le azioni (algoritmo) dell’unità di controllo
• In pratica l’algoritmo per una MdT è una sequenza di quintuple del tipo:
< simbolo_letto, stato_corrente, simbolo_da_scrivere, sinistra/destra/ferma, nuovo_stato >
Es. <|, S1, ^, D, S2 > : se leggi | e sei nello stato S1 allora scrivi ^, sposta a destra la testina e vai nello stato S2
![Page 21: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/21.jpg)
MdT: sottrazione tra interi
• Progettiamo un algoritmo per eseguire la sottrazione tra due numeri interi n e m, n≥0, m≥0 • Per semplicità assumiamo che n≥m
• La testina è posizionata sulla prima cella vuota a destra dell’ultimo simbolo del sottraendo
• Il modello di calcolo ci "obbliga" a pensare l’algoritmo in base alle operazioni possibili
S0
Configurazione iniziale
![Page 22: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/22.jpg)
MdT: sottrazione tra interi
• Progettiamo un algoritmo per eseguire la sottrazione tra due numeri interi n e m, n≥0, m≥0 • Per semplicità assumiamo che n≥m
• La testina è posizionata sulla prima cella vuota a destra dell’ultimo simbolo del sottraendo
• Il modello di calcolo ci "obbliga" a pensare l’algoritmo in base alle operazioni possibili
S0
Configurazione iniziale
Cancellare ugual numero di simboli da n e da m in
modo che sul nastro resti solo il risultato finale
![Page 23: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/23.jpg)
MdT: algoritmo per la sottrazione
1. Diminuisci di una unità m • ricorda di aver cancellato un simbolo da m
2. Spostati a Sx in cerca del primo simbolo di n
3. Cancellalo • Ricorda che ora entrambi gli operandi sono stati
diminuiti di una unità
4. Spostati a Dx in cerca dell’ultimo simbolo di m • Se non ci sono più simboli da cancellare da m allora
cancella il separatore HALT
• In caso contrario torna al punto 1
![Page 24: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/24.jpg)
La MdT per la sottrazione…
• Alfabeto = {I, *, ^}
• Stati = {S0, S1, S2, S3, HALT} • S0 ≡ stato iniziale della computazione ovvero
ricerca ultimo simbolo di m
• S1 ≡ diminuito m
• S2 ≡ raggiunto simbolo iniziale di n
• S3 ≡ diminuiti entrambi operandi
![Page 25: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/25.jpg)
…la MdT per la sottrazione
<^,S0,^,Sx,S0>
<|,S0,^,Sx,S1>
<*,S0,^,F,HALT>
<^,S1,^,Dx,S2>
<|,S1,|,Sx,S1>
<*,S1,*,Sx,S1>
<|,S2,^,Dx,S3>
<^,S3,^,Sx,S0>
<|,S3,|,Dx,S3>
<*,S3,*,Dx,S3>
![Page 26: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/26.jpg)
La Matrice Funzionale
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^FHALT *SxS1 *DxS3
![Page 27: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/27.jpg)
Computazione 3-1
S0
^ ^ | | | * | ^ ^ ^
n m
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 28: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/28.jpg)
Computazione 3-1
S0
^ ^ | | | * | ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 29: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/29.jpg)
Computazione 3-1
S0
^ ^ | | | * | ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 30: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/30.jpg)
Computazione 3-1
S1
^ ^ | | | * ^ ^ ^ ^
diminuito m
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 31: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/31.jpg)
Computazione 3-1
S1
^ ^ | | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 32: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/32.jpg)
Computazione 3-1
S1
^ ^ | | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 33: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/33.jpg)
Computazione 3-1
S1
^ ^ | | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 34: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/34.jpg)
Computazione 3-1
S1
^ ^ | | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 35: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/35.jpg)
Computazione 3-1
S2
^ ^ | | | * ^ ^ ^ ^
raggiunto simbolo iniziale di n
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 36: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/36.jpg)
Computazione 3-1
S3
^ ^ ^ | | * ^ ^ ^ ^
Diminuiti entrambi gli operandi
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 37: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/37.jpg)
Computazione 3-1
S3
^ ^ ^ | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 38: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/38.jpg)
Computazione 3-1
S3
^ ^ ^ | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 39: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/39.jpg)
Computazione 3-1
S3
^ ^ ^ | | * ^ ^ ^ ^
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 40: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/40.jpg)
Computazione 3-1
S0
^ ^ ^ | | * ^ ^ ^ ^
Stato iniziale della computazione
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 41: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/41.jpg)
Computazione 3-1
HALT
^ ^ ^ | | ^ ^ ^ ^ ^
trovare un * nello stato iniziale della computazione è segno del fatto che non ci sono più simboli da processare in m
S0 S1 S2 S3 ^ ^SxS0 ^DxS2 ^SxS0
| ^SxS1 |SxS1 ^DxS3 |DxS3 * ^F HALT *SxS1 *DxS3
![Page 42: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/42.jpg)
Have Fun with MdT
1. Stabilire se un numero rappresentato con ‘|’ è pari oppure dispari
2. Stabilire se una stringa binaria è palindroma (ovvero si legge indifferentemente da Sx a Dx, es.: 010010)
![Page 43: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/43.jpg)
Soluzioni
![Page 44: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/44.jpg)
Esercizio 1
• Stabilire se un numero rappresentato con ‘|’ è pari oppure dispari
S0
^ ^ ^ | | | | ^ ^ ^
Configurazione iniziale
^ ^ ^ ^ ^ ^ ^ P ^ ^
Configurazione finale
![Page 45: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/45.jpg)
Esercizio 1
• Cancellare i simboli dal nastro e memorizzare in uno stato la situazione di parità/disparità • q0 ≡ stato iniziale della computazione ovvero PARI
• q1 ≡ DISPARI
S0 S1 ^ P F HALT D F HALT
| ^ Dx S1 ^ Dx S0
![Page 46: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/46.jpg)
Esercizio 2
• Stabilire se una stringa binaria è palindroma (ovvero si legge indifferentemente da Sx a Dx, es.: 010010)
S0
^ ^ ^ 0 1 1 0 ^ ^ ^
Configurazione iniziale
^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Configurazione finale
![Page 47: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/47.jpg)
Esercizio 2
• Stabilire se una stringa binaria è palindroma (ovvero si legge indifferentemente da Sx a Dx, es.: 010010)
S0
^ ^ ^ 0 1 0 0 ^ ^ ^
Configurazione iniziale
^ ^ ^ ^ 1 ^ ^ ^ ^ ^
Configurazione finale
![Page 48: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/48.jpg)
Esercizio 2
S0 S1 S2 S3 S4 S5
0 0 S0 Dx ^ S2 Sx 0 S2 Sx 0 S3 Sx ^ S0 Dx 0 F Halt
1 1 S0 Dx ^ S3 Sx 1 S2 Sx 1 S3 Sx 1 F Halt ^ S0 Dx
^ ^ S1 Sx ^ S5 Dx ^ S4 Dx ^ S5 Dx ^ F Halt ^ F Halt
S1: leggo il primo simbolo a sinistra S2: ho letto 0 e mi sposto tutto a sinistra S3: ho letto 1 e mi sposto tutto a sinistra S4: verifica che l’ultimo simbolo a sinistra sia 0 S5: verifica che l’ultimo simbolo a sinistra sia 1 S0: mi riporto a destra della stringa se leggo 0 o 1, altrimenti prova a leggere il primo simbolo a sinistra
![Page 49: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/49.jpg)
Tesi di Church-Turing
• La classe delle funzioni calcolabili coincide con la classe delle funzioni calcolabili da una MdT • ogni funzione calcolabile è calcolata da una MdT
• non esiste alcun formalismo capace di risolvere una classe di problemi più ampia di quella che si può risolvere con MdT
• Le funzioni calcolabili con C o Java sono di più di quelle calcolabili con MdT?
![Page 50: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/50.jpg)
Tesi di Church-Turing
• La classe delle funzioni calcolabili coincide con la classe delle funzioni calcolabili da una MdT • ogni funzione calcolabile è calcolata da una MdT
• non esiste alcun formalismo capace di risolvere una classe di problemi più ampia di quella che si può risolvere con MdT
• Le funzioni calcolabili con C o Java sono di più di quelle calcolabili con MdT?
NO
![Page 51: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/51.jpg)
MdT vs. CPU
• MdT 1. Legge / scrive su
nastro
2. Transita in un nuovo stato
3. Si sosta sul nastro di cella in cella
4. Esegue un programma specifico CABLATO nella macchina è specifica per un certo problema
• CPU 1. lettura / scrittura da /
su memoria RAM o ROM
2. nuova configurazione dei registri della CPU
3. scelta della cella di memoria su cui operare
4. È generale, nel senso che può eseguire programmi diversi
![Page 52: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/52.jpg)
La MdT Universale (MdTU)
• Legge dal nastro DATI e PROGRAMMA • Il programma non è più cablato nell’unità di controllo
• Codificato sul nastro come i dati
• In pratica sono rappresentate sul nastro anche le 5-ple che definiscono l’algoritmo solutivo
• E’ una macchina programmabile • prende le 5-ple (istruzioni) dal nastro FETCH
• le decodifica DECODE
• le esegue scrivendo sul nastro EXECUTE
• E’ un computer programmabile!
![Page 53: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/53.jpg)
MdTU vs. Macchina Von Neumann
MdTU (controllo)
Nastro
MdTU è un modello della macchina di Von Neumann
ovvero un modello degli attuali calcolatori!
(manca solo la parte di I/O)
processore memoria interna
memoria esterna
interfaccia periferiche
![Page 55: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/55.jpg)
BACKUP SLIDES
![Page 56: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/56.jpg)
MdT: il modello matematico
Una MdT è definita da una quintupla
M = (X, Q, fm, fd, )
X = insieme finito di simboli
comprende il blank ovvero cella vuota
Q = insieme finito di stati
comprende HALT che definisce la terminazione
![Page 57: La macchina più geek dell'universo: The Turing Machine | Laboratorio B-Geek](https://reader033.fdocumenti.com/reader033/viewer/2022052307/55beddfcbb61eb663e8b4692/html5/thumbnails/57.jpg)
MdT: il modello matematico
Una MdT è definita da una quintupla:
M = (X, Q, fm, fd, )
Funzione di direzione
Determina lo spostamento della testina
S=sinistra, D=destra, F=ferma
},,{: FDSXQfd
XXQfm :Funzione di macchina
Determina il simbolo da scrivere sul nastro
Funzione di transizione di stato
Definisce lo stato successivo della computazione
QXQ :