Computable sets and Halting problem

 A set A ⊆ Z is computable if there is an algorithm for deciding membership in A.

Deciding membership in $A$ means algorithm should respond back Yes/No for the given input element.

First thing to notice is that any computable set is listable. Listable set implies there is an algorithm that prints $L \in \mathcal{Z}$. Then, checking if a given input is there in the $L$ is simple. 

However, not very clear if every listable set is computable.

Assume for a moment, that the algorithm is very complicated and takes long time to output list elements. For example, say it takes a day to print each element of the list. Then, for a given integer say $42$, if the algorithm didn't print that yet, it is impossible to say if it will print this at all.

Once we agree that every listable set is not computable, next step is to see if we can identify listable sets that are not computable.

This leads to Halting problem:

Halting problem asks a simple question. Given a program $p$ and an input $x$, the question Halting problem seeks is can $p$ terminate or will it continue for ever?

Say our program $p$ is

while (true) {

    do something;

}

This is an infinite loop. Our Halting algorithm (if we can build one) returns NO to the question if $p$ terminates.

Similarly if $p$ is the following expression in Mathematica,

FindInstance[k == x^3 + y^3, {x, y}, PositiveIntegers, 2]

Our Halting algorithm returns YES to the question if $p$ terminates for $k=1729$.

Theorem: The halting problem is undecidable.

Proof is clever. Since, halting problem takes as input a program $p$ and input $x$, say we do have a program $A$ which returns true if $p$ halts and false otherwise.

Since, the universe of inputs is any possible program one can conceive, I can write a devilishly cunning program ($DCP$) that runs forever while indicating to $A$ that it will terminate and vice-versa.

Then, $DCP($A$) returns true while running forever and false while terminating which is a contradiction. This proves that the halting problem is undecidable.

Corollary identifies a set $A$ consisting of $2^p3^x$ such that program $p$ halts on input $x$. By above theorem, $A$ is not computable. However $A$ is listable.

The following algorithm shows how to make $A$ listable.

For input $N=0,1,2...$ and during iteration $N$, 

foreach $p$

    run $p$ on input $x \leq N$ in $N$ steps

    print $2^p3^x$ if program terminates within these $N$ steps.