News for hackers. Stuff that matters.

A comment on Rice’s Theorem: An interactive tutorial. Parent comment

Re:Rice’s Theorem: An interactive tutorial by wizeman on Friday November 25, 2022 @12:41PM (#33744863)
> 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).

[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by danbruc on Saturday November 26, 2022 @09:35AM (#33752958)
Replied to the wrong comment.

https://news.ycombinator.com/item?id=33749430

[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by wizeman on Saturday November 26, 2022 @09:57AM (#33753148)
Interesting, thanks you! I am having a bit of difficulty understanding the exact implications in this context, but I will give it some thought.
[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by danbruc on Saturday November 26, 2022 @11:41AM (#33754144)
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.
[ Parent | on HN ]