In reality, this was not an impossible program to make, in terms of real life computers. |
Yes it is. Boundedness has nothing to do with the halting problem.
Even if you give someone a
specific program, if it is sufficiently complex you cannot solve the halting problem.
A lot of the problem depends on how you define things, too. For example, does the following program terminate?
1 2 3 4 5 6
|
#include <iostream>
int main()
{
std::cout << "Hello world!\n";
}
|
The C++ Standard tries to guarantee that it will, in fact, halt, because the program is allowed to continue to termination after simply
submitting the text to the output device.
But the OS may never finish executing the program. Or refuse to return control to it until the text actually has printed on the console. The problem with this restriction is that it unreasonably adds extra variables into the execution of the program. So, we discard those possibilities. We assume that the OS is a good doggie and always returns to play.
Therefore, we'll consider this an example where the halting problem can be solved.
Now take the code to Minecraft. Does it halt? Write an algorithm that proves it will. (Without crashing, mind you.) Even if the OS and network and everything else that works with it behave perfectly, and discounting radioactive decay and things like the sun exploding, it it is
possible that program can never terminate. Isn't it?
Now, write a program that proves that Minecraft will terminate at some point. You can't. Not even for that one
specific program.
That's the halting problem.
Hope this helps.