1. Show that prfs are closed under three-way mutual induction. Three-way mutual induction means that each induction step after calculating the base is computed using the previous value of the other function. The formal hypothesis is:
Assume g1, g2, g3, h1, h2, and h3are already known to be prf, then so are f1, f2, and f3, where
f1(x,0) = g1(x); f1(x,y+1) = h1(f2(x,y),f3(x,y));
f2(x,0) = g2(x); f2(x,y+1) = h2(f3(x,y),f1(x,y))
f3(x,0) = g3(x); f3(x,y+1) = h3(f1(x,y),f2(x,y))
2. Let S be an arbitrary non-empty, re set. Furthermore, let S be the range of some partial recursive function fs. Show that S is the range of some primitive recursive function, call it hs.
Question
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
Denote by <a, b, c> := <<a, b>,<c>> where <x,y>=pair(x,y) and denote a=p1(z)=<<z>1>1, b=p2(z)= <<z>1>2, c=p3(z)=<z>2, where z=<a, b, c>. Then both <a, b, c> = pair(pair(a,b),c) as well as p1, p2 and p3 are prfs.Denote T(x,y) = <f1(x,y), f2(x,y), f3(x,y)>. Then also f1(x,y)=p1(T(x,y)), f2(x,y)=p2(T(x,y)), f3(x,y)=p3(T(x,y)).
Moreover, T(x, 0) = <g1(x), g2(x), g3(x)> is prf. (as a composition of prfs) and
T(x, y+1) = <f1(x,y), f2(x,y), f3(x,y)> =
= < h1(f2(x,y),f3(x,y)), h2(f3(x,y),f1(x,y)), h3(f1(x,y),f2(x,y)) >
= <h1(p2...
Return to homework library