# Intuitve Proof that the halting set is recursively enumerable

I am trying to understand intuitively how the halting set $$K := \{(i, x) \mid$$ program $$i$$ halts when run on input $$x\}$$ is recursively enumerable.

Is there a simple explanation which says why this is? I'm not looking for a proof or anything that contains too many technical terms. One way that I was told to think about it was if you plot Turing machines on the $$x$$-axis and time on the $$y$$-axis, you can sort of think about in a diagonalization proof sort of way. I might have missed something and I want to fully understand this way of thinking.

• The relevant "diagonalization" idea is often called dovetailing Commented Jan 13, 2022 at 3:32

Consider the program which takes a pair $$(i,x)$$ and runs program $$i$$ on input $$x$$. The set of pairs $$(i,x)$$ for which this program halts is precisely $$K$$, so $$K$$ is recursively enumerable.
The key idea is that we can recursively simulate steps in the operation of a Turing machine program on a given input. So to list out the elements of $$K$$ first we can look at the source code for program 1 and simulate 1 step of its operation on input $$x$$. Next we can also look at the source code for program 2 and simulate 2 steps of operation of both programs 1 and 2 on input $$x$$. And so on, at stage $$n$$ simulating $$n$$ steps of operation of each of programs $$1\ldots n$$ on input $$x$$. At any stage if a program halts on the input, we spit it out in the list.