There was some chatter on Discord with interest in seeing BB(6) holdouts. Here is my list of holdouts ~1.5M TMs. It includes all of my filters (those described in Shawn's Holdouts and also CPS). I think the biggest thing it is missing is the “new and improved” CTL stuff.
1 Like
Quick start for “new and improved” CTL stuff: unpack attached files and…
[justinb@husk beaver6]$ ./make_seed_db.py
[justinb@husk beaver6]$ git clone -q -b finite-automata-reduction https://github.com/UncombedCoconut/bbchallenge-deciders.git
[justinb@husk beaver6]$ cd bbchallenge-deciders/decider-finite-automata-reduction/
[justinb@husk decider-finite-automata-reduction]$ patch -p2 < ../../use_6_states.patch
[justinb@husk decider-finite-automata-reduction]$ cargo run -r -q -- -d ../../bb.6x2.unknown.db
494383+ 964321 █████████████████████████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ All Deciders: 00:31:10
1458704/ 1458704 ~00:00:00 ██████████████████████████████████████████████████████████████████████████████████████████████████ direct-1 : 00:00:16
1367694/ 1367694 ~00:00:00 ██████████████████████████████████████████████████████████████████████████████████████████████████ direct-2 : 00:00:52
1226203/ 1226203 ~00:00:00 ██████████████████████████████████████████████████████████████████████████████████████████████████ direct-3 : 00:05:27
597054/ 1073630 ~00:22:42 ██████████████████████████████████████████████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ direct-4 : 00:24:34
Etc.
The decider’s README gives instructions for using multiple CPUs or a cluster. It is also probably right to suggest --features=sink_heuristic by default, but no heuristics are really tested on BB(6).
When done, ./export_lists.py in the original directory can… well, you know.
export_lists.py (582 Bytes)
use_6_states.patch (832 Bytes)
make_seed_db.py (902 Bytes)
By request, I tried running @TonyG’s bouncers decider in this setting, but I failed – it hit an internal assertion I’m not comfortable trying to debug.
[Edit: fixed a dumb mistake involving DB-read size, and since the new error matches the one caused by incorrect DB handling, there may be more where that came from.]
bouncers_6_states.patch (3.5 KB)
[justinb@husk beaver6]$ git clone -q https://github.com/TonyGuil/bbchallenge.git TonyG
[justinb@husk beaver6]$ cd TonyG/
[justinb@husk TonyG]$ patch -p1 < ../bouncers_6_states.patch
patching file Bouncers/Bouncer.cpp
patching file Bouncers/BouncerVerifier.cpp
patching file bbchallenge.h
[justinb@husk TonyG]$ cd Bouncers/
[justinb@husk Bouncers]$ c++ -Wall -O3 -march=native -oDecideBouncers DecideBouncers.cpp BouncerDecider.cpp Bouncer.cpp -lboost_thread
[justinb@husk Bouncers]$ python -c 'import os; open("all.umf", "wb").writelines(i.to_bytes(4, "big") for i in range((os.path.getsize("../../bb.6x2.unknown.db")-30)//36))'
[justinb@husk Bouncers]$ ./DecideBouncers -D../../bb.6x2.unknown.db -Iall.umf -Uout_100K.umf -T100000 -S5000
nThreads = 4
#96: Error at line 490 in CheckTapesEquivalent
The output means: it got to TM index 96 before it failed to violate a technical condition,
// Check that the repeater segments overlap by at least the length of one
// repeater (this ensures that we can insert more repeaters into the segment
// and the two descriptors will still be equivalent)
and died.
The patch I used is attached for reference – though, per the above, it doesn’t work.
This is line 530 of BouncerDecider.cpp:
if (RepeaterCount < 5) continue ;
I fixed the problem with machine #96 by changing the magic number 5 to 9 (and machine #96 is indeed a Bouncer). But now it gives the same error at machine #8532. So it looks like I need to do this properly.
I’m more amused than I should be that this line is under suspicion – a hard-coded “5” blamed, but not at all for the reason one would expect. (Naturally, I’d looked at it, but I let it go after seeing it wasn’t a “5” I was looking for. I did realize that I didn’t understand the acceptable-repeater condition, though.)
If this means a trial-and-error heuristic for drawing the wall-/repeater-transition boundaries survived BB(5) and is only now breaking down, that’s remarkable.
That 5 was the smallest that I could make it without breaking a BB(5) machine, so I’m not at all surprised that it’s not enough for BB(6). However…I need to buckle down and do this more intelligently.
I ran all these machines for half a million steps, and 440 of them halted! Here is a list. Each line contains the (zero-based) machine index followed by the number of steps before halting:
BB6_Halters.txt (6.9 KB)
The shortest time to halt is 27627 steps, by machine 650181 (machine code 1RB1RA_1LC0RA_1LD0LC_0LE0LB_1RF1LF_1RD—). This is short enough that you can see it in the simulator.
2 Likes
I have managed to get my Bouncers decider to check all these machines (with TimeLimit=100,000). It takes about three hours, and decides 63506 out of 1458704 machines. I added a new Decider type 100, for machines that halt; the verification info is just the number of steps before halting. Unfortunately I forgot to tell the Decider to count halting machines separately from Bouncers, so some of those 63506 machines will be Halters, not Bouncers. (Not 440 of them, because 100,000 != half a million.) I will run it again tonight to get the figures.
The Decider works for 5-state machines with a binary machine spec (from the seed database file), and 5- and 6-state machines with an ASCII spec (from a text file or the command line). I had to modify bbchallenge.h to do this, so none of my other deciders (Cyclers, Translated Cyclers, Halting Segments, FAR) works now. But making the required modifications is not difficult, and I’ll try and get round to it in the next few days, so that I can update them all at once.
Update: 89 of those 63506 machines are Halters, leaving 63417 Bouncers. The DVF file is 184MB, so I can’t post it here. Here is the UMF file:
BB6_100K.umf (5.3 MB)
Also, I ran the machines for two million steps, and the number of Halters increased to 641:
2M_Halters.txt (10.1 KB)
@mateon1 used an accelerated simulator to check for halters in 20 million steps, results here: https://cdn.discordapp.com/attachments/1084047886494470185/1089634011502084126/bb6.halters.20M.txt
I’ve updated my little export_lists.py script to break Shawn’s file down into halters, bouncers, otherwise CTL decided, and undecided. At this moment that leaves 213,163 undecided.
export_lists.py (1.4 KB)
Ran Translated Cycler detection out to 10M steps and here are the results:
- Input: 214163
- Halt: 58
- Infinite: 32254
- Unknown: 181851
in.txt.gz (1.6 MB)
halt.txt.gz (1.0 KB)
inf.txt.gz (518.5 KB)
unknown.txt.gz (1.8 MB)