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!