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

Recursively enumerable predicate

  1. Dec 20, 2007 #1
    Hi all,

    could someone please explain to me, why, having recursively enumerable predicate Q(x,y) which is not recursive, the function defined as

    f(x) \simeq \mu_{y} Q(x,y)

    doesn't define partially recursive function?

    Ok, here's the argument for it: the program will "try" if Q(x,y) for y = 0 and since Q(x,y) is only r.e., we'll get stuck in case Q(x,0) doesn't hold. BUT is this a problem? I mean, partially recursive functions are not expected to converge on every output so this is not a problem, is it?

    I searched the literature and found the following proof in Odifreddi's Classical Recursion Theory:

    Let A be an r.e. nonrecursive set and define:

    \psi(x,y) \simeq 0 \Leftrightarrow (y = 0 \wedge x \in A) \vee y = 1

    Then [itex]\psi[/itex] is partial recursive, but if

    f(x) = \mu_{y} (\psi(x,y) \simeq 0)

    then [itex]f[/itex] (total) [Why is [itex]f[/itex] total?] is not partial recursive, otherwise it would be recursive and since

    f(x) = 0 \Leftrightarrow x \in A

    so would be A.

    As I highlighted, I can't see why [itex]f[/itex] is total and thus from my point of view there is no contradiction if [itex]f[/itex] were partial recursive.

    Thank you for any suggestion, I'll be thankful for anything.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted