# Whether the following are the domain of a partially computable function

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?

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

https://en.wikipedia.org/wiki/Primitive_recursive_function

• 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? – Carl Mummert Oct 25 '16 at 12:29
• Sorry, I have updated it now. – 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.
• 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. – Amrita Oct 26 '16 at 0:07
• 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. – Amrita Oct 26 '16 at 1:16
• Yeah awesome!. Just one small correction, you conclude $\{x|(\forall t)g(t)\ne x\}$ is not recursively enumerable. – Amrita Oct 26 '16 at 5:10