The forum of the Computer Science students of the University of Pisa

Domande Orale Degano

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.