Recursion-theoretic if-statements

[kanima]

Hi, there, I was wondering if anyone knew a good way to implement if-statements in recursion-theoretic terms. Basically, I've come to the understanding that primitive recursion is analogous to a for-loop and mu-recursion to more general while-loops, but is there in general a simple analog of an if-statement in recursion theory?

For example, suppose that given partial recursive functions [itex]g[/itex] and [itex]h[/itex] I had the following algorithm which takes [itex]x[/itex] as input.

if [itex]x < 50[/itex] then

return [itex]g(x)[/itex]​

​

else

return [itex]h(x)[/itex]​

​

How could I define a partial recursive function computing the above algorithm? What if the condition [itex]x < 50[/itex] were replaced by some more general recursive predicate [itex]R(x)[/itex]?

I suspect this shouldn't be so difficult but I am quite new to this subject. If this is the case, I would be quite glad if someone would share their knowledge me.

Thanks!

 

[Stephen Tashi]

I don't know the answer to your question, but it prompted me to look up "partial recursive function". I notice there a considerable difference between how it is defined on the Wikipedia (http://en.wikipedia.org/wiki/Computable_function) versus Wolfram (http://mathworld.wolfram.com/RecursiveFunction.html).

If we use the Wolfram definition, your question could be interpreted as asking how to write a function who definition has an "if ... then " clause as a series of equations. However, I'm not sure that question is significant if we are allowed to use "function symbols" in the equations unless there is some restriction on what functions can be represented by "function symbol". Is there something that says a "function symbol" cannot stand for a function (say on the non-negative integers) which is the list of pairs (x, f(x)) = { (1,0),(2,0),(3,1),(4,1),... }, which amounts to f(k) = 0 if k < 3 and f(k) = 1 otherwise.

 

[kanima]

Sorry, I should have been more specific, especially because of the many guises this same subject appears in.

My definition of partial recursive function is more in line with the one given in the following wikipedia article:
http://en.wikipedia.org/wiki/Μ-recursive_function.

Wikipedia calls them partial [itex]\mu[/itex]-recursive functions, and the https://www.amazon.com/dp/044450205X/?tag=pfamazon01-20I am following simply calls them partial recursive functions.

The class of functions defined in this way is equivalent to the class of those defined in the Wolfram link. This class of functions is also equivalent to the class of Turing-computable functions: functions whose values can be computed by some Turing machine.

It shouldn't be very difficult to implement conditional if-statements on Turing machines (since they're pretty natural models of computation). However, I am interested in seeing how a function computed by an algorithm with an if-statement can be built up from definition given in the wikipedia page on [itex]\mu[/itex]-recursive functions.

 

[Stephen Tashi]

Perhaps the place to start is to find a function T(x) that returns 1 if x < 50 and returns 0 otherwise. Then the function you asked about is defined by f(x) = T(x)g(x) + (1-T(x))h(x).

What is a "general recursive predicate"? Is there a definition or theorem that says its evaluation (as true or false , or 1 or 0) is computable.

 

[kanima]

Yes, I believe you're right, and looks like the answer was quite simple after all. By a recursive predicate I did just mean a recursive function that could only give the values 0 or 1. So I guess the function [itex]f[/itex] in your example would be recursive if the predicate [itex]T[/itex] expressing the condition was recursive.