Re:Hypercomputation: Computing more than the Turing machine ...
by pas on Monday September 11, 2017 @05:55AM
(#15217288)
The general halting problem takes a potentially unbounded input.
That's why it's impossible to solve.
If it were finite (bounded), then you could do an enumeration of the possible programs of that bounded size, and you could make a program that simply looks up that list. (Sure, maybe the making of the list would be a bit problematic, because it'd take ... multiple eons, lesser gods would die, rise and die again during that time, but it's still finite.)
That's why it's impossible to solve.
If it were finite (bounded), then you could do an enumeration of the possible programs of that bounded size, and you could make a program that simply looks up that list. (Sure, maybe the making of the list would be a bit problematic, because it'd take ... multiple eons, lesser gods would die, rise and die again during that time, but it's still finite.)