Per definizione, se le funzioni $f:NN^k -> NN$ e $g:NN^(k+2)->NN$ sono PR, lo è anche $h:NN^(k+1)->NN$ definita da:
- $h(x_1,...,x_k,0)=f(x_1,...,x_k)$;
- $h(x_1,...,x_k,y+1)=g(x_1,...,x_k,y,h(x_1,...,x_k,y))$.
Domanda: se al secondo membro della seconda riga avessi $g(x_1,...,x_k,y,h(x_1,...,x_k,rho(y)))$, dove $rho:NN rightarrow NN$ è PR e tale che $\rho(y)<=y$ $forall y$, allora $h$ sarebbe comunque PR?
Riporto qui sotto qualche tentativo, di cui non sono nemmeno troppo convinto:
Testo nascosto, fai click qui per vederlo
Mettendo in corrispondenza $NN$ con le successioni finite a valori in $NN$, definisco la funzione $H$ tale che $H(x_1,...,x_k,y)$ sia il numero che rappresenta la successione $[h(x_1,...,x_k,0),...,h(x_1,...,x_k,y)]$, e cerco di dimostrare che $H$ è PR: oltre a $f$ e $g$, dovrebbero servirmi:
- la funzione che associa a un numero naturale la successione di lunghezza $1$ corrispondente e reinterpreta quest'ultima come numero naturale;
- la funzione che aggiunge un numero in fondo a una successione;
- la funzione $pi(s,i)$ che interpreta $s$ come successione e restituisce l'$i$-esimo elemento.
Infine, con la funzione che restituisce l'ultimo elemento di una successione, ottengo $h$ da $H$.
Ora, ammesso che quanto detto finora funzioni, se scelgo in modo furbo la corrispondenza tra numeri e successioni le quattro funzioni appena descritte dovrebbero essere PR, e da qui concluderei per composizione.
- la funzione che associa a un numero naturale la successione di lunghezza $1$ corrispondente e reinterpreta quest'ultima come numero naturale;
- la funzione che aggiunge un numero in fondo a una successione;
- la funzione $pi(s,i)$ che interpreta $s$ come successione e restituisce l'$i$-esimo elemento.
Infine, con la funzione che restituisce l'ultimo elemento di una successione, ottengo $h$ da $H$.
Ora, ammesso che quanto detto finora funzioni, se scelgo in modo furbo la corrispondenza tra numeri e successioni le quattro funzioni appena descritte dovrebbero essere PR, e da qui concluderei per composizione.
