Simone Martini Anno Accademico 1995/96

Università di Udine September 17, 1996

Esercizi e complementi di Metodi per il Trattamento dell’Informazione^{1}

Tutte le discipline a carattere matematico e sperimentale hanno bisogno di un congruo numero di esercizi per poter essere appieno comprese e padroneggiate. Gli argomenti che costituiscono il programma del Corso di Metodi per il Trattamento dell’Informazione non fanno eccezione, con il problema che non è facile trovare raccolte di esercizi adeguate alla preparazione dell’esame. Queste pagine cercano di essere un primo contributo in tal senso, raccogliendo esercizi di diversa difficoltà, quasi tutti corredati da estese soluzioni. La raccolta comprende tutte le prove d’esame dell’A.A. 1994/95 (vedi il paragrafo 4). In aggiunta a questi esercizi di formato “classico”, si sono inseriti anche alcuni brevi argomenti, non compresi nei manuali adottati per il corso, scelti per il loro interesse o per la loro utilità per gli esercizi.

Come tutte le prime versioni, anche queste note conterranno molti refusi e, forse, qualche errore. Per cercare di eliminarli dalle versioni successive metto in palio una taglia: il primo studente a segnalare un refuso (o un errore), con relativa correzione, riceverà un quarto di punto di incremento sulla votazione del suo scritto sufficiente.

Ringrazio Fabio Alessi per aver contribuito esercizi e soluzioni per la parte di linguaggi formali.

1 Teoria della Calcolabilità

1.1 Notazioni

C sono le funzioni ricorsive unarie; φ è un’enumerazione canonica di C; Ω è la funzione ovunque indefinita; |A| è la cardinalità dell’insieme A; π_{0} (π_{1}) è la prima (seconda) proiezione sulle coppie codificate.

1.2 Insiemi ricorsivi e r.e.

1.2.1. Dato un insieme r.e. R, esiste g totale ricorsiva tale che, per ogni x,

W_{g(x)} = \{ \begin{matrix}N & se x ∈ R \\ ∅ & se x ∉ R. \end{matrix}

Sol. La richiesta g manda x nell’indice del seguente programma:

                                begin
                                input y;
                                esegui x ? ∈ R;
                                if (x ? ∈ R)↓ thenoutput y
                                end

Si tratta ovviamente di una funzione calcolabile e totale coi richiesti requisiti.

Più formalmente, la funzione g si ottiene tramite il teorema s-m-n. Definiamo la funzione

f(x, y) ≃ \{ \begin{matrix}y & se x ∈ R \\ ↑ & altrimenti. \end{matrix}

ed applichiamo s-m-n per ottenere una funzione totale e calcolabile g tale che φ_{g(x)}(y) ≃ f(x, y).

1Note ad uso esclusivo degli studenti. \begin{matrix}c \\ ◯ \end{matrix} S. Martini, 1995. Tutti i diritti riservati.

Si osservi che non esiste una funzione ricorsiva h tale che, per ogni x,

h(x) = \{ \begin{matrix}un indice di N & se x ∈ R \\ un indice di ∅ & se x ∉ R. \end{matrix}

1.2.2. (Generalizzazione del precedente). Sia R un insieme r.e. e siano W_{i} ⊆ W_{j}. Dimostrare che esiste g totale ricorsiva tale che, per ogni x,

W_{g(x)} = \{ \begin{matrix}W_{j} & se x ∈ R \\ W_{i} & se x ∉ R. \end{matrix}

Sol. La funzione g manda x nell’indice del seguente programma:

                   begin
                   input y;
                   eseguiinparallelo x ? ∈ R and φ_{i}(y);
                   { if (x ? ∈ R)↓ thenif φ_{j}(y)↓ thenoutput 0
                     if φ_{i}(y)↓ thenoutput 0

}

                   end.

1.2.3. Esiste una funzione calcolabile g tale che

W_{g(i,m)} = \{ \begin{matrix}E ⊆ W_{i}, E finito & se m ∈ K \\ W_{i} & se m ∉ K. \end{matrix}

Sol. La funzione g manda i ed m nell’indice del seguente programma:

                         begin
                         input y;
                         if φ_{m}(m)↓_{y} thenoutput φ_{i}(y)
                                elseloopforever
                         end.

1.2.4. (Suzuki) Dimostrare che non esiste una funzione totale ricorsiva f tale che, per ogni x per

cui W_{x} è ricorsivo,

W_{f(x)} = \overline{W_{x}}.

Sol. Supponiamo che tale f esista. Per l’esercizio 1.2.1, esiste g, tale che

W_{g(x)} = \{ \begin{matrix}N & se x ∈ K \\ ∅ & se x ∉ K. \end{matrix}

L’insieme W_{g(x)} è ricorsivo, e dunque avremmo W_{f(g(x))} = \overline{W_{g(x)}}, ovvero

W_{f(g(x))} = \{ \begin{matrix}N & se x ∉ K \\ ∅ & se x ∈ K. \end{matrix}

Ma questo è assurdo, perché equivale a

x ∈ \overline{K} ⟺ W_{f(g(x))} ≠ ∅,

che implica la ricorsiva enumerabilità di \overline{K}:

x ∈ \overline{K} ⟺ ∃y.y ∈ W_{f(g(x))}
⟺ ∃y∃p.φ_{f(g(x))}(y)↓_{p}

da cui \overline{K} r.e. per il teorema di proiezione.

1.2.5. Sia f una funzione totale calcolabile. Per ogni insieme r.e. W_{x} è possibile determinare in modo effettivo un indice per f^{−1}(W_{x}).

Sol. Si consideri la funzione h(x, y) ≃ φ_{x}(f(y)). Il teorema s-m-n fornisce una funzione totale calcolabile s tale che φ_{s(x)}(y) ≃ h(x, y) ≃ φ_{x}(f(y)). Dunque W_{s(x)} = {y | f(y) ∈ W_{x}} = f^{−1}(W_{x}). La funzione s stabilisce la tesi.

1.2.6. Dire se esiste una funzione totale ricorsiva h che, per ogni funzione calcolabile (cioè per ogni suo indice), calcola il suo minimo indice (cioè h(i) = min_{j}[φ_{i} = φ_{j}]).

Sol. Tale funzione non può esistere, altrimenti sarebbe decidibile l’equivalenza di programmi, sarebbe cioè ricorsivo l’insieme {(i, j) | φ_{i} = φ_{j}}: basterebbe vedere se h(i) ≃ h(j). L’insieme in questione non è invece ricorsivo (perché?).

1.2.7. Si classifichino secondo la teoria della calcolabilità l’insieme

A = {i | ∃y φ_{i}(y) ≃ φ_{y}(i)}

ed il suo complementare.

Sol. L’insieme è banalmente ricorsivo: per ogni i, è certo φ_{i}(i) ≃ φ_{i}(i). Dunque A = ℕ; il complementare di un insieme ricorsivo è ricorsivo (in questo caso è vuoto).

1.2.8. Sia A un insieme r.e. Si mostri che esiste R ricorsivo tale che

\begin{matrix}∀i ∈ A ∃j ∈ R φ_{i} = φ_{j} and \\ ∀j ∈ R ∃i ∈ A φ_{i} = φ_{j} \end{matrix}

(un R siffatto si dice rappresentazione ricorsiva di A).

Sol. Sia A = cod g e si definisca per ricorsione primitiva la funzione

\begin{aligned}f(0) & = & g(0) \\ f(n + 1) & = & P ad(g(x), f(x)), \end{aligned}

dove P ad(x, y) indica un indice z > y per φ_{x}, ottenuto con la tecnica del padding. Si definisca R = cod f; la funzione f è totale e calcolabile perché P ad lo è (vedi poi). R è ricorsivo perché enumerato in modo crescente; la verifica che soddisfa le condizioni richieste non è difficile. La definizione formale di P ad è semplice: si ricordi che il lemma del padding assicura che esiste una funzione totale calcolabile p tale che, per ogni indice i, φ_{p(i)} = φ_{i} ed inoltre p(i) > i. Definiamo prima la sua iterazione (per ricorsione primitiva):

\begin{aligned}h(0, x) & ≃ & x \\ h(n + 1, x) & ≃ & p(h(n, x)) \end{aligned}

ed infine P ad(x, y) ≃ μz.h(z, x) > y.

1.2.9. (Longo) Si consideri la seguente nozione debole di uguaglianza estensionale:

φ_{i} ≃^{w} φ_{j} sse ∀x[φ_{i}(x)↓ ∧ φ_{j}(x)↓ ⇒ φ_{i}(x) ≃ φ_{j}(x)].

Diciamo che i è il primo indice debole di φ_{i} sse i = min_{j} φ_{i} ≃^{w} φ_{j}. Si dimostri che l’insieme dei primi indici deboli di tutte le funzioni parziali ricorsive, cioè l’insieme

PID_{φ} = {k_{i} | k_{i} = min_{j}[φ_{i} ≃^{w} φ_{j}] and i ∈ N}

è ricorsivo (PID_{φ} dipende ovviamente dall’enumerazione scelta φ). Si dimostri, poi, che non si può effettivamente costruire un indice per la sua funzione caratteristica (“effettivamente” deve essere qui inteso: “in modo uniforme a partire dall’enumerazione fissata delle parziali ricorsive”).

Sol. Detta Ω la funzione ovunque indefinita, per ogni i si ha Ω ≃^{w} φ_{i}. Ma allora PID è finito (e dunque ricorsivo), essendo contenuto nell’intervallo [0, u], dove u è il minimo indice di Ω.

Per la seconda parte dell’esercizio, sia

f(x, y) ≃ \{ \begin{matrix}1 & se φ_{x}(x)↓ \\ ↑ & altrimenti. \end{matrix}

Sia s la funzione del teorema s-m-n: φ_{s(x)}(y) ≃ f(x, y) (dunque φ_{s(x)} è la funzione costante 1 (se x ∈ K), oppure è la funzione ovunque indefinita Ω). Scelto m qualsiasi, è possibile enumerare le ricorsive parziali “scambiando tra loro le funzioni φ_{0} e φ_{s(m)}”. In modo più preciso: definiamo la funzione

σ(x) ≃ \{ \begin{matrix}0 & se x = s(m) \\ s(m) & se x = 0 \\ x & altrimenti. \end{matrix}

La σ è certo calcolabile e dunque l’enumerazione data da μ = φ∘σ è una buona gödelizzazione di C. Si osservi che μ_{0} è la funzione ovunque indefinita sse m ∉ K. Se fossimo in grado di produrre effettivamente la funzione caratteristica di PID_{μ}, essa deciderebbe dell’appartenenza di m a \overline{K}:

PID_{μ} = \{0\} sse m ∈ \overline{K}.

Per concludere basta ora osservare che σ (e dunque μ) dipende in modo uniforme da m: il preteso modo uniforme di ottenere la funzione caratteristica di PID darebbe un algoritmo di decisione per \overline{K}. (Quest’ultima parte dovrebbe essere data con maggior dettaglio: σ(m, x), poi s-m-n ancora una volta, ecc.).

1.3 Riduzioni, insiemi creativi, produttivi, m-completi

1.3.1. Si classifichino secondo la teoria della calcolabilità l’insieme

Rec = {i | W_{i} ricorsivo}

ed il suo complementare.

Sol. È immediato osservare che Rec è un insieme di indici che rispetta le funzioni. Il teorema di Rice ci assicura che sia Rec che il complementare non sono ricorsivi. È poi semplice rendersi conto che l’insieme delle funzioni con dominio ricorsivo non è chiuso all’insù (si fornisca un controesempio). Lo stesso vale per \overline{Rec}. Per il teorema di Rice-Shapiro i due insiemi assegnati non sono r.e. (e la dimostrazione del teorema prova, in realtà, che si tratta di insiemi produttivi). Forniamo comunque delle riduzioni da \overline{K} che mostrino direttamente la produttività di Rec e \overline{Rec}. Per Rec si definisca

h(x, y) ≃ \{ \begin{matrix}φ_{y}(y) & se x ∈ K \\ ↑ & altrimenti. \end{matrix}

Dal teorema s-m-n si ottiene una funzione totale calcolabile g tale che φ_{g(x)}(y) ≃ h(x, y). Se ora x ∈ K, φ_{g(x)} è definita per quegli y per cui φ_{y}(y)↓, ovvero W_{g(x)} = K, che implica g(x) ∉ Rec. Se, viceversa, x ∉ K, φ_{g(x)} = Ω, ovvero W_{g(x)} = ∅, che implica g(x) ∈ Rec. Riassumendo: x ∈ \overline{K} sse g(x) ∈ Rec, ovvero g stabilisce la m-riduzione \overline{K} ≤_{m} Rec.

Per \overline{Rec} si definisca

k(x, y) ≃ \{ \begin{matrix}y & se x ∈ K oppure y ∈ K \\ ↑ & altrimenti. \end{matrix}

Ancora dal teorema s-m-n, si ottiene una funzione totale calcolabile t tale che φ_{t(x)}(y) ≃ k(x, y). Si osservi ora che x ∈ K sse t(x) ∈ Rec, ovvero K ≤_{m} Rec, che è lo stesso che dire \overline{K} ≤_{m} \overline{Rec}.

1.3.2. Sia A = \{i | φ_{i}(i) ≃ 0\}. Si dimostri in modo diretto che \overline{A} è produttivo (cioè esibendo la sua funzione produttiva, e non per riduzione).

Sol. Si definisca, tramite il teorema s-m-n, la funzione g tale che

φ_{g(x)}(y) ≃ \{ \begin{matrix}0 & φ_{x}(y)↓ \\ ↑ & altrimenti. \end{matrix}

e si osservi che g(x) ∈ A sse g(x) ∈ W_{x} (infatti g(x) ∈ A sse φ_{g(x)}(g(x)) ≃ 0 sse φ_{x}(g(x))↓ sse g(x) ∈ W_{x}). Un semplice ragionamento per casi mostra che g è la funzione produttiva di \overline{A}: se W_{x} ⊆ \overline{A}, allora g(x) ∈ \overline{A}\W_{x}. Supposto infatti W_{x} ⊆ \overline{A}, certo g(x) ∈ \overline{A}; se fosse g(x) ∈ A, si avrebbe g(x) ∈ W_{x}, ovvero g(x) ∈ \overline{A}, che è assurdo. D’altra parte g(x) ∉ W_{x}, perché altrimenti si avrebbe sia g(x) ∈ A che g(x) ∉ A.

1.3.3. Si classifichino secondo la teoria della calcolabilità l’insieme

B = {i | ∃y φ_{i}(y)↓ ∧ φ_{y}(i)↓ ∧ φ_{i}(y) ≃ φ_{y}(i)}

ed il suo complementare.

Sol. L’insieme B è r.e. per il teorema di proiezione:

x ∈ B sse ∃y∃p_{1}∃p_{2} φ_{i}(y) ↓_{p_{1}} ∧ φ_{y}(i) ↓_{p_{2}} ∧ φ_{i}(y) ≃ φ_{y}(i).

Il suo complementare è produttivo: mostriamo una riduzione K ≤_{m} B (e dunque \overline{K} ≤_{m} \overline{B}). Si definisca

h(x, y) ≃ \{ \begin{matrix}0 & se x ∈ K \\ ↑ & altrimenti. \end{matrix}

e sia g la funzione totale calcolabile che si ottiene dal teorema s-m-n: φ_{g(x)}(y) ≃ h(x, y). Ora x ∈ K implica che φ_{g(x)} è la costante 0 e, per esempio, φ_{g(x)}(g(x))↓ e φ_{g(x)}(g(x)) ≃ φ_{g(x)}(g(x)), ovvero g(x) ∈ B. Viceversa, x ∉ K implica φ_{g(x)} = Ω e dunque, per ogni y, φ_{g(x)}(y) ↑ e g(x) ∉ B. Dunque K ≤_{m} B. L’insieme B è quindi m-completo (creativo), perché r.e. e K ≤_{m} B; \overline{B} è produttivo.

1.3.4. Si classifichino secondo la teoria della calcolabilità gli insiemi

\begin{aligned}A & = & \{< i, j >| ∀x φ_{i}(φ_{j}(x)) ≃ x\} \\ B & = & \{< i, j >| ∃x φ_{i}(φ_{j}(x)) ≃ x\} \end{aligned}

ed i loro complementari. Si dica poi quali m-riduzioni tra questi quattro insiemi si possono derivare dalla classificazione così ottenuta.

Sol. B è r.e. per proiezione. \overline{B} è produttivo:

φ_{h(x)}(y) ≃ \{ \begin{matrix}y & se x ∈ K \\ ↑ & altrimenti. \end{matrix}

La funzione h′(x) ≃< h(x), h(x) > stabilisce la riduzione K ≤_{m} B. \overline{A} è produttivo, con la stessa riduzione di \overline{B}. A è produttivo:

φ_{g(x)}(y) ≃ \{ \begin{matrix}y & se φ_{x}(x) non converge in al più y passi \\ ↑ & altrimenti. \end{matrix}

g′(x) ≃< g(x), g(x) > è la riduzione cercata.

1.3.5. Numeri casuali (Kolmogorov)

Possiamo definire la complessità di un numero x come il minimo indice di un programma che, sull’argomento 0, stampa x: Cpl(x) = μk.φ_{k}(0) ≃ x. Diremo allora che un numero x è casuale (secondo Kolmogorov) se la sua complessità è maggiore o uguale ad x stesso:

Rnd = {x | Cpl(x) ≥ x} = {x | ∀i φ_{i}(0) ≃ x ⇒ i ≥ x}.

Gli elementi di Rnd sono dunque quei numeri che non hanno “descrizioni più piccole di loro”. In altre parole, non esiste alcun modo più compatto per definirli che elencarne esplicitamente le cifre.

Proveremo che: (i) esistono infiniti numeri casuali; (ii) ogni funzione calcolabile (totale) g che enumera solo numeri casuali (cioè il cui codominio è contenuto in Rnd), ne enumera un sottoinsieme finito (cioè cod g è finito). Ne segue che Rnd è infinito e non contiene insiemi r.e. infiniti: è dunque un insieme immune. Il suo complementare

\overline{Rnd} = \{x | ∃i φ_{i}(0) ≃ x ∧ i < x\}

è r.e., come si vede facilmente per proiezione: \overline{Rnd} è dunque un insieme semplice.

Dimostriamo dunque (i): Rnd è infinito. Scegliamo k arbitrario e consideriamo il minimo x che non sia stampato dai programmi da 0 a k (sull’argomento 0). Certo è x ≤ k + 1 (il caso peggiore si ha quando tutti i programmi sono definiti e stampano tutti i valori da 0 a k: in questo caso x è proprio k+1; se qualche programma non è definito, o se più di un programma stampa lo stesso valore, ci deve essere un numero compreso tra 0 e k che non viene stampato: esso è lo x che ci interessa). D’altra parte, ogni programma che stampa x deve avere indice maggiore o uguale a k + 1 (ovvero Cpl(x) ≥ k + 1). Ne segue che Cpl(x) ≥ k + 1 ≥ x e dunque x è casuale. Abbiamo pertanto dimostrato che, per k arbitrario, esiste un numero casuale di complessità maggiore di k. Ne segue che Rnd è infinito.

Dimostriamo ora (ii), nella sua contrapposizione: per ogni f totale calcolabile con cod f infinito, cod f ⊈ Rnd. Data f, definiamo la funzione

g(z, x) ≃ f(μy.f(y) > z).

La g è totale, perché cod f è infinito. Dal teorema s-m-n e da quello di ricorsione si ottiene e tale che

φ_{e}(x) ≃ g(e, x) ≃ f(μy.f(y) > e).

Osserviamo ora che φ_{e}(0) ∈ cod f (banalmente) ed anche φ_{e}(0) ∉ Rnd, dato che φ_{e}(0) > e.

1.3.6. Si dimostri che l’immunità di Rnd implica l’indecidibilità del problema della fermata.

Sol. Se Halt(x, y) ≡ φ_{x}(y)↓ fosse decidibile, sarebbe decidibile anche Halt′(x, y, z) ≡ φ_{x}(y)↓ z e dunque calcolabile e totale la funzione Cmp(z) ≃ μk.Halt′(k, 0, z). Ma questo fornirebbe un algoritmo per decidere l’appartenenza a Rnd: x ∈ Rnd sse x > Cmp(x).

1.4 Teorema di ricorsione

1.4.1. Si dimostri che esiste un indice i tale che

W_{i} = {i, i^{2}, i^{3}, i^{4}, …}.

Sol. Sia

φ_{h(x)}(y) ≃ \{ \begin{matrix}1 & se esiste k, y = x^{k} \\ ↑ & altrimenti. \end{matrix}

La funzione h è totale e calcolabile. Per il teorema di ricorsione esiste i per cui φ_{h(i)} = φ_{i}. Tale i soddisfa le richieste dell’esercizio.

1.4.2. Esiste un intero e tale che, per ogni n,

φ_{e}(n) ≃ φ_{n}(e)

Sol. Sia

g(k, n) ≃ \{ \begin{matrix}φ_{n}(k) & se φ_{n}(k)↓ \\ ↑ & altrimenti. \end{matrix}

Per il teorema s-m-n, esiste s totale calcolabile per cui φ_{s(i)}(n) ≃ g(k, n). Per il teorema di ricorsione esiste e per cui φ_{s(e)} = φ_{e}, ovvero, per ogni n,

φ_{e}(n) ≃ φ_{s(e)}(n) ≃ \{ \begin{matrix}φ_{n}(e) & se φ_{n}(e)↓ \\ ↑ & altrimenti. \end{matrix}

che è come dire φ_{e}(n) ≃ φ_{n}(e).

1.4.3. Si dimostri che l’insieme dei punti fissi di una funzione totale calcolabile non è mai finito. (Suggerimento: mostrare che in caso contrario una funzione totale calcolabile non avrebbe alcun punto fisso).

Sol. Supponiamo che, per una data f, F = {i | φ_{i} = φ_{f(i)}} sia finito. La finitezza di F assicura l’esistenza di una funzione calcolabile g diversa da tutte quelle con indici in F (∀i ∈ F g ≠ φ_{i}). Si definisca ora la funzione

h(j, x) ≃ \{ \begin{matrix}g(x) & se j ∈ F \\ φ_{f(j)}(x) & se j ∉ F. \end{matrix}

Applicando il teorema s-m-n si ottiene una funzione totale e calcolabile s per la quale il teorema di ricorsione fornisce un indice i tale che

φ_{i} = φ_{s(i)} = \{ \begin{matrix}g & se i ∈ F \\ φ_{f(i)} & se i ∉ F. \end{matrix}

Ma questo è assurdo: se i ∈ F, φ_{i} = g e ciò non può essere per la scelta di g; se i ∉ F, φ_{i} = φ_{f(i)}, ovvero i ∈ F.

1.4.4. (Generalizzazione del precedente) Sia A l’insieme dei punti fissi di una funzione totale calcolabile f. Si mostri che se A è ricorsivo e non banale, allora contiene indici per tutte le funzioni calcolabili (cioè {φ_{i} | i ∈ A} = C).

Sol. Come l’esercizio precedente.

1.4.5. Se A è ricorsivo ed è l’insieme dei punti fissi di una funzione totale calcolabile f, allora \overline{A} non è un insieme di punti fissi.

Sol. Si supponga che \overline{A} sia l’insieme dei punti fissi di g e si definisca la funzione

φ_{h(i)}(x) ≃ \{ \begin{matrix}φ_{f(i)} & se i ∉ A \\ φ_{g(i)} & se i ∈ A. \end{matrix}

La funzione h non ha punti fissi: assurdo.

1.4.6. Sia A un insieme produttivo che rispetta le funzioni. Si dimostri che A ≰_{m} \overline{A}. (Suggerimento: la pretesa riduzione non ha punti fissi).

Sol. Supponiamo che h : A ≤_{m} \overline{A}. Applicando il teorema di ricorsione si ottiene n tale che φ_{n} = φ_{h(n)}. Ma ora, essendo h una m-riduzione, si ha n ∈ A sse f(n) ∈ \overline{A}; d’altra parte, siccome A rispetta le funzioni, n ∈ A sse f(n) ∈ A. Dunque f(n) ∈ A sse f(n) ∈ \overline{A}: assurdo.

1.4.7. Un insieme A è produttivo sse \overline{K} ≤_{m} A.

Sol. Parte centrale della dimostrazione del teorema di Myhill.

1.4.8. Teorema di mutua ricorsione (Smullyan)

Date due funzioni totali calcolabili f e g di due variabili esistono a e b tali che φ_{a} = φ_{f(a,b)} e φ_{b} = φ_{g(a,b)}.

Sol. Si applichi alla funzione f il secondo teorema di ricorsione con parametri, ottenendo una funzione totale calcolabile n tale che, per ogni x, φ_{n(x)} = φ_{t(n(x),x)}. Consideriamo ora la funzione (totale calcolabile) h(z) ≃ g(n(z), z), ed applichiamo ad essa il teorema di ricorsione; si ottiene b tale che φ_{b} = φ_{g(n(b),b)}. Si prenda infine a = n(b).

Negli esercizi è talvolta conveniente usare questo teorema sulle coppie codificate, ovvero nell’enunciato: date due funzioni totali calcolabili unarie f e g, esistono a e b tali che φ_{a} = φ_{f(<a,b>)} e φ_{b} = φ_{g(<a,b>)}.

1.4.9. Enunciare e dimostrare un teorema di mutua ricorsione (vedi 1.4.8) con parametri (si veda l’esercizio 1.5.7 per un esempio d’uso).

1.5 Riduzioni che sfruttano il teorema di ricorsione

1.5.1. Si classifichino secondo la teoria della calcolabilità l’insieme

A = {i | ∀y φ_{i}(y) ≃ φ_{y}(i)}

ed il suo complementare.

Sol. A è produttivo, per riduzione da \overline{K}. Sia

h(x, z, y) ≃ \{ \begin{matrix}φ_{y}(z) & se φ_{x}(x) non converge in al più y passi \\ ↑ & altrimenti. \end{matrix}

Applicando il teorema s-m-n si ottiene una funzione totale e calcolabile g tale che φ_{g(x,z)}(y) ≃ h(x, z, y), per ogni x, y, z. Si osservi che quando x ∈ \overline{K} si ha φ_{g(x,z)}(y) ≃ φ_{y}(z); quando invece x ∈ K, la funzione φ_{g(x,z)} ha dominio finito (perché a partire da un certo y_{0}, per ogni y ≥ y_{0}, φ_{x}(x)↓ y. Applicando il teorema di ricorsione con parametro si ottiene una funzione totale e calcolabile n tale che, per ogni x, φ_{n(x)} = φ_{g(x,n(x))}. Se dunque x ∈ \overline{K}, φ_{n(x)}(y) ≃ φ_{y}(n(x)) e n(x) ∈ A. Se, invece, x ∈ K, φ_{n(x)} ha dominio finito e dunque esisterà certo un y per il quale φ_{n(x)}(y) ≄ φ_{y}(n(x)) (per esempio un indice abbastanza grosso di una funzione costante). La funzione n stabilisce la riduzione cercata: \overline{K} ≤_{m} A.

L’insieme \overline{A} è produttivo. Mostriamo infatti una riduzione K ≤_{m} A (da cui \overline{K} ≤_{m} \overline{A}). Sia

h(x, z, y) ≃ \{ \begin{matrix}φ_{y}(z) & se φ_{x}(x)↓ \\ ↑ & altrimenti. \end{matrix}

Applicando, come nel caso precedente, prima il teorema s-m-n e poi quello di ricorsione con parametro si ottiene una funzione totale calcolabile m tale che

φ_{m(x)}(y) ≃ \{ \begin{matrix}φ_{y}(m(x)) & se x ∈ K \\ ↑ & altrimenti. \end{matrix}

È chiaro che se x ∉ K, m(x) è un indice della funzione ovunque divergente, che non appartiene certo ad A (stesso argomento del caso precedente).

1.5.2. Si classifichino, dal punto di vista della teoria della calcolabilità, gli insiemi

A = {< i, j > | φ_{i} assume il valore i per esattamente j argomenti distinti}
B = {< i, j > | φ_{i} assume il valore i per almeno j argomenti distinti}

ed i loro complementari.

Sol. L’insieme A è produttivo, per riduzione da \overline{K}. Sia

h(x, y) ≃ \{ \begin{matrix}y & se φ_{x}(x)↓ \\ ↑ & altrimenti. \end{matrix}

Dal teorema s-m-n otteniamo una funzione totale calcolabile k tale che φ_{k(x)}(y) ≃ h(x, y). Si ha: x ∈ K ⇒ φ_{k(x)} = id ⇒< k(x), 0 >∉ A; d’altra parte, x ∉ K ⇒ φ_{k(x)} = Ω ⇒< k(x), 0 >∈ A. Ovvero \overline{K} ≤_{m} A, attraverso la funzione f(x) ≃< k(x), 0 >.

L’insieme \overline{A} è produttivo. Dimostriamo che K ≤_{m} A, da cui \overline{K} ≤_{m} \overline{A} e, dunque, la tesi. Definiamo la funzione

h(z, x, y) ≃ \{ \begin{matrix}z & se (x = 0 or … or x = z − 1) and φ_{x}(x)↓ \\ ↑ & altrimenti. \end{matrix}

Applicando s-m-n e poi, come prima, il teorema di ricorsione con parametro, si ottiene una funzione totale calcolabile m tale che: x ∈ K implica φ_{m(x)} assume il valore m(x) esattamente m(x) volte; x ∈ \overline{K} implica φ_{m(x)} = Ω. Dunque, supposto che l’enumerazione delle funzioni non assegni 0 come indice di Ω (si osservi che è sempre possibile scegliere un’enumerazione siffatta), x ∈ K sse < m(x), m(x) >∈ A.

L’insieme B è r.e. per proiezione:

B = {< i, j > | ∃q∃p Seq(q) ∧ lung(q) < j ∧ ∀x < j φ_{i}((q)_{x})↓_{p}}

L’insieme \overline{B} è produttivo: x ∈ K sse < n(x), 1 >∈ B, dove n è la funzione ottenuta nella prima parte dell’esercizio.

Ne segue che B, essendo r.e. con complementare produttivo, è creativo e, dunque, m-completo per il teorema di Myhill.

1.5.3. Dati due insiemi di naturali A e B, si definisce l’insieme A · B nel modo seguente:

A · B = {z | ∃a ∈ A ∃b ∈ B φ_{a}(b) ≃ z}.

Si classifichino secondo la teoria della calcolabilità gli insiemi

\begin{aligned}C & = & \{< i, j >| W_{i} · W_{j} = ∅\} \\ D & = & \{< i, j >| W_{i} · W_{j} = \{i\}\} \end{aligned}

ed i loro complementari.

Sol. L’insieme \overline{C} è r.e., come facilmente si vede dalla sua definizione

\overline{C} = \{< i, j >| ∃a ∈ W_{i} ∃b ∈ W_{j} φ_{a}(b)↓\}

e dal teorema di proiezione, ricordando che l’appartenenza ad un insieme r.e. (per esempio a ∈ W_{i}) è un predicato r.e. (in a e i).

L’insieme C è produttivo (e dunque \overline{C} è creativo, ovvero m-completo). Si osservi infatti che

x ∈ \overline{K} ⟺ \{x\} · \{x\} = ∅.

Rimane solo da esplicitare la dipendenza tra x ed un indice per {x}: la funzione totale h tale che

φ_{h(x)}(y) ≃ \{ \begin{matrix}0 & se y = x \\ ↑ & altrimenti \end{matrix}

serve allo scopo: per ogni x, W_{h(x)} = {x}. Ricapitolando, si ha

x ∈ \overline{K} ⟺< h(x), h(x) >∈ C.

Gli insiemi D e \overline{D} sono entrambi produttivi. Per mostrare una riduzione da \overline{K} a \overline{D}, si può partire da quella appena data per C: invece di un singoletto \{x\}, con x ∈ \overline{K}, dobbiamo ora formare singoletti {n(x)} tali che φ_{n(x)}(n(x)) ≃ n(x) quando x ∈ K. La funzione n si ottiene da una variante della funzione h:

φ_{k(x,z))}(y) ≃ \{ \begin{matrix}z & se y = z ∧ x ∈ K \\ ↑ & altrimenti \end{matrix}

e dal secondo teorema di ricorsione con parametro, che dà una funzione totale calcolabile n tale che, per ogni x, φ_{n(x)} = φ_{k(x,n(x)))}, ovvero

W_{n(x)} = \{ \begin{matrix}\{n(x)\} t.c. φ_{n(x)}(n(x)) ≃ n(x) & se x ∈ K \\ ∅ & altrimenti. \end{matrix}

La funzione che manda x in < n(x), n(x) > fornisce la riduzione K ≤_{m} D.

Per la riduzione \overline{K} ≤_{m} B, possiamo modificare la definizione della funzione k, in modo da farla comunque convergere su z (ovvero, sull’indice “di se stessa”, dopo l’applicazione del teorema di ricorsione):

φ_{t(x,z))}(y) ≃ \{ \begin{matrix}z & se y = z \\ y & se x ∈ K \\ ↑ & altrimenti. \end{matrix}

Procedendo ora come prima, si ottiene una funzione totale calcolabile m tale che:

W_{m(x)} = \{ \begin{matrix}\{m(x)\} t.c. φ_{m(x)}(m(x)) ≃ m(x) & se x ∈ \overline{K} \\ N & altrimenti. \end{matrix}

Osservando che N · N = N, la riduzione cercata è stabilita da p(x) ≃< m(x), m(x) >.

1.5.4. Si classifichino secondo la teoria della calcolabilità gli insiemi

\begin{aligned}C & = & \{< i, j >| |W_{i} · W_{j}| = 2 ∧ i ∈ W_{i} · W_{j}\} \\ D & = & \{< i, j >| |W_{i} · W_{j}| = i ∧ i ∈ W_{i} · W_{j}\} \end{aligned}

ed i loro complementari (si veda l’esercizio 1.5.3 per la definizione di A · B)..

Sol. Gli insiemi assegnati sono tutti produttivi. Una riduzione K ≤_{m} C può essere stabilita a partire dalla funzione

φ_{h(x,z))}(y) ≃ \{ \begin{matrix}y & se (y = z ∨ y = e) ∧ x ∈ K \\ ↑ & altrimenti, \end{matrix}

dove e è un indice (fissato) di Ω. Dal secondo teorema di ricorsione con parametro si ottiene una funzione totale calcolabile n tale che, per ogni x, φ_{n(x)} = φ_{k(x,n(x)))} è l’identità ristretta a

W_{n(x)} = \{ \begin{matrix}\{n(x), e\} & se x ∈ K \\ ∅ & altrimenti. \end{matrix}

La funzione che manda x in < n(x), n(x) > fornisce la riduzione K ≤_{m} C (si osservi che n(x) ≠ e).

Per la riduzione \overline{K} ≤_{m} C, usiamo la funzione

φ_{k(x,z))}(y) ≃ \{ \begin{matrix}y & se y = z ∨ y = e ∨ x ∈ K \\ ↑ & altrimenti \end{matrix}

ed il teorema di ricorsione (dettagli lasciati per esercizio).

La riduzione K ≤ D si può ottenere con la funzione

φ_{s(x,z))}(y) ≃ \{ \begin{matrix}y & se (y = z ∨ y ∈ \{e_{1}, …, e_{z−1}\}) ∧ x ∈ K \\ ↑ & altrimenti, \end{matrix}

dove e_{1}, …, e_{z−1} sono z − 1 indici di Ω, ottenuti in modo ricorsivo (per esempio usando il lemma del padding) a partire da un indice e fissato (formalmente, la condizione y ∈ {e_{1}, …, e_{z−1}} si scriverà y ∈ W_{p(z)}, con p funzione totale calcolabile che si ottiene dal padding e W_{p(z)} finito). Dal teorema di ricorsione si ottiene una funzione totale calcolabile q tale che φ_{q(x)} è l’indentità ristretta a

W_{q(x)} = \{ \begin{matrix}\{q(x), e_{1}, …, e_{q(x)−1}\} & se x ∈ \overline{K} \\ ∅ & altrimenti. \end{matrix}

La riduzione cercata è stabilita dalla funzione che manda x in < q(x), q(x) >. Infine, la riduzione \overline{K} ≤_{m} D si stabilisce con la funzione

φ_{s(x,z))}(y) ≃ \{ \begin{matrix}y & se y = z ∨ y ∈ \{e_{1}, …, e_{z−1}\} ∨ x ∈ K \\ ↑ & altrimenti. \end{matrix}

1.5.5. Si classifichino secondo la teoria della calcolabilità gli insiemi

\begin{aligned}A & = & \{i | ∀x.φ_{i}(x)↓ ⇒ φ_{i}(x) ≤ i\} \\ B & = & \{i | |\{x | φ_{i}(x)↓ ∧ φ_{i}(x) > i\}| = 4\} \end{aligned}

ed i loro complementari (|A| denota la cardinalità dell’insieme A). Sol. \overline{A} = \{i | ∃x.φ_{i}(x)↓ ∧ φ_{i}(x) > i\} è r.e. per il teorema di proiezione. Mostriamo una riduzione K ≤_{m} \overline{A}, col che \overline{A} è creativo e A produttivo.

φ_{h(x,z))}(y) ≃ \{ \begin{matrix}z + 1 & se x ∈ K \\ ↑ & altrimenti, \end{matrix}

Dal secondo teorema di ricorsione con parametro si ottiene una funzione totale calcolabile n tale che, per ogni x, φ_{n(x)} = φ_{h(x,n(x))}; ora si ha x ∈ K sse n(x) ∈ \overline{A}.

Sia B che \overline{B} sono produttivi.

1.5.6. Si classifichino secondo la teoria della calcolabilità l’insieme

A = {i | W_{i} = {π_{0}(i) + i}}

ed il suo complementare.

1.5.7. Si classifichino secondo la teoria delle calcolabilità l’insieme

C = {x | |{y | φ_{π_{0}(x)}(y) ≃ π_{1}(x)}| = x}

ed il suo complementare. Sol. Stabiliamo che K ≤_{m} C. Sia

φ_{h(x,z)}(y) ≃ \{ \begin{matrix}π_{1}(z) & se x ∈ K e y < z \\ ↑ & altrimenti, \end{matrix}

e si applichi il teorema di mutua ricorsione con parametro (1.4.9) ad h e alla proiezione p(x, z) ≃ x. Si ottiene una funzione m tale che

\begin{aligned}φ_{π_{0}(m(x))} & = & φ_{h(x,m(x))} \\ φ_{π_{1}(m(x))} & = & φ_{p(x,m(x))} = φ_{x} \end{aligned}

Se x ∈ K, si ha

φ_{π_{0}(m(x))}(y) ≃ \{ \begin{matrix}π_{1}(m(x)) & se y < z \\ ↑ & altrimenti, \end{matrix}

da cui m(x) ∈ C. Se x ∉ K, φ_{π_{0}(m(x))} = Ω, ovvero m(x) ∉ C. Dunque m : K ≤_{m} C.

Una riduzione \overline{K} ≤_{m} C si ottiene partendo dalla funzione

φ_{k(x,z)}(y) ≃ \{ \begin{matrix}π_{1}(z) & se x ∈ K oppure y < z \\ ↑ & altrimenti, \end{matrix}

e procedendo in modo analogo. In conclusione sia C che \overline{C} sono produttivi.

1.5.8. Si considerino i seguenti insiemi ed i loro complementari:

\begin{aligned}A & = & \{< i, j >| |E_{i}| = j\}, \\ B & = & \{< i, j >| |E_{i}| < j\}, \\ C & = & \{< i, j >| |E_{i}| = 2\}. \end{aligned}

Si dimostri se ognuno di questi sei insiemi è o meno ≤_{m} rispetto a ciascuno dei cinque rimanenti.

Sol. Per risolvere il problema è opportuno individuare la classificazione di alcuni insiemi, da cui dedurre l’esistenza (o meno) di alcune relazioni; potremo poi determinare le eventuali riduzioni mancanti. Sia Div = {i | φ_{i} = Ω}.

(a): Div ≤_{m} A è facile: i ∈ Div sse < i, 0 >∈ A. Dalla produttività di Div segue quella di A.

(b): Div ≤_{m} B, con la stessa riduzione di (a): B è produttivo.

(c): \overline{B} è r.e., dal teorema di proiezione.

(d): C ≤_{m} A è evidente: < i, j >∈ C sse < i, 2 >∈ A.

(e): C e \overline{C} sono entrambi produttivi, come si vede senza grande difficoltà modificando leggermente le riduzioni della dimostrazione del teorema di Rice-Shapiro.

(f): Da (e) e (d) si ottiene che \overline{A} è produttivo.

Da questi primi fatti possiamo già dedurre l’esistenza di molte riduzioni; le riassumiamo nella tabella seguente (√ indica l’esistenza della riduzione; × la non esistenza):

≤_{m} A B C \overline{A} \overline{B} \overline{C}
A √ ×  ×
B √ √ √ √ × √
C √ × √  ×

Le riduzioni della riga B si ottengono in virtù dell’esercizio 1.4.7.

(g): A ≤_{m} C. Si tratta di una riduzione non banale. Introduciamo in primo luogo la notazione Bcod(φ_{i}, y) per indicare il “codominio di φ_{i} ristretta a [0, y] per y passi”:

Bcod(φ_{i}, y) = {z | ∃x ∈ [0, y] φ_{i}(x)↓_{y}z}

Definiamo ora la funzione

φ_{s(<i,j>)}(y) ≃ \{ \begin{matrix}0 & |Bcod(φ_{i}, y)| < j \\ 1 & |Bcod(φ_{i}, y)| = j \\ 2 & |Bcod(φ_{i}, y)| > j \end{matrix}

Osserviamo che, purché j ≠ 0, |E_{i}| = j sse |E_{s(<i,j>)}| = 2. Per ottenere la riduzione cercata occorre trattare il caso j = 0. Ma si osservi che < i, 0 >∈ A sse < i, 0 >∈ B sse f(< i, 0 >) ∈ C, dove f : B ≤_{m} C. In conclusione, la funzione

g(x) ≃ \{ \begin{matrix}f(x) & se π_{1}(x) = 0 \\ s(x) & altrimenti \end{matrix}

stabilisce la cercata riduzione A ≤_{m} C. (Problema: Esiste una riduzione più semplice?)

(h): (g) e (d) danno A ≡_{m} C.

(i): per riempire le quattro caselle rimaste, è sufficiente domandarsi ora se C ≤_{m} \overline{C}: questo problema è infatti equivalente, in virtù di (h), agli altri tre. Si ha che C ≰_{m} \overline{C} (si supponga il contrario con funzione r e si applichi il teorema di mutua ricorsione alla funzione r e all’identità, ottenendo n tale che φ_{π_{0}(n)} = φ_{r(n)} e derivando un assurdo, secondo lo schema dell’esercizio 1.4.6).

In conclusione, la tabella seguente riassume le risposte al quesito posto:

\begin{matrix}≤_{m} & A & B & C & \overline{A} & \overline{B} & \overline{C} \\ A & √ & × & √ & × & × & × \\ B & √ & √ & √ & √ & × & √ \\ C & √ & × & √ & × & × & × \end{matrix}

1.6 Operatori ricorsivi, λ-calcolo

1.6.1. Data una funzione totale calcolabile f, si consideri l’insieme

Fix(f) = {i | φ_{i} = φ_{f(i)}}.

Si diamo esempi di funzioni per cui Fix(f) è ricorsivo, r.e. non ricorsivo, produttivo. Sol. Il ragionamento è semplificato scegliendo f estensionale, perché in tal modo Fix(f) è un insieme che rispetta le funzioni e vi possiamo applicare i noti teoremi.

• Sia f = id. Allora Fix(f) = ℕ. Inoltre, per f estensionale, Fix(f) è ricorsivo se e solo se coincide con ℕ (per il teorema di Rice, osservando che Fix(f) non è mai vuoto, per il teorema di ricorsione).

• Sia

h(i, x) ≃ \{ \begin{matrix}0 & se x = 0 \\ φ_{i}(x) & altrimenti. \end{matrix}

Dal teorema s-m-n otteniamo una funzione totale calcolabile estensionale t (un’operazione effettiva) tale che φ_{t(i)}(x) ≃ h(i, x). Fix(t) = {i | φ_{i}(0) = 0}, che è r.e. per proiezione e non ricorsivo per il teorema di Rice.

• Sia f estensionale tale che l’operatore ricorsivo associato f̂ abbia come minimo punto fisso una funzione totale g (e dunque sia unico). In tale caso Fix(f) è l’insieme degli indici di g, che non è r.e. per il teorema di Rice-Shapiro (dalla cui dimostrazione si ottiene anche una riduzione da \overline{K} che mostra che Fix(f) è produttivo).

1.6.2. È dato l’operatore

Ψ(f)(x, y, z) ≃ \{ \begin{matrix}y · y & se x = 0 \\ f(x − 1, y, z) + 1 & se x > 0 e z = 0 \\ f(x, y, z − 1) & se x > 0 e z > 0. \end{matrix}

Ψ (ristretto alle funzioni calcolabili) è un operatore ricorsivo? In caso negativo, mostrare che il suo minimo punto fisso non è calcolabile. In caso positivo, fornire un lambda-termine che lambda-definisce il minimo punto fisso di Ψ. Sol. Ψ è ricorsivo: segue dal teorema di Myhill-Shepherdson, dal momento che Ψ corrisponde ad un’operazione effettiva (in virtù della calcolabilità della definizione per casi ed il teorema s-m-n). Quanto al suo minimo punto fisso, si vede immediatamente che il terzo argomento della funzione Ψ(f) non è significativo (cioè non contribuisce al risultato). Il minimo punto fisso di Ψ può dunque essere espresso nel modo seguente, come si dimostra per induzione su x:

\begin{aligned}h(0, y, z) & ≃ & y · y \\ h(x + 1, y, z) & ≃ & h(x, y, z) + 1 \end{aligned}  (1)

ovvero

h(x, y, z) ≃ y^{2} + x.

Un termine che λ-definisce h è dunque

λxyz.\underline{+} (\underline{∗} y y)x

dove \underline{+} e \underline{∗} sono, rispettivamente, i λ-termini che definiscono somma e prodotto. Alternativamente (ma in modo assai più lungo…), osservando che la (1) è una definizione per ricorsione primitiva, si può usare il procedimento standard visto a lezione.

1.6.3. Per ogni naturale n, possiamo definire induttivamente il lambda-termine ⌈n⌉ come segue:

⌈0⌉ = λx.x ⌈n + 1⌉ = λx.x⌈n⌉

Dato ora il linguaggio

L = {a^{n}b^{m}c^{p} | ⌈0⌉⌈n⌉ =_{β} ⌈0⌉ ∨ (λx.x⌈0⌉)⌈m⌉ =_{β} (λx.λy.yx)⌈p⌉},

(a) si dia una definizione di L che non faccia riferimento al lambda-calcolo;

(b) si dimostri se L è regolare, libero, ovvero non libero da contesto.

Sol. (a) L = {a^{n}b^{m}c^{p} | n = 0 ∨ m = n + 2}.

(b) L è libero perché generato dalla grammatica

\begin{aligned}S & ::= & T | ARcc \\ T & ::= & bT | cT | ϵ \\ R & ::= & bRc | ϵ \\ A & ::= & a | aA \end{aligned}

L non è regolare, perché altrimenti lo sarebbe anche L^{R}. Sia N la costante per L^{R} di cui il pumping lemma asserisce l’esistenza e consideriamo la stringa z = c^{N}b^{N+2}a. In ogni scomposizione z = uvw con |uv| ≤ N si ha v = c^{k}, che non può essere pompata.

1.6.4. Teorema di ricorsione ed operatore di punto fisso L’operatore di punto fisso del λ-calcolo

Y = λf.(λx.f(xx))(λx.f(xx))

corrisponde in modo preciso alla dimostrazione del secondo teorema di ricorsione. Si ricordi che nel λ-calcolo non c’è distinzione tra programmi ed argomenti (non c’è enumerazione esplicita dei programmi): l’applicazione del programma x all’argomento y (che nel caso classico si dovrebbe intendere “del programma di indice x all’argomento y” e scrivere φ_{x}(y)) si denota semplicemente con xy. Ne segue che anche il teorema s-m-n diviene “banale”, corrispondendo a nient’altro che l’aggiunta di un λ: data un’espressione (λ-termine) P_{x,y} che dipende da x ed y, la “funzione s del teorema s-m-n” (che nel caso classico soddisfa la relazione φ_{s(x)}(y) ≃ P_{x,y}) corrisponde direttamente a S = λx.P_{x,y}. Infatti, per ogni x, Sx =_{β} P_{x,y}. La possibilità di non distinguere tra numeri come argomenti e numeri come indici di programmi, rende la costruzione di Y particolarmente semplice e mette in luce la presenza delle diagonalizzazioni (autoapplicazioni) nella dimostrazione del secondo teorema di ricorsione. Ripercorreremo dunque tale dimostrazione, costruendo nel contempo l’operatore Y.

Data f totale calcolabile,  f
si consideri l’autoapplicazione φ_{x}(x),  xx
e quindi la funzione s tale che φ_{s(x)} = φ_{f(φ_{x}(x))}; λx.f(xx)
detto e un indice di s, si consideri n = φ_{e}(e);  N ≡ (λx.f(xx))(λx.f(xx))
n è l’indice cercato: φ_{n} = φ_{f(n)}.  N soddisfa N =_{β} (fN)

Se adesso si astrae N rispetto ad f, si ottiene Y. Si osservi che quest’ultimo passaggio corrisponde ad un rafforzamento dell’usuale enunciato del teorema di ricorsione: l’indice n si ottiene in modo uniforme (cioè totale e calcolabile) da un indice per f. Nel λ-calcolo questa uniformità è espressa, in modo assai perspicuo, con una semplice λ-astrazione.

2 Linguaggi formali

2.0.1. È dato il linguaggio L = {0^{n}1^{n} | n ≥ 0}.

(a) Dire, dimostrando la risposta, se i seguenti linguaggi sono regolari: L_{0} = L(0 + 1)^{∗}L^{R} L_{1} = 0^{∗}L L_{2} = 1^{∗}L L_{3} = 11^{∗}L

(b) Determinare una grammatica libera G che generi L_{3}.

(c) Porre G in forma normale di Greibach.

Sol. L_{0} è regolare: L_{0} = (0 + 1)^{∗}, dal momento che ϵ ∈ L. Nessuno degli altri linguaggi è regolare. Per L_{1} e L_{2} si può usare il pumping lemma. Ad esempio, per L_{1}: sia N la costante di cui il lemma assicura l’esistenza e si consideri la stringa z = 0^{N}1^{N}; in ogni scomposizione z = uvw con |uv| ≤ N e |v| ≥ 1 si ha v = 0^{k}, con k ≥ 1; “pompando all’ingiù” v si ottiene la contraddizione: uv^{0}w = 0^{N−k}1^{k} ∉ L. Per L_{3} il pumping lemma non può essere applicato direttamente (perché?). Osserviamo, però, che le le stringhe 101, 1001, 10001,…, 10^{m}1, definiscono tutte classi di equivalenza diverse ripetto alla relazione indotta dal linguaggio (xRy sse per ogni z, [xz ∈ L sse yz ∈ L]). Siccome tali classi risultano infinite, il teorema di Myhill-Nerode ci assicura che L non è regolare. Alternativamente, la non regolarità si può stabilire usando un omomorfismo inverso. Si definisca f : {a, b, c}^{∗} → {0, 1}^{∗} con f(a) = 1, f(b) = 0 e f(c) = 1. Si ha L′ = f^{−1}(L_{3}) ∩ a^{∗}b^{∗}c^{∗} = {aa^{∗}b^{n}c^{n} | n ≥ 0}. Sostituiamo ora ad ogni a la stringa vuota: g(a) = ϵ, g(b) = 0, g(c) = 1. Si ha g(L′) = L. Siccome i linguaggi regolari sono chiusi per sostituzione, intersezione ed omomorfismi inversi, se L_{3} fosse regolare, lo sarebbe anche L.

2.0.2. Mostrare che, se L è un linguaggio regolare sull’alfabeto Σ, allora

L′ = {x | ∃y ∈ Σ^{∗}.yx ∈ L}

è regolare.

Sol. Ricordiamo che, se L è regolare, allora L^{R} è regolare e ragioniamo come segue:

(L′)^{R} = {x^{R} | ∃y ∈ Σ^{∗}.yx ∈ L}
= {x^{R} | ∃y ∈ Σ^{∗}.(yx)^{R} ∈ L^{R}}
= {x^{R} | ∃y ∈ Σ^{∗}.x^{R}y^{R} ∈ L^{R}}
= L^{R}/Σ^{∗}

Ne consegue che (L′)^{R} (e dunque L′) è regolare, perché quoziente di linguaggi regolari. In modo alternativo, si poteva costruire un automa M′ per L′ a partire da uno (M) per L (Idea: detto q_{0} lo stato iniziale di M, l’automa M′ deve avere un nuovo stato iniziale, con una ϵ-transizione verso q_{0} ed ogni altro stato di M raggiungibile da q_{0}).

2.0.3. Sia L il linguaggio accettato dall’automa seguente:

(a) Si determini L.

(b) Posto L_{1} = bb(a + b)^{∗}, si determini L/L_{1}. (c. Determinare un linguaggio libero non regolare L_{2} ⊆ L/L_{1}, giustificando tale risposta.

(d) Si dica se il linguaggio L_{3} = {www | w ∈ L/L_{1}} è regolare, libero, ovvero non libero da contesto.

Sol. (a) L = (b + ab)^{∗}aa(a + ba)^{∗}bb(a + b)^{∗}

(b) L/L_{1} = (b + ab)^{∗}aa(a + ba)^{∗}.

(c) Ad esempio {(ab)^{m}aa(ba)^{m} | m ≥ 0}, generato da S ::= aa | abSba, per dimostrare la non regolarità del quale si può usare il pumping lemma con la stringa (ab)^{N}aa(ba)^{N}.

2.0.4. Sia

L = {0^{n}1^{n} | n ≥ 0}.

Determinare i seguenti linguaggi:

L^{c}, L/L, L^{c}/L^{c}, L/L^{c}, L(L^{c})^{R}

dimostrando per ciascuno di essi se sia regolare, libero da contesto, ovvero non libero da contesto (L^{c} = Σ^{∗} − L, Σ = {0, 1}).

Sol.: L^{c} non è certo regolare, perché i regolari sono chiusi per complementazione e L è noto come non regolare. L^{c} = Σ^{∗}10Σ^{∗} ∪{0^{h}1^{k} | h ≠ k} e si tratta di un linguaggio libero, essendo generato dalla grammatica seguente:

S ::= R | 0Z | U1
Z ::= 0Z | P
U ::= U1 | P
P ::= 0P 1 | ϵ
R ::= produzioni per l’espressione regolare Σ^{∗}10Σ^{∗}.

L/L = L, libero non regolare. L^{c}/L^{c} = Σ^{∗}, regolare. L/L^{c} = {0^{h}1^{k} | h > k}, non regolare (pumping lemma, per esempio con stringa 0^{N}1^{N−1}, pompando all’insù), libero (grammatica analoga a quella di L^{c}, omettendo tutte le produzioni che nominano R ed U). L(L^{c})^{R} = Σ^{∗} − {1^{n}0^{n} | n ≥ 0}, equivalente ad L^{c}.

2.0.5. Fissato Σ = {a, b}, per ogni y ∈ Σ^{∗} si definisca

r(y) = (numero di a in y) − (numero di b in y).

Si studino i seguenti linguaggi:

L_{1} = {x ∈ Σ^{∗} | ∀y segmento iniziale di x, r(y) ≥ 0}
L_{2} = {x ∈ Σ^{∗} | ∀y segmento iniziale di x, 2 ≥ r(y) ≥ 0}
L_{3} = L_{1}/(L_{2}{ϵ}).

Sol. L_{1} non è regolare: se lo fosse, sia N la costante del pumping lemma e scegliamo z = a^{N}b^{N}. In ogni scomposizione z = uvw con |uv| ≤ N si ha uv = a^{k}. Essendo |v| ≥ 1, si ottiene uv^{0}w = a^{h}b^{N} con h < N, che non appartiene a L_{1}. L_{1} è libero: un semplice automa a pila che lo riconosce ha due stati q_{0} (iniziale e finale) e q_{1}. Da q_{0} si mette in pila A tutte le volte che si legge a e si toglie un A quando si legge b e sulla pila c’è almeno un A. Se si legge b e sulla pila vi è il solo simbolo di fine-pila, l’automa transita in q_{1} da cui cicla in q_{1} con qualsiasi input e qualsiasi carattere in pila.

L_{2} è regolare (automa non difficile).

L_{3} = L_{1}.

2.0.6. (a) Sia L un linguaggio regolare sull’alfabeto Σ. Stabilire se i seguenti linguaggi sono in generale regolari:

L_{1} = {xa |ax ∈ L},

L_{2} = {bx | ∃a ∈ Σ.ax ∈ L},

L_{3} = {xcy | |x| = |y| & cxy ∈ L} (c ∈ Σ carattere fissato).

(b) Si considerino gli insiemi A_{1} = {3k + 1 | k ≥ 0} ed A_{2} = {2k |≥ 0}. Siano L_{1} ed L_{2} i linguaggi definiti esprimendo gli elementi di A_{1} e A_{2}, rispettivamente, in base 3 (pertanto L_{1}, L_{2} ⊆ {0, 1, 2}^{∗}). Si stabilisca se L_{1} ed L_{2} sono liberi (Suggerimento per L_{2}: un numero espresso in base 3 è divisibile per 2 sse lo è la somma delle sue cifre).

2.0.7. (a) Stabilire se i seguenti linguaggi sull’alfabeto Σ = {0, 1} sono regolari o liberi.

• L_{1} = {x ∈ Σ^{∗} | il terz’ultimo carattere è 0};

• L_{2} = {x ∈ Σ^{∗} | il terz’ultimo carattere è 0 se |x| è pari};

• L_{3} = {x ∈ Σ^{∗} | ⌊|x|/2⌋-esimo elemento è 0};

• L_{4} = {xwx | x, w ∈ Σ^{∗} \ {ϵ}};

• L_{5} = {xwx^{R} | x, w ∈ Σ^{∗} \ {ϵ}};

• (L_{5})^{c}.

(b) Si determini un linguaggio infinito L′_{1} tale che per ogni linguaggio libero L′_{2} {xwx | x, w ∈ L′_{1}, w ∈ L′_{2}} è libero.

3 Semantica

3.0.1. Nel contesto del linguaggio IMP, si definisca la semantica denotazionale del nuovo comando wa b do c_{1} • c_{2} in modo che soddisfi la seguente relazione, per ogni b ∈ BExpr e c_{1}, c_{2} ∈ Com:

wa b do c_{1} • c_{2} ≈ if b then c_{1}; (wa b do c_{1} • c_{2}); c_{2} else skip

Si diano poi regole di semantica operazionale strutturata per lo stesso comando e si dimostri l’equivalenza delle due semantiche. Sol.

C[[wa b do c_{1} • c_{2}]] = fixH
H = λf.λs.COND(B[[b]]s, C[[c_{2}]](f(C[[c_{1}]]s)), s)

Le regole di semantica operazionale sono:

\frac{< b, s >→ true < c_{1}, s >→ s_{1} < wa b do c_{1} • c_{2}, s_{1} >→ s_{2} < c_{2}, s_{2} >→ s′}{< wa b do c_{1} • c_{2}, s >→ s′}

e

\frac{< b, s >→ false}{< wa b do c_{1} • c_{2}, s >→ s.}

L’equivalenza da dimostrare assume la forma seguente, per ogni c′ ∈ Com:

∀s ∈ Store < c′, s >→ s′ ⟺ C[[c′]]⌊s⌋ = ⌊s′⌋

L’implicazione da sinistra a destra si stabilisce per induzione sulla derivazione senza grossi problemi (il solo caso da mostrare è, ovviamente, quello relativo a wa). Da destra a sinistra l’implicazione si dimostra per induzione strutturale su c′. Nell’unico caso interessante, quando c′ è wa b do c_{1} • c_{2}, si procede con un’ulteriore induzione sugli approssimanti di fixH.

3.0.2. (a) Sia D un dominio puntato e sia f : D → D monotona. Si diano condizioni sufficienti affinché ∀t ∈ B_{⊥} e ∀x, y ∈ D

f(COND(t, x, y)) = COND(t, f(x), g(x)).

(b) Si consideri la seguente dichiarazione in REC:

h(x) = d_{1}
g(x) = d_{2}
p(x) = d_{3}

f(x, y) = if p(x) then y

else h(f(g(x), y))

dove d_{1}, d_{2} e d_{3} sono generici termini con F V (d_{i}) ⊆ {x}. Assumendo la semantica in call-by-value, si dimostri che, per ogni coppia di termini chiusi t_{1} e t_{2},

h(f(t_{1}, t_{2})) = f(t_{1}, h(t_{2})).

Cosa si può dire nel caso della semantica in call-by-name? Sol. (a). In generale si ha

f(COND(t, x, y)) ≥ COND(t, f(x), g(x))

L’uguaglianza si ottiene se f è stretta: f(⊥_{D}) = ⊥_{D}. (b). Si dimostra per induzione di punto fisso (il predicato è certo inclusivo per il teorema di Manna-Veuillemen), sfruttando il fatto dimostrato in (a). Nel caso del call-by-name, si dimostra la più debole h(f(t_{1}, t_{2})) ≥ f(t_{1}, h(t_{2})).

3.0.3. Si dimostri che, per ogni f, g funzioni continue tra gli opportuni c.p.o. puntati, vale

fix(f ∘ g) = f(fix(g ∘ f)).

Sol.: Dimostriamo per prima cosa che

fix(f ∘ g) ≤ f(fix(g ∘ f)).  (2)

A tale scopo basterà mostrare che il membro destro è un punto fisso di f ∘g: siccome fix(f ∘g) è il minimo punto fisso, si ottiene la disuguaglianza voluta. Dunque:

\begin{aligned}(f ∘ g)(f(fix(g ∘ f))) & = & f(g(f(fix(g ∘ f)))) \\ & = & f(fix(g ∘ f)). \end{aligned}

Per dimostrare l’altra disuguaglianza, cioè

fix(f ∘ g) ≥ f(fix(g ∘ f)),

osserviamo che questa, per definizione di punto fisso, può essere riscritta come

f(g(fix(f ∘ g))) ≥ f(fix(g ∘ f)),

che è implicata, per la monotonia di f, da

g(fix(f ∘ g)) ≥ fix(g ∘ f).

Quest’ultima, infine, non è che la (2), a meno dello scambio tra f e g.

3.0.4. Data la seguente definizione alternativa della semantica denotazionale del comando while di

IMP:

C′[[while b do c]] = (fixH)C[[c]]
H = λf ∈ [Store_{⊥} → Store_{⊥}] → [Store_{⊥} → Store_{⊥}].
λK ∈ [Store_{⊥} → Store_{⊥}].λs ∈ Store_{⊥}.
COND(B[[b]]s, fK(Ks), s),

si dimostri che per ogni b ∈ BExp ed ogni c ∈ Com si ha

C′[[while b do c]] = C[[while b do c]].

Sol. Detto G il funzionale il cui punto fisso costituisce la semantica standard di while:

G = λg ∈ [Store_{⊥} → Store_{⊥}]
λs ∈ Store_{⊥}.
COND(B[[b]]s, g(C[[c]]s), s),

e definito il predicato binario

P (f, g) ≡ ∀s ∈ Store_{⊥} fC[[c]]s = gs,

si chiede dunque di dimostrare che vale

P (fixH, fixG).

Trattandosi di un predicato inclusivo, possiamo stabilire la tesi per induzione di punto fisso rispetto ai due funzionali H e G. Base: P (⊥, ⊥) è ovvio. Passo: supponiamo che valga P (f, g); si ha

P (Hf, Gg) ≡ ∀s ∈ Store_{⊥}
COND(B[[b]]s, fC[[c]](C[[c]]s), s) = COND(B[[b]]s, g(C[[c]]s), s)
≡ ∀s ∈ Store_{⊥} fC[[c]](C[[c]]s) = g(C[[c]]s)
≡ true

dove l’ultima equivalenza si ottiene per ipotesi induttiva.

3.0.5. Nel contesto di IMP con errori aritmetici, si definisca la semantica denotazionale del comando stop in modo che soddisfi la seguente relazione, per ogni comando c_{1} e c_{2}:

c_{1}; stop ≈ c_{1}; stop; c_{2}  (1)

Si dimostri la (1) per la semantica data.

Sol.

C[[stop]] = \underline{λ}s.case s of

ER(s′).ER(s′) | OK(s′).ER(s′) end

Se C[[c_{1}]]s = ⊥ è facile vedere che membro sinistro e destro della (1) hanno entrambi valore ⊥. In caso contrario, per s = L(s′), con s′ ∈ Store e L ∈ {OK, ER}, si ha

C[[c_{1}; stop; c_{2}]]s = C[[c_{2}]](ER(s′)) = ER(s′) = C[[c_{1}; stop]]s

dove la seconda uguaglianza sfrutta una proprietà generale della semantica di IMP con errori:

∀s ∈ Store, C[[c]]ER(s) = ER(s).

3.0.6. Nel contesto del linguaggio IMP, si definisca la semantica denotazionale del nuovo comando wa b_{1} do b2 • c_{1}c_{2} in modo che soddisfi la seguente relazione, per ogni b_{1}, b_{2} ∈ BExpr e c_{1}, c_{2} ∈ Com:

wa b_{1} do b_{2} • c_{1}c_{2} ≈ if b_{1} then c_{1}; wa b_{1} do b_{2} • c_{1}c_{2} else if b_{2} then c_{2}; wa b_{1} do b_{2} • c_{1}c_{2} else skip

Si diano poi regole di semantica operazionale strutturata per lo stesso comando e si dimostri l’equivalenza delle due semantiche.

4 Prove d’esame

15 febbraio 1995, compitino: 1.5.1; 1.6.1; 1.6.2. 30 maggio 1995, compitino: 2.0.1; 2.0.2; 3.0.1. 6 giugno 1995, esame: 1.3.4; 1.6.3; 2.0.3; 3.0.2. 27 giugno 1995, esame: 1.5.3; 2.0.4; 3.0.3. 10 luglio 1995, esame: 1.5.4; 2.0.5; 3.0.4. 5 settembre 1995, esame: 1.5.5; 2.0.6; 3.0.5. 3 ottobre 1995, esame: 1.5.6; 2.0.7; 3.0.6.