logoalt Hacker News

IsTomyesterday at 12:11 PM2 repliesview on HN

> particular values can be calculated

You need proofs of nontermination for machines that don't halt. This isn't possible to bruteforce.


Replies

QuadmasterXLIIyesterday at 1:01 PM

If such proofs exist that are checkable by a proof assistant, you can brute force them by enumerating programs in the proof assistant (with a comically large runtime). Therefore there is some small N where any proof of BB(N) is not checkable with existing proof assistants. Essentially, this paper proves that BB(5) was brute forcible!

The most naive algorithm is to use the assistant to check if each length 1 coq program can prove halting with computation limited to 1 second, then check each length 2 coq program running for 2 seconds, etc till the proofs in the arxiv paper are run for more than their runtime.

show 2 replies
gus_massayesterday at 1:47 PM

You can try them with simple short loops detectors, or perhaps with the "turtle and hare" method. If I do that and a friend ask me how I solved it, I'd call that "bruteforce".

They solved a lot of the machines with something like that, and some with more advanced methods, and "13 Sporadic Machines" that don't halt were solved with a hand coded proof.