CALCOLABILITA’
AFFERMARE CHE UN PROBLEMA E’ RISOLUBILE MEDIANTE
UN PROCESSO AUTOMATICO EQUIVALE A DIRE CHE E’
POSSIBILE TROVARE UN ALGORITMO RISOLUTIVO CHE
PORTI, DOPO UN NUMERO FINITO DI OPERAZIONI, ALLA
SOLUZIONE CERCATA .
CALCOLABILITA’
•UNA FUNZIONE E’ CALCOLABILE SE ESISTE UN
ALGORITMO CHE LA RISOLVE
•PER OGNI FUNZIONE CALCOLABILE E’POSSIBILE
COSTRUIRE UNA MACCHINA DI TURING
•E’POSSIBILE COMBINARE TANTE MACCHINE
SEMPLICI PER RISOLVERE QUALSIASI COMPITO
DESCRIVIBILE TRAMITE UN ALGORITMO
CALCOLABILITA’
UNA MACCHINA DI TURING CHE SI ARRESTI E TRASFORMI
UN NASTRO t IN UNO t’ RAPPRESENTA L’ALGORITMO PER
LA ELABORAZIONE Y=F(X), CON X E Y CODIFICATI SU t E t’
MdT CALCOLA
Y=F(X)
TESI DI CHURCH-TURING
• QUANTO NON E’ CALCOLABILE SU UNA DELLE MACCHINE
IDEALI PROPOSTE DA TURING NON E’ CALCOLABILE SU
NESSUNA ALTRA MACCHINA, SIA ESSA IDEALE O REALE
• NON ESISTE UN FORMALISMO NE’ UNA MACCHINA
CONCRETA CHE POSSA CALCOLARE UNA FUNZIONE NON
CALCOLABILE SECONDO TURING
• UN ALGORITMO E’ CIO’ CHE PUO’ ESSERE REALIZZATO
CON UNA MACCHINA DI TURING
TESI DI CHURCH-TURING
• Tutte le definizioni di algoritmo che noi conosciamo sono
EQUIVALENTI
• Tutte le definizioni di algoritmo che chiunque farà saranno
equivalenti a quelle conosciute
• Ciò porta al fatto che tutti i computer sono EQUIVALENTI tra
di loro
Problemi non Computabili
• La domanda alla quale si vuole rispondere è la seguente:
– Tutti i problemi sono computabili? O, in altre parole, ci sono problemi per i
quali non esiste nessun algoritmo in grado di risolverli?
• La risposta a questa domanda è:
– Esistono problemi che non sono computabili
Problema dell’ Arresto
• Dato un programma P ed i suoi dati di input D si vuole sapere se
tale programma terminerà.
• Tale problema NON E’ COMPUTABILE, cioè non esiste un
algoritmo in grado di risolverlo
Problema dell’ Arresto
• Supponiamo che esista un algoritmo, Test_arresto(P,D), che
risolva il problema e che si comporti come in figura
P
D
P(D) si arresta?
Si
No
Stampa OK
Stampa NO
e fermati
e fermati
Problema dell’ Arresto
• Supponiamo di utilizzare come dati D lo stesso P. Chiamiamo
questa versione Test_arresto_nuovo
P
P(P) si arresta?
Si
No
Stampa OK
Stampa NO
e fermati
e fermati
Problema dell’ Arresto
• Test_arresto_nuovo può essere schematizzato in termini di
Test_arresto come segue
Test_arresto_nuovo(P) {
Test_arresto(P,P);
}
Problema dell’ Arresto
Supponendo che test_arresto e Test_arresto_nuovo esistano,
costruiamo un nuovo algortimo Test_arresto_loop che si
comporta come segue
P
P(P) si arresta?
Si
No
Esegui un ciclo
Stampa NO
infinito
e fermati
Problema dell’ Arresto
• Test_arresto_loop può essere schematizzato in termini di
Test_arresto_nuovo come segue
Test_arresto_loop(P) {
if ( Test_arresto_nuovo(P) da NO in Output)
fermati;
else
esegui un ciclo infinito;
}
Problema dell’ Arresto
Consideriamo, infine, il caso in cui a Test_arresto_loop diamo in
ingresso lo stesso Test_arresto_loop
Test_arresto_loop
Test_arresto_loop(Test_arresto_loop) si arresta?
Si
No
Esegui un ciclo
Stampa NO
infinito
e fermati
Problema dell’ Arresto
E’ immediato constatare che l’algoritmo Test_arresto_loop mostra
una evidente contraddizione logica, e quindi NON ESISTE
Test_arresto_nuovo NON ESISTE
Test_arresto NON ESISTE
MODELLO DI VON NEUMANN
unita'
controllo
unita'
ingresso
unita'
memoria
unita'
aritmetica
unita'
uscita
MODELLO DI VON NEUMANN
• Elaborazione sequenziale
• Linguaggio imperativo
• Memoria comune per dati ed Istruzioni
Elaborazione
Y=F(X)
• assegnare i valori Y ai corrispondenti attributi Ay
in base alla regola F, partendo dai valori X degli
attributi Ax
• La decomposizione dell’elaborazione in azioni
componenti ci porta a costruire l’algoritmo di
calcolo, detto anche processo di elaborazione
• Il processore (o unità di controllo) nel modello di
Von Neumann è la macchina che esegue il
processo di elaborazione
• Il processo(algoritmo) è formalmente descritto
mediante un programma, registrato nella
memoria dell’elaboratore
• Un programma è formalmente descritto mediante
un linguaggio noto al processore
MACCHINA DI VON NEUMANN
• stato: (A,V) A={a1,a2,...,an} e V={v1,v2,...,vn}
• una azione elaborativa altera lo stato
• essa assegna un valore ad uno o piu' attributi
Esempi
– assegnazione del valore 3 all’attributo a1
– assegnazione del valore a1 ad a2
– assegnazione del valore derivante da un ingresso ad a1
Macchina Astratta
Generalizzata (MAG)
• Ciasun linguaggio di programmazione definisce i
tipi che tratta e le operazioni su di essi
• Il processore è una parte hardware del
calcolatore o esso stesso un programma
utilizzato per l’esecuzione o per l’interpretazione
di altri programmi
• Per ciascuna coppia linguaggio-processore sono
diversi i tipi,le operazioni definite e quindi le
Istruzioni ed i programmi
Macchina Astratta
Generalizzata (MAG)
• Modello dal quale trarre come casi particolari i
componenti delle macchine concrete
• Cosituita da:
– un insieme di registri di memoria
– un registro speciale PI atto a contenere la
informazione "puntatore alla prossima
istruzione”
– un processore
MAG: TIPI
• Dati (le informazioni da elaborare o elaborate)
• Istruzioni (le azioni da compiere)
• Puntatori (a dati e a istruzioni)
– Il valore di un tipo puntatore è uno
specifico registro di memoria
MAG: Istruzioni e Programmi
• Nella famiglia di tipi T è definito un insieme di
operazioni elementari O
• Mediante composizione di uno o più operatori
viene definito l’insieme di funzioni f:
U=f(I)
• Ogni funzione trasforma un insieme I di k valori in
un insieme Q di q valori
MAG: Istruzioni e Programmi
• Mediante la f si costruisce un’ azione elaborativa
che consiste nell’assegnare i valori U ai registri
della macchina, cioè ai registri di memoria e/o al
registro speciale PI
• Un’azione elaborativa si esprime mediante un’
istruzione che, in generale, è composta da 3
componenti
MAG: Istruzioni e Programmi
i=(f,P1,P2)
• f è la funzione da calcolare
• P1 rappresenta i valori di I ed è un insieme di
valori e/o puntatori a registri contenenti valori
• P2 è costituito da q-1 puntatori a registri di
memoria associati ad altrettanti valori
dell’insieme U che rappresentano i dati elaborati
dall’istruzione. L’ultimo valore di U è destinato al
registro PI ed è un puntatore ad un’istruzione
Modello Operativo della MAG
1- Prelievo dalla memoria dell’istruzione definita da
PI e suo spostamento nel processore
2- prelievo delle informazioni P1 dalla memoria
oppure direttamente dall’istruzione
3- calcolo dei valori U=f(I)
4- memorizzazione dei valori calcolati nei registri
P2
5- trasferimento in PI dell’ultimo valore di U
6- ripetizione delle operazioni a partire dal punto 1
ALU
5
PROCESSORE G
3
f
a
P1
P2
U
1
I
U=f(I)
4
2
a
PI
f
P1
P2
U
I
P2
memoria M
•
•
•
•
•
1) (f,P1,P2) spostata in memoria in un registro di G
2) si costituisce l'insieme di I
3) si esegue il calcolo U=f(I)
4) q-1 valori sono memorizzati nei registri puntati da P2
5) l'ultimo valore di U, uq, e' memorizzato in PI
P1
• Un modello semplice (es MdT) è in grado di
calcolare mediante apposite macchine costruite
su di esso problemi complessi
• Nel caso di macchine a programma ciò si ottiene
inserendo l’apposito programma
• Una macchina può simularne un’altra (più
semplice o più complessa) se attrezzata con un
programma
• Con riferimento al modello di Von Neumann, una
coppia linguaggio processore è in grado di
operare equivalentemente ad un’altra coppia con
azioni elaborative diverse (ma equivalenti per la
Tesi di Church)
Registro PI
• ORDINAMENTO STATICO O DINAMICO
• I1>I2>……………<IN STATICO
• UQ=FQ(I)
DINAMICO
HARDWARE E SOFTWARE
Hardware
Software
Macchina Virtuale
• Hardware: l’insieme di circuiti, dei
componenti elettrici, elettronici e meccanici
• Software: l’insieme dei programmi operanti
sulla macchina
Strato Hardware
• Il classico strato hardware è costituito da una
macchina di Von Neumann detta Macchina di
base:
– linguaggio macchina
– processore hardware
– memoria fisica e registri fisici
Software
• I sistemi di elaborazione sono completati da appositi programmi
che ne consentono un uso più semplice. Essi cosituiscono il
Software di base
• Con tali programmi il calcolatore appare all’utente come una
macchina diversa che verrà indicata come Macchina Virtuale
Gerarchia di Astrazione
di un Calcolatore
LIVELLO
.
.
6
5
4
3
2
1
0
ASTRAZIONE
.
.
Programma App
Linguaggio di Programmazione
Ling. Assemblativo
Nucleo del Sist. Operativo
Linguaggio Macchina
Microprogramma
Logica Digitale
STRATO
Programmi e pacchetti integrati
Programmi e pacchetti applicativi
Linguaggi di programmazione
Sistema operativo
Linguaggio macchina
Microprogrammi
DESTINATARIO
Organizzazione utente
Utente finale
Progettista di applicazioni
Gestione del sistema
Macchina base
Circuiti interni
COSA E’ LA RICORSIVITA’ ?
ANNIDARSI DI COSE DENTRO LE COSE
Ma …..
Attenzione ai paradossi !
A PRIMA VISTA :
COSA DEFINITA IN
TERMINI DI SE STESSA
IL DIALOGO CON A,B,C …...
PUSH, POP e PILE
RICORSIVITA’
•NEL CAMPO MUSICALE
Bach
Suite Francise n. 5
“AABB”
•NEL CAMPO LINGUISTICO
Rete di Transizione Ricorsiva
(RTN)
•NEL CAMPO DELLE STRUTTURE GEOMETRICHE
MOLTO NOTA
Leonardo Pisano “figlio di Bonaccio”
detto FIBONACCI
1202
Il Diagramma G e le successioni ricorsive
Possiamo definire strutture geometriche infinite usando lo stesso metodo,cioe’quello di espandere un nodo dopo l’altro. Per
esempio, definiamo un diagramma infinito chiamato “Diagramma G” . Useremo a questo scopo una rappresentazione implicita. In
due nodi scriveremo semplicemente la lettera ‘G’, che starà per una copia del Diagramma G, nella figura 31a, abbiamo disegnato il
Diagramma G implicitamente. Ora se vogliamo vedere il Diagramma G più esplicitamente, possiamo espandere ciascuna delle due
G, cioè, sostituirle con lo stesso diagramma, ma in dimensioni ridotte (vedi Fig 31b). Questa versione “disecondo ordine” del
diagramma G ci dà una vaga idea dell’aspetto che avrebbe il Diagramma G se fosse completo, cosa che è impossibile
G
H
G
H
(a)
(c)
H
G
G
G
G
H
H
H
(b)
FIGURA 31. (a) Diagramma G, senza espansioni
(b) Diagramma G, con una espansioni
(c) Diagramma H, senza espansioni
(d) Diagramma H, con una espansioni
(d)
Il Diagramma G e le successioni ricorsive
H
G
G
H
(a)
(c)
H
G
G
G
G
H
H
H
(b)
(d)
(a) Diagramma G, senza espansioni
(b) Diagramma G, con una espansioni
(c) Diagramma H, senza espansioni
(d) Diagramma H, con una espansioni
Nella Figura si vede una parte ancora più grande del diagramma G, in cui
tutti i nodi sono stati numerati cominciando dal basso e da sinistra a destra.
In basso sono stati inseriti due nodi supplementari che portano i numeri 1 e
2.
14
15
9
16
17
19
18
11
10
6
21
20
12
7
13
8
4
5
3
2
1
Questo albero infinito, possiede alcune propietà matematiche molto curiose. Se
ci muoviamo lungo il suo bordo destro, troviamo la famosa successione dei
numeri di Fibonacci
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …….
Il migliore modo per definire questi numeri consiste in una ricorsione in base
alle due formule
FIBO(n) = FIBO(n-1) + FIBO(n-2)
FIBO(0) = 1
FIBO(1) = 1
per n >= 2
Come si vede, ogni numero di Fibonacci viene definito in base ai numeri
di Fibonacci definiti in precedenza. Potremo rappresentare le due formule
con una RTN
Porre x=FIBO(n-1)
FIBO(n)
inizio
Porre y=FIBO(n-2)
X+Y
fine
Il valore è 1