Teoria degli algoritmi

Teoria degli algoritmi

Antonio Maida

1. Computabilità effettiva

Si indicherà con p₀, p₁, p₂, … la successione crescente dei numeri primi, con p₀=2.

Saranno considerati i due alfabeti H={⏐} e M={⏐, ∗⎬}.

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

Una relazione R=R₁×…×R_n è una relazione numerica se R_n⊆ωⁿ, è una relazione alfabetica se R_n⊆W_Eⁿ; nei due casi, l’insieme ambiente di R, ambR, è rispettivamente ωⁿ o W_Eⁿ.

Per cose note, gli insiemi ωⁿ e W_Eⁿ sono numerabili. E dunque, ogni relazione numerica o alfabetica è numerabile. Una funzione numerica od alfabetica y=f(x₁…x_n) è anche una funzione parziale; se poi 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 quello di semisistema di Axel Thue (1912-1954, Tönsberg, Norvegia).

Tramite il concetto di procedura si definiscono i seguenti pseudoconcetti, tipici del costruttivismo, riguardanti relazioni e funzioni, R=R₁×…×R_n ed y=f(x₁…x_n), numeriche od alfabetiche, ma estendibili 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.

c). Una funzione f dicesi parziale computabile (pcompf) se esiste una procedura che per ogni x, qualora x sia un argomento, calcola il valore f^x dopo un numero finito di passi.

d). Una funzione f 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 è 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

Si osservi che ωⁿ e W_Eⁿ sono decidibili ed enumerabili.

Una elencazione di ωⁿ è la diagonalizzazione. Ad esempio, la diagonalizzazione di ω² è:

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

Una elencazione di W_Eⁿ è invece quella lessicografica. Ad esempio, l’elencazione lessicografica di W_E, essendo E={a,b,c}, è la seguente:

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

Aritmetizzazioni

Una aritmetizzazione di W_Eⁿ (alfabetizzazione di ωⁿ) è una funzione f:W_Eⁿ→ωⁿ (f:W_Mⁿ→ωⁿ) verificante le:

a) f è biunivoca e computabile.

b) Il cod(f) è decidibile.

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

Una particolare aritmetizzazione di W_Eⁿ è la gödelizzazione g seguente. Per n=1, si elenchino gli x∈E con numeri dispari consecutivi g(x), iniziando dal dispari 3; se x∈W_E, e poi W=x₀…x_n-1 allora g(W)=p₀^g(x₀)…p_n-1^g(x_n-1). Si procede allo stesso modo per n>1.

Una particolare alfabetizzazione di ωⁿ è invece la seguente. Per ogni x∈ω si definisca induttivamente ϕ:ω→W_M: ϕ₀=∗, ϕ_x=ϕ_(x−1)∗. Si porrà poi, per ogni x₁…x_n∈ωⁿ, ϕⁿ(x₁…x_n)=ϕ(x₁)…ϕ(x_n).

Ogni aritmetizzazione f induce una elencazione di W_Eⁿ. Infatti, per b) e c), è possibile trovare il primo numero n₁ e la P₁∈W_Eⁿ, tali che n₁∈codf e f(P₁)=n₁. Iterando, si ottiene l’elencazione P₁, P₂, …

2. Funzioni ricorsive

La teoria delle funzioni ricorsive, 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.

Le funzioni di Proiezione. Uⁿ_i:ωⁿ→ω, Uⁿ_i(x₁…x_n)=x_i.

Regole

Le regole sono le quattro seguenti:

Sostituzione s:

Assegnate (m+1) funzioni g ed h_i, la funzione f=f(g(h₁,…,h_m) ottenuta per sostituzione delle h nella g, è definita da f(x₁…x_n)=g(h₁(x₁…x_n)…h_m(x₁…x_n)).

Ricorsione r:

Assegnate due funzioni g ed h, la funzione f, ottenuta per ricorsione da g ed h, è quella definita dalle: f(x₁…x_n,0)=g(x₁…x_n), f(x₁…x_n,y+1)=h(x₁…x_n,y,f(x₁…x_n,y)).

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: f(x₁…x_n)=y⇔(g(x₁…x_n,y)=0 e x<y⇒(esiste g(x₁…x_n,x)≠0)).

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^{s,r}, RG=Inz^{s,r,n}, RPA=Inz^{s,r,m}

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

Una relazione R⊆ωⁿ si dirà ricorsiva primitiva (primR) se f_R∈RP, ricorsiva (ricR) se f_R∈RG, ricorsivamente enumerabile (renR) se esiste una funzione parziale ricorsiva f tale che domf=R.

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

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: RG=comp.

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 argomenti 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 di RP ad un solo argomento. Sia f₁, f₂,… una elencazione di RP₁, e si consideri la funzione g(n)=f_n(n)+1.

Assegnato n, per la enumerabilità di RP è possibile trovare dopo un numero finito di passi la funzione f_n; per la computabilità di f_n, sarà allora possibile calcolare f_n(n) dopo un numero finito di passi, e quindi anche g(n). Allora g∈comp⊂RG. Ma g∉RP; diversamente, per qualche n si avrebbe g=f_n, e quindi l’assurdo f_n(n)=g(n)=f_n(n)+1.

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.

Una prima precisazione del concetto di algoritmo si deve ad Andrei Marköv (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∈W_E, 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_i

P₁→(•)Q₁

P₂→(•)Q₂

……

P_r→(•)Q_r.

Notazioni

a) A:P^→.

Se nessuna delle P_i occorre in P.

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

Se, essendo P_h la prima delle P_i occorrente in P, R è ottenuta da P rimpiazzandovi l’occorrenza più a sinistra di P_h→(•)Q_h con Q_h, e rispettivamente P_h è semplice o terminale.

c) A:P╞R o A:P╞•R.

Se esiste una sequenza R₀, R₁,…,R_k di k+1≥1 parole di E per le quali si abbia rispettivamente:

A:R₀├R₁├…├R_k oppure A:R₀├R₁├…├R_k−1├•R_k.