Why is computable function in $\Delta_{1}^0$?

Question

I am not sure why computable functions are in $\Delta_{1}^0$. Can anyone explain this?

Answer 1

Suppose that $S$ is a set of positive integers, or items which can be coded as positive integers. One definition of $\Sigma_1^0$ is that it is the set of all sets $S$ expressible in the form $$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$ A set $S$ is in $\Pi_1^0$ iff its complement, $S^C$, is in $\Sigma_1^0$, and $\Delta_1^0=\Sigma_1^0 \cap \Pi_1^0$. So, a set $S$ will be in $\Delta_1^0$ iff both $S$ and $S^C$ are in $\Sigma_1^0$.

If membership in $S$ is decidable, then there is a Turing machine $M$ which decides in a finite number of steps whether or not any given $x$ is in $S$. Then $$S=\{x\mid (\exists y)P_M(x,y)\},$$ where $y$ records a possible computation of $M$, and $P_M$ checks to see whether $y$ is a record of a legal computation of $M$ which starts from the input $x$ and ends at an accepting state. Since checking to see whether something records a legal Turing machine computation or not is simple, $P_M$ is primitive recursive. So, $S\in \Sigma_1^0$. However, also, $$S^C=\{x\mid (\exists y)P'_M(x,y)\},$$ where $P'_M$ now checks to see whether $y$ is a record of a legal computation of $M$ which starts at $x$ and ends in a rejecting state. $P'_M$ is primitive recursive for the same reason that $P_M$ was, so $S^C\in \Sigma_1^0$. Therefore $S\in \Delta_1^0$.

You can also prove that if $S\in \Delta_1^0$, then $S$ is decidable, so being $\Delta_1^0$ is equivalent to being decidable. To see this, suppose that $S\in \Delta_1^0=\Sigma_1^0\cap \Pi_1^0$. Then $$ S=\{x\mid (\exists y_1)\cdots (\exists y_r) P(x,y_1,\ldots,y_r)\} $$ and $$ S^C=\{x\mid (\exists y_1)\cdots (\exists y_s) Q(x,y_1,\ldots,y_s)\} $$ for some $r$ and $s$ and primitive recursive $P$ and $Q$. To construct a Turing machine $M$ deciding whether or not $x$ is in $S$, let $M$ successively construct each possible sequence $(y_1,\ldots,y_{\max(r,s)})$ and then test $(x,y_1,\ldots,y_r)$ with $P$, halting and accepting on success, and $(x,y_1,\ldots,y_s)$ with $Q$, halting and rejecting on success. Since one of these tests must eventually succeed, $M$ will always halt.

If $S$ is the graph of a computable function, then membership in $S$ is decidable as given any $(x,y)$, you can compute $f(x)$ and then accept $(x,y)$ if $y=f(x)$ and reject it otherwise. So, $S\in \Delta_1^0$ in this case as well.

Proving that a decidable set $S$ was in $\Delta_1^0$ depended on the fact that $M$ was always guaranteed to halt regardless of whether $x\in S$ or not. If $M$ only halted when it accepted, and otherwise might run forever, you would only have $S\in \Sigma_1^0$. Just as being decidable characterized the $\Delta_1^0$ sets, the property of being semi-decidable in this way characterizes the $\Sigma_1^0$ sets, which are also called "recursively enumerable".