- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey! ![Eek! :eek: :eek:](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows:
The definition of a primitive recursive function is the following:
I got stuck right now... The two definitions are similar and a function that is $\mu-$recursive satisfies $4$ properties and the first $3$ are very similar to the properties of a primitive recusive function. But there are $\mu-$recursive functions that are not primtive recursive. Could you explain to me why this hold?? (Wondering)
According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows:
- The constant, projection, and successor functions are all $\mu-$recursive.
- If $g_1, \dots , g_m$ are $n-$variable $\mu-$recursive functions and $h$ is an $m-$variable $\mu-$recursive function, then the composite function $f=h \circ (g_1, \dots , g_m)$ is also $\mu-$recursive.
- If $g$ and $h$ are $n-$ and $(n+2)-$variable $\mu-$recursive functions, then the function $f$ defined from $g$ and $h$ by primitive recursion is also $\mu-$recursive.
- If $g$ is a total $(n+1)-$variable $\mu-$recursive function, then the function $f$ defined from $g$ by unbounded minimalization is also $\mu-$recursive.
The definition of a primitive recursive function is the following:
- The constant, projection, and successor functions are all primitive recursive functions.
- If $g_1, \dots , g_m$ are $n-$variable primitive recursive functions, and if $h$ is an $m-$variable primitve recursive function, then the composite function $h \circ (g_1, \dots , g_m)$ is also a primitive recursive function.
- If $g$ and $h$ are $n-$ and $(n+1)-$variable primitive recursive functions, then $(n+1)-$variable function $f$ defined from $g$ and $h$ by primitive recursion is also a primitive recursive function.
I got stuck right now... The two definitions are similar and a function that is $\mu-$recursive satisfies $4$ properties and the first $3$ are very similar to the properties of a primitive recusive function. But there are $\mu-$recursive functions that are not primtive recursive. Could you explain to me why this hold?? (Wondering)