Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

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

[tex]

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

[/tex]

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:

[tex]

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

[/tex]

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

[tex]

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

[/tex]

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

[tex]

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

[/tex]

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Recursively enumerable predicate

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**