Informateci

Mi sono presentata con i compitini a cui ha dato solo uno sguardo veloce.

- Descrivere le proprietà di A = { i | φ_i = φ_2i }
- A è un i.i.r.f.? No
- Come trovare un i che dimostri che l'insieme non è vuoto (serve il teorema di ricorsione)
- Enunciato e dimostrazione del teorema di ricorsione
- Enunciato e dimostrazione intuitiva del teorema di accelerazione

L'importante è provare a iniziare a scrivere qualcosa, nel caso vi blocchiate (o sbagliate a scrivere qualcosa) vi dà dei suggerimenti per arrivare alla soluzione. Un'altra cosa importante è non dare l'idea di aver imparato le dimostrazioni dei teoremi a memoria.

Mi sono presentato con i compitini all'appello di luglio 2019, rimbalzato dopo 40 minuti di orale. Mi ha chiesto:

- Dato I = { x | #( dom( φ_x )) = 1 } dire se R o RE. ( È co-RE )
- Enunciare e dimostrare il teorema 1.10.4 (pre-Rice).
- Enunciare e dimostrare (in dettaglio) il teorema 3.5.2 ( riduzioni in LOGSPACE classificano P e NP ).

Ripresentato a settembre con i compitini, orale durato 4 minuti (verbalizzato). Mi ha chiesto:

- Enunciare e dimostrare il teorema di ricorsione (Kleene 2) 1.9.14
- Mi ha chiesto come farei a dimostrare che un MdT non deterministica può calcolare gli stessi problemi di una macchina deterministica e vice-versa. ( Enunciato del teorema 3.3.6)

NOTA: consiglio a chiunque di andare a ricevimento e di chiarivi ogni possibile dubbio (anche banale), apprezza il vostro impegno e interesse in materia.

- dimostrare che [math]EXT è non ricorsivo
- [math]EXT è un [math]I.I.R.F.? (risposta: si)
- dimostrazione del Teorema di Rice
- [math]NP \subseteq EXP come ci si arriva? quindi dimostrare il Teorema 3.3.6.

• Dimostrazione Circuit-SAT NP-completo e cosa cambia rispetto alla dimostrazione Circuit-Value P-completo;

• Data Mdt non det. con grado di non determinismo N, come trasformarla in una Mdt non det. con grado di non determinismo 2;

• In quali casi A si riduce ad A-segnato (più esempi)

• Teorema di Forma Normale

- proprietà dell'insieme A_n = { i<n | phi_i è totale } è un iirf? descriverne le proprietà (r,re,non-re)
- proprietà dell'insieme infinito rappresentato dall'unione di A_n con n=1,2,3...N è un iirf?
- Definizione di iirf e Lemma (pre-Rice) con dimostrazione

- Dimostrazione completezza di Circuit Value
- Teorema di accelerazione lineare (con collegamenti al teorema di compressione lineare) e differenze rispetto al teorema di accelerazione di blum
- Definizione di funzione di misura appropriata

1) dato A = { i | 3 \in(dom(phi_i))} ragionare sull'insieme (è ricorsivamente enumerabile?)
2) dimostrare che K è RE-completo per ≤rec
3) dimostrare che le funzioni calcolabili totali classificano R ed RE
4) supponiamo che NP = co-NP, cosa possiamo dire su P è incluso in NP? (in pratica voleva fregarmi facendomi dire che P = NP in questo caso, e ci è riuscito, perché in realtà non si può dire nulla)

Orale durato una trentina di minuti, Degano molto tranquillo, alla fine mi ha messo 27.

1) Proprietà dell'insieme { x < f(42) | φ_x(f(42)) = φ_f(42)(x) } con f calcolabile totale.
2) Enunciato e dimostrazione del teorema di ricorsione.
3) Dimostrare che LOGSPACE è chiuso per composizione.

L'esame a distanza è solo orale su Microsoft Teams e dura massimo 30 minuti (meno se si risponde senza esitazioni).

Un orale del 29 maggio 2020:

- def i.i.r.f.
- teo+dim Sia A i.i.r.f. diverso da insieme vuoto e dai numeri naturali allora K <= A oppure K<= A segnato
- K è i.i.r.f. ?
- Dim Circuit-SAT è NP-completo

Teorema di Rice (pag 70)
P incluso ed è proprio in EXP: corollario 3.4.3 (pag 163)
Teorema forma Normale (pag 46)
NP incluso EXP Teorema 3.3.6 (pag 156) + corollario 3.4.3 (pag 163)
Teorema 3.3.6(pag 156)
Teorema di Enumerazione (pag 47)
Teorema di Accelerazione lineare (pag 141)