Re:Did Turing prove the undecidability of the halting problem?
by jononor on Tuesday July 02, 2024 @08:19AM
(#40855899)
That is a much lower complexity grade than I thought we would struggle with. Especially since we have decades of experience in solvers for rather large Boolean Satisfiability Problems, which seems like it could be adapted here.
[ Parent
| on HN ]
Re:Did Turing prove the undecidability of the halting problem?
by kragen on Tuesday July 02, 2024 @08:36AM
(#40856026)
bounded model checking is indeed a thing, but it's bounded
Re:Did Turing prove the undecidability of the halting problem?
by arethuza on Tuesday July 02, 2024 @09:11AM
(#40856305)
A few months back I spent a couple of hours writing a binary TM simulator (yes I know you can download them - I wanted to write one) and then spent a couple of weeks running various TMs for days on end...
They exhibit quite bizarre amounts of complexity for what are really simple structures - indeed some TMs have apparently been observed employing Collatz conjecture type behaviour.