Dipartimento di Informatica Università degli Studi di Bari Aldo Moro
Orientamento Consapevole 2020
Agenda Introduzione Cenni Storici Parole e Automi Frasi e Grammatiche Macchina di Turing Linguaggi di Programmazione
Introduzione Cenni Storici sul Calcolo Automatico
Preistoria del Calcolo Informatica / Computer Science Antico Egitto, Civiltà Precolombiane, Medio Oriente, Cina, India, Antica Grecia, ...
contare (lat. "computare") con le dita (lat. "digitus"), con le mani, ...
calcolare con pietroline (lat. "calculus") bastoncini, cerchi, ...
Universo del Calcolabile tutto ciò che si può fare manipolando segni [...] secondo regole
[cfr. Borzacchini]
tutti i problemi che si prestano a formalizzazioni (matematiche) possono essere computati
Cenni Storici.. Inizi 1600 René Descartes (Cartesio)
idea: tradurre ogni problema in termini matematici e risolverlo tramite equazioni/computazioni intuizione applicata al campo geometrico:
punti come coppie ordinate di numeri rette come equazioni di 1° grado in due incognite...
1643 Pascal (e Schickard 1623)
procedimenti meccanici per il calcolo: Pascalina (addizionatore)
..Cenni Storici.. 1666 Leibniz: “Calculemus” propone il ricorso a un calcolo formale per dirimere controversie razionalmente
Calcolo: per estensione “qualunque notazione che rappresenti il ragionamento, quand'anche non avesse alcun rapporto con i numeri” Characteristica Universalis formalizzazione di un linguaggio universale Ideazione del Calculus Ratiocinator
1671 macchina calcolatrice (Mechanische rekenmachine) capace di simulare la mente umana nelle operazioni aritmetiche
1768 Automa di Kempelen o Turco Meccanico capace (?) di giocare a scacchi
..Cenni Storici.. 1837-42 C. Babbage concepì la macchina analitica (analytical engine), primo esempio di macchina universale (hardware), cui collaborò anche L. Menabrea
e che Ada Lovelace Byron corredò del software
..Cenni Storici 1847 G. Boole in The Mathematical Analysis of Logic propone l'associazione tra matematica e logica
logica come scienza delle leggi dei simboli prima associata alla losoa / metasica
1854 in An Investigation of the Laws of Thought, B. riconduce le composizioni degli enunciati a semplici operazioni:
algebre di Boole
Z3 di Konrad Zuse Linguaggio di programmazione (funzionale): Plankalkül
Futuro? Quantum Computing Qbit etc. sovrapposizione di e 0 1
Calcolo Matematica
/
trasformazioni che manipolano sequenze di simboli codicate in binario quindi numeri interi naturali:
0, 1, 10, 11, 100, ...
Alfabeti Alfabeto: insieme nito e non vuoto di simboli:
Esempi
Scott Aaronson: What is a Quantum CoScott Aaronson: What is a Quantum Co……
f : x y
Stringhe Stringa (o parola): sequenza di simboli da un alfabeto :
ogni è un simbolo di , per ogni posizione
è la lunghezza della stringa indica la stringa senza simboli ( ) detta stringa muta (o parola vuota)
Abbreviazione: dato un simbolo
Chiusura
denota l'insieme (innito) di tutte le stringhe fatte di simboli scelti da
Concatenazione (Prodotto) Operazione " " denita sulle stringhe: date sullo stesso alfabeto,
è la stringa ottenuta facendo seguire ai simboli di tutti quelli di conservando l'ordine
op. associativa ma non commutativa sia
presso di sottostringa di
= {0, 1}Σbin
= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Σdec
= {a, b, c, d, e, f, g, h, i, j, k, l,Σlet
m, n, o, p, q, r, s, t, u, v, w, y, z}
Σ
s[i] Σ i
n ε n = 0
n volte
Σbin ε 0 11 101 010101010 101010101 Σdec ε 110 1234567890 33333333 Σlet ε abba uniba vercingetorige
Σ∗
Σ∗
Σ
z = ⋅ ⋅w1 w2 w3 w1 z w2 z
l. composto dalla sola stringa vuota l. delle stringhe di 1 solo simbolo
l. di tutte le stringhe di lunghezza 2
l. delle stringhe di lunghezza 3
linguaggio vuoto l. nito
Esempi
susso di
Linguaggi Formali Un linguaggio su è un sotto-insieme di stringhe di :
Operazioni di Prodotto e Potenza estese ai linguaggi:
Esempi
... e così via, quindi
( )
⋅ = { ⋅ ∈ ∧ ∈ }L1 L2 w1 w2 w1 L1 w2 L2
= {ε} ∧ = ⋅ L ∀n > 0L0 Ln Ln−1
{ε} = Σ0
Σ = Σ1
Σ3
stati nali: indicano l'accettazione della stringa in input
sembrare, ridursi un automa. 2. In cibernetica (in partic. nella teoria generale degli a.), sistema denito da un insieme di segnali di entrata, di stati interni e di segnali di uscita, e tale che per ogni segnale in entrata fornisce un segnale d’uscita dipendente dallo stato interno in cui il sistema stesso si trova. 3. Nella teoria dei sistemi complessi, a. cellulare, strategia di rappresentazione di sistemi complessi (v. complessità), i cui elementi costituenti sono immaginati come collocati nei nodi di una rete e possono assumere diversi stati a seconda delle interazioni con gli elementi vicini.
http://www.treccani.it/vocabolario/automa/
comportamento indipendente dall'istante in cui agisce
q0
q1 q2 q3 q4 q5
a b a a b a a b a a b a
Control Unit
input da nastro di celle, ciascuna con un simbolo dell'alfabeto d'ingresso convenzione: il nastro scorre verso sinistra, un simbolo alla volta
l'unità di controllo determina il funzionamento in ogni istante, si trova in uno dei suoi stati (memoria interna):
stato iniziale:
Automa | Diagramma di transizione Per descrivere il funzionamento di un automa:
B
0..9
C .
D
0..9
Grammatiche Sintassi: come formare frasi
Grammatica Una grammatica è un modello astratto che descrive matematicamente un linguaggio su un dato alfabeto
Si usa anche un altro alfabeto di variabili o simboli non terminali il più importante è il simbolo di partenza, indicato con (scopo, start)
Una regola di riscrittura ha una parte sinistra e una parte destra :
e sono stringhe di simboli da entrambi gli alfabeti
Grammatiche - Esempi : e : e
: e : e
Derivazioni la derivazione diretta è una relazione tra stringhe, ad es. , indicata con:
Σ
S
S
S
S
A
S
S
Ba
BA
aA
Bb
S
S
Bb
Bb
che vale se, data la regola , si ottiene sostituendo in
La derivazione è la relazione tra stringhe indicata con
in cui si ottiene da tramite una sequenza di derivazioni dirette
Derivazioni | Esempi Data con le regole
derivazione diretta: derivazione:
Linguaggi Generati dalle Grammatiche Una grammatica denisce un insieme di stringhe derivabili da il linguaggio generato da :
Linguaggi Generati da Grammatiche | Esempi genera genera
genera genera
di grammatiche / linguaggi / macchine riconoscitrici |
ω ⇒ ω′
ω ⇒ ∗ ω′
ω′ ω
∗
G S G
G3 L( ) = { 1 i ≥ 0}G3 0i
S
S
S
S
A
S
S
Ba
BA
aA
Bb
S
S
bA
Bb
Macchine di Turing Funzioni Algoritmi Programmi
Funzione relazione che associa elementi di due insiemi
ogni è associata ad al più un focus su funzioni sui domini dei numeri naturali o delle stringhe
Algoritmo descrizione formale della procedura per risolvere il problema di come ottenere [output] da [input]
descrizione in un numero nito di passi: ogni passo (elementare) richiede un numero nito di risorse es. una ricetta
Programma algoritmo scritto in un linguaggio interpretabile da una macchina
Problema della Decisione Entscheidungsproblem posto da David Hilbert nel 1928
Esiste una procedura automatica in grado di stabilire, per ogni enunciato espresso nel linguaggio formale della logica del primo ordine, se esso è deducibile o meno all'interno del sistema formale?
G2
0S0− −− ⇒ 1
0S0− −− ⇒ 1
0S0− −− ⇒ 1
0A0− −−− ⇒ 3
cos : R → R
idea meccanismo astratto che simuli il lavoro dell'impiegato diligente una MdT consta di
un nastro innito con simboli da una testina di lettura e scrittura un insieme di stati interni un'unità di controllo capace di spostare e di leggere/scrivere un simbolo da/su , secondo un programma interno
Computazione nella Macchina di Turing Funzionamento
a ogni avvio, si trova
nello stato a ogni passo
, considerato corrente e letto da , esegue un'istruzione detta transizione:
passa nello stato ( ammissibile) scrive nella cella di indicata da sposta di una posizione a sinistra o a destra secondo
Caratteristiche Salienti
La funzione di transizione costituisce un insieme nito di istruzioni La MdT è l'agente di calcolo che esegue le istruzioni
La MdT opera in modo discreto e deterministico La MdT può utilizzare il nastro per memorizzare i risultati intermedi
M T Σ H
q ′ q = q ′
Nessuna limitazione sulla lunghezza delle stringhe di ingresso: nastro innito, una memoria di capacità non limitata
Le operazioni che la MdT può eseguire sono semplici, di complessità nita Numero delle istruzioni eseguite durante una computazione: illimitato
Dato che le istruzioni sono di numero nito, è ammessa la possibilità di eseguire più volte la stessa istruzione Esiste la possibilità di computazioni innite
MdT, Linguaggi e Problemi Una mdT decide un linguaggio su se, avendo ssato due stringhe di output che corrispondano a e , essa, ricevendo sul nastro una stringa
termina rispondendo quando appartiene a termina rispondendo quando non appartiene a
Una mdT calcola una funzione se, per ogni stringa del suo dominio, essa termina la computazione avendo calcolato l'output corretto
per le altre stringhe può divergere (iterare all'innito senza terminare) funzione parziale
MdT Universale Corrispondenza tra MdT e Funzioni Calcolabili
Ogni mdT calcola una funzione denita su stringhe di un dato alfabeto Ogni funzione calcolabile ha una mdT che la calcola (Tesi di Turing)
Codica sui Numeri Naturali
Ogni mdT può essere mappato su un numero naturale
nel seguito: [Cantor] ogni coppia di numeri naturali può essere mappato su un numero naturale
Algoritmo Universale Dati la funzione denita:
L Σ Sì No
f w f(w)
M x
M x
è calcolabile (esiste una mdT che la calcola)
Algoritmo
eseguire sull'input per passi se la mdT termina la sua esecuzione entro passi
allora termina restituendo in output altrimenti (non si è fermata), termina restituendo in output
Macchina Universale Una MdT è determinata da con le istruzioni per il suo controllo: il suo programma
Teorema Si può costruire una MdT universale che simuli il lavoro di ogni altra MdT:
dati una MdT , ossia indicizzata dal numero , e un input , restituirà come output
Problemi (Linguaggi) Non Decidibili Esistono funzioni non calcolabili attraverso una MdT
Problema della Terminazione (Halting Problem)
Si può denire una MdT che, avendo in input un'altra MdT e un suo possibile input , sappia decidere se il calcolo di termini o meno?
ossia dovrebbe terminare sempre rispondendo o a seconda della terminazione di (cioè applicata al suo input )
Problema della Fermata La risposta è negativa
Si dimostra per assurdo supponendo che esista (quindi anche il suo codice ) 1. derivando da una MdT che
termina quando su non termina diverge se su termina
2. applicando a se stessa (come input): terminando indicherebbe di non terminare e viceversa (paradosso)
f(x, y, z) = { 1 0
 converge in z passi sull'input yMx
altrimenti
U
H
H yH H D
H yH H yH
descrizione informale descrizione formale
Macchine e Linguaggi Macchina sica (calcolatore) : dispositivo capace di eseguire istruzioni espresse in un linguaggio comprensibile per tale esecutore
Linguaggio di macchina : linguaggio formale compreso dalla macchina utile a descrivere algoritmi
Macchina astratta per , denotabile con : insieme di algoritmi e strutture dati che permettono di memorizzare ed eseguire programmi in
A Turing Machine - OverviewA Turing Machine - Overview

Programma Programma: descrizione di un algoritmo come sequenza di istruzioni in dato un linguaggio di programmazione
Denisce un processo deterministico (meccanico)
La computazione di un qualunque programma in può essere simulata da una MdT
dato un numero anche alto di transizioni non fa altro che cambiare bit in memoria
Linguaggio TM Memoria (nastro)
var. input var. locali * registri e spazio di lavoro
INIT inizializza la variabile locale a HOME sposta la testina in posizione iniziale * avendo allocato variabili LOAD carica il valore della la variabile nel registro STOR memorizza il valore del registro nella variabile RETURN cancella le variabili e lascia la variabile nella posizione di output CLEAR cancella il valore del registro BRN salta all'istruzione con l'etichetta se il valore del registro è GOTO salta all'istruzione etichettata con NOP nessuna operazione (spesso con GOTO) INC incrementa il valore del registro DEC incrementa il valore del registro ZERO azzera il valore del registro
Linguaggio WHILE
vi vi 0
l l
t t
t t
t t
Struttura Macchina Astratta
I S; I
V ≠V
A B …
0 1 9
1. Acquisizione da memoria della prossima istruzione 2. Decodica dell'operazione e dei suoi operandi 3. Acquisizione degli operandi 4. Esecuzione dell'operazione 5. Memorizzazione del risultato 6. Se l'istruzione è HALT
termina altrimenti
Traduzione | Interpretazione
Traduzione | Compilazione
Traduzione | Ibrida
Schema Compilazione
voce Informatica @ Treccani Borzacchini: Il computer di Platone Dedalo Toalori et al.: Teoria della computabilità e della complessità McGaw-Hill Sudkamp: Languages And Machines Addison-Wesley Gabbrielli e Martini: Linguaggi di programmazione. Principi e paradigmi McGraw-Hill Sebesta: Concepts of Programming Languages Pearson
Hofstadter: Gödel, Escher, Bach: un'eterna ghirlanda brillante. Adelphi Doxiadis e Papadimitriou: Logicomix Guanda (graphic novel)
Link
Linguaggio Formale su Wikipedia Introduzione ai Linguaggi Formali su Wikiversity JFLAP: www.jap.org
Automaton Simulator: automatonsimulator.com Simulatore di MdT: turingmachinesimulator.com Automi Cellulari: Gioco della Vita