\myheading{Halting problem}

Judging by a source code of a function, can you say, will it terminate at some point, or will it spin into an infinite loop?
Alan Turing famously proved that this is impossible (\emph{Halting Problem}).

But let's see...

Let's say, you have a very basic 8-bit CPU, like 8080 or 6502.
Say, there are only 5 8-bit registers, or 2 16-bit registers + one 8-bit register.
Not uncommon for cheap CPUs of that era.

And there is no RAM attached.
So all memory you can use is 40 bits.
This is not uncommon for geeks of the time, when RAM chips were expensive and bought after CPU.

You can simulate such a basic CPU on any decent desktop computer.
To track all states, you can use a dictionary.
Key = values-from-all-registers-including-PC, value = boolean.
The key has a size of 40 bits.
The size of the whole dictionary is $2^{40}$ bits or $2^{32}$ bytes (just 4GB of RAM).

Now you can simulate any code running on this toy CPU using your desktop computer and track all states.
When the code stops, you stop.
When you hit a state that already encountered (checked using the dictionary), you stop and report an infinite loop.

Hence, to tell if the program will stop or not, you just need a computer with bigger RAM.
To simulate a program running on your desktop computer with 4GB of RAM, you would need
a computer with at least $2^{2^{64}}$ bits of RAM.

$log_{10}(2^{2^{64}}) \approx 5.55 \cdot 10^{18}$, but still theoretically possible.

These toy CPUs and computers are in fact LBAs (Linear bounded automaton) -- a Turing machine with limited tape (or memory).

While Turing's Halting Problem is about Turing machine with infinite tape (or RAM).