3
$\begingroup$

I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set.

As an attempt to solve the problem, I could only think of a proof by construction. Without loss of generality, let the alphabet be $\Sigma=\{0,1\}$. The construction goes as follows, suppose that $TM$ $M$ recognizes an infinite computably enumerable set $L$, we can form a decidable language $D \subseteq L$ as follows:

1) lexicographically enumerate all input words $w$ in $\Sigma^*$ and repeatedly perform steps $a-b:$

a) at the $k$th step, run $M$ on input words $\{w_0,w_1,...,w_k\}$ for $k$ steps, where words $\{w_0,w_1,...,w_k\}$ are lexicographically ordered

b) if $M$ accepts an input word $w \in \{w_0,w_1,...,w_k\}$ from step 2, include $w$ in a temporary language $D_{temp}$

2) partition the words in $D_{temp}$ into two, those starting with $0$ are $\in D$, while those starting with $1$ are $\not \in D$, along with all other words $\Sigma^* - D_{temp}$.

Step (1) does not loop in a word $w$ since each run of step (1) is limited for a finite number of $k$ steps. Is this construction okay ? Or did I miss something ...

$\endgroup$
  • $\begingroup$ You have to show (1) $D$ is infinite and (2) $D$ is decidable. Try proving both properties. $\endgroup$ – Yuval Filmus Mar 10 at 12:56
7
$\begingroup$

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.

Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this contradicts the infinitude of $L$.

Furthermore, $D$ is decidable. Given a word $w$, run the enumerator for $L$, and halt whenever one of the following events happen:

  • If $w_i = w$, output Yes.
  • If $|w_i| > |w|$, output No.

Since $L$ is infinite, this algorithm will eventually stop.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, corrected. $\endgroup$ – Yuval Filmus Mar 10 at 21:15
2
$\begingroup$

Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.

| cite | improve this answer | |
$\endgroup$

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.