Table of Contents

  1. Contribute
  2. Zoology
  3. Write deciders
  4. Write proofs
    1. Deciders
    2. Individual machines
  5. Reproduce results
  6. This website
  7. Share the story

Contribute

The Busy Beaver Challenge is a collaborative project and there are many ways in which you can contribute to it. Our reproducibility and verifiability statement outlines our philosophy regarding contributions to the Busy Beaver Challenge.

Zoology

We aim at collaboratively building a zoology of the machines of the Busy Beaver Challenge. This will allows us to understand what these machines are capable of and where complexity lies.

The zoology is collaborative and you can contribute to it on the forum.

Write deciders

Reaching the goal of the Busy Beaver Challenge requires to decide the behavior of 88,664,064 Turing machines. We hope to do this automatically by writing deciders which are programs that decide if machines halt or not.

You are invited to write deciders in order to further reduce the number of undecided machines in the seed database.

Places to look at if this task interests you:

If you write a decider for the Busy Beaver Challenge we ask that you:

  1. Read our reproducibility and verifiability statement
  2. Create a post on forum following these instructions
  3. Give the seed database’s indices of the machines that your decider has decided
  4. Write tests for your deciders against example machines and counterexample machines in the seed database

If consensus is reached that your decider is correct, it will be applied to the seed database and used to produce a new version of the undecided machines index file.

Write proofs

Deciders

As advocated for in our reproducibility and verifiability statement it is very important that deciders are proved correct.

Places to look at if this task interests you:

You can post your proofs on the thread related to the decider that you proved.

We would encourage the use of automatic proving tools such as Lean or Coq although it would be an extremely demanding endeavour.

Individual machines

It is most likely that some machine will be needed to be decided by hand. For instance, see Dan Briggs’ github about Skelet’s machines.

We collect these individual proofs on the forum. Please create a new post in this category for each proof indicating in the title the ID in the seed database of the machine that you are deciding.

Reproduce results

To increase trust in the results of the Busy Beaver Challenge it is important for independent reproduction of its results. See our reproducibility and verifiability statement.

This can for instance be done by reproducing deciders or the code that generated the seed database.

Places to look at if this task interests you:

If you reproduce results of the Busy Beaver Challenge please share about your reproduction on the dedicated section of the forum.

This website

This website is also written collaboratively, its code can be improved in many ways!

Here are some examples of missing features:

Pages like /story, /method, /contribute are also collaborative and you can submit changes on github.

Share the story

If you are interested in the Busy Beaver Challenge please don’t hesitate to talk about it around you and share https://bbchallenge.org.

If you are a teacher and would like to engage with your students on this topic some teaching material (which you can contribute to improve!) is available on the forum.

The goal of the Busy Beaver Challenge can only be achieved collaboratively.