Let's see, I just looked that up before. Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. So that seems a lot less worse then at first sight, but on the other hand this uses a terrible bound for the number of steps.
> Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps.
I'm following so far.
> This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit.
Perhaps I'm reading this incorrectly, but these proofs seem to assume that you're simulating the machine running step by step?
Is it proven that the only way to solve the bounded Halting problem is by running the program step by step?
If not, it seems that this is only proving a high complexity bound (i.e. that the problem is not more complex that EXPTIME), not a low bound (i.e. that the problem can be solved in less complexity than EXPTIME).
Naively it seems not to bad to me but I am totally not an expert. If you have a million bits of state, we ask if a machine will halt in a million steps, otherwise we can not be sure that the machine does not use more than a million bit of memory. This of course heavily underestimates the hardness as you can have a machine with only 20 bit that goes through a million states. This also means that the EXPTIME is not that bad because the problem size is only 20, the number of bits required to write the number of bits in the machine, not the number of bits in the machine itself.
[1] https://cs.stackexchange.com/questions/112684/halting-proble...
[2] https://en.wikipedia.org/wiki/EXPTIME