Lin recurrence periods

[Nicholas Drozd]

Lin recurrence is the periodic repetition of a certain behavior on the tape, either in place or off to one side or the other. We say that a program enters into Lin recurrence after step S with a period of length P.

Two Busy Beaver-like questions we can ask are: what are the greatest possible values of S and P for a given program class?

The lowest possible value for P is 1. This is the P that accompanies all the highest values of S that we have (namely the current BBB champions). So as far as anybody knows, the best way to maximize S is to minimize P.

What is the highest possible value of P? That is, what is the longest possible Lin recurrence period for a given program class? Call this function BBP. Of course, it is uncomputable. In fact it is equicomputable with the classic Busy Beaver function BB, in the sense that either one can be calculated given a solution for the other. But apparently BBP is strictly faster-growing than BB.

BBP(2, 2) = 9
BBP(3, 2) = 92

What about BBP(4)? Last year Boyd found a program that enters into Lin recurrence after 7,170 steps with a period of 29,117. Can we do any better? Indeed we can. I ran Shawn's LR detector, which is remarkably fast, against a list of 4-state 2-color holdouts and three programs showed up each with a period of 88,381:

   |------------------------------------+--------+--------|
   | Program                            | Start  | Period |
   |------------------------------------+--------+--------|
   | 1RB 0LA  0RC 1RD  1LA 0LD  1LC 0RD | 73,906 | 88,381 |
   | 1RB 0RC  1LD 0RB  1RA 0LC  0LA 1LC | 58,076 | 88,381 |
   | 1RB 0LA  1RC 0RA  1LD 0RC  0LB 1LA | 57,810 | 88,381 |
   |------------------------------------+--------+--------|

Three programs with exactly the same long period -- what a coincidence! Except if you look close, you can see that they are really the same program, just started from different states.

In any case, we seem to have BBP(4, 2) = 88,381. Never say never, but at this point I would be fairly surprised to see that improved.

On the 2-state k-color side, we have BBP(2, 3) = 60 (again, with two witnesses that are rotations of each other) and BBP(2, 4) >= 298,438. I wouldn't be surprised if that could be improved.

It would be interesting to know the true relationship between BBP and BB.

[Shawn Ligocki]

Cool! That's quite a long period!

Quick computation tip FWIW: running "Code/Lin_Recur_Detect.py" with "--no-min-start-step" will provide a big speedup. Basically, the way I find min start step is super inefficient. Running locally, I see 4s for your current 4x2 champion with start step calculation and 0.5s w/o.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CABAiW0rNhQGh1YCm%2BKurp%2BkP6soDn8-tjC1htfAezoVkgbqPBA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Shawn Ligocki]

Interestingly, unlike Boyd's machine, these ones are "fully structured" ... that said after analyzing it a bit it looks pretty chaotic :)

On Tue, Mar 29, 2022 at 12:18 PM Nicholas Drozd <nichol...@gmail.com> wrote:

--

[Shawn Ligocki]

Nick, I have extended the search out to 16M steps and have not found any larger periods. Specifically, I can concretely say that, among 4x2 TMs which enter Lin Recurrence on or before step 8,388,608 (2^23) and which also have period <= 8,388,608, the TMs with longest periods are:

1RB 0RD  1LC 0RB  0LA 1LD  1RA 0LD   | Lin_Recur 88381 461 <131072

1RB 0LA  1RC 0RA  1LD 0RC  0LB 1LA   | Lin_Recur 88381 461 <131072

1RB 0LA  0RC 1RD  1LA 0LD  1LC 0RD   | Lin_Recur 88381 -461 <131072

1RB 0RA  1RC 0RB  1LD 1LC  1RA 0LC   | Lin_Recur 29117 525 <32768

1RB 1LB  1RC 0LD  0LA 1RA  0LB 0RA   | Lin_Recur 25506 44 <524288

1RB 0LD  0LC 1RC  1RA 1LA  0LA 0RC   | Lin_Recur 25506 44 <524288

1RB 1LD  1LC 0LD  1RC 1RA  0LB 0RA   | Lin_Recur 17620 -118 <262144

1RB 0RD  1LB 1LC  1LA 1RD  0RA 0LC   | Lin_Recur 17620 118 <262144

1RB 1RA  1LC 0LD  1RA 0LB  0LB 0RA   | Lin_Recur 11528 -118 <131072

1RB 0RD  1LC 0RA  1LA 1LC  0RA 0LC   | Lin_Recur 11528 118 <131072

1RB 0LC  1RC 1RB  1LA 0LD  0LC 0RB   | Lin_Recur 11528 -118 <131072

1RB 0RA  0LC 1RD  0LD 1LC  1RA 0LA   | Lin_Recur 8109 85 <262144

1RB 0LB  1RC 0RB  0LD 1RA  0LA 1LD   | Lin_Recur 8109 85 <32768

1RB 1RC  1LC 0LD  1RA 0LB  1LC 0RC   | Lin_Recur 7583 75 <8192

1RB 0RD  1LC 0RA  1LA 1LB  1RB 0LB   | Lin_Recur 7583 -75 <16384

1RB 0LC  1RC 1RA  1LA 0LD  1LA 0RA   | Lin_Recur 7583 75 <8192

1RB 0LB  1LC 0RD  1LD 1LB  1RB 0RA   | Lin_Recur 7583 -75 <16384

1RB 1RA  0RC 0LB  0RD 0RA  1LD 0LA   | Lin_Recur 5588 106 <32768

1RB 0RD  0RC 1RB  1LD 0RC  1LA 0LC   | Lin_Recur 5479 87 <8192

1RB 0LD  1LC 0RC  0LA 1LA  0RD 0RB   | Lin_Recur 5360 -10 <8192

(I added this to my github at https://github.com/sligocki/busy-beaver/blob/main/Machines/lin_recur_period/4x2 )

The columns to the right of "Lin_Recur" in this file mean LR period, offset (- is left, + is right) and upper-bound of start-step (technically this is the smallest power of 2 >= max(period, start_step)).

All TMs are only considered in TNF (Tree Normal Form) and only TMs A0 -> 1RB are considered. If you allow A0 -> 0RB, you cannot get any increase in period, but you can get a slight increase in start-step. Ex: 

0RB 1RD  1LC 0LD  1RA 0LC  1LB 0RD

Has period 88381, offset -461 and start_step 58077 (It is just another permutation of the top machine I listed above with start state C).

This search tool 10 hours running serially on my laptop using a new lr_enum C++ program (which looks to be ~400x faster than the Python Lin_Recur_Detect.py I used previously). You can find the code to build and run yourself at https://github.com/sligocki/busy-beaver/tree/main/cpp . I ran it as:

$ lr_enum 4 2 10000000 4x2.lr.txt 4x2.unknown.txt

which puts all the Lin Recurrent 4x2 TMs in 4x2.lr.txt and the unknown (not halting nor Lin Recurrent) in 4x2.unknown.txt (Code is potentially in flux as I hack on it)

Among other things, here is a distribution of # TMs discovered to be Lin Recurrent at each cutoff:

max(period, start_step)	Additional # TMs
1	2
2	48
4	26,856
8	854,225
16	1,365,738
32	313,480
64	39,302
128	7,608
256	1,898
512	520
1,024	147
2,048	57
4,096	36
8,192	17
16,384	10
32,768	5
65,536	0
131,072	11
262,144	3
524,288	3
1,048,576	1
2,097,152	0
4,194,304	0
8,388,608	0

The 1 TM found at the 1,048,576 cutoff is

1RB 1LA  0RC 1RC  1LD 0RB  0LD 1LA

with period 104, offset +8 and start_step 586,388

which is AFAIK, the second largest known contender for maximum Lin Recurrence start_step (I think Nick calls this BBLR). The champion is still the current reigning BBB(4, 2) champion Nick announced in July 2021:

1RB 1LD  1RC 1RB  1LC 1LA  0RC 0RD

which "Spins out" after 32779478 steps (in other words: period 1, offset -1, start_step 32,779,478)

Cheers,

-Shawn

On Tue, Mar 29, 2022 at 12:18 PM Nicholas Drozd <nichol...@gmail.com> wrote:

--

[Shawn Ligocki]

I ran a search for long LR Period machines in 2x4 space out to 138M steps (detecting all machines which have both start-step and period <= 67,108,864). The top machines so far are:

1RB 2LB 0RA 1LA  2LA 3RA 0LB 2LA   | Lin_Recur 33209131 39579 <67108864

1RB 0RA 3LB 1RB  2LA 0LB 1RA 2RB   | Lin_Recur 33209131 -39579 <67108864

1RB 3LB 2RB 0RA  2LA 3LA 0LB 1RA   | Lin_Recur 12611018 -7048 <16777216

1RB 2LA 3LB 0RB  0LA 3LB 2RA 1RB   | Lin_Recur 2230034 -720 <8388608

1RB 2LA 3LA 0LB  1LA 2RA 3RB 0RA   | Lin_Recur 1595511 -1257 <8388608

See top 20: https://github.com/sligocki/busy-beaver/blob/main/Machines/lin_recur_period/2x4

So, once again, it looks like multi-symbol has proven more powerful than multi-state by a pretty significant margin.

These are most likely NOT the longest periods and extending the search further should find more results. This search took about a day running in parallel on a 12 core machine.

Cheers,

-Shawn

[Shawn Ligocki]

Haha, of course, right after I sent this I got the new 4x2 results in and they are also increasing:

1RB 0LA  0RC 1LA  1RD 0RD  1LB 1RB   | Lin_Recur 2575984 1440 <33554432

1RB 0LA  0RC 0RD  1LA 0RA  0LC 1RA   | Lin_Recur 2353542 1440 <33554432

These were also searched up to 138M steps and took about 16 hours running in parallel on a 12 core machine.

-Shawn

[Nicholas Drozd]

That's wild. Chalk up one more wrong prediction for me!

I ran the LR detector and got start steps in the 20 millions:

  - 1RB 0LA  0RC 0RD  1LA 0RA  0LC 1RA
    - step:  22,269,896
    - period: 2,353,542
  - 1RB 0LA  0RC 1LA  1RD 0RD  1LB 1RB
    - step:  24,378,294
    - period: 2,575,984

Both of them reach all states in the recurrence period, and therefore do not quasihalt. It would be interesting to know if the longest period always reaches all states. I imagine that it does.

The apparent 4x2 BBP champion is remarkably simple (CFG attached). It can be proved statically that control will always return to state B. There are two routes:

  * B -> A. A loops to itself, but only on marks, of which there are only finitely many. So the A loop always terminates, returning control to B.

  * B -> C -> D -> B.

And that's it. That's the extent of the branching.

It isn't quite possible to prove statically that it doesn't quasihalt. That would require proving that both branches will always eventually get taken.

Still, this is another small piece of evidence against the Spaghetti Code Conjecture.

[Shawn Ligocki]

And we have another one. BBP(4, 2) > 7M

1RB 0LD  1RC 1LD  1LD 0RC  0LA 1LB   | Lin_Recur 7129704 512 <536870912

This is reaching the limit at which I can reasonably detect these (1 billion steps) and the search at this size has not yet finished.

[Nicholas Drozd]

The minimum step finder says that the recurrence starts at step 309,086,174. I'm having trouble verifying it though, either because the numbers are wrong or because there is a bug in my test apparatus.

[Shawn Ligocki]

Yeah, that machine runs long enough, it's hard to analyze without care!

My 1B step run completed so I can confidently say that among TMs which enter Lin Recurrence with start_step and period <= 536,870,912 . The longest period is 7,129,704 for the TM previously mentioned.

[Tristan Stérin]

I absolutely love your question. Your results are wild.

They put into perspective our current bbchallenge's results (5-state 2-symbol machine). In my naivety we have only ran the decider for Translated Cyclers on very small parameters compared to your findings:

1. 73,857,622 machines were found (83% of our seed database of undecided machines) with thresholds 1,000 for time and 5,00 for space.
   
2. An extra ~2,000 machines were found by increasing thresholds to 10,000 for time and 5,000 for space.

After reading your results today I ran a partial search on the remaining 1,330,882 undecided machines with increased (but still quite low) thresholds: 100,000 for time and 50,000 for space.

I found:

• Current S champion: S = 66,872 - https://bbchallenge.org/29274305 - 1RB---1LC0RD1LD0LC1LA0LE1RE1RC
• Current P champion: P = 91,995 - https://bbchallenge.org/31357173 - 1RB---1LC0LE1RD0LB0RD1RA0LC0RA

The website still shows them as "Undecided" because there were so few machines detected in my search (18 on ~500,000 tested) that I did not bother updating the index of undecided machines just yet.

Given your results I expect that there must be S and P BEASTS in the remaining 1M undecided machines of bbchallenge. We will run the decider with more intensive parameters when we get < 100k machines left. I hope to then be able to update this thread with a reasonable conjecture for BBS(5,2) and BBP(5,2).

Note:  I have ignored in this email the case of machines that repeat a pattern "in place" (we call them Cyclers on bbchallenge) because I intuitively believe that there are less potent than translation-based machines. But we will be able to verify this hypothesis in the future. Note that they might deserve their own category because their behaviors are simpler to track than translated ones. Maybe BBS_0/BBP_0 or I don't know!

Thank you again for this beautiful question,

[Tristan Stérin]

I have looked for Translated Cyclers within Skelet's machines, and I found 7, I posted about it at https://discuss.bbchallenge.org/t/skelet-machines-that-are-translated-cyclers/58. 

This is perhaps already known, especially with Dan Briggs' work however, I found striking that different looking machines achieve the same S = 24,265 and P = 91,995 scores (unless I have a bug). It seems that you also had found that some 4-state machines achieved the same scores.

You can reproduce these results by running:

`go test -run TestSkeletMachines -v`

On https://github.com/bbchallenge/bbchallenge-deciders/tree/main/decider-translated-cyclers.

[Tristan Stérin]

Oups, sorry, my reporting of P and S was wrong, I corrected it and in fact, as expected these machines have mostly different values of P and S.

However, something still stands out is that those P and S are quite small. This makes me think that maybe Skelet's missed some bigger P and S machines in his search?

See updated https://discuss.bbchallenge.org/t/skelet-machines-that-are-translated-cyclers/58

[Nicholas Drozd]

It looks like that first machine reaches Lin recurrence after 66,350 steps, with a period of just 1. After 66,345 steps, the tape is blank! There is a 4-state machine that does exactly the same thing:

  * 1RB 0LC  1LD 0LA  1RC 1RD  1LA 0LD

(Note that the 4-state machine doesn't have a halt instruction.)

Are these two machines identical? That is, do they implement the same function? Or is it just a coincidence?

As far as searching the BBChallenge holdouts for BBLR / BBP scores, I am somewhat pessimistic, and for two reasons.

1. Shawn's long-period machine is already, even at just 4 states and 2 colors, difficult to verify. Finding the lengths of periods is feasible, but finding when exactly they start is not. I think 5 states is totally hopeless.

2. As I understand it, BBChallenge is oriented around halting machines. Every machine in the database has a halt instruction. But we know that Lin recurrent machines won't halt, and so they can make use of that extra instruction. (They can be halt-free.) So the holdouts in the database represent, with respect to this particular problem, an expressively impoverished set of machines.

As an aside, it's funny how non-standard the terminology here is. BBChallenge calls these "translated cyclers", which is a perfectly good name. Back in the 80s, Machlin (and possibly Brady before her) called them "traveling loops". I've been calling it "Lin recurrence". This name is not particularly descriptive of the phenomenon itself, but it does pay tribute to Shen Lin, who in 1963 first implemented the recurrence check. Ironically, Lin himself did not come with a name for it; he just wrote a single long paragraph describing an algorithm to detect it.

> I have ignored in this email the case of machines that repeat a pattern "in place" (we call them Cyclers on bbchallenge) because I intuitively believe that they are less potent than translation-based machines.

I've wondered about that too. To explain why this might be the case, I think about it as a set of requirements. You're tasked with writing a program that will run for a long time, and then at some point come to cycle in-place forever. That means its behavior in the recurrence period has to be pretty specific, and it has to stick the landing just right. But if you don't have to aim for such a narrow target and the recurrence is allowed to shift to the side, you would have more leeway in how you approached it.

Maybe. Or that could all be totally wrong! It would be nice to know.

> Note that they might deserve their own category because their behaviors are simpler to track than translated ones.

Is this actually true? Whether the cycle moves or stays in place, you still have to track the history of the machine one way or another. This is in contrast to conditions that can be checked by looking only at the machine as it is in one moment: halting, spinning out, blank tape, maybe others? So maybe tracking in-place is a little easier than tracking traveling because you don't have to worry about finding any max/min points, but still I would think they're in the same "termination complexity class".

[Shawn Ligocki]

On Tue, Jun 7, 2022 at 6:22 PM Nicholas Drozd <nichol...@gmail.com> wrote:

2. As I understand it, BBChallenge is oriented around halting machines. Every machine in the database has a halt instruction. But we know that Lin recurrent machines won't halt, and so they can make use of that extra instruction. (They can be halt-free.) So the holdouts in the database represent, with respect to this particular problem, an expressively impoverished set of machines.

An alternative way to look at this would be to say that BBC will be in a position to find machines in a class halfway between the no-halt 4-state (8 transitions) and no-halt 5-state (10 transitions) class.

 

As an aside, it's funny how non-standard the terminology here is. BBChallenge calls these "translated cyclers", which is a perfectly good name. Back in the 80s, Machlin (and possibly Brady before her) called them "traveling loops". I've been calling it "Lin recurrence". This name is not particularly descriptive of the phenomenon itself, but it does pay tribute to Shen Lin, who in 1963 first implemented the recurrence check. Ironically, Lin himself did not come with a name for it; he just wrote a single long paragraph describing an algorithm to detect it.

 I think Shen Lin actually did have a name for this: "partial recurrence" in his dissertation. I riff on this name to describe it in a blog post.

 

> Note that they might deserve their own category because their behaviors are simpler to track than translated ones.

Is this actually true? Whether the cycle moves or stays in place, you still have to track the history of the machine one way or another. This is in contrast to conditions that can be checked by looking only at the machine as it is in one moment: halting, spinning out, blank tape, maybe others? So maybe tracking in-place is a little easier than tracking traveling because you don't have to worry about finding any max/min points, but still I would think they're in the same "termination complexity class".

The algorithm does feel simpler to implement (for complete recurrence / cycling in place). For example, Heiner had an algorithm for detecting these: Run two simulations one at twice the speed of the other. If they are ever in the same configuration (exactly) then you have cycled in place. But theory-wise they do seem to be in the same complexity place.

[Tristan Stérin]

> As far as searching the BBChallenge holdouts for BBLR / BBP scores, I am somewhat pessimistic, and for two reasons.

I agree with these concerns, we will not find the winners.

> An alternative way to look at this would be to say that BBC will be in a position to find machines in a class halfway between the no-halt 4-state (8 transitions) and no-halt 5-state (10 transitions) class.

Yes!

> Is this actually true? Whether the cycle moves or stays in place, you still have to track the history of the machine one way or another. This is in contrast to conditions that can be checked > by looking only at the machine as it is in one moment: halting, spinning out, blank tape, maybe others? So maybe tracking in-place is a little easier than tracking traveling because you >don't have to worry about finding any max/min points, but still I would think they're in the same "termination complexity class".

I agree with you that they are both in the same class. However, I would still argue that in-place cyclers form a strict sub-class with a tiny bit less complexity. As you said, the code for cyclers is really conceptually simple (put configurations in a bag, if see one twice return 'true') whereas there are strictly more concepts needed in the translated case (min/max, yes for instance). Another way to put it is that I believe that there will always be a shorter formal proof of termination (let say in Lean or Coq), for an in-place Cycler than for a translated one. But, in essence, I still agree with you: their complexity is similar and very low.

[Nicholas Drozd]

>  I think Shen Lin actually did have a name for this: "partial recurrence" in his dissertation.

Yes, thanks for pointing that out. He had a name for it, but it was so bland that I totally forgot about it :)

If I may make a somewhat pedantic distinction, total vs partial recurrence does not exactly line up to in-place vs traveling cyclers. Consider this 3/2 machine, an example of Lin's:

  * 1RB ---  0RC 1LB  1LA 0RB

This one is a traveling cycler, and also a total recurrence: the marks on the tape are exactly the same at its recurrence points, just shifted over.

If you run it with a "contracting tape" simulator that drops trailing blanks, it will look like it cycles in-place, and it would be detected by the basic configs-in-a-bag algorithm.

This blurs the line between in-place and traveling.

[Tristan Stérin]

I am unfamiliar with the definition of total/partial recurrence, what do they exactly mean?

Also, I am not sure that I understood what you meant by "contracting tape" simulator.

Thank you!

[Nicholas Drozd]

The basic way to implement the tape in a simulator is to use an array of some kind. The reader sometimes has to go past the edge of the array. This can be handled by producing a new blank cell and adding it to the tape, then moving to that cell. If you do that, then you can start with just one cell and let the tape grow as the machine runs. If you want to track the total number of cells that the machine traverses, this is a good way to do it.

But if you don't care about that, you can drop blank cells at the edges. Say you're in a situation like this:

  11_11_11[_]

That is, you're scanning a blank at the very edge of the (representation of) the tape. Now you move left. What happens to that blank cell on the edge? You can keep it around, or you can get rid of it. After all, if you return to that spot, a new blank cell will be produced anyway. If you drop it, you will end up with this:

  11_11_1[1]

This is what I mean by a "contracting tape" simulator.

Now, if you run the machine I posted above with a cell-preserving / non-contracting simulator, it will look like a traveling cycler: the machine's activity moves to the right forever. But if you run it with a contracting tape, it will look like an in-place cycler. The machine covers its tracks by erasing everything. It moves, but you would only be able to tell if you kept track of the starting cell.

[Shawn Ligocki]

As I mentioned in my last email, "Partial Recurrence" is just the term that Shen Lin first used for what you call "Translation Cycling" and what Nick calls "Lin Recurrence".

On the other hand, I would say that Total Recurrence is not well defined. I think you could plausibly either define it as the same as what your "Cycling" TMs do (completely repeat tape position without moving/translating) or you could define it as repeating "relative to the TM head". Let me elaborate:

There are two ways to think about TM simulation:

1. One is to use a fixed tape and have the TM move around on that tape. In this approach it makes sense to say that a TM comes back to a location. I assume this is what y'all do at bbchallenge?
2. Another is to fix the TM head and move the tape. In this approach you often don't keep track of "locations" on the tape. Instead "most" you just consider the "relative configuration". This is the approach that I use. In this approach, you can plausibly call something "Total Recurrent" if it repeats a "relative configuration" (which may have translated). So y'all would (presumably) call these "Translating Cyclers", but they can be detected with a simpler algorithm than the general case, because they are completely repeating tape configuration (relative to the TM head).
   

I'm not exactly sure if that's the distinction that Nick is making, but that's my take :)

-Shawn

--

You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/dd42ab0e-5700-488a-9bfe-ed78de80cd77n%40googlegroups.com.

[Tristan Stérin]

> This is what I mean by a "contracting tape" simulator.

I understand now thank you!

> 1.  One is to use a fixed tape and have the TM move around on that tape. In this approach it makes sense to say that a TM comes back to a location. I assume this is what y'all do at bbchallenge?

Yes exactly! 

> 2. Another is to fix the TM head and move the tape. In this approach you often don't keep track of "locations" on the tape. Instead "most" you just consider the "relative configuration". This > is the approach that I use. In this approach, you can plausibly call something "Total Recurrent" if it repeats a "relative configuration" (which may have translated). So y'all would (presumably) call these "Translating Cyclers", but they can be detected with a simpler algorithm than the general case, because they are completely repeating tape configuration (relative to the TM head).

Thats a cool way of doing it! I get it now.

Thank you for your answers!

[Yongyi Chen]

Just found a record-breaking 4x2 with an insanely long period and preperiod!

• 1RB0LA_0RC1RD_1LD0RB_1LA1RB -- period = 212,081,736, preperiod = 5,248,647,886.

I've also found 6 more Turing machines that could be candidates:

• 1RB1LC_0LA1RD_0RB0LC_1LA0RD
• 1RB1LC_0LA1RD_1LA0LC_0RB0RD
• 1RB0LC_1RC0RB_1LD0RA_1LA0LD
• 1RB0LA_1RC1LA_1LB1RD_1LC0RD
• 1RB1LC_1LA1RD_1RA0LC_1LB0RD
• 1RB0RA_1LC0RD_1LD0LC_1RA0LB

So far I've determined that if they are translated cyclers (Lin recurrent), either the period or the preperiod for each of them has to be more than 10^10.

-Yongyi

[Yongyi Chen]

Second one on my list has fallen! 1RB1LC_0LA1RD_1LA0LC_0RB0RD has a period of 483328 after around (and at most) 63854348937 steps.

[Yongyi Chen]

And another! Also figured out the exact preperiods:

1RB1LC_0LA1RD_1LA0LC_0RB0RD: period 483328, preperiod 59560191024

1RB1LC_0LA1RD_0RB0LC_1LA0RD: period 966716, preperiod 119120230102

My computer took 13 minutes and 25 minutes respectively to calculate the exact preperiods...

No word yet on the others. For a max period of 10^10 it was unable to find periodicity looking through 10^11 terms so far.

[nichol...@gmail.com]

Wow! This is great timing. I have been meaning to fix up my recurrence detector for a while, and now is the perfect opportunity :)

Quick refresher for everyone. We are looking at Lin recurrence here, and we are interested in finding both the longest recurrence periods and the longest "preperiod", that is, the longest time before entering into recurrence. The reigning champ in both of these categories up to now was a single program found by Shawn. It enters into Lin recurrence after 309_086_174 steps, with a period of 7_129_704. (One single program was the champ in both categories, but there is no known reason why this must be the case.)

Verifying long recurrences is not straightforward. It is relatively easy to verify period length, but it is very difficult to determine when exactly recurrence starts. If you only care about find the period at some time or other, you can run it while checking every now and then, and eventually it will turn up. But if you want to know the exact starting step, you have to check every step against every previous step, yielding a disastrous quadratic runtime. (Or is there a better way to do it???)

In terms of computational complexity, detecting Lin recurrence is "twice as hard" as detecting halting -- if you had an oracle to solve the halting problem, you would have to invoke it twice to determine Lin recurrence.

Yongyi, you have reported several findings so far. The first has period of 212_081_736 and with a start of 5_248_647_886. Is that an exact starting point? I.e., the recurrence begins at exactly that point and not before?

And the other two so far: period 483_328 with start 59_560_191_024 / period 966_716 with start 119_120_230_102. Just to clarify, you are claiming that that these are exact starting points?

I will get right to work trying to verify! In the meantime, I would be extremely interested to hear what sorts of techniques you have used to find these, hardware setup, etc.

[Shawn Ligocki]

Welcome Yongyi! Cool finds! What led you to think these specific TMs might have really long periods/pre-periods?

I can confirm all 3 of these. At least, for now I can confirm that they all enter Lin Recurrence satisfied by the prepriod (start_step) and periods you list. I haven't checked yet if those are minimal (if the period might start sooner or if the actual period might divide those listed). I've written up a new lr_check program to quickly verify a TM enters LR with a given start_step and period (see repo):

$ ./lr_check 1RB0LA_0RC1RD_1LD0RB_1LA1RB 5248647886 212081736

Success
  start_step: 5248647886
  period: 212081736
  offset: -2016
Runtime: 24.0881s
$ ./lr_check 1RB1LC_0LA1RD_1LA0LC_0RB0RD 59560191024 483328
Success
  start_step: 59560191024
  period: 483328
  offset: -384
Runtime: 285.907s

$ ./lr_check 1RB1LC_0LA1RD_0RB0LC_1LA0RD 119120230102 966716

Success
  start_step: 119120230102
  period: 966716
  offset: 384
Runtime: 555.16s

But they still take a while to run! I think this is almost completely just the time needed for my C++ simulator to run ~100 billion steps.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/26abbbf0-cb8a-4028-8549-1f8cf2b036b5n%40googlegroups.com.

[Shawn Ligocki]

OK, I can confirm that the start_step (preperiod) values are minimal via brute force (just trying my tool with start_step - 1):

$ ./lr_check 1RB0LA_0RC1RD_1LD0RB_1LA1RB 5248647885 212081736
Failed
  is_halted: 0
  steps_run: 5460729621
Runtime: 23.904s
$ ./lr_check 1RB1LC_0LA1RD_1LA0LC_0RB0RD 59560191023 483328
Failed
  is_halted: 0
  steps_run: 59560674351
Runtime: 284.46s
$ ./lr_check 1RB1LC_0LA1RD_0RB0LC_1LA0RD 119120230101 966716
Failed
  is_halted: 0
  steps_run: 119121196817
Runtime: 546.917s

[Yongyi Chen]

Yep, all three starting points I gave are exact starting points! After finding the period, I used binary search to get the exact starting position :)

For example, this is the transcript of running my period detection program on your 7129704 program.

------------------------------

1 |                          1
258199645 | 11 1  1  1111  11111111 1111 111111 11  
509048817 |  
[found] 516178521 |  111111 11  
Preliminary: (7129704, 509048817, 512)
Performing binary search with low = 258199645 and high = 509048817
Preperiod 383624231 ✅
Preperiod 320911938 ✅
Preperiod 289555791 ❌
Preperiod 305233864 ❌
Preperiod 313072901 ✅
Preperiod 309153382 ✅
Preperiod 307193623 ❌
Preperiod 308173502 ❌
Preperiod 308663442 ❌
Preperiod 308908412 ❌
Preperiod 309030897 ❌
Preperiod 309092139 ✅
Preperiod 309061518 ❌
Preperiod 309076828 ❌
Preperiod 309084483 ❌
Preperiod 309088311 ✅
Preperiod 309086397 ✅
Preperiod 309085440 ❌
Preperiod 309085918 ❌
Preperiod 309086157 ❌
Preperiod 309086277 ✅
Preperiod 309086217 ✅
Preperiod 309086187 ✅
Preperiod 309086172 ❌
Preperiod 309086179 ✅
Preperiod 309086175 ✅
Preperiod 309086173 ❌
Preperiod 309086174 ✅
4.38953 s | (7129704, 309086174, 512)

------------------------------

Update on the other holdouts: No period up to 10^11 after 8 trillion terms. After looking at the tapes a bit, I'm now slightly more convinced they aren't periodic, but perhaps reduce to a complicated bouncer.

Also, 1RB0LC_1RC0RB_1LD0RA_1LA0LD and 1RB0RA_1LC0RD_1LD0LC_1RA0LB seem equivalent in behavior and similarly for 1RB0LA_1RC1LA_1LB1RD_1LC0RD and 1RB1LC_1LA1RD_1RA0LC_1LB0RD.

-- Yongyi

[Yongyi Chen]

Oh, forgot to mention: my hardware is a laptop from 2021 running 8-core 16-thread Intel Core i7-10875H.

So far I have not taken advantage of multithreading.

On Monday, October 21, 2024 at 1:19:00 PM UTC-4 nichol...@gmail.com wrote:

[Yongyi Chen]

And finally, about how I found those particular programs. I generated 4-state 2-symbol Turing machines using the naive algorithm (no reason I couldn't use the TNF enumeration algorithm to prune it further, but I just didn't get around to that yet), then crucially sorted them by 3 numbers: tape size after 10^5 steps, tape size after 10^6 steps, and the ratio of those 2 tape sizes. This allows me to skip sections of relatively routine Turing machines (for example, bouncers show quadratic step-to-tape-size relationship, counters show logarithmic, and so on). For example, machines that become periodic early on would show a ratio of around 10, bouncers would show a ratio of around 3.16, which is the square root of 10, and exponential counters would show a ratio of around 1.2 or so. In between the large sections you can find very weird machines. There's a particular class of weird machines I like to characterize as "meandering" or "snakes." I manually picked those out and analyzed those.

Of course this isn't rigorous, and I definitely missed other weird machines that happen to be hiding among the common ones.

There are plenty of non-meandering weird ones too, and I don't think they will be translated cyclers. But here they are anyway!

Highly irregular faux exponential counters:

1RB0RC_1LA1RC_0LD0RB_0LA1LD
1RB0RC_0LD1RC_1LD0RB_0LA1LA
1RB1LA_0RC1RC_0LD0RB_0LA1LD

1RB1LC_1LD0RB_1RA0LC_0RA0LD

1RB1LC_0LA0RB_1RD0LC_1LA0RD
1RB0RB_1LC1RA_1LD0LC_0RA0LD
1RB1LC_1RD0RB_1LA0LC_0LA0RD

Tetration counters(!):

1RB1RC_1RD0RA_1RA1LD_1LA0LC
1RB0LC_0RD0RA_1LA1RD_1LD0LA
1RB0RC_1LD1LC_1LB1RA_1LA0LB
1RB1LC_0RD0RB_1RD0LA_1LD1RA

1RB0RC_1LD1RA_1RA0LB_0LC1LA

1RB1RC_0LC0RA_1RA1LD_1LA0LC

A particular cube-like fractal (the shapes are all the same, interestingly):

1RB0LA_1RC---_0RD0RC_1LD0LA

1RB---_0RC0RB_1LC0LD_1RA0LD
1RB1RC_0RC0RB_0LD1LA_1LD0LA
1RB0LA_0RC0RB_0LD1LA_1LD1RC
1RB0LA_0RC0RB_0LD1LA_1LD1RC
1RB0LA_1RC1LA_0RD0RC_1LD1RB
1RB1LC_0RD0RB_1RA0LC_1LD1RA

1RB1LC_0RD0RB_1RA0LC_1LD0RA
1RB0LA_1RC1LA_0RD0RC_1LD0RB

1RB0LA_1RC1LD_0LD0RB_0RC1LA

A different fractal:

1RB0RB_0RC0LC_1LD1RA_1LA1LD
1RB1LC_1RC1RB_1LD0LD_0LA0RA
1RB1RA_1LC0LC_0LD0RD_1RA1LB

"Bricks":
1RB0LC_1RC0RD_1LA1LC_1RC0RA

1RB0LC_1RD1RB_1LB0LD_1LA0RB

That's just a sampling. I'm keeping track inside an Excel document. Happy to share if anyone wants!

On Monday, October 21, 2024 at 1:19:00 PM UTC-4 nichol...@gmail.com wrote:

[Shawn Ligocki]

I can confirm the periods are minimal as well

$ ./lin_recur <(echo 1RB0LA_0RC1RD_1LD0RB_1LA1RB) 1 40
Running Lin Recur Detection
Lin Recurrence Detected
  start_step: 8589934592
  period: 212081736
  offset: -2016
Runtime: 92.0037s
$ ./lin_recur <(echo 1RB1LC_0LA1RD_1LA0LC_0RB0RD) 1 40
Running Lin Recur Detection
Lin Recurrence Detected
  start_step: 68719476736
  period: 483328
  offset: -384
Runtime: 884.273s
$ ./lin_recur <(echo 1RB1LC_0LA1RD_0RB0LC_1LA0RD) 1 40
Running Lin Recur Detection
Lin Recurrence Detected
  start_step: 137438953472
  period: 966716
  offset: 384
Runtime: 1420.51s

--

You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/71045a1c-f431-4a9e-b11f-f19bbf25fc7an%40googlegroups.com.

[Yongyi Chen]

>  What led you to think these specific TMs might have really long periods/pre-periods?

I talk about that in the above messages (they're out of order since each of my messages have a moderation await delay).

Anyway, I published my code to yongyi781/turing: Turing machine simulation and period detection in C++ !

[Terry Ligocki]

Hey, I'm really late to the party but it was great to see what you've been working on and making the code available on GitHub is wonderful! Definitely write when you have something to share. There is also the "bbchallenge.org" Discord and Wiki which might be other places to communicate and research.

Terry J. (Ligocki, tjli...@gmail.com)

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/4e227483-e928-4f7e-aa1c-ef696e6e485en%40googlegroups.com.