> As a simple example, restricting amount of memory makes it possible to build a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources.
I feel like "finite" is doing a lot of work there.
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...