Translated cycler
44394115 (bbch). The same bounded pattern is being translated to the right forever. The text annotations illustrate the main idea for recognising "Translated Cyclers": find two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state (here state D) such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.Translated cyclers are close to Cyclers in the sense that they are only repeating a pattern but there is added complexity as they are able to translate the pattern in space at the same time, hence the decider for Cyclers cannot directly apply here.
A translated cycler has two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.
Here are the properties of the translated cycler shown in the figure:
- L = 2. After the translated cycler reaches record 1, the translated cycler moves at most L = 2 symbols to the left.
- The cycle period is 10 steps. This is the number of steps from record 1 to record 2.
- The cycle offset is 2 symbols to the right. In other words, after each cycle, the TM moves 2 places to the right.
- The cycle start time is 6 steps. This is the position of record 1.