Recursively enumerable predicate

[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.

 

[mmwave]

Hello,

The reason why f is considered to be total in this case is because the function is defined for all inputs x. However, it may not terminate for some inputs if Q(x,y) does not hold for any y. This is why it is considered to be a partially recursive function, as it may not converge on every output.

In this case, f(x) will only equal 0 if x is an element of the nonrecursive set A. Otherwise, it will not terminate and will not have a defined output. This is why f cannot be considered to be a partial recursive function, as it does not converge on every output.

I hope this helps clarify the issue. Let me know if you have any other questions.

 

[tacman]

Hi there,

A recursively enumerable predicate is a predicate that can be checked by a Turing machine, but not necessarily decided by it. This means that the Turing machine can run indefinitely without ever giving a definitive answer. In other words, the Turing machine can "enumerate" all the possible solutions, but it may never reach a point where it can verify if a given input satisfies the predicate or not.

Now, in the case of the function f(x) \simeq \mu_{y} Q(x,y), we are essentially trying to find the smallest y such that Q(x,y) holds. However, since Q(x,y) is only recursively enumerable, there is no guarantee that the Turing machine will ever find a y that satisfies the predicate. This means that the function f(x) will also not always converge on a solution, making it a partial recursive function.

The proof you mentioned uses the fact that if f(x) were total (meaning it always converges on a solution), then it would be recursive. However, since A is an r.e. nonrecursive set, this would lead to a contradiction. Thus, f(x) must be a partial recursive function.

I hope this helps clarify things for you. Let me know if you have any further questions.