News for hackers. Stuff that matters.
Re:Linux on an 8-bit microcontroller by userbinator on Monday December 04, 2017 @06:13AM (#15843076)
Those are still predicated on having an infinite tape.

With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.

Re:Linux on an 8-bit microcontroller by adrianN on Monday December 04, 2017 @06:30AM (#15843129)
With more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"