Also worth noting that, from a practical perspective, even very simple programs/TMs can exhibit very complex behaviours that make it difficult to work out whether they will actually halt or not.
At the time of writing there are 2833 5 state binary TMs that haven't been decided yet:
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.
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.
Comments
Also worth noting that, from a practical perspective, even very simple programs/TMs can exhibit very complex behaviours that make it difficult to work out whether they will actually halt or not.
At the time of writing there are 2833 5 state binary TMs that haven't been decided yet:
https://github.com/bbchallenge/bbchallenge-undecided-index/b...
This comment really didn't age well https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-prov...
Ha! - I had no idea thanks
To be fair, the announcement I linked was published 2 hours after your comment. It was just perfect timing.
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.
bounded model checking is indeed a thing, but it's bounded
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.
awesome!
Apparently, there is news on this:
https://www.quantamagazine.org/amateur-mathematicians-find-f...
Not sure why that github still lists so many undecideds.