Funzioni Flashcards

Question

35. Cosa vuol dire relazione ricorsiva primitiva e funzione buona?

Answer 1

$R\sube \N^k$ si definisce relazione ricorsiva primitiva quando $\exists f:\N^k\to\N$ funzione ricorsiva primitiva tale che $f(\vec x)=0\Lrarr \vec x\in R$ (esiste funzione rp che determina appartenenza a R). Tale funzione $f$ si dice funzione buona per $R$. Alternativamente, $R\in\N^k$ è relazione rp $\Rarr \chi_R$ funzione caratteristica è rp $$ \chi_R:\N^k\to \N\\\vec x \to \begin{cases}1\text{ se }\vec x\in R\\0\text{ se }\vec x\notin R\end{cases} $$

Answer 2

$R,S\sube \N^k$ - $\Rarr R^c=\N^k\setminus R$ è relazione rp (complementare) - $R\cup S$ è rp (somma) - $R\cap S$ è rp (prodotto)

Answer 3

Relazione identificata dalla ripetizione dell’ultimo valore (proiezione doppia ultimo valore) Relazione opposta (proiezione invertita) Massimo (relazione x

Answer 4

min{z\in N | (x,z)\in R} se esiste altrimenti 0

Answer 5

Per ogni z

Answer 6

1. voglio dimostrare che f è rp → scrivo schema rp 2. f è definita per min. limitata, quindi cerco funzioni per min. limitata 3. f(x,0) è sempre 0 quindi costante 4. per altro caso, uso generico h(vec x, y, t) 1. f cerca min intero inferiore a y+1: 3 casi 1. trovo presto z

Answer 7

$$ A:\N^2\to\N\\\begin{cases}A(0,y)=y+1\\A(x+1,0)=A(x,1)\\A(x+1,y+1)=A(x,A(x+1,y))\end{cases} $$ Si osserva che $A$ è computabile (basta cercare un algoritmo online) - **Esempio** ![image.png](attachment:012e8bfe-394b-4f20-a704-8a85e4869c01:image.png) Rispetto a $x$, la complessità cresce esponenzialmente

Answer 8

1. $A(1,y)=y+2$ per induzione su $y$ 2. $A(2,y)=2y+3$ 3. $A(3,y)=2^{y+3}-3$ 4. $A(4,y)=2^{2^{2^{...^{2^{16}}}}}-3$ ($y$ volte elevamento a potenza) 5. $\forall x,y\in\N,A(x,y)\ge y+1$ per induzione su $x$ e poi su $y$ 6. $\forall x,y\in\N, A(x,y)< A(x,y+1)$ - **Dimostrazione** 💡Idea: distinguono 2 casi 7. $A(x,y+1)\le A(x+1,y)$ 8. $\forall x,y\in\N,A(x,y)< A(x+1,y)$ - **Dimostrazione** 💡Idea: usando proprietà precedenti 9. $A(x_1,y)+A(x_2,y)\le A(\max(x_1,x_2)+4,y)$ 10. $A(x,y)+y< A(x+4,y)$

Answer 9

per ogni g rp esiste c tale che g(vec x) < A(c, sum x) DIMOSTRAZIONE NON VA SAPUTA Faccio vedere che vale per funzioni iniziali e continua a valere per costruzione → induzione strutturale

Answer 10

Sia A rp per assurdo allora anche B(x)=A(x,x) è rp Per il lemma precedente B(x) rp è < A(c,x) cioè B(c) < A(c,c) che è assurdo (dovrebbe essere uguale)

Answer 11

Codifichiamo con opportuno alfabeto sigma={c,0...9,s,epsilon,(,),dot,<>,R)

Answer 12

Per assurdo ogni funzione computabile unaria è rp attraverso enumerazione sia f1,...fn lista sia g(x)=fx(x)+1 g rp (per assurdo) però esiste n t.c. g(n)=fn+1 che è assurdo

Answer 13

g: N^k+1 si dice regolare quando forall x in N^k, esiste y\in N t.c. g(x,y)=0

Answer 14

quando f(x) è min{y\in N t.c. g(x,y)=0}

Funzioni Flashcards

(39 cards)