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 @10:34AM (#33743292)
> the halting problem of Turing machines with state space of N bits

That's an oxymoron, because Turing machines have a state space of infinite bits by definition. I understand you mean "deterministic finite-state machines" rather than "Turing machines".

> It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers.

I mean, I agree that it's likely, but again, is this proven?

I'm not aware that it is and therefore I think this is actually missing many of the points I mentioned.

It could be false for all we know.

[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by rocqua on Friday November 25, 2022 @10:41AM (#33743355)
I understand you mean "deterministic finite-state machines" rather than "Turing machines".

I meant "Turing machines with X states and a type limited to Y bits, with X + Y = N". You can, of course, cast those as Deterministic Finite State Machines, but that will require incredibly many states.

[ Parent | on HN ]