Pages: [1]   Go Down
Print
Author Topic: Soluzione esercizio n°1 compito 7 febbraio 2008  (Read 3602 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
moltisanti
Matricola
*
Offline Offline

Posts: 84


« 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?
Logged
Pages: [1]   Go Up
Print
Jump to: