5 ms·

A Busy Beaver champion derived from scratch

99 points by nickdrozd 5y ago

FartyMcFarter 5y ago
Can something really be called a Turing machine if it's not able to halt (or continue going) by itself? In this case it appears that the author considers halting to be decided externally to the program, which is not the mechanism Turing machines use.
- tetha 5y ago
  Hm. I'm not sure if you're asking what you want to ask. The definition of a turing machine is not based on the halting property at all. A turing machine is defined as a 5 tuple (if I recall right) with some structure to the tuple elements and that's it. Infinitely running turing machines are just turing machines. The halting problem is actually based around the idea of halting, or non-halting turing machines. Now, a busy beaver is defined as a turing machine which stops after making a mess of a certain size. So a TM that never stops cannot be a busy beaver by strict definition.
  - FartyMcFarter 5y ago
    What I meant is that the usual formal definition of Turing machine includes a built-in notion of halting that works as such: the machine's state + the symbol under the head decides whether it halts or not at every step (regardless of the contents in the rest of the tape). In the case of the OP's machine, this isn't the case if I understand correctly. So the OP's machine isn't really a Turing machine by the usual definition.
    - tetha 5y ago
      It does contain that definition, but non-halting is valid. The simplest definition has a set of states S, and a subset of states F called the final states. Given an input I, if the turing machine started on I, enters a state F eventually, the turing machine is considered 'halting' and accepts the input as part of it's described language, otherwise it is not. It is perfectly valid to define a turing machine with an empty set of final states. Or, in a functional sense, it is perfectly valid to define the predicate "has this halted?" as the constant false. However, all turing machines with an empty set of final states accept the empty language, and the empty language only, making them rather boring.
      - FartyMcFarter 5y ago
        As you said, machines that don't halt are offtopic, as they can't be busy beaver champions. The question I'm raising is about how halting works in Turing machines Vs the machine used in the OP.
    - Kranar 5y ago
      There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations. What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense. Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)). QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them. Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.
brilee 5y ago
a typo in the collatz description: C (2k + 1) = C (3k + 2) should be C (2k + 1) = C (6k + 4)
- mattashii 5y ago
  yes, but note that those two are the same when C (2k) is applied as well. C (2k + 1) = C (3k + 2) saves you one step of computation, which can save you a lot of time if you're applying the steps.
Y_Y 5y ago
Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in its own right, but deserves a different label, since the beaver never halts but rather gets bored and wanders off.
- robbedpeter 5y ago
  ADHD Aardvark, maybe?
  - codeulike 5y ago
    Makework Manatee?
    - Y_Y 5y ago
      Diligent Dingo
      - sdenton4 5y ago
        Prolific Pangolin Interminable Ibex Verbose Vervet
        pdpi 5y ago
        This thread reminds me of how Ubuntu has wonderfully memorable release codenames
        nathell 5y ago
        Canonical missed a great opportunity by not naming 18.04 „Busy Beaver”.
        Pet_Ant 5y ago
        That might have been a poor choice for Googleability.
throwaway81523 5y ago
Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse engineering showed that the program turns out to compute a variant of the Collatz function, where instead of C(n:odd)=3n+1, we have L(3k)=0 and L(3k+r)=L(5k+r+3). There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs), but this Collatz example doesn't satisfy that criterion. Thus the author suggests that the spaghetti conjecture is false. Discussion: the whole thing is very encoding dependent, but if you figure the BB machine on N states is randomly distributed on all the N-state machines, then for the types of encodings being discussed, for large N, the flow graph has (I think) a high chance of being complete but that is not guaranteed. So that's a reason to think the conjecture is strictly false but approximately true. The BB champ being a Collatz variant is iirc a well known approach to manually constructed BB champs. That is inspired by an old result (Conway's?) found in Jeff Lagarias's book on the 3n+1 problem. It says the generalized Collatz conjecture is Pi-0-2 complete so specific instances sound like a good place to look for functions that are on the edge of undecidability. I wonder if anything is known about the arithmetic (not computational) complexity of random programs like that. I'm imaginging e.g. Shannon's theorem that most boolean functions on N inputs require exponentially many gates to compute. The analogy would be with the likelihood of functions on some parameter, expressed as N-state programs, being Pi-0-2 complete.
- wizzwizz4 5y ago
  > we have L(3k)=0 and L(3k+r)=L(3k+r+3) L(3k+r)=L(5k+r+3)
  - throwaway81523 5y ago
    Oops, fixed.
- krick 5y ago
  I'm absolutely out of the loop and didn't even remember what a BB game is (that's why I clicked, TBH), but when reading your post the first thing that came to my mind was hydra games, as in "Goodstein's theorem". Goodstein sequences are known to reach 0, eventually (unlike the Collatz function, ironically), but that requires some absoulutely astronomical number of steps. I have no idea how complicated it is to encode, though. So, was it used in generating BBs as well?
codeulike 5y ago
So what does "colour" means with regards to Turing Machines?
- throwaway81523 5y ago
  I think it means the number of possible settings for 1 square of the tape. 2 colors = each square is either black or white, i.e. it's a binary machine.
jakear 5y ago
Great writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically: For N=0,1: the problem is trivaial/degenerate. For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish. For N=n+1: well we just proved it up till n, so it seems pretty unlikely that n+1 would be different, things don't really just suddenly change like that y'know? QED So I'm not too surprised that this conjecture is being called into question. [1]: https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjecture.html https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjec...

99 points by nickdrozd 5y ago

Can something really be called a Turing machine if it's not able to halt (or continue going) by itself? In this case it appears that the author considers halting to be decided externally to the program, which is not the mechanism Turing machines use.

tetha 5y ago
Hm. I'm not sure if you're asking what you want to ask. The definition of a turing machine is not based on the halting property at all. A turing machine is defined as a 5 tuple (if I recall right) with some structure to the tuple elements and that's it. Infinitely running turing machines are just turing machines. The halting problem is actually based around the idea of halting, or non-halting turing machines. Now, a busy beaver is defined as a turing machine which stops after making a mess of a certain size. So a TM that never stops cannot be a busy beaver by strict definition.
- FartyMcFarter 5y ago
  What I meant is that the usual formal definition of Turing machine includes a built-in notion of halting that works as such: the machine's state + the symbol under the head decides whether it halts or not at every step (regardless of the contents in the rest of the tape). In the case of the OP's machine, this isn't the case if I understand correctly. So the OP's machine isn't really a Turing machine by the usual definition.
  - tetha 5y ago
    It does contain that definition, but non-halting is valid. The simplest definition has a set of states S, and a subset of states F called the final states. Given an input I, if the turing machine started on I, enters a state F eventually, the turing machine is considered 'halting' and accepts the input as part of it's described language, otherwise it is not. It is perfectly valid to define a turing machine with an empty set of final states. Or, in a functional sense, it is perfectly valid to define the predicate "has this halted?" as the constant false. However, all turing machines with an empty set of final states accept the empty language, and the empty language only, making them rather boring.
    - FartyMcFarter 5y ago
      As you said, machines that don't halt are offtopic, as they can't be busy beaver champions. The question I'm raising is about how halting works in Turing machines Vs the machine used in the OP.
  - Kranar 5y ago
    There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations. What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense. Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)). QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them. Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.

brilee 5y ago

a typo in the collatz description: C (2k + 1) = C (3k + 2) should be C (2k + 1) = C (6k + 4)

mattashii 5y ago
yes, but note that those two are the same when C (2k) is applied as well. C (2k + 1) = C (3k + 2) saves you one step of computation, which can save you a lot of time if you're applying the steps.

Y_Y 5y ago

Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in its own right, but deserves a different label, since the beaver never halts but rather gets bored and wanders off.

robbedpeter 5y ago
ADHD Aardvark, maybe?
- codeulike 5y ago
  Makework Manatee?
  - Y_Y 5y ago
    Diligent Dingo
    - sdenton4 5y ago
      Prolific Pangolin Interminable Ibex Verbose Vervet
      - pdpi 5y ago
        This thread reminds me of how Ubuntu has wonderfully memorable release codenames
        nathell 5y ago
        Canonical missed a great opportunity by not naming 18.04 „Busy Beaver”.
        Pet_Ant 5y ago
        That might have been a poor choice for Googleability.

throwaway81523 5y ago

Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse engineering showed that the program turns out to compute a variant of the Collatz function, where instead of C(n:odd)=3n+1, we have L(3k)=0 and L(3k+r)=L(5k+r+3). There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs), but this Collatz example doesn't satisfy that criterion. Thus the author suggests that the spaghetti conjecture is false. Discussion: the whole thing is very encoding dependent, but if you figure the BB machine on N states is randomly distributed on all the N-state machines, then for the types of encodings being discussed, for large N, the flow graph has (I think) a high chance of being complete but that is not guaranteed. So that's a reason to think the conjecture is strictly false but approximately true. The BB champ being a Collatz variant is iirc a well known approach to manually constructed BB champs. That is inspired by an old result (Conway's?) found in Jeff Lagarias's book on the 3n+1 problem. It says the generalized Collatz conjecture is Pi-0-2 complete so specific instances sound like a good place to look for functions that are on the edge of undecidability. I wonder if anything is known about the arithmetic (not computational) complexity of random programs like that. I'm imaginging e.g. Shannon's theorem that most boolean functions on N inputs require exponentially many gates to compute. The analogy would be with the likelihood of functions on some parameter, expressed as N-state programs, being Pi-0-2 complete.

wizzwizz4 5y ago
> we have L(3k)=0 and L(3k+r)=L(3k+r+3) L(3k+r)=L(5k+r+3)
- throwaway81523 5y ago
  Oops, fixed.
krick 5y ago
I'm absolutely out of the loop and didn't even remember what a BB game is (that's why I clicked, TBH), but when reading your post the first thing that came to my mind was hydra games, as in "Goodstein's theorem". Goodstein sequences are known to reach 0, eventually (unlike the Collatz function, ironically), but that requires some absoulutely astronomical number of steps. I have no idea how complicated it is to encode, though. So, was it used in generating BBs as well?

codeulike 5y ago

So what does "colour" means with regards to Turing Machines?

throwaway81523 5y ago
I think it means the number of possible settings for 1 square of the tape. 2 colors = each square is either black or white, i.e. it's a binary machine.

jakear 5y ago

Great writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically: For N=0,1: the problem is trivaial/degenerate. For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish. For N=n+1: well we just proved it up till n, so it seems pretty unlikely that n+1 would be different, things don't really just suddenly change like that y'know? QED So I'm not too surprised that this conjecture is being called into question. [1]: https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjecture.html https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjec...