aiuto esercizio
Inviato: 27/06/2018, 21: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
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