5 ms·

So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 step

by avmich 4y ago

So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 steps at worst. Can't we brute force the solution? It's like 5 million seconds - or less than two months - 1 billion steps a second, which looks doable for a modest system, and we don't even need much memory...

lukevp 4y ago
I think the problem is that some of the Turing machines are infinite, so getting 47 million steps in is the _entrypoint_ and you must then run until it halts (or you determine it’s not going to halt somehow). So the search space is unbounded, but it seems like you could snapshot the state of each machine at the 47 million steps and then incrementally search a couple thousand steps forward on each one looking for halting? I may be totally off though, I won’t pretend to fully grok this.
- deleted 4y ago
  [deleted]
- avmich 4y ago
  In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)." So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
  - teraflop 4y ago
    No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts. If you simulate a Turing machine up to that many steps, and find it hasn't halted yet, then the conjecture is refuted if you know the machine's execution will eventually terminate -- but famously, there's no algorithm that can reliably tell you whether or not a given TM halts. If it was just about the maximum number of steps that could be executed by a 5-state Turing machine, it would be trivially false, because it's easy to construct a Turing machine that runs forever.
    - avmich 4y ago
      Yeah, I was surprised the statement is constructed this way. Adding condition of eventual halting - which is what makes it the busy beaver - makes the difference :) .
      - penteract 4y ago
        I think that this wording relies on carefully interpreting "before halting". A TM which runs forever can run more than 47 million steps, but it does not run more than 47 million steps steps before halting, since it never halts.
        tcosmo 4y ago
        I have changed the wording on the website in order to make it hopefully more straightforward: "This conjecture says that if a 5-state Turing machine runs for more than 47,176,870 steps without halting then it will never halt (starting from all-0 memory tape)."
  - rrss 4y ago
    > So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture No, you do not refute the conjecture if you run up to this number and a machine does not stop. Finding a machine that runs for more than 47,176,870 steps is easy - there are plenty of machines that run forever. The trick is that it needs to stop.
- daveguy 4y ago
  If you get < 47M steps out of all possible 5 state machines, they you have proven the conjecture. A 5 state requires at most 47M states. I don't know if that's an upper bound or a precise estimate, but if they all halt, it's true.
  - zaarn 4y ago
    The tape under the turing machine is infinite, so it's certainly not limited to 47M states. The conjecture states that all machines that halt will do so within 47M states.
    - schoen 4y ago
      Steps rather than states.
  - schoen 4y ago
    The 47 million thing is based on a specific machine, which was identified as the current 5-state champion in 1990 and is known to halt. https://bbchallenge.org/story#goal https://bbchallenge.org/story#goal Since nobody has found any busier 5-state beaver than that since 1990, Scott Aaronson conjectured that this might be the actual maximum for halting 5-state machines.
    - deleted 4y ago
      [deleted]
deleted 4y ago
[deleted]
schoen 4y ago
Further to what other people have said, a weird thing about the Busy Beaver is that it's eventually harder than all of mathematics. https://bbchallenge.org/story#what-is-known-about-bb https://bbchallenge.org/story#what-is-known-about-bb (People have proven in Gödel-style that eventually any given mathematical theory is not strong enough to confirm, by any method, that a specific high-enough BB value is correct.) And it famously "grows faster than any computable function". https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_function_S https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_fun... The people running this challenge believe that confirming with certainty the very next value, BB(6), probably requires answering questions that are, or are equivalent to, mathematical conjectures that humanity will never resolve. A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant which has similarly bizarre properties about it being as hard as all of the rest of mathematics to calculate digits of this number.
- tromp 4y ago
  > A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega More precisely, Chaitin's Omega quantifies the behaviour of all Lisp expressions, since he defined it not in terms of Turing machines, but in terms of a universal lisp interpreter. Not your standard lisp either, but a minimal version geared toward Algorithmic Information Theory [1]. [1] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chaitin_G_J.html https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...

by avmich 4y ago

lukevp 4y ago

I think the problem is that some of the Turing machines are infinite, so getting 47 million steps in is the _entrypoint_ and you must then run until it halts (or you determine it’s not going to halt somehow). So the search space is unbounded, but it seems like you could snapshot the state of each machine at the 47 million steps and then incrementally search a couple thousand steps forward on each one looking for halting? I may be totally off though, I won’t pretend to fully grok this.

deleted 4y ago
[deleted]
avmich 4y ago
In "Story" website section: "This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)." So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
- teraflop 4y ago
  No, you seem to be misunderstanding the conjecture. It's about the maximum number of steps executed by a Turing machine that eventually halts. If you simulate a Turing machine up to that many steps, and find it hasn't halted yet, then the conjecture is refuted if you know the machine's execution will eventually terminate -- but famously, there's no algorithm that can reliably tell you whether or not a given TM halts. If it was just about the maximum number of steps that could be executed by a 5-state Turing machine, it would be trivially false, because it's easy to construct a Turing machine that runs forever.
  - avmich 4y ago
    Yeah, I was surprised the statement is constructed this way. Adding condition of eventual halting - which is what makes it the busy beaver - makes the difference :) .
    - penteract 4y ago
      I think that this wording relies on carefully interpreting "before halting". A TM which runs forever can run more than 47 million steps, but it does not run more than 47 million steps steps before halting, since it never halts.
      - tcosmo 4y ago
        I have changed the wording on the website in order to make it hopefully more straightforward: "This conjecture says that if a 5-state Turing machine runs for more than 47,176,870 steps without halting then it will never halt (starting from all-0 memory tape)."
- rrss 4y ago
  > So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture No, you do not refute the conjecture if you run up to this number and a machine does not stop. Finding a machine that runs for more than 47,176,870 steps is easy - there are plenty of machines that run forever. The trick is that it needs to stop.
daveguy 4y ago
If you get < 47M steps out of all possible 5 state machines, they you have proven the conjecture. A 5 state requires at most 47M states. I don't know if that's an upper bound or a precise estimate, but if they all halt, it's true.
- zaarn 4y ago
  The tape under the turing machine is infinite, so it's certainly not limited to 47M states. The conjecture states that all machines that halt will do so within 47M states.
  - schoen 4y ago
    Steps rather than states.
- schoen 4y ago
  The 47 million thing is based on a specific machine, which was identified as the current 5-state champion in 1990 and is known to halt. https://bbchallenge.org/story#goal https://bbchallenge.org/story#goal Since nobody has found any busier 5-state beaver than that since 1990, Scott Aaronson conjectured that this might be the actual maximum for halting 5-state machines.
  - deleted 4y ago
    [deleted]

deleted 4y ago

[deleted]

schoen 4y ago

Further to what other people have said, a weird thing about the Busy Beaver is that it's eventually harder than all of mathematics. https://bbchallenge.org/story#what-is-known-about-bb https://bbchallenge.org/story#what-is-known-about-bb (People have proven in Gödel-style that eventually any given mathematical theory is not strong enough to confirm, by any method, that a specific high-enough BB value is correct.) And it famously "grows faster than any computable function". https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_function_S https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_fun... The people running this challenge believe that confirming with certainty the very next value, BB(6), probably requires answering questions that are, or are equivalent to, mathematical conjectures that humanity will never resolve. A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant which has similarly bizarre properties about it being as hard as all of the rest of mathematics to calculate digits of this number.

tromp 4y ago
> A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega More precisely, Chaitin's Omega quantifies the behaviour of all Lisp expressions, since he defined it not in terms of Turing machines, but in terms of a universal lisp interpreter. Not your standard lisp either, but a minimal version geared toward Algorithmic Information Theory [1]. [1] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chaitin_G_J.html https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...