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.
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.