# Recursively enumerable predicate

1. Dec 20, 2007

### twoflower

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 $\psi$ is partial recursive, but if

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

then $f$ (total) [Why is $f$ 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 $f$ is total and thus from my point of view there is no contradiction if $f$ were partial recursive.

Thank you for any suggestion, I'll be thankful for anything.