Funzione primitiva ricorsiva tramite ricorsione primitiva
Salve a tutti,
sto preparando l'esame di Teoria della Computazione 2 dove si studiano le funzioni parziali ricorsive. Non ho problemi a calcolare tali funzioni tramite l'operatore di composizione, ma ho qualche problema a calcolarle tramite l'operatore di ricorsione primitiva. Per esempio, come si può mostrare che la funzione f:N-->N definita da f(x) = x^2 + x + 1 è primitiva ricorsiva utilizzando la ricorsione primitiva? Ringrazio anticipatamente per l'aiuto. Ciao.
sto preparando l'esame di Teoria della Computazione 2 dove si studiano le funzioni parziali ricorsive. Non ho problemi a calcolare tali funzioni tramite l'operatore di composizione, ma ho qualche problema a calcolarle tramite l'operatore di ricorsione primitiva. Per esempio, come si può mostrare che la funzione f:N-->N definita da f(x) = x^2 + x + 1 è primitiva ricorsiva utilizzando la ricorsione primitiva? Ringrazio anticipatamente per l'aiuto. Ciao.
Risposte
"magsas":
Non ho problemi a calcolare tali funzioni tramite l'operatore di composizione
Hai definito la composizione nel caso in esame (io non ho provato)? Benissimo, allora
"magsas":
ho qualche problema a calcolarle tramite l'operatore di ricorsione primitiva
nel caso direi è $S(x)$ (successore) se $x=0$, e la tua composizione altrimenti.
Cosa ti torna? Fammi vedere, anche io sto studiando questi argomenti.
Ciao rggb,
non ho molto capito cosa intendevi dire. Comunque, per composizione dovrebbe essere così: f(x) = + ( * (x,x), S(x) ).
Quello che non mi riesce è la definizione tramite l'operatore di ricorsione primitiva, cioè questo:
non ho molto capito cosa intendevi dire. Comunque, per composizione dovrebbe essere così: f(x) = + ( * (x,x), S(x) ).
Quello che non mi riesce è la definizione tramite l'operatore di ricorsione primitiva, cioè questo:
- f( X1,......,Xn-1, 0 ) = g(X1,.....Xn-1)[/list:u:1irl4a1w]
- f( X1,......,Xn-1, Y+1 ) = h(X1,.....Xn-1, Y, f( X1,......,Xn-1, Y )[/list:u:1irl4a1w]
dove f:N^n --> N, g:N^n-1 --> N, h:N^n+1 --> N.
Non so se mi sono spiegato bene....
[ Vedo che assumi già definite le funzioni + e * - non lo davo per scontato. 
Le chiamerò $\s\u\m$ e $\m\u\l$ ]
Le definizioni alle quali sono abituato sono differenti, comunque è quello che intendevo. La ricorsione primitiva è l'operatore che si compone di una funzione "base" per $x=0$ e una funzione "induzione" per $x>0$. Nella tua notazione, $g(x)$ può essere $S(x)$ (se preferisci, diventa $f(0)=S(0)$) e la tua $h(x)$ può essere $U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))$ dove $U$ è la funzione selettore (spero di non aver fatto errori banali).
Attendo commenti.
Le chiamerò $\s\u\m$ e $\m\u\l$ ]Le definizioni alle quali sono abituato sono differenti, comunque è quello che intendevo. La ricorsione primitiva è l'operatore che si compone di una funzione "base" per $x=0$ e una funzione "induzione" per $x>0$. Nella tua notazione, $g(x)$ può essere $S(x)$ (se preferisci, diventa $f(0)=S(0)$) e la tua $h(x)$ può essere $U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))$ dove $U$ è la funzione selettore (spero di non aver fatto errori banali).
Attendo commenti.
"Rggb":
[ Vedo che assumi già definite le funzioni + e * - non lo davo per scontato.
In realtà bisogna dimostrarle all'esame, qui, per farla breve, le ho supposte note. Perdono.
"Rggb":
Le definizioni alle quali sono abituato sono differenti, comunque è quello che intendevo. La ricorsione primitiva è l'operatore che si compone di una funzione "base" per $x=0$ e una funzione "induzione" per $x>0$. Nella tua notazione, $g(x)$ può essere $S(x)$ (se preferisci, diventa $f(0)=S(0)$) e la tua $h(x)$ può essere $U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))$ dove $U$ è la funzione selettore (spero di non aver fatto errori banali).
Attendo commenti.
Per prima cosa vediamo se ho capito. Per te $U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))$ significa che restituisci solo la seconda componente?
Se è così, non mi trovo perché la funzione induttiva dovrebbe essere chiamata su input più piccoli e mi pare che $f(x+1)=(x+1)^2+(x+1)+1$ è diversa da $f(x+1)=U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))$.
Dov'è che sbaglio?
Esatto, il selettore che restituisce la seconda componente.
Come ho detto, forse ho fatto un errore banale (mi sto confondendo, fra x+1 e x-1
), ma principalmente questa incomprensione fra noi dipende dalle notazioni. Allora, vediamo di cominciare da qui: secondo la tua definizione, l'operatore di ricorsione primitiva, con una sola variabile, è
$f(x)={ ( g(), x=0 ),( h(x-1, f(x-1)), x>0 ):}$
o anche
${ (f(0)=g()), ( f(x+1)=h(x, f(x))):}$
ho capito bene?
Come ho detto, forse ho fatto un errore banale (mi sto confondendo, fra x+1 e x-1
), ma principalmente questa incomprensione fra noi dipende dalle notazioni. Allora, vediamo di cominciare da qui: secondo la tua definizione, l'operatore di ricorsione primitiva, con una sola variabile, è$f(x)={ ( g(), x=0 ),( h(x-1, f(x-1)), x>0 ):}$
o anche
${ (f(0)=g()), ( f(x+1)=h(x, f(x))):}$
ho capito bene?
"Rggb":
Esatto, il selettore che restituisce la seconda componente.
Come ho detto, forse ho fatto un errore banale (mi sto confondendo, fra x+1 e x-1
$f(x)={ ( g(), x=0 ),( h(x-1, f(x-1)), x>0 ):}$
o anche
${ (f(0)=g()), ( f(x+1)=h(x, f(x))):}$
ho capito bene?
La seconda definizione.
"magsas":
La seconda definizione.
Ok perfetto (del resto, sono equivalenti
)Quindi potremmo fare:
$f(0)=S(0)$
$f(x+1)=\s\u\m(\s\u\m(S(x), S(x)), \s\u\m(\m\u\l(x, x), S(x)))$
dove $\s\u\m\(x, y)$ è la somma e $\m\u\l(x, y)$ il prodotto, come accennavo prima.
Però mi sembra complicato
Ci dovrebbe essere una strada più semplice... no? Come ti ho detto, ci stiamo aiutando a vicenda in quanto anche io sto studiando l'argomento.
"Rggb":[/quote]
[quote="magsas"]
Quindi potremmo fare:
$f(0)=S(0)$
$f(x+1)=\s\u\m(\s\u\m(S(x), S(x)), \s\u\m(\m\u\l(x, x), S(x)))$
dove $\s\u\m\(x, y)$ è la somma e $\m\u\l(x, y)$ il prodotto, come accennavo prima.
Però mi sembra complicato
Mi sembra che vada bene. Poi, complicata o meno l'importante è che funzioni!! Di soluzioni migliori per ora non me ne vengono...
Come vedi, ho usato la prima idea che avevo
$U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))
e l'ho "adattata al caso" $x+1$ (nei testi che ho io si usa induttivamente $x$ sulla base di $x-1$)
$\s\u\m(\s\u\m(S(x), S(x)), \s\u\m(\m\u\l(x, x), S(x)))
e probabilmente hai ragione, può andare. La formula induttiva è identica alla tua, che usa '+' e '*', ti basta cambiare notazione.
Mi riprometto di tornare sull'argomento in caso mi rendessi conto di aver fatto/scritto errori.
$U^2(x-1, \s\u\m(\m\u\l(x, x), S(x)))
e l'ho "adattata al caso" $x+1$ (nei testi che ho io si usa induttivamente $x$ sulla base di $x-1$)
$\s\u\m(\s\u\m(S(x), S(x)), \s\u\m(\m\u\l(x, x), S(x)))
e probabilmente hai ragione, può andare. La formula induttiva è identica alla tua, che usa '+' e '*', ti basta cambiare notazione.
Mi riprometto di tornare sull'argomento in caso mi rendessi conto di aver fatto/scritto errori.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo