[Solved]: Halting problem without input?

Problem Detail: 

I'm only a layman therefore only discuss stuff naïvely.

I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able to solve some unsolved mathematical problems. We could write some brute-force programs to check Goldbach conjecture, say, and then throw it into the decider to see what happens. Then he refers to halting problem to say that such kind of dream is not possible.

However I notice that there's difference between halting problem and his scenario. Such a brute-force checking program has nothing to do with input data, but for halting problem, we assume the decider to check for every input. So I wonder whether halting problem without input is also undecidable?

I googled and found this. Personally I think it's wrong and couldn't be corrected because of self-reference.

Thanks for your help!

Asked By : Frank Science

Answered By : Yuval Filmus

Here is a different proof using Berry's paradox instead of the liar paradox. Suppose that the halting problem (for programs with no input) were decidable. For each $n$, let $f(n)$ be the smallest number which cannot be computed by a program of length at most $n$ (without inputs). Consider the following program for computing $f(n)$:

Go over all programs of length at most $n$, and for each one that halts, store the number it computes. Output the smallest number not encountered in this way.

This is computable since we can solve the halting problem for the relevant programs, and so we can determine which programs halt. What is the length of this program? The code itself is fixed apart from the length $n$, which can be encoded using $2\log n$ bits. All in all, this program has length $2\log n + C$ for some constant $C$. For large enough $n$ we have $2\log n + C \leq n$, and so there is a program of length at most $n$ which computes $f(n)$! This cannot be, and we are forced to conclude that the halting program is not computable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49281