Re-constructing the seed database

Results reproduction
1

I created a project to reproduct the seed database. The enumeration, pruning, and simulation are all done in C++, with threading and comparison to the original results written in Python.

While very much a work in progress, my code generates the exact same results as those of the original repo.

1 Like
2

Great news!!! Thank you for this work!

Sorry the below is mildly relevant since I read in your repo The results I had agree with those of the original repository completely - it found the exact same 88,664,064 undecided machines as the original repository.

Feel free to ignore what I say about the hash.

Do you get the same hash of the seed database? It should be e57063afefd900fa629cfefb40731fd083d90b5e there are a few subtleties:

  1. The 88,664,064 machines are divided into 2 sets, 14,322,029 first machines exceeded time limit (47M) and the next 74,342,035 machines exceeded space limit (12k). Those two sets are put consecutively in the database and are each respectively lexicographically sorted.
  2. The DB contains a 30 bytes header whose first 13 bytes are used and the rest are 0. The header contains in order:
    a. 14,322,029: number of undecided machines that exceeded the 47M steps time limit. 4-byte big endian integer
    b. 74,342,035: number of undecided machines that exceeded the 12k cells space limit. 4-byte big endian integer
    c. 88,664,064: total number of undecided machines. 4-byte big endian integer
    d. 1: a boolean indicating that the machines were lexicographically sorted. The first 14,322,029 undecided machines (47M time limit exceeded) were lexicographically sorted independently of the next 74,342,035 undecided machines (12k space limit exceeded). 1-byte boolean

Don’t hesitate if I can provide further help and thank you very much for putting the effort!

3

I browsed through your repo, impressive work!

With respect to the pruning, note that the methods implemented in bbchallenge are exactly those described in [Marxen and Buntrock, 1998]: Heiner Marxen - Attacking the Busy Beaver 5 (look for “There are further equivalence classes of medium importance, e.g:”).

Thank you very much again for this dedicated work.