What I consider to be an immediate next goal at https://bbchallenge.org
is to decide unilateral and bilateral bouncing 5-state machines (such as https://bbchallenge.org/6048289
). Concretely this means to write an algorithm that recognises this behavior and prove that the algorithm is correct. We estimate that bouncers account for at least 90% of the currently remaining undecided machines. Deciding them would hopefully leave us with less than 200,000 undecided machines left.
A lot of you, I believe, have thought about this kind of machines, or have even already decided them, probably using different names such as "Chrismas trees" (I used to call them "Wedding cakes").
I would be super interested in organising a collaborative call about these machines with the goal to share our techniques and hopefully come up with a decider that is provably correct (similarly to these
). I would largely be happier with an incomplete decider (i.e. doesn't recognise all bouncers) that we can prove correct than with a complete one for which we cannot write the proof.
Would that be appealing to you? Concretly, I would propose a 2h Zoom call at a time that suits all time zones involved to collaboratively tackle this problem. From this initial call would probably come some follow up, either offline or online, to share implementations and proofs.
Given, the large number of machines that this effort will decide, it seems very worthwhile to me! Although, we are not in a huge rush and we could start this effort in a few months if it suits better.