Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion-theoretic if-statements

  1. Jun 19, 2011 #1
    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]​

    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.

  2. jcsd
  3. Jun 20, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
    Last edited by a moderator: Apr 26, 2017
  4. Jun 20, 2011 #3
    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:

    Wikipedia calls them partial [itex]\mu[/itex]-recursive functions, and the https://www.amazon.com/Classical-Re...05X/ref=sr_1_1?ie=UTF8&qid=1308593616&sr=8-1"I 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.
    Last edited by a moderator: Apr 26, 2017
  5. Jun 20, 2011 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
  6. Jun 23, 2011 #5
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook