News for hackers. Stuff that matters.

A comment on Did Turing prove the undecidability of the halting problem?. Parent comment

Re:Did Turing prove the undecidability of the halting problem? by arethuza on Tuesday July 02, 2024 @06:28AM (#40855207)
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...

[ Parent | on HN ]
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
[ Parent | on HN ]
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.

[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by kragen on Tuesday July 02, 2024 @09:12AM (#40856311)
awesome!
[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by SkiFire13 on Tuesday July 02, 2024 @11:17AM (#40857495)
This comment really didn't age well https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-prov...
[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by arethuza on Tuesday July 02, 2024 @12:01PM (#40857934)
Ha! - I had no idea thanks
[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by SkiFire13 on Saturday July 06, 2024 @03:27AM (#40888752)
To be fair, the announcement I linked was published 2 hours after your comment. It was just perfect timing.
[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by ted_dunning on Tuesday July 02, 2024 @01:29PM (#40858739)
Apparently, there is news on this:

https://www.quantamagazine.org/amateur-mathematicians-find-f...

Not sure why that github still lists so many undecideds.

[ Parent | on HN ]