Why is the set $K$ recursively enumerable?

Question

I am trying to understand why the set $K=\{i \mid M_i(i) \;\mathsf{halts}\}$ is recursively enumerable, where $M_i(i)$ is a Turing machine that is given its own index (in the standard enumeration of Turing machines) as input ("the halting problem").

If we cannot determine if $M_i(i)$ halts, how could we even produce the set $K$ in the first place? If $K$ were recursively enumerable, we could have a Turing machine $M_K$ that takes this set as input and outputs a list of all of its elements. But if this were the case, the halting problem would be solvable because of the fact that all of the elements of $K$ are known in the first place.

I am obviously missing a big point here. What am I missing?

Answer 1

You're misunderstanding what "recursively enumerable" means. If taking the set as input were allowed, then everything would be recursively enumerable (or nothing noncomputable would be, if you require the input the be computed first) because given a set $X$ as input, enumerating its members is as simple as reading them off.

A set $S$ is recursively enumerable if there is a Turing machine $M_S$ which, given no input, lists out the members of $S$. In this case, the halting set can be enumerated by the following process:

At stage $0$, start $M_0$ running on input $0$.

At any stage $s > 0$, start $M_s$ running on input $s$, and advance each machine started at an earlier stage by one step. If there is an $M_i$ for $i < s$ so that $M_i$ just now halted, output $i$.

This process enumerates the members of $K$, in no particular order. It's still difficult to tell whether a given $n$ is in $K$; if it is, it'll eventually show up, but if it isn't we'll never be sure of that.

Answer 2

Just because you have a machine that outputs the elements of $K$ doesn't mean they "are all known".

The problem is that $M_K$ does not necessarily output the elements in order, so just observing the run of that machine will never allow you to conclude that some number is not in $K$. You can fun the machine for a year and notice that your favorite number has not yet been output, but you can't know whether it will be output next week, or in another year, or a century -- or, indeed, never at all.

This is THE difference between "decidable" and "recursively enumerable".