Re:I'm Betting on HTML
by vidarh on Wednesday August 02, 2023 @07:59AM
(#36969657)
The worst case solution is just brute forcing, yes.
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.
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.