Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
What does $\Delta_1^0$ mean? –  Chris Eagle Feb 23 '13 at 23:59
    
arithmetic hierarchy... –  UQT Feb 23 '13 at 23:59
4  
Because both they and their complement are r.e., i.e. $\Sigma^0_1$. –  Benedict Eastaugh Feb 24 '13 at 0:11
2  
@ChrisEagle This is standard notation in computability theory; see arithmetical hierarchy. –  MJD Feb 24 '13 at 2:43

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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