0

In class I was given this problem with solution. I was hoping someone could shed some light on them.

$\underline{Question}$

Is the set K RE (recursively enumerable)?

K = { $i$ | $P_{i}$ halts on input $i$ }

$\underline{Solution}$

For j = 1 to infinity: 
    For i = 1 to j:
        Run program i on input i for j steps; if it halts, print i
    (end for)
(end for)

The solution does not seem to make sense to me since the set K is undecidable and if you can list all the elements in K then you can list all the elements in $\bar{K}$, therefore the sets K and $\bar{K}$ should be decidable by their solution.

Also, the program should not halt (or move on to the next program) if it reaches a program $i$ that does not halt. Correct?

Andrés E. Caicedo
  • 79,201
Brandon Dalton
  • 3
  • 1
    The program (call it $P $) never halts. At stage $i $, it runs $P_1$ on input 1 for $i $ steps and if $P_1$ halts, then $P $ lists 1 ( if $P_1$ hasn't halted yet, $P$ does not print 1); then it does the same with 2: runs $P_2$ on input 2 for $i $ steps, and if it halts, $P $ prints 2; and so on until doing the same with $P_i $. Once all these things happen, stage $i $ ends and $P$ starts stage $i+1$. In particular, $P$ never halts. If $P_k$ halts on input $k$ after $j$ steps, then $P$ prints $k$ infinitely often: once at each stage $n$ that is at least as large as both $k$ and $j$. – Andrés E. Caicedo Dec 09 '17 at 02:39

1 Answers1

3

That you can list $K $ does not mean you can list its complement. Perhaps the thing to note to build your intuition is that the program is not listing the elements of $K $ in increasing order. Indeed, maybe program 20 halts on input 20 but only does it after several million steps, while program 19 doesn't halt on input 19 and program 21 halts on input 21 after 2 steps. What do you do to enumerate $\bar K $? If the elements of $K $ were being listed in order it would be easy: once a number larger than 20 is listed, you would know whether 20 is in $K $ (if it was already listed) or not ( in which case you list it in $\bar K $). But the way things are, 21 is listed quickly and you wait and wait and essentially decide 20 is never going to appear, and you should list it in $\bar K $, but then it shows up. And what about 19? At what point would you list it in $\bar K $?

Andrés E. Caicedo
  • 79,201