Teoria degli algoritmi

Teoria degli algoritmi

Antonio Maida

1. Computabilità effettiva

Si indicherà con p p p

, , , …..

0 1 2

p =2.

la successione crescente dei numeri primi, con 0

Saranno considerati i due alfabeti ∗⎬.

H=⎨⏐⎬ M=⎨⏐,

Le parole di H sono le cifre o i numerali di M. n

ω

⊂

Una relazione R=Rx …x è una relazione numerica se R , è una relazione alfabetica se

1 n n

n n

ω

⊂ W E; nei due casi, l’insieme ambiente di R, ambR, è rispettivamente o W E.

R n n

ω

Per cose note, gli insiemi e W E sono numerabili. E dunque, ogni relazione numerica o

alfabetica è numerabile. Una funzione numerica od alfabetica y=fx …x è anche una funzione

1 n

parziale; se poi il domf=ambf la f è allora una funzione totale.

Costruttivismo.

Il concetto di procedura è intuitivo; una procedura consta di una lista finita di istruzioni in base

alle quali è possibile fare dei passi successivi senza equivoci. Tale concetto è poi formalizzabile in

Axel Thue

quello di semisistema di (1912-1954, Tönsberg, Norvegia).

Tramite il concetto di procedura si definiscono i seguenti pseudoconcetti, tipici del costruttivismo,

…x ed y=fx …x , numeriche od alfabetiche, ma estendibili

riguardanti relazioni e funzioni, R=Rx 1 n 1 n

in modo ovvio a relazioni e funzioni arbitrarie purché numerabili. Una formalizzazione di tali

concetti avverrà nella teoria delle funzioni ricorsive per quanto riguarda il caso numerico, e nella

teoria degli algoritmi per quanto riguarda il caso alfabetico.

a). Una relazione R dicesi enumerabile (enR) se esiste una procedura che elenca i suoi elementi.

b). Una relazione R dicesi decidibile (adecR) se esiste una procedura che, per ogni x∈ambR,

decide dopo un numero finito di passi se Rx.

f

c). Una funzione dicesi parziale computabile (pcompf) se esiste una procedura che per ogni x,

f

qualora x sia un argomento, calcola il valore x dopo un numero finito di passi.

f

d). Una funzione dicesi computabile (compf) se è totale e pcomp.

e). Una funzione alfabetica f su E che sia parziale computabile dicesi algoritmo in E. Si dice che f è

n

applicabile a P∈W E, se P∈domf.

Si prova che i concetti del costruttivismo sono riconducibili ad uno solo di essi. Ad esempio:

Una relazione R è decidibile se e solo se essa è enumerabile assieme al suo complementare.

Enumerabilità dell’insieme ambiente.

n n

ω

Si osservi che e W E sono decidibili ed enumerabili.

n 2

ω ω

Una elencazione di è la diagonalizzazione. Ad esempio, la diagonalizzazione di è:

00 01 10 02 11 20 03 12 21 30,…

n

E è invece quella lessicografica. Ad esempio, l’elencazione lessicografica

Una elencazione di W

di WE, essendo E=⎨a,b,c⎬, è la seguente:

∆ a b c aa ab ac ba bb bc ca cb cc aaa aab,…

Aritmetizzazioni n

n ω

Una aritmetizzazione di W E (alfabetizzazione di ) è una funzione

n

n ω ω

→ →

f f

:W E ( : WM)

verificante le:

f è biunivoca e computabile.

a) f

b) Il cod( ) è decidibile. f f f

c) Esiste una procedura che, per ogni y∈cod( ), trova quell’ x∈dom , tale che x=y.

n

Una particolare aritmetizzazione di W E è la gödelizzazione g seguente. Per n=1, si elenchino gli

3; ∈WE,

x∈E con numeri dispari consecutivi g(x), iniziando dal dispari se poi W=x …x allora

0 n-1

x

g( )

g(x ) n–1

gW=p …p . Si procede allo stesso modo per n>1.

0 0 n-1 n

ω

Una particolare alfabetizzazione di è invece la

n

ϕ:ω → WM

ϕ0= ϕx= ϕ(x−1).

seguente. Per ogni x∈ω si definisca induttivamente Si porrà poi, per ogni

⏐ ⏐

,

n

∈ω

x …x ,

1 n =ϕx ϕx

ϕx ∗ ∗

…x … .

1 1

n n

n

Ogni aritmetizzazione f induce una elencazione di W E. Infatti, per b) e c), è possibile trovare il

n

∈W ∈codf

primo numero n e la P E, tali che n e f(P )=n . Iterando, si ottiene l’elencazione P .

1 1 1 1 1 i

2. Funzioni ricorsive

teoria delle funzioni ricorsive,

La dovuta essenzialmente a Gödel, è ricostruibile

nell’aritmetica.

Funzioni iniziali

L’insieme Iniz delle funzioni iniziali è costituito dalle seguenti funzioni (totali), con i≤n:

La funzione Zero. Z:ω→ω, Zx=0.

La funzione Successore. N:ω→ω, Nx=x+1.

n

ω →ω,

Le funzioni di Proiezione. U : U (x …x )=x .

1

ni ni n i

Regole

Le regole sono le quattro seguenti:

Sostituzione s:

Assegnate (m+1) funzioni g ed h , la funzione f= f(g(h , …,h ) ottenuta per sostituzione delle h

i m i

1

nella g, è definita da =g(h

fx …x (x …x )…h (x …x )).

1 1 1

n n m n

1

Ricorsione r:

Assegnate due funzioni g ed h, la funzione f, ottenuta per ricorsione da g ed h, è quella definita

dalle: 0)=gx

f(x …x …x f(x …x ,y+1)=h(x …x ,y,fx …x y).

1 1 1 1 1

n n n n n

Si conviene che, per n=0, g sia una costante k.

Minimalizzazione m:

Assegnata la funzione g, la funzione f, ottenuta per minimalizzazione da g, è quella definita da:

=y⇔(gx

…x …x y=0 e x<y⇒(esiste gx …x x≠0)).

fx

1 1 1

n n n

Minimalizzazione normale n:

È il caso particolare di m quando la f è totale.

Funzioni e relazioni ricorsive

Si osservi che s ed r, ma non m, mutano funzioni totali in funzioni totali. In n, la g è normale.

Gli elementi delle chiusure

RP=Inz RG=Inz RPA=Inz

{s,r} {s,r,n} {s,r,m}

sono rispettivamente le funzioni ricorsive primitive, ricorsive generali e parziali ricorsive.

∈RP, ∈RG,

n

Una relazione R⊂ω si dirà ricorsiva primitiva (primR) se f ricorsiva (ricR) se f

R R

ricorsivamente enumerabile (renR) se esiste una funzione parziale ricorsiva f tale che domf=R.

è la nota funzione caratteristica di R. Si prova che RP, contrariamente ad RG, è enumerabile.

La f R

Si hanno le:

RP⊂RG⊂RPA RP≠RG f∈RG⇒f totale (f totale, f∈RPA)⇔f∈RG.

Tesi di Church e sue conseguenze. RG=comp

Tesi di Church : .

Il senso della tesi è il seguente. Sicuramente RG⊂comp, poiché le funzioni primitive sono

computabili e le regole conservano la computabilità. Viceversa, una prova del fatto che comp⊂RG

non è realizzabile a causa della primitività del concetto di funzione computabile. Vi sono però vari

aegomenti a favore del viceversa. Intanto, tutte le funzioni notoriamente comp sono anche RG; in

secondo luogo, tutti i tentativi fatti nel precisare il concetto di funzione computabile si

equivalgono. La tesi sarà dunque valida fino a prova contraria.

La tesi implica ovviamente che: RPA=pcomp, ric=adec e ren=en.

Conseguenze della tesi di Church :

a) enRP⇒RP≠RG.

b) nonenRG.

Dim: Le due prove sono analoghe; per cui, si prova solo la a). Se RP è enumerabile allora, poiché è

riconoscibile se una funzione è ad una o più argomenti, lo sarà anche l’insieme RP degli elementi

1

di RP ad un solo argomento. Sia f , f ,…

1 2

, e si consideri la funzione

una elencazione di RP

1 g(n)=f (n)+1.

n

Assegnato n, per la enumerabilità di RP è possibile trovare dopo un numero finito di passi la

1

funzione f ; per la computabilità di f , sarà allora possibile calcolare f (n) dopo un numero finito di

n n n

passi, e quindi anche g(n). Allora g∈comp⊂RG. Ma g∉RP; diversamente, per qualche n si avrebbe

g=f , e quindi l’assurdo f (n)=g(n)=f (n)+1.

n n n

3 Algoritmi di Marköv

Si ricordi che, in generale ed in modo informale, un algoritmo in un alfabeto E è una funzione

computabile che muta parole di E in parole di E. Andrei Marköv

Una prima precisazione del concetto di algoritmo si deve ad (1856-1922,

Ryazan, Russia). Siano E’⊂E due alfabeti finiti, e

→ •

due segni non appartenenti ad E. Parole del tipo

P→Q P→•Q,

essendo P,Q∈WE, diconsi rispettivamente produzioni semplici, e produzioni terminali in E o su

E’. Con P→(•)Q

si indica indifferentemente una produzione semplice o terminale.

Schema di algoritmo di Marköv . A

Una schema di algoritmo di Marrköv in E o su E’ è una lista finita di r≥1 produzioni in E

distinte:

aventi le P

i →(•)Q

P

1 1

→(•)Q

P

2 2

………

→(•)Q .

P

r r

Notazioni

: Si scrive

A

a) :P⊃.

Se nessuna delle P occorre in P.

i

A A

b) :P├R o :P├•R.

Se, essendo P la prima delle P occorrente in P, R è ottenuta da P rimpiazzandovi l’occorrenza

h i

più a sinistra di P

h →(•)Q

con Q , e rispettivamente P è semplice o terminale.

h h h

A A

c) :P╞R o :P╞•R. =P, =R

Se esiste una sequenza R R ,…,R di k+1≥1 parole di E per le quali si abbia

0 1 k

rispettivamente:

A A

├R ├…├R ├R ├…├R ├•R

:R , oppure : R .

0 1 k 0 1 k−1 k