Skelet #10 Backtracking?

Individual machines
1

https://bbchallenge.org/3810716

It looks like you all classified this TM as infinite via Backtracking. My own Backtracking implementation was not able to prove this, so either one of our codes has a bug or mine has room for improvement :slight_smile:

Do you have any stats for this run? Tree depth (max steps), max tree width, num nodes in tree? I have run this up to tree width of 1M (I’m doing BFS in order to give up early) and still it fails. If you’d like to try my code you can use:

$ time Code/Backtracking_Filter.py --infile=<(echo "1RB 0RA  0LC 1RA  1RE 1LD  1LC 0LD  --- 0RB") --steps=1_000_000 --max-width=1_000_000 --outfile=bt.out.pb && Code/Read_Record.py bt.out.pb

real	1m50.573s
user	1m48.460s
sys	0m1.511s
tm {
  ttable_packed: "\322I\231J\352\"\232!\200Q"
}
status {
  quasihalt_status {
  }
}
filter {
  backtrack {
    parameters {
      num_steps: 1000000
      max_width: 1000000
    }
    result {
      elapsed_time_us: 110473405
      max_steps: 34
      max_width: 1401613
      num_nodes: 2264641
    }
  }
}

ttable: 1RB 0RA  0LC 1RA  1RE 1LD  1LC 0LD  --- 0RB
Serialized sizes: 50 12 2 30

Which basically tells you that it ran the BFS until the width was 1.4M (34 steps) and then gave up (after exploring 2.2M nodes).

But I did write this code probably over a decade ago, so it certainly could be flawed!

2

Yep, you have found a bug in the decider :smiley:

What happens now:

  1. I believe that it is a simple implementation error so I’m correcting it now (note that, thankfully we have a proof of correctness of the method used hence remaining errors are most likely to be implementational).

  2. I will add more tests to the code to make sure it is more reliable.

  3. I will roll back the index of undecided machines to where it was before applying this backward reasoning decider.

  4. Finally, I will apply the decider again and re-update the index.

Thank you very much for your finding, it is in my opinion, one of the many reasons why collaborating on this problem is great: we get to correct mistakes and continue on.

T

3

Of course, my updated code will be available for review, but I assume that you might be very busy and potentially unavailable to check it.

4

Bug fix: Debuggin Shawn's bug by tcosmo · Pull Request #7 · bbchallenge/bbchallenge-deciders · GitHub

5

I applied the corrected decider to the DB and it decided 2,035,610 machines (more info at [Decider] Backward reasoning). In particular it has decided Skelet’s machines 18 and 25. Actually its funny but both of these machines are [Decider] Translated cyclers with higher parameters that what we looked for. Machine 18 has big “S” and Machine 25 has big “P”, with the notations of https://groups.google.com/g/busy-beaver-discuss/c/lcr_6buFz_8.

6

By curiosity I checked out all Skelet machines against [Decider] Translated cyclers, results are fun :Skelet machines that are Translated Cyclers