> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it.
This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible.
On the other hand knowing a little bit about the program already can make this statement not apply. As a simple example, restricting amount of memory makes it possible to construct a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources.
Real life programs are even easier to work with. Consider a CPU that increments a separate register for every executed instruction and terminates when the register overflows. We can easily tell that every program running on that CPU has to terminate.
As you see, it is rather silly to use general mathematical properties of programs and apply them to real life programs without considering for how real life programs are different from mathematical concepts. Real life programs are not spherical cows in vacuum, they don't have infinite time and memory to execute and the CPUs executing them are not perfect Turing machines.
I feel like "finite" is doing a lot of work there.
So, read it the following way:
Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use.
Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just look at Busy Beaver function to appreciate how quickly this grows with amount of available memory: https://en.wikipedia.org/wiki/Busy_beaver
Basically, Busy Beaver function tells how long a program, given an amount of memory, can execute and still terminate.
This fantastic function is my favorite function if we ever play a game of "who can think a function that grows faster".
As a corollary, since every real life program has finite memory, it is not possible to construct a non-terminating program that will not repeat its output. Knowing this you just construct a simple program that looks for cycle in the program state.
You could think about this way: hardcoding a constant (moving it from heap to compiled code) doesn't magically cause the program to use less memory.
Thinking it in a different way, from purely physical point of view, every bit of information can be translated to some minimum amount of energy or mass (mass energy equivalence).
Since state ("state", not "possible states") of Turing machine is bits of information, you can't have a Turing machine with infinite size of state. Now, "possible states" are capped because if the state is finite in size, the number of possible states is less or equal than all permutations of it (permutations == possible states).
It is largely philosophical question which is "memory" available to the program and which is "Turing machine state". In case of real programs we see that memory can be reassigned depending on requirements.
There are some cases when the distinction becomes important in reality. Consider a trained AI that gets "baked in" and shipped to the user to compress/decompress images.
Let's say it does fantastic job at compression and decompression but takes 2GB of disk storage and memory when executing.
If you just compress a single small image you realistically need to send 2GB of the AI plus the very small image, but when you have billions of images this static cost of the AI gets amortized.
The same way happens when you run any real program on an operating system. In reality the program is much larger because even if it prints Hello World it still needs to do a bunch of data like recognize your monitor it is talking to. We conveniently package the common parts of the program as "Operating System" and then just let exchanging the small part that will make sense when coupled with correct OS.
That's also how you can have very small webpage that takes GBs of memory to execute... sadly...
It started to sound like "I read one Wikipedia article on the halting problem, so I'm a computer scientist...Allow me to show you how I am smarter than all of my colleagues who are only scientists."
To make it more concrete, if you take a bunch of heuristics like scanning for while(true) {}, scanning whether there are any loops at all, discarding primitive foreach loops that have a linear relationship to the input data amount, etc, you have built a rudimentary halting problem decider that has 3 outputs: "will halt", "won't halt", "I don't know". You can make it better with lots of research, SAT3 solvers, etc, but ultimately you will have to accept that there will always be programs that the decider will output "I don't know" for.
When you can make assumptions about a program and its inputs, the halting problem doesn't apply. I mean, just simple observation shows that if you can't make whether your program terminates a condition inside your program, then the halting problem ambiguity as stated can't apply -- you may still not be able to determine if it halts or not, but with enough constraints or assumptions that can be taken as true, you absolutely can know if your program halts or not without executing it.
I'd be more inclined to replace it with "any non-trivial" in this case.