Let $f(x,t)=\begin{cases} 1 \quad \text{if Prime(x) is true }\\ 0 \quad \text{otherwise}\end{cases}$

Clearly f(x,t) is a computable predicate, since Prime(x) is primitive recursive and definition by cases is also primitive recursive.

Could we say $\{x|(\forall t)f(t,x)\}$ is recursively enumerable(r.e). It is the domain of a partially computable function. Here by partially computable function, I mean a program which computes the function which may or may not halt.

I find whenever a predicate f is computable, we could always say $\{x|(\forall t)f(t,x)\}$ is r.e. Is this true?

Could someone give a counterexample of a predicate where this is not true?

How to argue that a set is recursive or recursively enumerable?

Definition of a r.e. http://prnt.sc/9lq22b


  • $\begingroup$ You defined $f(x)$ with one input, but then you are using $f(t,x)$ with two inputs. What is $f(t,x)$? Could you please revise the question to make it more clear and direct? $\endgroup$ – Carl Mummert Oct 25 '16 at 12:29
  • $\begingroup$ Sorry, I have updated it now. $\endgroup$ – Amrita Oct 25 '16 at 23:58

Let $A$ be a recursively enumerable set which is not recursive. The complement $\mathbb N\setminus A$ is not recursively enumerable, since a recursively enumerable set with recursively enumerable complement is recursive. Since $A$ is recursively enumerable and nonempty, there is a computable surjection $g:\mathbb N\to A.$ Define a predicate $$f(t,x)=\begin{cases} 1\text{ if }g(t)\ne x,\\ 0\text{ if }g(t)=x. \end{cases}$$ Then $f(t,x)$ is computable, and $\{x|(\forall t)f(t,x)=1\}=\{x|(\forall t)g(t)\ne x\}=\mathbb N\setminus A$ is not recursively enumerable.

| cite | improve this answer | |
  • $\begingroup$ The link says h(i,x) is not computable. Also how is f(t,x) a predicate here. Do you mean $f(t,x) =1$ if it does not halt within first t steps and 0 otherwise. Could you elaborate more? In the book, I am reading they don't use Turing machines. From what I read now about these, this is just a model of computation. $\endgroup$ – Amrita Oct 26 '16 at 0:07
  • $\begingroup$ Since $f(t,x)$ is a predicate. Aren't both the same. Sorry I forgot to mention that predicates take only 1 if true or 0 if false values. $\endgroup$ – Amrita Oct 26 '16 at 1:16
  • $\begingroup$ Yeah awesome!. Just one small correction, you conclude $\{x|(\forall t)g(t)\ne x\}$ is not recursively enumerable. $\endgroup$ – Amrita Oct 26 '16 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.