Skelet machines that are Translated Cyclers

Note: I do not claim necessarily anything new and some people have done a lot of work on Skelet’s machines, including Dan Briggs.

By looking a bit at individual Skelet’s machines I realise that some of them are “just” [Decider] Translated cyclers which are currently still undecided because they need bigger a time threshold that what we’ve used so far in order to be detected. They have relatively big “S” and “P”, with the notation of where “P” is the size of the period and “S” the time to wait before the period begins.

So here they are the 7/43 Skelet’s machines that were found to be Translated Cyclers (hypothesis verified by running the decider individually on the machines with 10,000,000 time threshold and 500,000 memory threshold):

Unless I have a bug of course, I found it striking that different looking machines all achieve S = 24,265 and P = 91,995 its seems to resonate with some results on 4 states machines shown in (guess what, I had a bug in my reporting of P and S, I corrected it and now, values are mostly different except for P = 4,328 but machines’ diagrams look similar.)

However, we notice that these P and S are still quite small compared to the results for 4-state machines given in We expect that there are some 5-state machines with way bigger P and S, which makes us wonder about the completeness of Skelet’s list.

You can reproduce these results by running bbchallenge-deciders/decider-translated-cyclers at main · bbchallenge/bbchallenge-deciders · GitHub witht the test command:

go test -run TestSkeletMachines -v

I have not updated the status of these machines to Decided because there are so few of them. They will get decided later when we run [Decider] Translated cyclers on the entire remaining database with high thresholds (will do it when we get to let’s say < 200,000 machines left to decide).

It does looks like Dan Briggs’s proof of machine 18 agrees with this, IIUC and he also lists proofs for 2, 5, 6 and 25.

Using my Lin Recurrence (Translated Cycler) code, I am also able to classify these machines from your Skelet list. Here are my values:

  • Skelet 2: Start = 15,055, Period = 4328, Offset = -74
  • Skelet 5: Start = 15,063, Period = 4328, Offset = 74
  • Skelet 6: Start = 24,149, Period = 4328, Offset = -74
  • Skelet 14: Start = 4265, Period = 91,995, Offset = -543
  • Skelet 18: Start = 6102, Period = 1143, Offset = 19
  • Skelet 22: Start = 4663, Period = 91,995, Offset = 543
  • Skelet 25: Start = 6354, Period = 589, Offset = -23

So, it looks like the same list as you have and all the periods match (which is good :slight_smile: ). My start steps look like they are slightly earlier than yours, so maybe your algorithm is not finding the very earliest moment when recurrence starts (instead maybe you only consider it to have started after it reaches an empty part of the tape or something maybe?). Of course, you don’t need to find the earliest start step to prove they are infinite, so no really problem here :slight_smile:

1 Like

Great that we got same P!

You are entirely correct, the S that I gave corresponds to the first “record position” (a position that reached further than any positions before) of the period, which (a) is not exactly S in the best case scenario (b) could in fact overestimate S in a case where the transient regime went really far. [Decider] Translated cyclers (described here, Section 3 in more details) only detects period when record positions occur, hence in a case like scribbled under, the algorithm will not recognise the period when it first occurs, but when it starts visiting unseen positions:

Screenshot 2022-06-05 at 10.11.31

Hence, my values of S are to be ignored until I fix this.