Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Busy Beaver hunters fear the Antihydra

benbrubaker.com

Post reply on HN
Print view View original

71–80 of 80 posts

Re: Why Busy Beaver hunters fear the Antihydra

#71

Post by _alternator_ »

KalMann wrote: post #65
_alternator_ wrote: post #38

Earlier quoted context omitted.

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 c…

Trust me, I understand proof by contradiction :). The point I was missing was the difference between an undecidable question vs impossible. See the rest of the thread above.

Re: Why Busy Beaver hunters fear the Antihydra

#72

Post by breuleux »

KalMann wrote: post #28
_alternator_ wrote: post #21

Earlier quoted context omitted.

Ok, I read this post quite a while ago and something about the reasoning bothered me then, and it still bothers me now. In short, my read is that the argument does not rule out that there is a computable function that grows faster than BB(N), but rather it shows that it is impossible to prove or “decide” whether a given computable function grows faster than BB(N). Maybe this is equivalent to the conclusion stated? Am…

I think Scott's reasoning is correct in the end. If you suppose you had a computable function f(N) such that f(N) is always greater than BB(N). Then you could exploit the function f to solve the halting problem. Given a program of length N, run the program for f(N) steps. If it halts within that time, you know it's a halting program. If it doesn't halt within that time you know it will never halt.

But does "a computable function that grows faster than BB(N)" actually mean that f(N) is always greater than BB(N), or could it be taken to simply mean that f(N) > BB(N) for a proportion of N that trends towards 1? In other words, could you have a function that almost always upper bounds BB(N), except for a tiny (but still technically infinite) proportion of exceptions? Such a function would be larger than BB in a meaningful sense, but if the sequence of exceptions is not computable, it wouldn't be possible to solve the halting problem with it. There may be a problem with this concept, but it doesn't appear obvious to me.

Re: Why Busy Beaver hunters fear the Antihydra

#73

Post by entaloneralie »

sligocki wrote: post #62
entaloneralie wrote: post #57

Immediately 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?

Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation.

  15/6 red [green] > blue [green]
  5/2 red > blue

  red green
These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator.

Re: Why Busy Beaver hunters fear the Antihydra

#74

Post by 7373737373 »

entaloneralie wrote: post #63
7373737373 wrote: post #61

Earlier 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

Do you happen to know what the smallest/first (by some measure) Fractran program is of which it is unknown whether it halts or not? Or even undecidable?

Re: Why Busy Beaver hunters fear the Antihydra

#75

Post by entaloneralie »

7373737373 wrote: post #74
entaloneralie wrote: post #63

Earlier quoted context omitted.

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

Do you happen to know what the smallest/first (by some measure) Fractran program is of which it is unknown whether it halts or not? Or even undecidable?

I don't, sorry. I have played with rewriting systems a lot, but not within the lens of computability. One thing that I've noticed where that some rules can be inferred to be exhaustive(an exhaustive rule can be applied without searching for another rule for as long as the rule can be applied), and that a program where all the rules have less tokens on the right side than on the left side are not turing complete.

https://wiki.xxiivv.com/site/pocket_rewriting

Re: Why Busy Beaver hunters fear the Antihydra

#76

Post by sligocki »

entaloneralie wrote: post #73
sligocki wrote: post #62

Earlier quoted context omitted.

50/18 reduces to 25/9 right?

Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation. 15/6 red [gre…

I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states:

> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.

Re: Why Busy Beaver hunters fear the Antihydra

#77

Post by KalMann »

breuleux wrote: post #72
KalMann wrote: post #28

Earlier quoted context omitted.

I think Scott's reasoning is correct in the end. If you suppose you had a computable function f(N) such that f(N) is always greater than BB(N). Then you could exploit the function f to solve the halting problem. Given a program of length N, run the program for f(N) steps. If it halts within that time, you know it's a halting program. If it doesn't halt within that time you know it will never halt.

But does "a computable function that grows faster than BB(N)" actually mean that f(N) is always greater than BB(N), or could it be taken to simply mean that f(N) > BB(N) for a proportion of N that trends towards 1? In other words, could you have a function that almost always upper bounds BB(N), except for a tiny (but still technically infinite) proportion of exceptions? Such a function would be larger than BB in a me…

> "a computable function that grows faster than BB(N)"

In the context that Scott Aaronson was using it probably yes as that is necessary for the most straightforward /obvious proof to work.

Re: Why Busy Beaver hunters fear the Antihydra

#78

Post by entaloneralie »

sligocki wrote: post #76
entaloneralie wrote: post #73

Earlier quoted context omitted.

Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation. 15/6 red [gre…

I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states: > The same…

I've seen this variance used a lot in the code golfing challenges I participate in, I feel like if I called it something other than Fractran, it wouldn't be long before someone points out that this is quite like fractran and I ough to call that

Re: Why Busy Beaver hunters fear the Antihydra

#79

Post by breuleux »

KalMann wrote: post #77
breuleux wrote: post #72

Earlier quoted context omitted.

But does "a computable function that grows faster than BB(N)" actually mean that f(N) is always greater than BB(N), or could it be taken to simply mean that f(N) > BB(N) for a proportion of N that trends towards 1? In other words, could you have a function that almost always upper bounds BB(N), except for a tiny (but still technically infinite) proportion of exceptions? Such a function would be larger than BB in a me…

> "a computable function that grows faster than BB(N)" In the context that Scott Aaronson was using it probably yes as that is necessary for the most straightforward /obvious proof to work.

I am curious if there is a proof for the less obvious case, though. Could a function be greater than BB most of the time? What are the conditions, exactly?

Re: Why Busy Beaver hunters fear the Antihydra

#80

Post by throwaway81523 »

shawnz wrote: post #55
throwaway81523 wrote: post #46

Earlier quoted context omitted.

Sure, but I only asked about the single case x=6.

The point stands: the hard part is proving that all the programs with longer runtime than your upper bound will never terminate, and once you've solved that, getting the exact value is just a little extra work

For arbitrary n, that proof is arbitrarily hard, even undecidable for large enough n. Again though, for the specific case n=6, that difficulty has not yet been demonstrated, especially if you're willing to accept probabilistic arguments instead of rigorous proofs. n-by-n checkers is PSPACE-complete but the specific case n=8 that people actually play, has been completely solved using computers.
Post reply on HN