Earlier quoted context omitted.
There is some nuances here. While the general halting problem for a general Turing machine is undecidable, and with a fairly easy to understand proof as well, the computers we run today are not a general Turing machine. They are of a weaker class called Linear Bounded Automatons and for the programs they can run, the halting problem is fact decidable, on a theoretical level due to their finite nature. So we will prob…
I have to admit my knowledge of complexity theory doesn’t extend too far, but isn’t the solution to LBAs just.. brute forcing? Also, is it even decidable a priori whether a program is LBA vs requiring a tape that is not only linear function of its input?
An LBA is effectively "just" a Turing machine that has a finite tape.
A typical current computer is an LBA only if you disallow all IO of any sort or bound that IO and include it as part of the system you analyse and so fix the values which will be provided as IO, which of course is a very unusual situation, and so that constraint does not really make the halting problem more tractable in situations we usually care about.