• ••\begin{aligned}• \\ • & • \\ & • \end{aligned}

Testi delle prove scritte degli esami di Teoria degli Algoritmi e Calcolabilità

Appello del 1 giugno ’93 (sessione estiva)

1) Sia T una collezione di formule del prim’ordine. Mostrare che da ogni dimostrazione di

T ⊢ A ⊃ B

si può ottenere una dimostrazione di

T ⊢∼ B ⊃∼ A.

2) Dimostrare il teorema di deduzione: Sia T una teoria del prim’ordine nel linguaggio L, e siano A e B formule chiuse di L. Se T ∪ {A} ⊢ B, allora T ⊢ A ⊃ B.

3) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

1. la funzione che enumera i numeri primi in modo crescente;

2. la funzione n ↦ [| log_{2} n|] che associa ad un numero la parte intera del valore assoluto del logaritmo in base 2 del numero.

Giustificare le affermazioni (senza invocare la tesi di Church).

4) Dimostrare che P SP ACE è chiuso per complementare e quantificazione limitata da un polinomio, ovvero se L ⊂ Σ^{∗} è in P SP ACE e p(n) è un polinomio space-constructable allora anche i seguenti linguaggi sono in P SP ACE:

1. \overline{L} = \{x ∈ Σ^{∗}|x ∉ L\}

2. (E_{)}p(L) = {x ∈ Σ^{∗}|(Ey) ∈ Σ^{∗}.(|y| = p(|x|) ∧ ⟨x, y⟩ ∈ L)}

dove |x| è la lunghezza della stringa x, mentre ⟨ , ⟩: Σ^{∗}, Σ^{∗} → Σ^{∗} è una qualche codifica delle coppie calcolabile da un traduttore T (a due nastri di input) che lavora in tempo polinomiale.

Appello del 1 luglio ’93 (sessione estiva)

5) Si consideri la classe di complessità

EXP = ∪_{c,d>0}DT IME(d^{(n^{c})})

Dimostrare che se L_{1} ≤_{P} L_{2} e L_{2} ∈ EXP allora L_{1} ∈ EXP.

6) Dimostrare la forma semplice del teorema di equivalenza (ponendo molta attenzione nell’eventuale uso del teorema della tautologia): Sia A′ la formula ottenuta rimpiazzando un’occorrenza della formula B con B′ in A. Se ⊢ B ≡ B′, allora ⊢ A ≡ A′.

7) Dimostrare che

(Ex).(A ⊃ B) ⟹ ((x).A) ⊃ ((Ex).B)

in uno dei sistemi formali.

8) Siano A e B due strutture per il linguaggio L. Si consideri il prodotto diretto A × B definito come segue: l’insieme base è il prodotto |A| × |B| degli insiemi base, le operazioni sono definite puntualmente da

f_{A×B}((a_{1}, b_{1}), …, (a_{n}, b_{n})) = (f_{A}(a_{1}, …, a_{n}), f_{B}(b_{1}, …, b_{n}))

e le relazioni da

((a_{1}, b_{1}), …, (a_{n}, b_{n})) ∈ p_{A×B} se e solo se(a_{1}, …, a_{n}) ∈ p_{A} e (b_{1}, …, b_{n}) ∈ p_{B}.

Si dice che una formula X di L soddisfa la proprietà (P) se vale (P) ⊧_{A×B} X se e solo se ⊧_{A} X e ⊧_{A} X, Siano A, B formule atomiche chiuse del linguaggio L e C una formula atomica con sola variabile libera x; dire quali delle seguenti affermazioni sono vere e quali sono false:

1. A soddisfa la proprietà (P),

2. A ∧ B soddisfa la proprietà (P),

3. ∼ A soddisfa la proprietà (P),

4. A ⊃ B soddisfa la proprietà (P),

5. (x)C soddisfa la proprietà (P),

6. ∼ (x)C soddisfa la proprietà (P). Giustificare le risposte.

9) Un numero reale r è ricorsivo se esistono due funzioni ricorsive f e g tali che

||r| − \frac{f(n)}{g(n)}| ≤ \frac{1}{n}, per ogni naturale n.

Si dirà che f e g approssimano r. Verificare che, dati un numero reale r ed un numero naturale n_{0} ≠ 0, se r è ricorsivo e 0 ≤ r ≤ \frac{1}{n_{0}} , allora si può scegliere l’approssimazione in modo tale che

f(m) = 0, e g(m) = 1, per m = 0, …, n_{0}.

Dire poi se 1. la somma di due numeri reali ricorsivi positivi è un numero reale ricorsivo,

2. la somma di due numeri reali ricorsivi negativi è un numero reale ricorsivo,

3. la somma di due numeri reali ricorsivi in generale è un numero reale ricorsivo. Giustificare le risposte senza utilizzare la tesi di Church.

Appello del 28 luglio ’93 (sessione estiva)

10) Si mostri che i polinomi nelle funzioni di verità della disgiunzione H_{∨} e della negazione H_{∼} sono sufficienti per definire tutte le funzioni di verità e che quelli nella sola funzione H_{∨} non lo sono.

11) Data B una struttura per il linguaggio L e data A una sottostruttura di B—si rammenta che una

sottostruttura A di B consiste di un insieme base |A| ⊂ |B| e l’interpretazione di L in A è tale che

c^{A} = c^{B}  per ogni costante di L
f^{A} = f^{B}|_{|A|^{n}}  per ogni simbolo funzionale n-ario di L
p^{A} = p^{B} ∩ |A|^{m} per ogni predicato m-ario di L—,

(P) ⊧_{A} X se e solo se ⊧_{B} X,

si dice che una formula X di L soddisfa la proprietà (P) rispetto ad A e B se vale Siano A, B formule atomiche chiuse del linguaggio L e C una formula atomica con sola variabile libera x; si dica quali delle seguenti affermazioni sono vere per ogni scelta di struttura B e sua sottostruttura A, e quali no (esibendo in questi casi controesempi mediante scelte opportune di L, B, e A):

1. A ∧ B soddisfa la proprietà (P) rispetto ad A e B,

2. ∼ A soddisfa la proprietà (P) rispetto ad A e B,

3. (Ex)C soddisfa la proprietà (P) rispetto ad A e B,

4. (x)C soddisfa la proprietà (P) rispetto ad A e B.

Si giustifichino le risposte. (tempo: 50 minuti)

12) Si dica quali relazioni di inclusione valgono tra le seguenti coppie di classi di complessità e quali non valgono—in termini compatti, si dica quali relazioni ⊂ e quali relazioni ⊄ valgono per le coppie di classi seguenti:

• DSP ACE(n) e DSP ACE(n^{2})

• DT IME(n^{2}) e DT IME(T (n)), dove

T (n) = \{ \begin{matrix}n & se n è dispari \\ n^{3} & se n è pari \end{matrix}

• NSP ACE(n^{2}) e NSP ACE(n^{5})

Si giustifichino tutte le risposte, dando pure per scontato che le funzioni n, n^{2}, T (n) e n^{5} siano time- e space-constructable.

13) Si dice rappresentazione decimale di un numero reale r una coppia (z, ρ) che consiste di un numero

intero z e di una funzione

ρ: N → {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

tali che

z = [r] (cioè z ≤ r < z + 1)

e

(n) z + ∑_{k=0}^{n} \frac{ρ(k)}{10^{k+1}} ≤ r < z + ∑_{k=0}^{n} \frac{ρ(k)}{10^{k+1}} + \frac{1}{10^{n}} .

Si sa che ogni rappresentazione decimale non può mai terminare con tutti 9, cioè non può succedere che esista un n_{0} tale che

(n) > n_{0} ρ(k) = 9

e che ogni numero reale ha un’unica rappresentazione decimale. Si dice che la rappresentazione decimale (z, ρ) di un numero reale r è ricorsiva se la funzione ρ è ricorsiva. Siano r_{1} e r_{2} due numeri reali con rappresentazioni decimali ricorsive (z_{1}, ρ_{1}) e (z_{2}, ρ_{2}) rispettivamente. Si dica in quali dei seguenti casi la rappresentazione decimale della loro somma r_{1} + r_{2} è ricorsiva:

1. le immagini ρ_{1}[N], ρ_{2}[N] ⊂ {0, 1, 2, 3},

2. le immagini ρ_{1}[N], ρ_{2}[N] ⊂ {0, 1, 2, 3, 4, 5},

3. (n) ∈ N ρ_{1}(10n) = 0 = ρ_{2}(10n).

Che cosa si può dire se le funzioni ρ_{1}, ρ_{2} sono ricorsive primitive? Si diano giustificazioni che non usano la tesi di Church. (tempo: 70 minuti)

Appello del 23 settembre ’93 (sessione estiva)

14) Si mostri che le funzioni numeriche u e v definite da

u: n ↦ \{ \begin{matrix}1 & se n = 0 \\ 0 & altrimenti \end{matrix} v: ⟨n, m⟩ ↦ \{ \begin{matrix}0 & se n = 0 oppure m = 0 \\ 1 & altrimenti \end{matrix}

sono ricorsive esibendo definizioni esplicite a partire dalle funzioni elementari mediante composizione, (accoppiamento,) e μ-operatore. Si deduca dunque che le funzioni di verità (sui valori 0 e 1) sono ricorsive. Si dica se u e v sono ricorsive primitive motivando le risposte. (tempo: 45 minuti)

15) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

16) Si consideri il linguaggio L con i seguenti simboli extralogici: un simbolo funzionale ∘ binario ed una costante ε. Sia T la teoria in L con assiomi

(x)(y)(z)(x ∘ (y ∘ z)) = ((x ∘ y) ∘ z)
(x)(x ∘ ε = x)
(x)(ε ∘ x = x)
(x)(y)(z)(x ∘ y = x ∘ z ⊃ y = z).

dato un insieme A, si consideri l’insieme

A^{∗} = ⋃_{n∈N} A^{n}

delle stringhe su A.

1. Si verifichi che la struttura M_{A} = (A^{∗}, ·, []), dove · è l’operazione di concatenazione di stringhe e [] è la stringa vuota, è modello di T.

2. Sia A = {a, b} con a ≠ b. Si mostri che se α è una stringa su A tale che

a · α = α · a,

allora α = \underbrace{a · . . . · a}_{k volte} per un opportuno k.

3. Sia A = {a, b} con a ≠ b. Date α e β stringhe su A si scriva CL(α, β) per la condizione

α · β = β · α e len(α) < len(β).

Si dica per ciascuna delle seguenti condizioni se essa comporta CL(α, β) oppure se è conseguenza di CL(α, β) (oppure non è correlata):

(a) α = [],

(d) α = \underbrace{γ · . . . · γ}_{h volte} e β = \underbrace{γ · . . . · γ}_{k volte}, per opportuni h e k,

(b) β = \underbrace{α · . . . · α}_{k volte} per un opportuno k, (e) α = β · γ · β oppure β = α · γ · α per un opportuna stringa γ.

Si diano almeno traccie della giustificazioni.

4. (Facoltativo) Si provi che non può esistere un’immersione dalla struttura prodotto M_{{a}} × M_{{b}} nella struttura M_{{a,b}}.

(tempo: 80 minuti)

17) Si definisca una nuova misura di complessita’ tempo per le NDTM (macchine di Turing nondeterministica) ed una classe di complessita’ ANP ad essa correlata come segue:

• M e’ accept time-bounded da T (n) se per ogni w ∈ Σ^{∗} tutte le computazioni di M che \underline{accettano} w terminano in al piu’ T (|w|)

• L ∈ ANP se esiste una NDTM M ed un polinomio T (n) t.c. L = L_{M} e M e’ accept time-bounded da T (n).

Dimostrare che ANP = NP.

Appello del 25 ottobre ’93 (sessione autunnale)

18) Si formalizzi il paradosso del barbiere. Più precisamente, si consideri la seguente affermazione:

(A) un barbiere di Agicol rade tutti e soli quegli uomini che non si radono da soli.

Si prenda il linguaggio L formato da due simboli relazionali B unario (da intendere come “… è un barbiere di Agicol”, Agicol è un paese di fantasia) ed R binario (da intendere “… rade … ”). Si formalizzi l’affermazione (A) con una formula del linguaggio L, e si dica poi quanti barbieri ci sono ad Agicol producendo una dimostrazione formale della risposta.

19) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

20) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

1. la funzione n ↦ [\sqrt{n}] che associa ad un numero la parte intera della radice del numero dato.

2. la funzione che associa ad un numero n i numeri primi minori od uguali ad n;

Giustificare le affermazioni (senza invocare la tesi di Church).

21) Si ricorda che Con è il linguaggio i cui elementi codificano/sono terne (G, s, t) dove G = (V, E) è un grafo diretto e s, t ∈ V sono tali che esiste un cammino da s a t in G. Sia 3.Con il linguaggio i cui elementi codificano/sono quadruple (G, s, u, t) dove G = (V, E) è un grafo diretto e s, u, t ∈ V sono tali che esistono un cammino da s a u ed uno da u a t. Si dia una riduzione log-space di 3.Con a Con.

Appello del 22 dicembre ’93 (sessione autunnale)

22) Sia L un linguaggio che consiste di un unico simbolo relazionale binario R. Si dica se la formula

((x)(Ey)R(x, y)) ⊃ ((Ey)(x)R(x, y))

vale in qualche modello del linguaggio, e si stabilisca se è valida.

23) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

24) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

1. la funzione che enumera in ordine crescente i multipli del numero 15;

2. la funzione che enumera in ordine crescente i numeri che non sono multipli di 15;

3. la funzione n ↦ [n · 7/15] che associa ad un numero la parte intera della moltiplicazione di n con 7/15.

Dire inoltre quali sono ricorsive primitive. Giustificare le affermazioni (senza invocare la tesi di Church).

25) Dimostrare che la relazione di riducibilità ≤_{L} è transitiva.

(tempo: 50 minuti)

Appello del 23 febbraio ’94 (sessione straordinaria)

26) Dimostrare che NLOG è propriamente contenuto in P SP ACE.

27) Si enunci e dimostri un teorema sulle funzioni ricorsive.

28) Si consideri il linguaggio L che consiste di di un simbolo funzionale binario f e di un simbolo funzionale unario g. Sia A = {a, b} un insieme fissato con due elementi.

1. Si consideri la struttura A = (A, f, g) per L definita sull’universo A dove f e g sono date della tavole di definizione

\begin{matrix}f & a & b \\ a & a & a \\ b & a & b \end{matrix}  \begin{aligned}& g \\ a & & b \\ b & & a. \end{aligned}

Dire se esiste un isomorfismo di strutture da A alla struttura definita sull’insieme dei valori di verità {T, F} con f interpretato dalla funzione congiunzione e g interpretato dalla funzione negazione.

2. Dire se esiste un isomorfismo di strutture da A alla struttura definita sull’insieme dei valori di verità {T, F} con f interpretato dalla funzione disgiunzione e g interpretato dalla funzione negazione.

3. Provare che per ogni numero naturale n ogni funzione h: A^{n} A è l’interpretazione di un termine del linguaggio L nella struttura A.

4. Si consideri la struttura A′ = (A, f′, g′) per L definita sull’universo A dove f′ e g′ sono date della tavole di definizione

\begin{matrix}f′ & a & b \\ a & a & b \\ b & b & a \end{matrix}  \begin{aligned}& g′ \\ a & & b \\ b & & a. \end{aligned}

Dire se esiste un isomorfismo di strutture da A′ alla struttura definita sull’insieme dei valori di verità {T, F} con f′ interpretato dalla funzione equivalenza e g′ interpretato dalla funzione negazione.

5. Dire se per ogni numero naturale n ogni funzione h: A^{n} A è l’interpretazione di un termine del linguaggio L nella struttura A′.

Giustificare le affermazioni. (tempo: 70 minuti)

29) Sia L un linguaggio con due simboli relazionali unari A, B. Dire se le seguenti formule sono teoremi della teoria vuota sul linguaggio L:

1. (Ex)(Ax ⊃ Bx) ⊃ ((x) Ax ⊃ (Ex) Bx),

2. ((x) Ax ⊃ (Ex) Bx) ⊃ (Ex)(Ax ⊃ Bx),

3. (x)(Ax ∨ Bx) ⊃ ((x) Ax ∨ (x) Bx).

Giustificare le affermazioni. (tempo: 50 minuti)

Appello del 8 giugno ’94 (sessione estiva)

30) Per formule ben formate A, B, C, si considerino le formule

\begin{matrix}(A ∨ B) ∧ ((A ⊃ C) ∧ (B ⊃ C)) ⊃ C \\ (A ⊃ (B ⊃ C)) ⟺ ((A ∧ B) ⊃ C). \end{matrix}

Si provi che queste sono tautologie, ed anche teoremi (possibilmente producendo dimostrazioni dirette dagli assiomi).

31) Si enunci e si dimostri un teorema sulla logica del prim’ordine.

32) Siano P l’insieme delle funzioni ricorsive parziali in una variabile naturale, R l’insieme delle funzioni ricorsive totali in una variabile naturale (dunque R ⊂ P). Sia θ: N → P una funzione. Si considerino le seguenti affermazioni:

(α) im θ ⊂ R,

(β) R ⊂ im θ,

(γ) (n, m) ↦ θ(n)(m): N → N è ricorsiva parziale.

Dire quali coppie di affermazioni possono essere contemporaneamente soddisfatte producendo un’opportuna scelta di θ. Dire inoltre per quali di queste coppie si ha che quando queste sono soddisfatte, allora la terza rimanente non può esserlo.

33) Sia Log^{2} = DSpace((log n)^{2}). Dire in che relazione sta Log^{2} rispetto a Log, NLog e P Space? Dire inoltre se Log^{2} e’ chiuso rispetto a ≤_{L} (cioe’ se L ≤_{L} L′ ∈ Log^{2} comporta L ∈ Log^{2}). Giustificare le affermazioni.

Appello del 20 luglio ’94 (sessione estiva)

34) Sia A una formula ben formata nel linguaggio L. Sia M un’interpretazione per L. Si provi che le seguenti formule sono vere in M

\begin{matrix}A ⊃ (Ex)_{1}A \\ (x)_{1}A ⊃ (Ex)_{1}A. \end{matrix}

35) Si enunci e si dimostri un teorema sulle funzioni ricorsive.

36) Siano e: {V, F }^{2} → {V, F } ed i: {V, F } → {V, F } le funzioni di verità con le seguenti tabelle:

\begin{matrix}e & V & F \\ V & V & F \\ F & F & V \end{matrix}  \begin{aligned}& i \\ V & & F \\ F & & V. \end{aligned}

Si consideri l’insieme F delle funzioni di verità definito come segue:

1. e ed i sono in F,

2. le proiezioni π_{i}^{n}: {V, F }^{n} → {V, F }: (α_{1}, …, α_{n}) ↦ α_{i} sono in F (per ogni n ed i ≤ n),

3. se f, g_{1}, …, g_{n} sono in F (e sono di opportuna arietà), allora f ∘ ⟨g_{1}, … g_{n}⟩ è in F.

Per f: {V, F }^{n} → {V, F } sia A_{f} l’insieme {(α_{1}, …, α_{n}) | f(α_{1}, …, α_{n}) = V } ⊂ {V, F }^{n}. Sia δ_{n}: {V, F } → {V, F }^{n}: α ↦ (α, …, α) la diagonale. Si dica per quali n si può affermare ciascuna delle seguenti affermazioni:

(α) ogni f: {V, F }^{n} → {V, F } in F è tale che f ∘ δ_{n} è costante,

(β) per ogni f: {V, F }^{n} → {V, F } in F si ha che la cardinalità di A_{f} è pari,

giustificando entrambe le affermazioni.

37) Sia IndSet il linguaggio che codifica le coppie (G, k), dove G e k sono un grafo ed un numero naturale rispettivamente, tali che esiste un insieme indipendente U di nodi di G con |U| = k. Si dice che U è indipendente se (n), n′ ∈ U.(n, n′) ∉ G. Si dia una riduzione di Clique ad IndSet, giustificando la scelta.

Appello del 28 settembre ’94 (sessione estiva)

38) Siano A e B formule ben formate nel linguaggio L. Si dimostri che la formula

((A ⊃ B) ⊃ B) ⊃ B

è una tautologia, ed anche un teorema (possibilmente producendo una dimostrazione diretta dagli assiomi).

39) Si enunci e si dimostri un teorema sulla logica formale.

40) Siano f, g: N × N N due funzioni ricorsive. Si consideri la funzione

∑<f/g: (x, y) ↦ [_{∑i<x} \frac{f(i, y)}{g(i, y)}]

che prende la parte intera della sommatoria dei quozienti indicati. Dire quando la funzione ∑_{<} f/g è ricorsiva giustificando la scelta. Se ne può dedurre informazioni circa la ricorsività della funzione

x ↦ [sin x]: N N?

E della funzione che associa ad ogni numero naturale x la prima cifra decimale nell’espansione di sin x? Si cerchi di giustificare le affermazioni.

41) Si dica che L ∈ NT IME′(f) se esiste una NDTM M tale che L = L(M) e per ogni w ∈ L esiste una computazione di M con input w accettante e con un numero di passi ≤ f(|w|). E’ facile vedere che NT IME(f) ⊆ NT IME′(f), perchè? Sotto quale ipotesi su f si ha che NT IME(f) = NT IME′(f)? Giustificare le affermazioni.

Appello del 1 gennaio ’95 (sessione autunnale)

42) Sia f: N N una funzione ricorsiva strettamente crescente. Si mostri che esiste una funzione

ricorsiva g: N N tale che

g ∘ f = id_{N} .

Si veda poi se il procedimento usato si può applicare per mostrare che la funzioine

g(n) = [log n]

è ricorsiva.

43) Si dimostri un teorema di logica formale.

44) Sia L un linguaggio e siano A e B interpretazioni di L. Si dice che B è sottostruttura di A se (i) |B| ⊂ |A (ii) c^{B} = c^{A} per ogni costante di L (iii) f^{A}(x_{1}, …, x_{n}) = f^{B}(x_{1}, …, x_{n}) per ogni (x_{1}, …, x_{n}) ∈ |B|^{n} e per ogni simbolo funzionale

f in L (iv) (x_{1}, …, x_{n}) ∈ R^{B} \underline{se e solo se} (x_{1}, …, x_{n}) ∈ R^{A} per ogni (x_{1}, …, x_{n}) ∈ |B|^{n} e per ogni

simbolo relazionale R in L. Data una formula chiusa X si considerino le affermazioni (α_{X}) se vale X in A, allora X vale in B, (β_{X}) se vale X in B, allora X vale in A. Si dica per quali delle seguenti formule vale (α_{X}) o (β_{X}):

(i) X è (x)A, (ii) X è (Ex)A, (iii) X è atomica, (iv) X è congiunzione di due formule che valgono in A,

(v) X è congiunzione di due formule che valgono in B. Giustificare le affermazioni.

45) Si consideri la definizione della classe complessità spazio

DSP ACE(f) = {L ∈ Σ^{∗}| esiste una DTM offline M space-bounded da f eL = L(M)} dove nella definzione di space-bounded si considerano solo celle usate sui nastri di lavoro (non su quello di input). Dire

1. che cosa succede se si toglie la restrizione che M sia offline,

2. che cosa può succedere se nella definzione di space-bounded si conisderano anche le celle usate sul nastro di input.

Appello del 24 febbraio ’95 (sessione straordinaria)

46) Dire se la relazione di riducibilità ≤_{P} è transitiva giustificando l’affermazione.

47) Si dimostri un teorema sulle funzioni ricorsive.

48) Sia L un linguaggio del prim’ordine e siano A e B interpretazioni di L. Sia poi f: A B un L-omomorfismo tale che f: |A| |B| sia suriettivo. Si dica per quali delle seguenti formule ben formate chiuse si può affermare che la validità in A assicura la validità in B:

(i) A atomica,

(ii) ∼ B, dove B non è vera in A,

(iii) ∼ C, dove C è qualunque,

(iv) D ∧ E

49) Si verifichi che la formula

((A ⊃ B) ⊃ B) ⊃ A

non è una tautologia nè una contraddizione. Si diano sostituzioni delle formule A e B che producono una tautologia ed una contraddizione rispettivamente. Giustificare le affermazioni.

Appello del 7 giugno ’95 (sessione estiva)

50) Si consideri l’insieme

L = {(V, E, a, b) | (V, E) è un grafo, a, b ∈ V, ed esiste un cammino in (V, E) da a a b }

Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore per la sua complessità, a scelta tempo o spazio, deterministica o nondeterministica.

51) Si enunci e si dimostri un teorema di teoria della complessità.

52) Si consideri l’alfabeto logico con simboli funzionali e costanti {s, z}, simboli relazionali {=, <} (il primo è il simbolo per la relazione di uguaglianza), l’arietà è tabulata come segue

\begin{matrix}s ↦ & 1 \\ z ↦ & 0 \\ =↦ & 2 \\ <↦ & 2 \end{matrix}

e le seguenti formule:

(x)(s(x) ≠ z)  (x)(y)(s(x) = s(y) ⊃ x = y)
(x)(x ≠ z ⊃ (Ey)(s(y) = x))  (x)(x < s(x))
(x)(y)(x < y ⊃ s(x) < s(y))  (Ex)(s(x) = z)
(Ex)(s(x) = x)  (Ex)(x < s(x))
(x)(y)(z)(x < y ∧ y < z ⊃ x < z)

Si dica quali sono gli insiemi massimali coerenti di formule dalla lista data sopra giustificando le affermazioni. Si determinino poi tutti gli insiemi coerenti dalla lista.

53) Si verifichi che

((∼ a) ⟺ b) ⟺ (∼ (a ⟺ b))

è una tautologia. Si dimostri quindi che i connettivi ∼ e ⟺ non sono adeguati. Si può adattare il metodo di dimostrazione usato per mostrare che ∼ e ⊃ non sono adeguati?

Appello del 12 luglio ’95 (sessione estiva)

54) Si consideri l’insieme

L = {(V, E, a, b) | (V, E) è un grafo, a, b ∈ V, ed esiste un cammino in (V, E) da a a b }

Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore ed una inferiore per la sua complessità, tempo o spazio, che sia deterministica o non-deterministica.

55) Si enunci e si dimostri un teorema di teoria della complessità.

56) Si introduce false < true sull’insieme {true, false}. Poi si dice che una funzione booleana f: {true, false}^{n} {true, false} è monotona se

f(x_{1}, …, x_{n}) ≤ f(y_{1}, …, y_{n})

ogni volta che x_{1} ≤ y_{1},…,x_{n} ≤ y_{n}. Ad esempio, la funzione booleana a due argomenti determinata dalla congiunzione è monotona. Si dica se i connettivi ∧ e ∨ sono sufficienti per esprimere

(α) tutte le funzioni booleane monotone,

(β) tutte le funzioni booleane,

giustificando le risposte.

57) Sia N il modello standard della teoria dei numeri. Si consideri l’interpretazione del linguaggio L della teoria dei numeri nel “prodotto” N × N: l’universo è l’insieme prodotto degli universi N × N, l’interpretazione è quella “coordinata per coordinata”. Ad esempio, l’interpretazione del simbolo + è

+^{N×N}((n_{1}, n_{2}), (m_{1}, m_{2})) = (n_{1} +^{N} m_{1}, n_{2} +^{N} m_{2}),

quella della costante 0 è

0^{N×N} = (0^{N}, 0^{N})

e così via per gli altri simboli e relazioni. Si noti in particolare che la definizioine coordinata per coordinata della relazione = è proprio la diagonale di N ×N—un sottoinsieme di (N×N)×(N×N). Si dica quali assiomi della teoria dei numeri non valgono in N × N giustificando le affermazioni. Appello del 28 settembre ’95 (sessione estiva)

58) Sia A un insieme finito, e si consideri l’insieme L di coppie di liste x e y di elementi di A tali che una sia ottenuta dall’altra permutando alcuni elementi. Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore ed una inferiore per la sua complessità, tempo o spazio, che sia deterministica o non-deterministica.

59) Si enunci e si dimostri un teorema di teoria della complessità.

60) Sia T una teoria del prim’ordine. Si dice che una formula A è negata pura se essa è dimostrabilmente equivalente ad una della forma ∼ P dove P (in forma abbreviata) contiene soltanto i connettivi ∧ e ∨ ed il quantificatore esistenziale. Si dica per quali operazioni logiche la classe delle formule negate pure è sicuramente chiusa, e per quali invece non è detto che lo sia. Si consideri poi il caso particolare della teoria T dell’ordine parziale: consiste di due simboli relazionali binari = e ≤ ed ha come assiomi quelli per l’uguaglianza ed i seguenti:

(x)x ≤ x
(x)(y)(x ≤ y ∧ y ≤ x) ⊃ x = y
(x)(y)(z)(x ≤ y ∧ y ≤ z) ⊃ x ≤ z.

Si dica se la formula (x)(y)(x ≤ y ∨ y ≤ x), che esprime il fatto che l’ordine è totale, è negata pura. In caso positivo, si accenni la dimostrazione formale; in caso negativo si proponga come estendere la teoria in modo che lo diventi.

61) Si consideri il linguaggio dei numeri naturali, e si consideri il modello standard su N. Si prenda ora l’insieme N_{1} = N ∪ (Z × {∞}) dove il carattere ∞ viene usato per avere i due addendi sicuramente disgiunti. Si estenda l’interpretazione standard su N per il linguaggio dei numeri naturali all’insieme N_{1} in modo che da mantenere verificati il maggior numero di assiomi della teoria dei numeri. (L’interpretazione del simbolo = deve essere quella canonica, cioè la diagonale di N_{1}.)

• ••\begin{aligned}• \\ • & • \\ & • \end{aligned}

Testi delle prove scritte degli esami di Teoria degli Algoritmi e Calcolabilità

Appello del 1 giugno ’93 (sessione estiva)

1) Sia T una collezione di formule del prim’ordine. Mostrare che da ogni dimostrazione di

T ⊢ A ⇒ B

si può ottenere una dimostrazione di

T ⊢ ¬B ⇒ ¬A.

2) Dimostrare il teorema di deduzione: Sia T una teoria del prim’ordine nel linguaggio L, e siano A e B formule chiuse di L. Se T ∪ {A} ⊢ B, allora T ⊢ A ⇒ B.

3) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

(α) la funzione che enumera i numeri primi in modo crescente;

(β) la funzione n ↦ [| log_{2} n|] che associa ad un numero la parte intera del valore assoluto del logaritmo in base 2 del numero.

Giustificare le affermazioni (senza invocare la tesi di Church).

4) Dimostrare che P SP ACE è chiuso per complementare e quantificazione limitata da un polinomio, ovvero se L ⊂ Σ^{∗} è in P SP ACE e p(n) è un polinomio space-constructable allora anche i seguenti linguaggi sono in P SP ACE:

(α) \overline{L} = \{x ∈ Σ^{∗}|x ∉ L\}

(β) ∃_{p}(L) = {x ∈ Σ^{∗}|∃y ∈ Σ^{∗}.(|y| = p(|x|) ∧ ⟨x, y⟩ ∈ L)}

dove |x| è la lunghezza della stringa x, mentre ⟨ , ⟩: Σ^{∗}, Σ^{∗} → Σ^{∗} è una qualche codifica delle coppie calcolabile da un traduttore T (a due nastri di input) che lavora in tempo polinomiale.

Appello del 1 luglio ’93 (sessione estiva)

5) Si consideri la classe di complessità

EXP = ∪_{c,d>0}DT IME(d^{(n^{c})})

Dimostrare che se L_{1} ≤_{P} L_{2} e L_{2} ∈ EXP allora L_{1} ∈ EXP.

6) Dimostrare la forma semplice del teorema di equivalenza (ponendo molta attenzione nell’eventuale uso del teorema della tautologia): Sia A′ la formula ottenuta rimpiazzando un’occorrenza della formula B con B′ in A. Se ⊢ B ≡ B′, allora ⊢ A ≡ A′.

7) Dimostrare che

∃x.(A ⇒ B) ⟹ (∀x.A) ⇒ (∃x.B)

in uno dei sistemi formali.

8) Siano A e B due strutture per il linguaggio L. Si consideri il prodotto diretto A × B definito come segue: l’insieme base è il prodotto |A| × |B| degli insiemi base, le operazioni sono definite puntualmente da

f_{A×B}((a_{1}, b_{1}), …, (a_{n}, b_{n})) = (f_{A}(a_{1}, …, a_{n}), f_{B}(b_{1}, …, b_{n}))

e le relazioni da

((a_{1}, b_{1}), …, (a_{n}, b_{n})) ∈ p_{A×B} se e solo se(a_{1}, …, a_{n}) ∈ p_{A} e (b_{1}, …, b_{n}) ∈ p_{B}.

Si dice che una formula X di L soddisfa la proprietà (P) se vale (P) ⊧_{A×B} X se e solo se ⊧_{A} X e ⊧_{A} X, Siano A, B formule atomiche chiuse del linguaggio L e C una formula atomica con sola variabile libera x; dire quali delle seguenti affermazioni sono vere e quali sono false: (α) A soddisfa la proprietà (P), (β) A ∧ B soddisfa la proprietà (P), (γ) ¬A soddisfa la proprietà (P), (δ) A ⇒ B soddisfa la proprietà (P), (ϵ) ∀xC soddisfa la proprietà (P), (ζ) ¬∀xC soddisfa la proprietà (P). Giustificare le risposte.

9) Un numero reale r è ricorsivo se esistono due funzioni ricorsive f e g tali che

||r| − \frac{f(n)}{g(n)}| ≤ \frac{1}{n}, per ogni naturale n.

Si dirà che f e g approssimano r. Verificare che, dati un numero reale r ed un numero naturale n_{0} ≠ 0, se r è ricorsivo e 0 ≤ r ≤ \frac{1}{n_{0}} , allora si può scegliere l’approssimazione in modo tale che

f(m) = 0, e g(m) = 1, per m = 0, …, n_{0}.

Dire poi se (α) la somma di due numeri reali ricorsivi positivi è un numero reale ricorsivo, (β) la somma di due numeri reali ricorsivi negativi è un numero reale ricorsivo, (γ) la somma di due numeri reali ricorsivi in generale è un numero reale ricorsivo. Giustificare le risposte senza utilizzare la tesi di Church.

Appello del 28 luglio ’93 (sessione estiva)

10) Si mostri che i polinomi nelle funzioni di verità della disgiunzione H_{∨} e della negazione H_{¬} sono sufficienti per definire tutte le funzioni di verità e che quelli nella sola funzione H_{∨} non lo sono.

11) Data B una struttura per il linguaggio L e data A una sottostruttura di B—si rammenta che una

sottostruttura A di B consiste di un insieme base |A| ⊂ |B| e l’interpretazione di L in A è tale che

c^{A} = c^{B}  per ogni costante di L
f^{A} = f^{B}|_{|A|^{n}}  per ogni simbolo funzionale n-ario di L
p^{A} = p^{B} ∩ |A|^{m} per ogni predicato m-ario di L—,

si dice che una formula X di L soddisfa la proprietà (P) rispetto ad A e B se vale Siano A, B formule atomiche chiuse del linguaggio L e C una formula atomica con sola variabile libera x; si dica quali delle seguenti affermazioni sono vere per ogni scelta di struttura B e sua sottostruttura A, e quali no (esibendo in questi casi controesempi mediante scelte opportune di L, B, e A):

(α) A ∧ B soddisfa la proprietà (P) rispetto ad A e B,

(β) ¬A soddisfa la proprietà (P) rispetto ad A e B,

(γ) ∃xC soddisfa la proprietà (P) rispetto ad A e B,

(δ) ∀xC soddisfa la proprietà (P) rispetto ad A e B.

Si giustifichino le risposte. (tempo: 50 minuti)

12) Si dica quali relazioni di inclusione valgono tra le seguenti coppie di classi di complessità e quali non valgono—in termini compatti, si dica quali relazioni ⊂ e quali relazioni ⊄ valgono per le coppie di classi seguenti:

• DSP ACE(n) e DSP ACE(n^{2})

• DT IME(n^{2}) e DT IME(T (n)), dove

T (n) = \{ \begin{matrix}n & se n è dispari \\ n^{3} & se n è pari \end{matrix}

• NSP ACE(n^{2}) e NSP ACE(n^{5})

Si giustifichino tutte le risposte, dando pure per scontato che le funzioni n, n^{2}, T (n) e n^{5} siano time- e space-constructable.

13) Si dice rappresentazione decimale di un numero reale r una coppia (z, ρ) che consiste di un numero

intero z e di una funzione

ρ: N → {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

tali che

z = [r] (cioè z ≤ r < z + 1)

e

∀n z + ∑_{k=0}^{n} \frac{ρ(k)}{10^{k+1}} ≤ r < z + ∑_{k=0}^{n} \frac{ρ(k)}{10^{k+1}} + \frac{1}{10^{n}} .

Si sa che ogni rappresentazione decimale non può mai terminare con tutti 9, cioè non può succedere che esista un n_{0} tale che

∀n > n_{0} ρ(k) = 9

e che ogni numero reale ha un’unica rappresentazione decimale. Si dice che la rappresentazione decimale (z, ρ) di un numero reale r è ricorsiva se la funzione ρ è ricorsiva. Siano r_{1} e r_{2} due numeri reali con rappresentazioni decimali ricorsive (z_{1}, ρ_{1}) e (z_{2}, ρ_{2}) rispettivamente. Si dica in quali dei seguenti casi la rappresentazione decimale della loro somma r_{1} + r_{2} è ricorsiva:

(α) le immagini ρ_{1}[N], ρ_{2}[N] ⊂ {0, 1, 2, 3},

(β) le immagini ρ_{1}[N], ρ_{2}[N] ⊂ {0, 1, 2, 3, 4, 5},

(γ) ∀n ∈ N ρ_{1}(10n) = 0 = ρ_{2}(10n).

Che cosa si può dire se le funzioni ρ_{1}, ρ_{2} sono ricorsive primitive? Si diano giustificazioni che non usano la tesi di Church. (tempo: 70 minuti)

Appello del 23 settembre ’93 (sessione estiva)

14) Si mostri che le funzioni numeriche u e v definite da

u: n ↦ \{ \begin{matrix}1 & se n = 0 \\ 0 & altrimenti \end{matrix} v: ⟨n, m⟩ ↦ \{ \begin{matrix}0 & se n = 0 oppure m = 0 \\ 1 & altrimenti \end{matrix}

sono ricorsive esibendo definizioni esplicite a partire dalle funzioni elementari mediante composizione, (accoppiamento,) e μ-operatore. Si deduca dunque che le funzioni di verità (sui valori 0 e 1) sono ricorsive. Si dica se u e v sono ricorsive primitive motivando le risposte. (tempo: 45 minuti)

15) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

16) Si consideri il linguaggio L con i seguenti simboli extralogici: un simbolo funzionale ∘ binario ed una costante ε. Sia T la teoria in L con assiomi

∀x∀y∀z(x ∘ (y ∘ z)) = ((x ∘ y) ∘ z)
∀x(x ∘ ε = x)
∀x(ε ∘ x = x)
∀x∀y∀z(x ∘ y = x ∘ z ⇒ y = z).

dato un insieme A, si consideri l’insieme

A^{∗} = ⋃_{n∈N} A^{n}

delle stringhe su A.

(α) Si verifichi che la struttura M_{A} = (A^{∗}, ·, []), dove · è l’operazione di concatenazione di stringhe e [] è la stringa vuota, è modello di T.

(β) Sia A = {a, b} con a ≠ b. Si mostri che se α è una stringa su A tale che

a · α = α · a,
allora α = \underbrace{a · . . . · a}_{k volte} per un opportuno k.

(γ) Sia A = {a, b} con a ≠ b. Date α e β stringhe su A si scriva CL(α, β) per la condizione

α · β = β · α e len(α) < len(β).

Si dica per ciascuna delle seguenti condizioni se essa comporta CL(α, β) oppure se è conseguenza di CL(α, β) (oppure non è correlata):

(a) α = [],

(b) β = \underbrace{α · . . . · α}_{k volte} per un opportuno k, (e) α = β · γ · β oppure β = α · γ · α per un opportuna stringa γ.

Si diano almeno traccie della giustificazioni.

(δ) (Facoltativo) Si provi che non può esistere un’immersione dalla struttura prodotto M_{{a}} × M_{{b}} nella struttura M_{{a,b}}.

(tempo: 80 minuti)

17) Si definisca una nuova misura di complessita’ tempo per le NDTM (macchine di Turing nondeterministica) ed una classe di complessita’ ANP ad essa correlata come segue:

• M e’ accept time-bounded da T (n) se per ogni w ∈ Σ^{∗} tutte le computazioni di M che \underline{accettano} w terminano in al piu’ T (|w|)

• L ∈ ANP se esiste una NDTM M ed un polinomio T (n) t.c. L = L_{M} e M e’ accept time-bounded da T (n).

Dimostrare che ANP = NP.

Appello del 25 ottobre ’93 (sessione autunnale)

18) Si formalizzi il paradosso del barbiere. Più precisamente, si consideri la seguente affermazione:

(A) un barbiere di Agicol rade tutti e soli quegli uomini che non si radono da soli.

Si prenda il linguaggio L formato da due simboli relazionali B unario (da intendere come “… è un barbiere di Agicol”, Agicol è un paese di fantasia) ed R binario (da intendere “… rade … ”). Si formalizzi l’affermazione (A) con una formula del linguaggio L, e si dica poi quanti barbieri ci sono ad Agicol producendo una dimostrazione formale della risposta.

19) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

20) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

(α) la funzione n ↦ [\sqrt{n}] che associa ad un numero la parte intera della radice del numero dato.

(β) la funzione che associa ad un numero n i numeri primi minori od uguali ad n;

Giustificare le affermazioni (senza invocare la tesi di Church).

21) Si ricorda che Con è il linguaggio i cui elementi codificano/sono terne (G, s, t) dove G = (V, E) è un grafo diretto e s, t ∈ V sono tali che esiste un cammino da s a t in G. Sia 3.Con il linguaggio i cui elementi codificano/sono quadruple (G, s, u, t) dove G = (V, E) è un grafo diretto e s, u, t ∈ V sono tali che esistono un cammino da s a u ed uno da u a t. Si dia una riduzione log-space di 3.Con a Con.

Appello del 22 dicembre ’93 (sessione autunnale)

22) Sia L un linguaggio che consiste di un unico simbolo relazionale binario R. Si dica se la formula

(∀x∃yR(x, y)) ⇒ (∃y∀xR(x, y))

vale in qualche modello del linguaggio, e si stabilisca se è valida.

23) Si enunci e dimostri un teorema sulle teorie logiche del primo ordine.

24) Dire se le seguenti funzioni numeriche sono ricorsive o meno, totali o meno:

(α) la funzione che enumera in ordine crescente i multipli del numero 15;

(β) la funzione che enumera in ordine crescente i numeri che non sono multipli di 15;

(γ) la funzione n ↦ [n · 7/15] che associa ad un numero la parte intera della moltiplicazione di n con 7/15.

Dire inoltre quali sono ricorsive primitive. Giustificare le affermazioni (senza invocare la tesi di Church).

25) Dimostrare che la relazione di riducibilità ≤_{L} è transitiva.

(tempo: 50 minuti)

Appello del 23 febbraio ’94 (sessione straordinaria)

26) Dimostrare che NLOG è propriamente contenuto in P SP ACE.

27) Si enunci e dimostri un teorema sulle funzioni ricorsive.

28) Si consideri il linguaggio L che consiste di di un simbolo funzionale binario f e di un simbolo funzionale unario g. Sia A = {a, b} un insieme fissato con due elementi.

(α) Si consideri la struttura A = (A, f, g) per L definita sull’universo A dove f e g sono date della tavole di definizione

\begin{matrix}f & a & b \\ a & a & a \\ b & a & b \end{matrix}  \begin{aligned}& g \\ a & & b \\ b & & a. \end{aligned}

Dire se esiste un isomorfismo di strutture da A alla struttura definita sull’insieme dei valori di verità {T, F} con f interpretato dalla funzione congiunzione e g interpretato dalla funzione negazione.

(β) Dire se esiste un isomorfismo di strutture da A alla struttura definita sull’insieme dei valori di verità {T, F} con f interpretato dalla funzione disgiunzione e g interpretato dalla funzione negazione.

(γ) Provare che per ogni numero naturale n ogni funzione h: A^{n} A è l’interpretazione di un termine del linguaggio L nella struttura A.

(δ) Si consideri la struttura A′ = (A, f′, g′) per L definita sull’universo A dove f′ e g′ sono date della tavole di definizione

\begin{matrix}f′ & a & b \\ a & a & b \\ b & b & a \end{matrix}  \begin{aligned}& g′ \\ a & & b \\ b & & a. \end{aligned}

Dire se esiste un isomorfismo di strutture da A′ alla struttura definita sull’insieme dei valori di verità {T, F} con f′ interpretato dalla funzione equivalenza e g′ interpretato dalla funzione negazione.

(ϵ) Dire se per ogni numero naturale n ogni funzione h: A^{n} A è l’interpretazione di un termine del linguaggio L nella struttura A′.

Giustificare le affermazioni. (tempo: 70 minuti)

29) Sia L un linguaggio con due simboli relazionali unari A, B. Dire se le seguenti formule sono teoremi della teoria vuota sul linguaggio L:

(α) ∃x(Ax ⇒ Bx) ⇒ (∀x Ax ⇒ ∃x Bx),

(β) (∀x Ax ⇒ ∃x Bx) ⇒ ∃x(Ax ⇒ Bx),

(γ) ∀x(Ax ∨ Bx) ⇒ (∀x Ax ∨ ∀x Bx).

Giustificare le affermazioni. (tempo: 50 minuti)

Appello del 8 giugno ’94 (sessione estiva)

30) Per formule ben formate A, B, C, si considerino le formule

\begin{matrix}(A ∨ B) ∧ ((A ⇒ C) ∧ (B ⇒ C)) ⇒ C \\ (A ⇒ (B ⇒ C)) ⇔ ((A ∧ B) ⇒ C). \end{matrix}

Si provi che queste sono tautologie, ed anche teoremi (possibilmente producendo dimostrazioni dirette dagli assiomi).

31) Si enunci e si dimostri un teorema sulla logica del prim’ordine.

32) Siano P l’insieme delle funzioni ricorsive parziali in una variabile naturale, R l’insieme delle funzioni ricorsive totali in una variabile naturale (dunque R ⊂ P). Sia θ: N → P una funzione. Si considerino le seguenti affermazioni:

(α) im θ ⊂ R,

(β) R ⊂ im θ,

(γ) (n, m) ↦ θ(n)(m): N → N è ricorsiva parziale.

Dire quali coppie di affermazioni possono essere contemporaneamente soddisfatte producendo un’opportuna scelta di θ. Dire inoltre per quali di queste coppie si ha che quando queste sono soddisfatte, allora la terza rimanente non può esserlo.

33) Sia Log^{2} = DSpace((log n)^{2}). Dire in che relazione sta Log^{2} rispetto a Log, NLog e P Space? Dire inoltre se Log^{2} e’ chiuso rispetto a ≤_{L} (cioe’ se L ≤_{L} L′ ∈ Log^{2} comporta L ∈ Log^{2}). Giustificare le affermazioni.

Appello del 20 luglio ’94 (sessione estiva)

34) Sia A una formula ben formata nel linguaggio L. Sia M un’interpretazione per L. Si provi che le seguenti formule sono vere in M

\begin{matrix}A ⇒ ∃x_{1}A \\ ∀x_{1}A ⇒ ∃x_{1}A. \end{matrix}

35) Si enunci e si dimostri un teorema sulle funzioni ricorsive.

36) Siano e: {V, F }^{2} → {V, F } ed i: {V, F } → {V, F } le funzioni di verità con le seguenti tabelle:

\begin{matrix}e & V & F \\ V & V & F \\ F & F & V \end{matrix}  \begin{aligned}& i \\ V & & F \\ F & & V. \end{aligned}

Si consideri l’insieme F delle funzioni di verità definito come segue:

(α) e ed i sono in F,

(β) le proiezioni π_{i}^{n}: {V, F }^{n} → {V, F }: (α_{1}, …, α_{n}) ↦ α_{i} sono in F (per ogni n ed i ≤ n),

(γ) se f, g_{1}, …, g_{n} sono in F (e sono di opportuna arietà), allora f ∘ ⟨g_{1}, … g_{n}⟩ è in F.

Per f: {V, F }^{n} → {V, F } sia A_{f} l’insieme {(α_{1}, …, α_{n}) | f(α_{1}, …, α_{n}) = V } ⊂ {V, F }^{n}. Sia δ_{n}: {V, F } → {V, F }^{n}: α ↦ (α, …, α) la diagonale. Si dica per quali n si può affermare ciascuna delle seguenti affermazioni:

(α) ogni f: {V, F }^{n} → {V, F } in F è tale che f ∘ δ_{n} è costante,

(β) per ogni f: {V, F }^{n} → {V, F } in F si ha che la cardinalità di A_{f} è pari,

giustificando entrambe le affermazioni.

37) Sia IndSet il linguaggio che codifica le coppie (G, k), dove G e k sono un grafo ed un numero naturale rispettivamente, tali che esiste un insieme indipendente U di nodi di G con |U| = k. Si dice che U è indipendente se ∀n, n′ ∈ U.(n, n′) ∉ G. Si dia una riduzione di Clique ad IndSet, giustificando la scelta.

Appello del 28 settembre ’94 (sessione estiva)

38) Siano A e B formule ben formate nel linguaggio L. Si dimostri che la formula

((A ⇒ B) ⇒ B) ⇒ B

è una tautologia, ed anche un teorema (possibilmente producendo una dimostrazione diretta dagli assiomi).

39) Si enunci e si dimostri un teorema sulla logica formale.

40) Siano f, g: N × N N due funzioni ricorsive. Si consideri la funzione

∑<f/g: (x, y) ↦ [_{∑i<x} \frac{f(i, y)}{g(i, y)}]

che prende la parte intera della sommatoria dei quozienti indicati. Dire quando la funzione ∑_{<} f/g è ricorsiva giustificando la scelta. Se ne può dedurre informazioni circa la ricorsività della funzione

x ↦ [sin x]: N N?

E della funzione che associa ad ogni numero naturale x la prima cifra decimale nell’espansione di sin x? Si cerchi di giustificare le affermazioni.

41) Si dica che L ∈ NT IME′(f) se esiste una NDTM M tale che L = L(M) e per ogni w ∈ L esiste una computazione di M con input w accettante e con un numero di passi ≤ f(|w|). E’ facile vedere che NT IME(f) ⊆ NT IME′(f), perchè? Sotto quale ipotesi su f si ha che NT IME(f) = NT IME′(f)? Giustificare le affermazioni.

Appello del 1 gennaio ’95 (sessione autunnale)

42) Sia f: N N una funzione ricorsiva strettamente crescente. Si mostri che esiste una funzione

ricorsiva g: N N tale che

g ∘ f = id_{N} .

Si veda poi se il procedimento usato si può applicare per mostrare che la funzioine

g(n) = [log n]

è ricorsiva.

43) Si dimostri un teorema di logica formale.

44) Sia L un linguaggio e siano A e B interpretazioni di L. Si dice che B è sottostruttura di A se (i) |B| ⊂ |A (ii) c^{B} = c^{A} per ogni costante di L (iii) f^{A}(x_{1}, …, x_{n}) = f^{B}(x_{1}, …, x_{n}) per ogni (x_{1}, …, x_{n}) ∈ |B|^{n} e per ogni simbolo funzionale

f in L (iv) (x_{1}, …, x_{n}) ∈ R^{B} \underline{se e solo se} (x_{1}, …, x_{n}) ∈ R^{A} per ogni (x_{1}, …, x_{n}) ∈ |B|^{n} e per ogni

simbolo relazionale R in L. Data una formula chiusa X si considerino le affermazioni (α_{X}) se vale X in A, allora X vale in B, (β_{X}) se vale X in B, allora X vale in A. Si dica per quali delle seguenti formule vale (α_{X}) o (β_{X}):

(i) X è (x)A, (ii) X è (Ex)A, (iii) X è atomica, (iv) X è congiunzione di due formule che valgono in A,

(v) X è congiunzione di due formule che valgono in B. Giustificare le affermazioni.

45) Si consideri la definizione della classe complessità spazio

DSP ACE(f) = {L ∈ Σ^{∗}| esiste una DTM offline M space-bounded da f eL = L(M)} dove nella definzione di space-bounded si considerano solo celle usate sui nastri di lavoro (non su quello di input). Dire

1. che cosa succede se si toglie la restrizione che M sia offline,

2. che cosa può succedere se nella definzione di space-bounded si conisderano anche le celle usate sul nastro di input.

Appello del 24 febbraio ’95 (sessione straordinaria)

46) Dire se la relazione di riducibilità ≤_{P} è transitiva giustificando l’affermazione.

47) Si dimostri un teorema sulle funzioni ricorsive.

48) Sia L un linguaggio del prim’ordine e siano A e B interpretazioni di L. Sia poi f: A B un L-omomorfismo tale che f: |A| |B| sia suriettivo. Si dica per quali delle seguenti formule ben formate chiuse si può affermare che la validità in A assicura la validità in B:

(ii) ¬B, dove B non è vera in A,

(iii) ¬C, dove C è qualunque,

(iv) D ∧ E

49) Si verifichi che la formula

((A ⇒ B) ⇒ B) ⇒ A

non è una tautologia nè una contraddizione. Si diano sostituzioni delle formule A e B che producono una tautologia ed una contraddizione rispettivamente. Giustificare le affermazioni.

Appello del 7 giugno ’95 (sessione estiva)

50) Si consideri l’insieme

L = {(V, E, a, b) | (V, E) è un grafo, a, b ∈ V, ed esiste un cammino in (V, E) da a a b }

Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore per la sua complessità, a scelta tempo o spazio, deterministica o nondeterministica.

51) Si enunci e si dimostri un teorema di teoria della complessità.

52) Si consideri l’alfabeto logico con simboli funzionali e costanti {s, z}, simboli relazionali {=, <} (il primo è il simbolo per la relazione di uguaglianza), l’arietà è tabulata come segue

\begin{matrix}s ↦ & 1 \\ z ↦ & 0 \\ =↦ & 2 \\ <↦ & 2 \end{matrix}

e le seguenti formule:

∀x(s(x) ≠ z)  ∀x∀y(s(x) = s(y) ⇒ x = y)
∀x(x ≠ z ⇒ ∃y(s(y) = x))  ∀x(x < s(x))
∀x∀y(x < y ⇒ s(x) < s(y))  ∃x(s(x) = z)
∃x(s(x) = x)  ∃x(x < s(x))
∀x∀y∀z(x < y ∧ y < z ⇒ x < z)

Si dica quali sono gli insiemi massimali coerenti di formule dalla lista data sopra giustificando le affermazioni. Si determinino poi tutti gli insiemi coerenti dalla lista.

53) Si verifichi che

((¬a) ⇔ b) ⇔ (¬(a ⇔ b))

è una tautologia. Si dimostri quindi che i connettivi ¬ e ⇔ non sono adeguati. Si può adattare il metodo di dimostrazione usato per mostrare che ¬ e ⇒ non sono adeguati?

Appello del 12 luglio ’95 (sessione estiva)

L = {(V, E, a, b) | (V, E) è un grafo, a, b ∈ V, ed esiste un cammino in (V, E) da a a b }

Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore ed una inferiore per la sua complessità, tempo o spazio, che sia deterministica o non-deterministica.

55) Si enunci e si dimostri un teorema di teoria della complessità.

56) Si introduce false < true sull’insieme {true, false}. Poi si dice che una funzione booleana f: {true, false}^{n} {true, false} è monotona se

f(x_{1}, …, x_{n}) ≤ f(y_{1}, …, y_{n})

ogni volta che x_{1} ≤ y_{1},…,x_{n} ≤ y_{n}. Ad esempio, la funzione booleana a due argomenti determinata dalla congiunzione è monotona. Si dica se i connettivi ∧ e ∨ sono sufficienti per esprimere

(α) tutte le funzioni booleane monotone,

(β) tutte le funzioni booleane,

giustificando le risposte.

57) Sia N il modello standard della teoria dei numeri. Si consideri l’interpretazione del linguaggio L della teoria dei numeri nel “prodotto” N × N: l’universo è l’insieme prodotto degli universi N × N, l’interpretazione è quella “coordinata per coordinata”. Ad esempio, l’interpretazione del simbolo + è

+^{N×N}((n_{1}, n_{2}), (m_{1}, m_{2})) = (n_{1} +^{N} m_{1}, n_{2} +^{N} m_{2}),

quella della costante 0 è

0^{N×N} = (0^{N}, 0^{N})

e così via per gli altri simboli e relazioni. Si noti in particolare che la definizioine coordinata per coordinata della relazione = è proprio la diagonale di N ×N—un sottoinsieme di (N×N)×(N×N). Si dica quali assiomi della teoria dei numeri non valgono in N × N giustificando le affermazioni. Appello del 28 settembre ’95 (sessione estiva)

58) Sia A un insieme finito, e si consideri l’insieme L di coppie di liste x e y di elementi di A tali che una sia ottenuta dall’altra permutando alcuni elementi. Si descriva (in modo ragionevolmente completo) una macchina che decide L. Si determini poi una limitazione superiore ed una inferiore per la sua complessità, tempo o spazio, che sia deterministica o non-deterministica.

59) Si enunci e si dimostri un teorema di teoria della complessità.

60) Sia T una teoria del prim’ordine. Si dice che una formula A è negata pura se essa è dimostrabilmente equivalente ad una della forma ¬P dove P (in forma abbreviata) contiene soltanto i connettivi ∧ e ∨ ed il quantificatore esistenziale. Si dica per quali operazioni logiche la classe delle formule negate pure è sicuramente chiusa, e per quali invece non è detto che lo sia. Si consideri poi il caso particolare della teoria T dell’ordine parziale: consiste di due simboli relazionali binari = e ≤ ed ha come assiomi quelli per l’uguaglianza ed i seguenti:

∀xx ≤ x
∀x∀y(x ≤ y ∧ y ≤ x) ⇒ x = y
∀x∀y∀z(x ≤ y ∧ y ≤ z) ⇒ x ≤ z.

Si dica se la formula ∀x∀y(x ≤ y ∨ y ≤ x), che esprime il fatto che l’ordine è totale, è negata pura. In caso positivo, si accenni la dimostrazione formale; in caso negativo si proponga come estendere la teoria in modo che lo diventi.

61) Si consideri il linguaggio dei numeri naturali, e si consideri il modello standard su N. Si prenda ora l’insieme N_{1} = N ∪ (Z × {∞}) dove il carattere ∞ viene usato per avere i due addendi sicuramente disgiunti. Si estenda l’interpretazione standard su N per il linguaggio dei numeri naturali all’insieme N_{1} in modo che da mantenere verificati il maggior numero di assiomi della teoria dei numeri. (L’interpretazione del simbolo = deve essere quella canonica, cioè la diagonale di N_{1}.)