Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Computabilità => Topic started by: moltisanti on 11-02-2010, 12:59:11



Title: Soluzione esercizio n°1 compito 7 febbraio 2008
Post by: moltisanti on 11-02-2010, 12:59:11
Ecco il testo:
Quote
Si dimostri che esiste una funzione totale e non calcolabile f : N → N tale che x2 ≤ f (x) ≤ x2 + 1, per ogni x ∈ N.
Ecco la mia soluzione:

f(x) =
  • \phi_{x}(x)+1 se \phi_{x}\left(x\right)\downarrow x^{2}
  • \phi_{x}\left(x\right)-1 se \phi_{x}\left(x\right)\downarrow x^{2}+1
  • x^{2} altrimenti

Assumendo che per ogni x ∈ N \phi_{x}\left(x\right) è un'enumerazione di tutte le funzioni unarie calcolabili, avremo che la funzione f definita come sopra risulta essere diversa da tutte le funzioni unarie calcolabili e pertanto è non calcolabile.

E' una soluzione corretta?