2
$\begingroup$

suppose we don't know that Halting problem is not recursive.

I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.

Can you direct prove that complement of halting set is not r.e.??

$\endgroup$

2 Answers 2

5
$\begingroup$

HINT: If a set and its complement are both recursively enumerable, the set is ... ?

Added: This hint was for the original version of the question, which assumed that the halting problem was undecidable and did not ask for a direct proof.

$\endgroup$
9
  • $\begingroup$ :) i know that :) $\endgroup$
    – a d
    May 13, 2013 at 21:02
  • 2
    $\begingroup$ @Mehdi: Then you’re done. $\endgroup$ May 13, 2013 at 21:03
  • $\begingroup$ Can you prove that complement of halting set is not r.e. ??? $\endgroup$
    – a d
    May 13, 2013 at 21:04
  • $\begingroup$ @Mehdi: If you know that an r.e. set whose complement is also r.e. is recursive, then you’ve proved that the complement of the halting set is not r.e. $\endgroup$ May 13, 2013 at 21:05
  • 2
    $\begingroup$ @Mehdi: But you said in your question that you do know that the halting set is not recursive. $\endgroup$ May 13, 2013 at 21:08
3
$\begingroup$

For notational convention we will call the halting set $K$ and the complement of the halting set $\overline{K}$.

Definition 1: A set $S$ is recursively enumerable if and only if it is the domain of some computable partial function $f$.

Theorem: $\overline{K}$ is not the domain of some computable partial function and is, by Definition 1, therefore not recursively enumerable.

Proof: We'll try to assume as little as we can without making the proof too long. Firstly, computable partial functions are functions made up from our basic 'computational' notions, such as the notions associated with primitive recursion (identity, successor, composition, constants), $\mu $-recursion (search), etc. So each computable partial function is a finite string of our finitely many basic computational notions and therefore we can list all computable partial functions as follows:

$f_1, f_2, f_3,... f_n... $

We will now add two more definitions to clarify the ideas $K$ and $\overline{K}$.

Definition 2: The halting set is defined as $K= \{\forall x| f_x(x) \downarrow \}$, or the set of all indexes of computable partial functions which halt when given their own index as an input.

Definition 3: The complement of the halting set is defined as $\overline{K} = \{ \forall x | f_x(x) \uparrow \}$, or the set of all indexes of computable partial functions which do not halt when given their own index as an input.

Looking back at our original Definition 1, the domains of the computable partial functions constitute all recursively enumerable sets. So we will denote $W_{f_n}=domain({f_n}$) and thusly we can list off all recursively enumerable sets as follows:

$W_{f_1},W_{f_2},W_{f_3},..., W_{f_n},...$

Where $f_n(x) \downarrow$ means the computable partial function $f_n$ halts when given input $x$, one important observation regarding the above list of all recursively enumerable sets is as follows:

$ x \in W_{f_n} \Leftrightarrow f_n(x) \downarrow $

In otherwords, $x$ is in $W_{f_n} $ if and only if $x$ is in the domain of $f_n$ (and therefore $f_n(x)$ halts).

We will now notice that for any recursively enumerable set $W_{f_n} \subseteq \overline{K} $ we can find an $x$ in $\overline{K}$ but not in $W_{f_n} $. In otherwords $W_{f_n} \neq \overline{K} $. This would imply that $\overline{K}$ is not recursively enumerable.

Consider $W_{f_n} \subseteq \overline{K} $, the number $n$ will be the desired number in $\overline{K}$ but not in $W_{f_n}$. By assumption $W_{f_n} \subseteq \overline{K} $ and because $K$ is defined as $K= \{\forall x| f_x(x) \downarrow \}$ if we had $n \in K$ then we'd have $n \in W_{f_n} \subseteq \overline{K}$ or $n \in \overline{K}$ which is a contradiction. So $n \in \overline{K}$ must hold. $\overline{K}$ is defined as $\overline{K} = \{ \forall x | f_x(x) \uparrow \}$ and so if $n \in \overline{K}$ then this means $f_n$ doesn't halt when given input $n$, or in other words, $n \notin W_{f_n} $. Hence $W_{f_n} \neq \overline{K} $. Because $W_{f_n}$ was chosen arbitrarily, we can conclude that $\overline{K} $ is not equivalent with any recursively enumerable set.

$\Box$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .