Halting problem without input?

Question

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!

Answer 1

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.

Answer 2

Any program and input pair can be converted to a program without input by just including the input in the program, so if the halting problem is decidable for programs without input, then it is decidable for all program and input pairs.

Answer 3

Actually, the halting problem is the problem where you're given an Turing machine description and an input, and you need to determine whether that Turing machine halts on that input. It doesn't matter that your "Goldbach checker" program doesn't take an input. Instead of calling it "a program that doesn't take an input", just call it "a program that ignores its input and checks Goldbach's conjecture regardless of what input it's give." It's perfectly valid to ask if the Goldbach checker halts when given input "Hello, Frank."