5 ms·

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 wheth

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/blob/main/bb5_undecided_machines.csv https://github.com/bbchallenge/bbchallenge-undecided-index/b...

jononor 2y ago
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.
- kragen 2y ago
  bounded model checking is indeed a thing, but it's bounded
  - arethuza 2y ago
    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.
    - kragen 2y ago
      awesome!
SkiFire13 2y ago
This comment really didn't age well https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-prov...
- arethuza 2y ago
  Ha! - I had no idea thanks
  - SkiFire13 2y ago
    To be fair, the announcement I linked was published 2 hours after your comment. It was just perfect timing.
ted_dunning 2y ago
Apparently, there is news on this: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ https://www.quantamagazine.org/amateur-mathematicians-find-f... Not sure why that github still lists so many undecideds.

jononor 2y ago

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.

kragen 2y ago
bounded model checking is indeed a thing, but it's bounded
- arethuza 2y ago
  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.
  - kragen 2y ago
    awesome!

SkiFire13 2y ago

This comment really didn't age well https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-prov...

arethuza 2y ago
Ha! - I had no idea thanks
- SkiFire13 2y ago
  To be fair, the announcement I linked was published 2 hours after your comment. It was just perfect timing.

ted_dunning 2y ago

Apparently, there is news on this: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ https://www.quantamagazine.org/amateur-mathematicians-find-f... Not sure why that github still lists so many undecideds.