User:ISquillante: Difference between revisions
Jump to navigation
Jump to search
ISquillante (talk | contribs) mNo edit summary |
ISquillante (talk | contribs) |
||
| Line 18: | Line 18: | ||
# There exists some natural number <math>p\ge1</math> such that for all sufficiently large <math>N</math>, the current state of <math>\tau</math> after <math>N</math> transitions is identical to the current state of <math>\tau</math> after <math>N+p</math> transitions. <math>p</math> is called the ''period length'' of <math>\tau</math>. | # There exists some natural number <math>p\ge1</math> such that for all sufficiently large <math>N</math>, the current state of <math>\tau</math> after <math>N</math> transitions is identical to the current state of <math>\tau</math> after <math>N+p</math> transitions. <math>p</math> is called the ''period length'' of <math>\tau</math>. | ||
# There is no natural number <math>x\ge1</math> such that for all sufficiently large <math>N</math>, the <math>N</math>-th transition is identical to the <math>N+px</math>-th transition. | # There is no natural number <math>x\ge1</math> such that for all sufficiently large <math>N</math>, the <math>N</math>-th transition is identical to the <math>N+px</math>-th transition. | ||
This second property is what distinguishes quasicyclers from translated cyclers; translated cyclers are defined by the negation of the second property of quasicyclers. | |||
==Properties== | ==Properties== | ||
For any quasicyclic Turing machine with preperiod of length <math>r</math> and period of length <math>p</math>, its [[Rate of tape growth|rate of strict tape growth]] <math>\gamma(x)</math> is bounded above by <math>\frac p2\sqrt{x}+\frac r3</math>. | For any quasicyclic Turing machine with preperiod of length <math>r</math> and period of length <math>p</math>, its [[Rate of tape growth|rate of strict tape growth]] <math>\gamma(x)</math> is bounded above by <math>\frac p2\sqrt{x}+\frac r3</math>. | ||
Latest revision as of 22:45, 6 June 2025
Isis Squillante
Discord: @isisoftheeast
E-Mail: isissquillante@gmail.com
Drafts below.
Quasicycler
A quasicycler is a Turing machine which is neither a cycler nor a translated cycler but cycles through states periodically.
Formal definition
A quasicycler or quasicyclic Turing machine is a Turing machine which has the following two properties:
- There exists some natural number such that for all sufficiently large , the current state of after transitions is identical to the current state of after transitions. is called the period length of .
- There is no natural number such that for all sufficiently large , the -th transition is identical to the -th transition.
This second property is what distinguishes quasicyclers from translated cyclers; translated cyclers are defined by the negation of the second property of quasicyclers.
Properties
For any quasicyclic Turing machine with preperiod of length and period of length , its rate of strict tape growth is bounded above by .