Insieme ricorsivo!

[*missdreamer*12]

Sia A un insieme di dimensione non finita di numeri naturali

dimostrare che:

A ricorsivo se e solo se esiste una funzione ricorsiva f(x) tale che f(n)

non riesco a dimostrare la freccia verso destra.
Verso sinistra credo sia abbastanza intuitivo perchè essendo f ricorsiva l'insieme A è ricorsivo ed essendo f tale che f(n)

Cita

Segnala

---

Risposte

TomSawyer1

22 gen 2007, 16:59

Che freccia verso destra?

Cita

Segnala

---

fields1

22 gen 2007, 19:59

Si riferisce all'implicazione verso destra.

In questo caso bisogna sfruttare il fatto che la funzione $H_{g} (n)=sum_(i=0)^n g(i)$ e' ricorsiva, se $g$ e' ricorsiva. Sia ora $f$ la funzione caratteristica di $A$: $f(n)=1$ se $n\in A$, $f(n)=0$ se $n\notin A$. Definiamo per minimizzazione $F(n)=\mu y. H_{f}(y)=n+1$

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[TomSawyer1]

Che freccia verso destra?

[fields1]

Si riferisce all'implicazione verso destra.

In questo caso bisogna sfruttare il fatto che la funzione $H_{g} (n)=sum_(i=0)^n g(i)$ e' ricorsiva, se $g$ e' ricorsiva. Sia ora $f$ la funzione caratteristica di $A$: $f(n)=1$ se $n\in A$, $f(n)=0$ se $n\notin A$. Definiamo per minimizzazione $F(n)=\mu y. H_{f}(y)=n+1$