Capitolo 3.

Esecutore, algoritmo e linguaggi universali.

 3.1 Introduzione.
 3.2 Esecutore N1.
 3.3 Esecutore N2.
     Problema 1: calcolare l'area di un quadrato nel linguaggio N2.
     Problema 2: risolvere una equazione di primo grado con N2
     Problema 3: calcolare la potenza ottava di un numero conN2
     Problema 4: determinare se un numero è positivo
     Problema 5: determinare il perimetro di un triangolo con N2
 3.4 Esecutore N3
     Problema 1:  calcolo della potenza n-esima di un numero con N3
     Problema 2:  calcolo del fattoriale di un numero numero con N3
 3.5 Esecutore U.R.M.
     Problema 1: dato il numero 1 restituire il successivo.
     Problema 2: scambiare il contenuto di due variabili.
     Problema 3: verificare che l'istruzione T può essere sostituita da .....
     Problema 4: somma di due numeri.
     Problema 5: prodotto di due numeri.
     Problema 6: sottrazione di due numeri.
     Problema 7: confrontare due numeri.
     Problema 8: differenza di quadrati.
 3.6 Computabilità.
     Teorema di Godel.
     Teorema di Turing.
     Funzione computabile.
 Esercizi N1
 Esercizi N2
 Esercizi N3
 Esercizi URM

3.1 Introduzione.

Un esecutore è una macchina in grado di compiere un certo numero di operazioni in una sequenza determinata.

Poichè l'esecutore è una macchina facciamo l'ipotesi che operi in modo discreto, cioè che è sempre possibile descrivere il suo funzionamento con una sequenza di stati successivi separati da intervalli di tempo.

Una elaborazione è una sequenza di operazioni compiute da un esecutore: ogni operazione individua una azione compiuta su dati in ingresso per ottenere dati in uscita.

Un algoritmo è, in prima approssimazione, l'insieme delle regole che definiscono una sequenza di operazioni.

Esempio. Risolvere una equazione di primo grado.

Obiettivo: determinare X in modo che A*X + B = 0

Variabili in ingresso: A,B

Variabili in uscita: X

Limiti sulle variabili in ingresso: A diverso da 0

Legge: X = -B / A

Algoritmo

1- se A = 0 e B < 0 allora non ci sono soluzioni

2- se A = 0 e B = 0 allora esistono infinite soluzioni

3- se A < 0 allora X = -B / A

E` corretto l'algoritmo descritto sopra ?

La proprietà più ovvia che deve avere un algoritmo è quella di poter essere eseguito dall'esecutore per cui è stato scritto: per esempio se l'esecutore non fosse in grado di eseguire l'operazione di divisione non sarebbe neppure capace di calcolare la radice di una equazione di primo grado con l'algoritmo descritto nell'esempio precedente.

Da ciò deriva una prima proprietà delle operazioni definite da una algoritmo: devono essere effettive, cioè conosciute ed eseguibili da un esecutore. La scrittura di un algoritmo deve poi avvenire in modo non ambiguo: nella linea 1 dell'esempio precedente se le premesse risultano vere non sono indicate azioni per l'esecutore.

Questo significa che un algoritmo deve essere descritto in un linguaggio in cui siano definite in modo rigoroso sia la sintassi, le regole di scrittura, sia la semantica, il significato operativo delle frasi.

Un'ultima considerazione: è impossibile nella realtà istruire un esecutore con un numero infinito di regole.

Possiamo ora dare una definizione più rigorosa di algoritmo :

Un algoritmo è un insieme finito di regole che definiscono una sequenza di operazioni non ambigue ed effettive.

3.2 Esecutore N1.

Supponiamo di avere un esecutore N1 che sappia riconoscere i numeri e le quattro operazioni sui numeri. Le operazioni agiscono su due numeri e devono comparire nella forma:
 

La sequenza con cui l'esecutore svolge le operazioni è data dall'ordine delle parentesi: prima quelle più interne e poi a salire quelle più esterne. Ad esempio è in grado di riconoscere le seguenti sequenze:

1- (* 34 12)

2- (* (+ 5.12 4) (/ 12.87 3))

3- (* (* (+ 4.34 5) (/ 9 0.3)) (- 12 5))

Il linguaggio che abbiamo a disposizione per tale esecutore ci permette di descrive solo sequenze di operazioni algebriche.

Esempio 1: descrivere per l'esecutore N1 le seguenti sequenze di operazioni:

1- (34 + 12 + 0.34) * (12 * 5 + 12.34) - (34 * 4)

2- 23 * 12 + 34 + 12 * ((23 + 18) / 0.23)

Soluzuione 1:

Tenendo conto che

(34 + 12 + 0.34) -- (+ (+ 34 12) 0.34) = a1

(12 * 5 + 12.34) -- (+ (* 12 5) 12.34) = b1

(34 * 4) -- (* 34 4) = c1

la a diventa

a1 * b1 - c1 -- (- (* a1 b1) c1)

e cioè:

(- (* (+ (+ 34 12) 0.34) (+ (* 12 5) 12.34)) (* 34 4))

Soluzione 2:

Tenendo conto che

(23 * 12 ) -- (* 23 12) = a1

((23 + 18) / 0.23) -- (/ (+ 23 18) 0.23) = b1

la b diventa

a1 + 34 + 12 * b1 -- (+ (+ 34 a1) (* 12 b1))

e cioè:

(+ (+ 34 (* 23 12)) (* 12 (/ (+ 23 18) 0.23)))

3.3 Esecutore N2.

L'esecutore N2 è un ampliamento dell'esecutore N1: riconosce, oltre ai numeri e alle operazioni, anche le variabili che vengono identificate da una sequenza di una o più lettere. Riconosce inoltre le seguenti tre istruzioni:
 

La 1 permette di attribuire ad una variabile un valore dall'esterno:

IN(A) legge dall'esterno un numero e lo assegna alla variabile A

La 2 permette di restituire all'esterno un numero o il valore di una variabile:

OUT(A) restitusce all'esterno il valore della variabile A

OUT(5) restituisce all'esterno il valore 5

OUT((+ 2 3)) restituisce all'esterno il valore 5

La 3 è l'istruzione di assegnazione: permette di assegnare ad una variabile un contenuto numerico. In una assegnazione l'esecutore valuta prima l'espressione a destra e assegna il risultato alla variabile a sinistra:

A <- 5 assegna a A il valore 5

B <- C assegna a B il valore della variabile C

Z <- (* 4 (+ 3 4)) assegna a Z il valore 28

T <- (* 4 A) assegna a T il valore di A moltiplicato per 4

A <- (+ A 1) calcola il valore di A + 1 e lo assegna a A

Nel linguaggio N2, una variabile deve essere inizializzata con un numero prima di comparire in unàespressione: in caso contrario esiste una forma di ambiguità.

Ad esempio:

è una sequenza non corretta, poichè l'espressione (+ X Y) non può essere valutata in quanto la variabile Y non è stata ancora inizializzata.

Sono scorrette le seguenti operazioni:
 

Problema 1: calcolare l'area di un quadrato nel linguaggio N2.

Obiettivo: determinare l'area del quadrato

Variabile in ingresso: X (misura del lato del quadrato)

Variabile in uscita: Y (misura dell'area del quadrato)

Limiti della variabile in ingresso: X 0

Legge che lega X a Y: Y = X * X
 

Problema 2: risolvere una equazione di primo grado nel linguaggio N2.

Una equazione di primo grado (in X) compare nella forma A * X + B = 0.

Obiettivo: determinare X in modo che A * X + B = 0

Variabili in ingresso: A, B

Variabile in uscita: X

Limiti sulle variabili in ingresso: A diverso da 0

Legge che lega X a A e B: X= - B / A

Descrizione nel linguaggio N2 (programma in N2):
 

N.B. Nel linguaggio N2 non possiamo controllare che il valore di A sia diverso da 0. Questo comporta che non sempre l'esecutore N2 è in grado di comportarsi correttamente.

Problema 3: calcolare la potenza ottava di un numero nel linguaggio N2.

Obiettivo: determinare Y in modo che Y = X^8

Variabile in ingresso: X

Variabile in uscita: Y

Legge: Y = X^8

Proponiamo due soluzioni:

soluzione 1:

metodo di calcolo: Y = X * X * X * X * X * X * X * X

soluzione 2:
 

metodo di calcolo: Y = (((X^2)^2)^2)

N.B. I due metodi di calcolo ottengono lo stesso risultato in modo diverso: quello che si può notare è che il primo procedimento richiede 8 moltiplicazioni, il secondo solo 3. Possiamo dire che la seconda soluzione è più efficiente della prima.

Problema 4: determinare se un numero è negativo nel linguaggio N2

Obiettivo: determinare se un numero è negativo

Variabile in uscita: Y

Variabile in ingresso: X

Legge: Se X è negativa allora Y=0 altrimenti Y=1.

Nel linguaggio N2 non siamo in grado di definire una tale legge.

Problema 5: determinare il perimetro di un triangolo nel linguaggio N2

Obiettivo: perimetro del triangolo noti i tre lati

Variabile in uscita: Y

Variabili in ingresso: A B C

Limiti sulle variabili in ingresso: A0, B0, C0, A+BC, A+CB, B+CA

Legge: Y= A+B+C
 

N.B. Nel linguaggio N2, non si sono potuti controllare i numerosi vincoli a cui devono sottostare i valori in ingresso.

3.4 Esecutore N3

Definiamo l'esecutore N3 come un'estensione dell'esecutore N2; l'esecutore N3 riconosce tutte le istruzioni di N2 e in più la seguente istruzione:
 

dove k è o un numero naturale o una variabile inizializzata con un numero naturale.

L'istruzione permette di indicare all'esecutore che il gruppo di istruzioni interne al ciclo deve essere ripetuto k volte. Se k è uguale a 0, nessuna istruzione interna al ciclo ripeti deve essere eseguita.

Ad esempio
 

Alla fine del ciclo X=5 , Y=625.

N.B. Se k è una variabile, k non deve comparire all'interno del ciclo:

RIPETI N VOLTE

X <- (* N X)

FINE-RIPETI

Qui l'uso è scorretto perchè all'interno del ciclo compare N.

Problema 1: descrivere il calcolo della potenza n-esima di un numero nel linguaggio N3.

Obiettivo: Determinare Y in modo che Y= X^N

Variabili in ingresso: X N

Variabile in uscita: Y

Limiti sulle variabili in ingresso: N è un numero naturale

Legge: Y = X * X * .. X (N moltiplicazioni)
 

N.B. Non è possibile nel linguaggio N3 controllare che N sia un numero naturale.

Problema 2: descrivere il calcolo del fattoriale di un numero nel linguaggio per l'esecutore N3.

Obiettivo: Determinare Y in modo che Y= X!

Variabile in ingresso: X

Variabile in uscita: Y

Limiti sulle variabili in ingresso: X è un numero naturale

Legge: Y = X * (X-1) * (X-2) .. * 2 * 1
 

N.B. Non è possibile nel linguaggio N3 controllare che N sia un numero naturale.

3.5 Esecutore U.R.M.

La sigla U.R.M stà per Unlimitated Register Machine (Macchina a Registri Illimitati). I registri sono delle entità astratte, associabili al concetto di variabile. Sono identificati da numeri naturali e possono contenere solo numeri naturali.

La macchina U.R.M riconosce quattro istruzioni:
 

dove

a) Z sta per Zero. E' un comando che pone a 0 il contenuto registro r.

Esempio:

Z(1) r1 <- 0

b) S sta per Successivo. Somma 1 al contenuto del registro r.

Esempio:

S(3) r3 <- r3 + 1

c) T sta per Trasferisce. Trasferisce il contenuto del registro rx nel registro ry. rx non viene modificato.

Esempio:

T(3,7) r7 <-- r3

d) J sta per Jump. Se rx = ry passa all'istruzione i, se sono diversi continua.

Esempio:

3 J(1,2,6) se r1 = r2 allora il controllo passa all' istruzione 6

altrimenti continua con l' istruzione 4

Il programma U.R.M. è una lista finita di istruzioni numerate con interi positivi e crescenti, ed individuata da un nome seguito eventualmente dai valori di inizializzazione dei registri. Il modello U.R.M. ha per ipotesi infiniti registri e nessun limite di tempo e di spazio per l'esecuzione del programma.

Esempio: Prova(10,5) -- registro 1 = 10 , registro 2 = 5. Il programma si chiama Prova.

Le istruzioni di un programma U.R.M. vengono eseguite sequenzialmente fino a quando non vi sono piu' istruzioni da computare. Il risultato viene di solito messo nel 1 registro. L'ordine di esecuzione delle istruzioni può essere modificato dall'istruzione J().

Problema 1: dato il numero 1 restituire il successivo.

Obiettivo: dato 1, restituire 2.

Registro utilizzato come input: r1 = 1

Registro utilizzato come output: r1

Legge: r1 = r1 + 1

Algoritmo:

r1 <- 1

r1 <- r1 + 1

Programma U.R.M.:

Psucc( 1 )

1 S(1)
 

Commento al programma: l'input viene posto nel registro 1. L'istruzione 1 incrementa di uno il contenuto del registro 1.

Il programma appena descritto è corretto per un qualsiasi altro input (Psucc(3) == OUTPUT = 4, Psucc(10) == OUTPUT = 11,etc.. ). Se indichiamo con x un numero generico il programma Psucc(x) dara' come risultato x+1.
 

Psucc( x )

1 S(1)
 

Questo ci permette di descrivere programmi generalizzati per qualsiasi valore in ingresso. Nel seguito useremo questa convenzione.

Problema 2: scambiare il contenuto di due variabili.

Obiettivo: il valore di x in y e quello di y in x

Registri in input: r1 = x , r2 = y

registri in output: r1 r2

legge: r1 = y, r2 = x

Algoritmo
 

r3 <- r1

r1 <- r2

r2 <- r3
 

Programma U.R.M:
 

Pscambio( x , y)

1 T(1,3)

2 T(2,1)

3 T(3,2)
 

Seguiamo il programma Pscambio(4,5) passo per passo:
 

reg 4 5 0 0 0 .. stato iniziale

reg 4 5 4 0 0 .. 1 T(1,3)

reg 5 5 4 0 0 .. 2 T(2,1)

reg 5 4 4 0 0 .. 3 T(3,2) -- fine
 

Problema 3: verificare che l'istruzione T può essere sostituita da un programma che contenga solo istruzioni Z, S, J.

Obiettivo: trasferire il dato contenuto nel r2 in r1 senza usare l' istr. T

Registri input: r1 = 0, r2 = y

Registri Output: r1, r2

Legge: r1 = r2

Algoritmo: per ottenere il risultato voluto si può continuare a sommare 1 al registro r1 fermandosi quando r1 = r2. Piu' precisamente:
 

r1 <- 0

mentre r1 < r2
 

Programma U.R.M:
 

PTransfer( 0 , y )

1 Z(1) { azzera r1 }

2 J(1,2,5) { se r1 = r2 fine lavoro }

3 S(1) { incrementa r1 }

4 J(1,1,2) { ritorna a 2 }
 

Seguiamo il programma Ptransfer(0,2) passo per passo:
 

reg 0 2 0 0 0 .. stato iniziale

reg 0 2 0 0 0 .. 1 Z(1)

reg 0 2 0 0 0 .. 2 J(1,2,5)

reg 1 2 0 0 0 .. 3 S(1)

reg 1 2 0 0 0 .. 4 J(1,1,2)

reg 1 2 0 0 0 .. 2 J(1,2,5)

reg 2 2 0 0 0 .. 3 S(1)

reg 2 2 0 0 0 .. 4 J(1,1,2)

reg 2 2 0 0 0 .. 2 J(1,2,5) -- fine
 

Problema 4: scrivere un programma U.R.M. che realizzi la somma di due numeri.

Obiettivo: sommare x e y

Registri in input: r1 = x, r2 = y

Registro in output: r1

Legge: r1 = x + y

Algoritmo: si somma 1 a r1 e r3 fino a quando r3 = r2.

Formalizzando:

r3 <- 0

mentre r3 < r2

{

r1 <- r1 + 1

r3 <- r3 + 1

}

Psomma( x , y )

1 Z(3) { azzera r3 }

2 J(2,3,6) { se r2 = r3 fine lavoro }

3 S(1) { incrementa r1 }

4 S(3) { incrementa r3 }

5 J(1,1,2) { ritorna a 2 }
 

Seguiamo il programma Psomma(5,2) passo per passo:

reg 5 2 0 0 0 .. stato iniziale

reg 5 2 0 0 0 .. 1 Z(3)

reg 5 2 0 0 0 .. 2 J(2,3,6)

reg 6 2 0 0 0 .. 3 S(1)

reg 6 2 1 0 0 .. 4 S(3)

reg 6 2 1 0 0 .. 5 J(1,1,2)

reg 6 2 1 0 0 .. 2 J(2,3,6)

reg 7 2 1 0 0 .. 3 S(1)

reg 7 2 2 0 0 .. 4 S(3)

reg 7 2 2 0 0 .. 5 J(1,1,2)

reg 7 2 2 0 0 .. 2 J(2,3,6) -- fine
 

Problema 5: scrivere un programma U.R.M. che realizzi la moltiplicazione di due numeri.

Obiettivo: moltiplicare x e y

Registri in input: r1 = x, r2 = y

Registro in output: r1

Legge: r1 = x * y

Algoritmo: realizzeremo il prodotto di due numeri tramite somme successive.

In prima approssimazione:
 

r5 <-0

r3 <-0

mentre r2 < r3 fai

{

r3 <- r3 + 1

somma r1 a r5

}

r5 <- r1

Sviluppando, come visto nell'esempio 4, l'algoritmo di somma:

Programma U.R.M.

Problema 6: scrivere un programma U.R.M. che realizzi la sottrazione di due numeri

Obiettivo: sottrarre x e y

Registri in input: r1 = x, r2 = y

Registro in output: r1

Legge: r1 = x - y

Limite: il numero y deve essere minore di x .

Algoritmo:

Programma U.R.M.

Problema 7: confrontare due numeri.

Obiettivo: determinare se x = y.

Registri input: r1 = x, r2 = y

Registri output: r1

Legge: r1 = 1 se x = y, r1 = 0 se x < y.

Algoritmo:

r3 <- 0

mentre (r1 < r3) e (r2< r3) fai

Programma U.R.R.

Problema 8: scrivere un programma U.R.M. che realizzi la differenza dei quadrati di due numeri.

Obiettivo: determinare x^2 - y^2.

Registri input: r1 = x, r2 = y

Registri output: r1

Limiti sulle variabili: x = y.

Legge: r1 = (x + y) * (x - y).

Algoritmo: l'algoritmo che cerchiamo di descrivere è la combinazione di tre algoritmi già analizzati.

Una prima descrizione può essere:
 

r3 <- r1

somma r2 a r3 in r3

sottrai r1 a r2 in r4

r1 <- r3

r2 <- r4

moltiplica r1 per r2 in r5

r1 <- r5
 

Programma U.R.M.

    Pdiff_qad( x , y)

    1 T(1,3)        6 J(1,1,3)         11 J(1,1,8)         16 J(2,3,24)        21 S(5)
    2 Z(4)          7 Z(4)             12 T(3,1)           17 S(3)             22 J(1,1,19)
    3 J(2,4,7)      8 J(1,2,12)        13 T(4,2)           18 Z(4)             23 J(1,1,16)
    4 S(4)          9 S(4)             14 Z(3)             19 J(1,4,23)        24 T(5,1)
    5 S(3)          10 S(2)            15 Z(5)             20 S(4)

3.6 Computabilità, linguaggi universali e algoritmo.

Con alcuni esecutori descritti precedentemente ci siamo trovati più di una volta nella impossibilità di scrivere un algoritmo in grado di risolvere il problema che ci eravamo posti.

Sorge spontanea una domanda: esiste un esecutore per il quale sia sempre possibile scrivere un algoritmo che risolva un qualunque problema ?

Ci chiediamo cioè se esiste un linguaggio per algoritmi che ci possa permettere di descrivere il modo di operare di un ipotetico esecutore ottimale in modo da metterlo in grado di risolvere un qualunque problema dato.

La domanda, sebbene formulata in modo ambiguo, permette comunque una risposta precisa: no.

Per giustificare tale risposta è sufficiente un esempio:

Problema: dato un cerchio di raggio R costruire un quadrato avente la stessa area, usando riga e compasso.

Questo problema, conosciuto fin dall'antichità, ha tormentato i matemateci per due millenni fino a quando Lindemann, nel 1882, dimostrò che il problema era irrisolubile.

Esistono molti altri problemi che sono irrisolubili e non solo: nel 1931 Kurt Godel ha dimostrato che

tutte le assiomatizzazioni coerenti (non contraddittorie) dell'aritmetica sufficientemente potenti contengono proposizioni indecidibili.

Il "teorema di incompletezza" di Godel sopra citato è da molti considerato come il risultato più importante di tutta la logica matematica anche perchè i suoi effetti si estendono rapidamente dall'aritmetica a tutti i sistemi formali.

Abbiamo citato il teorema di Godel perchè il fatto che esistono dei problemi irrisolubili potrebbe non essere un limite alla domanda che ci eravamo posti in partenza: a noi interessa trovare una soluzione per i problemi che ammettono una soluzione.

Il fatto è che non esiste un metodo di calcolo che ci permetta di dividere i problemi in due categorie: problemi risolubili e problemi irrisolubili.

Detto con parole diverse, il problema di classificare i problemi in risolubili e irrisolubili è un problema irrisolubile. (E` un risultato, equivalente al teorema di Godel, enunciato in modo rigoroso da Alan Turing nel 1936).

Dobbiamo quindi ancora rispondere alla domanda: quando un problema è risolubile ?

Precisiamo i termini della domanda: risolvere un problema corrisponde sostanzialmente a saper calcolare (computare) la relazione funzionale che lega i dati in ingresso a quelli in uscita. Possiamo quindi parlare indifferentemente di problemi risolvibili e di funzioni calcolabili.

La domanda diventa quindi: quando una funzione può dirsi effettivamente calcolabile (computabile) ?

Possiamo inanzitutto caratterizzare l'insieme delle funzioni calcolabili dalla macchina URM, formalizzando in modo rigoroso le nostre definizioni.

Sia:

f: N^n - N una funzione definita in N^n in N dove N è l'insime dei numeri naturali.

P un programma URM, cioè una composizione di operazioni base conosciute dalla macchina URM. (Z,S,T,J)

a1,a2,..an,b numeri naturali.
 

Indicheremo con P(a1,a2,..an) - b il fatto che un programma P sui dati iniziali a1,a2,..an termina fornendo come risultato b (converge a b).

Indicheremo con P(a1,a2..,an) - oo il fatto che il programma P sui dati iniziali a1,a2,..an non termina (diverge).

Definizione.

P URM-computa f se per ogni (a1,a2,..,an,b), P(a1,a2,..an) - b se e solo se (a1,a2,..,an) appartengono al Dom(f) e f(a1,a2,..an) = b.

Definizione.

Una funzione è URM-computabile se esiste P che la URM-computa.

La domanda che ci eravamo posti si può così formulare in modo preciso:

esistono funzioni computabili che non siano URM-computabili ? La risposta a questa domanda consiste in una serie di considerazioni che sono note con il nome di Tesi di Church. Benchè essa non sia stata ne dimostrata ne confutata è oggi accettata universalmente in campo matematico e informatico. Essa afferma:

Ogni funzione computabile è URM-computabile

Possiamo ora definire rigorosamente alcuni concetti che abbiamo in precedenza trattato intuitivamente:

Un linguaggio universale è un linguaggio per algoritmi equivalente a quello della macchina URM.

Un problema è risolvibile se e solo se la sua soluzione può essere espressa in un linguaggio universale.

Un algoritmo è un elenco di istruzioni equivalente ad un programma espresso in un linguaggio universale.

Storicamente il primo formalismo adeguato per la teoria della computabilità si deve ad Alan Turing. Una delle considerazioni più evidenti che si possono fare su questo risultato è che non esiste un programma scrivibile in uno dei linguaggi di programmazione ad alto livello, come Pascal, C, Fortran, Lisp, che non abbia un equivalente nel linguaggio URM.

Esercizi.

a- Scrivere per l'esecutore N1 le seguenti sequenze di operazioni:

b- Descrivere, se è possibile, per l'esecutore N2 i seguenti problemi:

c- Scrivere per l'esecutore N2 dei programmi in cui X e Y sono le variabili in ingresso, Z la variabile in uscita e la legge è:

d- Quali dei seguenti programmi rispettano le regole del linguaggio N2 senza ambiguità?

                     
   
   e- Descrivere, se è possibile, per l'esecutore N3 i seguenti problemi:

f- Scrivere un programma U.R.M per i seguenti problemi: