Immediately implements the Antihydra in Fractran 13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11
This is cool, could you please explain your implementation?
Why Busy Beaver hunters fear the Antihydra
61–70 of 80 posts
Re: Why Busy Beaver hunters fear the Antihydra
#62Immediately implements the Antihydra in Fractran 13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11
50/18 reduces to 25/9 right?
Re: Why Busy Beaver hunters fear the Antihydra
#63Immediately implements the Antihydra in Fractran 13122 -> 50/18, 55/42, 539/2, 297/275, 2/55, 2/11
This is cool, could you please explain your implementation?
For sure, here are the registers used for each fraction:
comp h^2 > comp H^2
comp h c > done H
comp > done c^2
done H^2 > done h^3
done H > comp
done > comp
Accumulator: comp h^8
Re: Why Busy Beaver hunters fear the Antihydra
#64Re: Why Busy Beaver hunters fear the Antihydra
#65Earlier quoted context omitted.
No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always greater than BB(N) then we can construct a Turing machine that solves the halting problem. Therefore no computable f(N) can exist.
This was the key missing part for me; the program can’t exist, whether we can prove it is beside the point. Thanks.
I think the issue is related to notion of a "direct" proof vs "proof by contradiction". What I gave was a proof by contradiction. Once you start thinking about the philosophy of proofs it, it's an interesting question to ask whether or not proofs by contradiction should really count. I don't know much about this but you can search up the term "Law of the excluded middle" is a good place to start reading about these concepts.
Re: Why Busy Beaver hunters fear the Antihydra
#66Earlier quoted context omitted.
Sure, but I only asked about the single case x=6.
If you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).
Not sure if this is a joke, but actually that is guaranteed to be true. It is proven that for all n: BB(n+1) >= BB(n) + 3. But it is not proven that BB(n+1) >= BB(n) + 4, haha.
Re: Why Busy Beaver hunters fear the Antihydra
#67The best current lower bound for BB(6) is 2↑↑2↑↑2↑↑9 (google "Knuth Up Arrow" if this makes no sense), a number so inconceivably large it gives me the willies. In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter). It r…
> best current lower bound Well is there a best current UPPER bound, or at least a "probvious" one?
There is of course not currently any upper bound on BB(6).
I find the question about a probvious upper bound more interesting - There is also not a probvious upper bound on BB(6), as this would require at least some understanding of the high-level behavior of all remaining holdout machines. However, there may soon be a 'probvious' upper bound on the value of BB(3,3) (BB for 3-state, 3-symbol machines). Up to equivalence, there are four remaining machines to decide to find the value of BB(3,3). One is a 'probviously halting' machine which will be the new champion if it halts, and for which probabilistic models of its behavior predict with high probability an exact halting time. One is a 'probviously nonhalting' machine. The two other machines are not well-understood enough to say whether they have any probvious long term behavior, but some suspect that they both 'probviously nonhalt'. If this is true it could be said that a 'probvious' upper bound exists for BB(3,3).
Re: Why Busy Beaver hunters fear the Antihydra
#68Re: Why Busy Beaver hunters fear the Antihydra
#69Earlier quoted context omitted.
It is definitely way too easy to accidentally confuse "x is true" and "x is proven to be true" on topics of undecidability, and this is one of those times where the answer is in fact obvious, but it takes you 15 minutes to realize that it's obvious. The halting problem is uncomputable (by diagonalization)--that is no computable function can solve the halting problem, rather than the weaker statement that we cannot as…
This indeed helps me! The key distinction that there is no computable function that solves the halting problem, and whether we can prove it is irrelevant, clarifies the issue. Thanks, I definitely learned something here, even if it’s obvious in retrospect.
Many of the most interesting theorems in math are obvious only in retrospect.
Re: Why Busy Beaver hunters fear the Antihydra
#70Earlier quoted context omitted.
This is cool, could you please explain your implementation?
For sure, here are the registers used for each fraction: comp h^2 > comp H^2 comp h c > done H comp > done c^2 done H^2 > done h^3 done H > comp done > comp Accumulator: comp h^8 The first two does the comparison for odd/even, the h register is moved to the H register during the comparison, then done does H += H>>2, and then keep trying. https://wiki.xxiivv.com/site/fractran.html
Thank you very much - great link too!