aiuto esercizio

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Erion
Salve a tutti,

sto studiando in questo periodo elementi di calcolabilità e complessità e inizio ora a provare a fare qualche esercizio. Qualcuno potrebbe darmi una mano su questo:

dire se ∃ f calcolabile totale t.c. ∀ x
f(x) = x se ∃ i<x : φi = φx
x+1 altrimenti


direi che la f non è calcolabile totale in quanto decidere se esiste i<x t.c. … è decidibile, però valutare φ può non essere decidibile (visto che φ è parziale). Quindi per alcuni indici i si può dire che il predicato vale e quindi f(x)=x, per altri si può dire che non vale quindi f(x)=x+1, però quando la φ diverge non possiamo restituire niente.

Grazie in anticipo dell’aiuto.

mizipolo
Mi sembra giusto!

Alternativamente (la butto lì senza pensarci troppo) potresti far vedere che la sua immagine è (o non è) un insieme ricorsivamente enumerabile

Invece, pensandoci meglio, forse qui non è banale farlo vedere. Però magari ti è utile come schema di soluzione in esercizi simili ;)

Provare a fare una riduzione da [math] o comunque da un insieme non ricorsivamente enumerabile.

Ne approfitto per spiegarmi meglio. L'idea sarebbe di dimostrare che la funzione non è calcolabile totale con una dimostrazione per assurdo, assumendo per ipotesi che la funzione sia calcolabile totale e concludendo che la sua immagine sia non r.e. (ad esempio tramite la riduzione di cui sopra).

Facendo vedere che l'immagine è r.e. non dimostri nulla. Per cui la riduzione da [math] è inutile.

Ripeto che non ci ho pensato molto su questa soluzione, quindi invito te e/o chiunque altro a verificare le mie parole
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”