\documentclass[12pt,twoside]{article} 
\renewcommand{\baselinestretch}{1} 
\setcounter{page}{1} 
\setlength{\textheight}{21.6cm} 
\setlength{\textwidth}{14cm} 
\setlength{\oddsidemargin}{1cm} 
\setlength{\evensidemargin}{1cm} 
\pagestyle{myheadings} 
\thispagestyle{empty}
\markboth{\small{John Nixon}}{\small{Developments in the analysis techniques for non-terminating Turing Machines}}
\usepackage{caption}
\usepackage{verbatim} %allows some sections to be temporarily commented out, which was %useful for correcting compilation errors that caused a problem with the long captions in two
%tables (search for 'comment' to find them)
\usepackage{enumitem}
\usepackage{amssymb}
\usepackage{longtable}
\usepackage{float}
\usepackage{subfigure}
\usepackage{multirow}
\usepackage{bigstrut}
\usepackage{bigdelim}
\usepackage{pdflscape}
\usepackage{adjustbox}
\usepackage{mleftright}
\usepackage{abraces}
%\usepackage{cmll}
\usepackage{pifont}
\usepackage[utf8]{inputenc}% add accented characters directly
\restylefloat{figure}
\restylefloat{table}
\usepackage{booktabs}
\usepackage{hyperref}%The inclusion of package hyperref converts all the references to equations etc. to internal links
\usepackage{array}
\usepackage{mathtools}% includes amsmath
\usepackage{amscd}
\usepackage{amsthm}
\usepackage{xypic}
%\usepackage{MnSymbol}
\everymath{\mathtt{\xdef\tmp{\fam\the\fam\relax}\aftergroup\tmp}}
\everydisplay{\mathtt{\xdef\tmp{\fam\the\fam\relax}\aftergroup\tmp}}


\begin{document}

\setbox0\hbox{$x$}
\newcommand{\un}{\underline}
%\centerline{\bf Mathematica Aeterna, Vol. x, 201x, no. xx, xxx - xxx}%uncomment this in published version
Date: 2025-12-30
\centerline{} 
\centerline{} 
\centerline {\Large{\bf Turing Machines}}
\centerline{}
 

%\centerline{\bf {John Nixon}} 

%\centerline{} 

%\centerline{Brook Cottage} 
 
%\centerline{The Forge, Ashburnham} 

%\centerline{Battle, East Sussex} 

%\centerline{TN33 9PH, U.K.}


%Email: John.h.nixon1@gmail.com

%Date: 2017-01-11
\setlength\nulldelimiterspace{0pt}
\newtheorem{Theorem}{\quad Theorem}[section]
\newtheorem{Definition}[Theorem]{\quad Definition} 
\newtheorem{Corollary}[Theorem]{\quad Corollary} 
\newtheorem{Lemma}[Theorem]{\quad Lemma} 
\newtheorem{Example}[Theorem]{\quad Example} 
\newtheorem{alg}[Theorem]{\quad Algorithm}
\newcounter{Hypothesis}
\newtheorem{hyp}[Hypothesis]{Hypothesis}

\begin{abstract}
Developments are given here for the analysis technique for non-terminating Turing Machines (TM's) that I described earlier in \cite{jhn2013} and \cite{jhn2017}. The main new ideas are the introduction of IRR patterns i.e. constraints satisfied by large sets of IRRs (Irreducible Regular Rules) and the logical relationships between them as a result of the general method for deriving IRR's from others described in my earlier paper. These logical relationships will be referred to as IGR's (IRR Generating Rules). IGR's have been reduced to their minimal form in a way analogous to the way in which regular rules were reduced to IRR's by taking out symbol strings that played no essential role. In the case of IGR's these symbol strings (actually pairs) will be referred to as context pairs. A new version of my computer program extending the previous analysis is described and is freely available that generates these IGR's up to a given length of IRR's that they generate. The results show repetition of the left hand halves (Left IGR's or LIGR's) of IGR's associated with different right hand halves. Because the LIGR's can be derived independently of the right hand halves of IGR's, this should be done separately and can be done using the currently known IRR's as previously described in my earlier papers. The LIGR's can be used to calculate all the IRR's of a TM. A procedure for the generation of all the LIGR's for a TM has been suggested and is expressed here by a detailed analysis of a TM though not yet as computer code.
\end{abstract}
{\bf Mathematics Subject Classification:} 68Q25 \\ 

{\bf Keywords:} Turing Machine (TM), Irreducible Regular Rule (IRR), IRR Generating Rule (IGR), LIGR (Left IGR).

\section{Introduction}
A lot of material that probably will not be needed has been removed. It will be available as an old version to show where the ideas came from, and this much shortened version will take its place as the latest version under active editing.
The following example was studied because old attempts at the analysis of \eqref{1} became very complicated.

\begin{equation}\label{tm2}\begin{array}{@{}c@{}}
1\un{a}\to 2b \_\\
1\un{b}\to 3\_b\\
1\un{c}\to 1b\_\\
2\un{a}\to 3b\_\\
2\un{b}\to 2c\_\\
2\un{c}\to 1\_c\\
3\un{a}\to 1\_a\\
3\un{b}\to 1\_a\\
3\un{c}\to 3c\_\\
\end{array}\end{equation}

The main results are contained in \eqref{1_}, \eqref{2_} and \eqref{3_} which were updated  together with some text on page 59. Table~\ref{equivTM1} is summarised by Figure~\ref{fig2} and shows how the TM can be `trapped' in a steady movement to its left. The results \eqref{1_}, \eqref{2_}, \eqref{3_} seem to be adequately describing the TM.  

section \ref{sec8} needs some discussion because the two examples are so different.

Some general heuristics are given right at the end regarding using the IGR's to generate a description of the action of a TM in terms of ever expanding cycles (when possible). The TM \eqref{6} is an example of this while TM \eqref{tm2} is not.


 A lot of material has been removed to 2017's 
\href{http://www.bluesky-home.co.uk/2017_Turing_notes.pdf}{Notes on Turing Machines}. These notes are now mostly superseded, but there may be a little there that is of use.

Comments are welcome. Please send them to
john.h.nixon1@gmail.com


Consider another example given by
\begin{comment}this is tm3.txt\end{comment}
\begin{equation}\label{6}
\begin{tabular}{ll}
$1\un{a}\to 2b\_$&$1\un{b}\to 2\_a$\\
$2\un{a}\to 1b\_$&$2\un{b}\to 2\_a$\\
$3\un{a}\to 3a\_$&$3\un{b}\to 1\_b$\\
\end{tabular}
.\end{equation}



The analysis techniques were initially applied to the following TM \eqref{1} which was generated randomly with 5 states and 5 symbols. This TM, being much larger than any that I have analysed before, has proved to be a much more challenging case.
\begin{equation}\label{1}
\begin{tabular}{lllll}
$1\un{a}\to 2\_d$&$2\un{a}\to 1c\_$&$3\un{a}\to 4c\_$&$4\un{a}\to 3\_b$&$5\un{a}\to 2\_e$\\
$1\un{b}\to 4\_d$&$2\un{b}\to 4\_c$&$3\un{b}\to 4\_c$&$4\un{b}\to 4b\_$&$5\un{b}\to 3\_e$\\
$1\un{c}\to 3\_a$&$2\un{c}\to 1d\_$&$3\un{c}\to 2\_a$&$4\un{c}\to 3c\_$&$5\un{c}\to 3a\_$\\
$1\un{d}\to 2b\_$&$2\un{d}\to 1a\_$&$3\un{d}\to 5\_c$&$4\un{d}\to 5\_c$&$5\un{d}\to 4\_a$\\
$1\un{e}\to 2b\_$&$2\un{e}\to 3\_c$&$3\un{e}\to 3b\_$&$4\un{e}\to 5a\_$&$5\un{e}\to 3a\_$\\
\end{tabular}
\end{equation}
I have just started (but not finished) the same analysis of the old example \eqref{1} to see how easy the method will be will be for larger TM's.

\begin{equation}\label{st1}1\left\{\begin{array}{@{}l}
\stackrel{a}{\to}2\_d\left\{\begin{array}{@{}l}\stackrel{a}{\to}2\_aa(2\un{a}d\to 2\_aa)\\\stackrel{b}{\to}4\_cd\\
\stackrel{c}{\to}2db\_(2\un{c}d\to 2db\_)\\
\stackrel{d}{\to}2ab\_(2\un{d}d\to 2ab\_)\\
\stackrel{e}{\to}3\_cd\\
\end{array}\right.\\
\stackrel{b}{\to}4\_d\\
\stackrel{c}{\to}3\_a\\
\stackrel{d}{\to}2b\_\\
\stackrel{e}{\to} 2b\_\\\end{array}\right.\end{equation}

\begin{equation}\label{st2}2\left\{\begin{array}{@{}l}
\stackrel{a}{\to}1c\_\\
\stackrel{b}{\to}4\_c\\
\stackrel{c}{\to}1d\_\\
\stackrel{d}{\to}1a\_\\
\stackrel{e}{\to}3\_c\\\end{array}\right.\end{equation}

\begin{equation}\label{st3}3\left\{\begin{array}{@{}l}
\stackrel{a}{\to}4c\_\\
\stackrel{b}{\to}4\_c\\
\stackrel{c}{\to}2\_a\\
\stackrel{d}{\to}5\_c\\
\stackrel{e}{\to}3b\_(3\un{e}\to 3b\_)\\\end{array}\right.\end{equation}

\begin{equation}\label{st4}4\left\{\begin{array}{@{}l}
\stackrel{a}{\to}3\_b\\
\stackrel{b}{\to}4b\_(4\un{b}\to 4b\_)\\
\stackrel{c}{\to}3c\_\\
\stackrel{d}{\to}5\_c\\
\stackrel{e}{\to}5a\_\\\end{array}\right.\end{equation}

\begin{equation}\label{st5}5\left\{\begin{array}{@{}l}
\stackrel{a}{\to}2\_e\\
\stackrel{b}{\to}3\_e\\
\stackrel{c}{\to}3a\_\\
\stackrel{d}{\to}4\_a\\
\stackrel{e}{\to}3a\_\\\end{array}\right.\end{equation}





A branch can end because of three conditions, (1) a repetition or loop (indicating that there is no point in continuing) because a substring in the same branch has been developed before and (2) a reference to a loop. This is indicated by the loop label (a greek letter) and an asterisk and (3) when the computation from the same CS appears on another branch. If the computation ends in a subset of a CS previously developed, the extra symbol(s) need to be added resulting in another subtree. A very simple case follows.
To get the results for $3b|b\_$ from those for $3|b\_$ $(\epsilon$ an extra $b$ must be put on the left.
The first branch gives rise to the loop $\delta$ going left and the added $b$ gives $3\un{b}ba\to 1\_aba$ and in its new location it gives rise to a new loop $1\un{a}ad\to 1\_aba$. The branch to $3b|c\_$ going to the loop $\theta$ going to the right, gives this same loop after the $b$ is added on the left because the extra symbol is added on the left. If the new symbol is added on the opposite side to the direction of travel in a cycle of the loop the same loop with be obtained after the symbol is added, but not otherwise.


How to handle reversals of direction add the extra symbol to extend the tree as above or start a new one?
a reversal of direction so that the pointer is on the other side of the string. In this case the computation continues on another tree because every possible state and symbol pair (accounting for all possible cases) is at the root of a tree

Another example is how the development of $2|bb\_$ is obtained from that of $2|b\_$.
Putting a $b$ on the left gives the first result $1\un{b}aba\to 3\_baba$. This results in two loops because
both starting points $3\un{c}bad$ and $3bbb\un{d}$ match the endpoint $3\_baba$. This is indicated by
$3\un{c}bad\to 3bbb\un{d}\to 3\_baba$. The other cases are very easy. Note that the $|$ has no meaning unless each symbol is added one at a time so they are omitted if this does not happen.


In case (1) in what follows the numbers in typewriter font represent different repeating conditions. The number is the length {\it l} of the string over which a repetition can occur. This includes the symbol added so it is always $\ge$ 1 and if $l=1$ there is no symbol string to be matched. The repeating condition is where the state, pointer position (right or left) and the symbol string match between a CS and another CS that is in the path to it from the root of the tree. Between these two CS's the pointer moves in a range. A repetition also requires every symbol in the second CS in the range to match the corresponding string from the first CS.

In case (2) a branch ends because the computation (taken as far as possible) goes in the opposite direction. This is indicated by an italicised identification number. These numbers are also repeated where a matching CS appears in another tree from where the computation can continue.

\begin{equation}\label{1_}1\_\left\{\begin{array}{@{}l}\stackrel{a}{\to}2|b\_\left\{\begin{array}{@{}l}\stackrel{a}{\to}3b|b\_(\epsilon)\left\{\begin{array}{@{}l}\stackrel{d}{\to}1\_aba(1\un{a}ad\to 1\_aba)\\
\stackrel{c}{\to}3bb|c\_(\theta^*)\end{array}\right.\\
\stackrel{b}{\to}2b|c\_(\zeta^*)\\
\stackrel{c}{\to}3\_bc|(\beta^*)\end{array}\right.\\
\stackrel{b}{\to}3\_b|\left\{\begin{array}{@{}l}\stackrel{d}{\to}1\_a|b(1d\un{b}\to 1\_ab)\\
\stackrel{c}{\to}2|bb\_(\alpha)\left\{\begin{array}{@{}l}\stackrel{ad}{\to}3\_b|aba(3\un{c}bad\to 3bbb\un{d}\to 3\_baba)\\
\stackrel{ac}{\to}3bbb|c\_(\theta^*)\\
\stackrel{b}{\to}2bb|c\_(\zeta^*)\\
\stackrel{c}{\to}1\_abc|(\eta^*,\text{ignore x})\end{array}\right.\end{array}\right.\\
\stackrel{c}{\to}1|b\_(1\un{c}\to 1b\_,\gamma)\end{array}\right.\end{equation}

\begin{equation}\label{2_}2\_\left\{\begin{array}{@{}l}\stackrel{a}{\to}3|b\_(\epsilon)\left\{\begin{array}{@{}l}\stackrel{d}{\to}3\_ba|(\delta^*)\\
\stackrel{c}{\to}3b|c\_(\theta^*)\end{array}\right.\\
\stackrel{b}{\to}2|c\_(2\un{b}\to2c\_,\zeta)\\
\stackrel{c}{\to}1\_c|\left\{\begin{array}{@{}l}\stackrel{d}{\to}3\_bc|(\beta)\stackrel{x=a,b,c}{\to}1\_abc(\eta)\left\{\begin{array}{@{}l}\stackrel{a}{\to} 1\_aba|c(1ab\un{b}\to 1\un{a}ab\to 1b\un{b}a\to 1\_aba)\\
\stackrel{b}{\to}3\_b|abc\left\{\begin{array}{@{}l}(x=d,3b\un{d}\to 3\_ba)\\\stackrel{d,x=c}{\to}1\_a|babc(1d\un{b}\to 1\_ab)\\
\stackrel{c,x=c}{\to}3\_baba|c(3\un{c}bab\to 3\_baba)\end{array}\right.\\
\stackrel{c}{\to}1b^{\rm 4}\_(\gamma^*)\end{array}\right.\\
\stackrel{c}{\to}1bb\_(\gamma^*)\end{array}\right.\\
\end{array}\right.\end{equation}

\begin{equation}\label{3_}3\_\left\{\begin{array}{@{}l}\stackrel{d}{\to}1\_a|\left\{\begin{array}{@{}l}\stackrel{a}{\to}3|bb\_(\epsilon^*)\\
\stackrel{b}{\to}3\_b|a(3b\un{d}\to 3\_ba,\delta)\\
\stackrel{c}{\to}2|bb\_(\alpha^*)
\end{array}\right.\\
\stackrel{c}{\to}3|c\_(3\un{c}\to 3c\_,\theta)\end{array}\right.\end{equation}

Do the results \eqref{1_},\eqref{2_} and \eqref{3_} adequately characterise TM~\eqref{tm2}?

By taking the longest results of the repeating cycles on the RHS's of \eqref{1_},\eqref{2_} and \eqref{3_} i.e. $1\_aba,3\_baba$ and adding every symbol in turn gives $1\un{a}aba\to 1\_abaa, 1\un{a}abaa\to C,1\un{b}abaa\to E, 1\un{c}abaa\to 3b^{\rm 5}\_, 1\un{b}aba\to 3\_baba, 3\un{a}baba\to A, 3\un{b}baba\to A, 3\un{c}baba\to E,1\un{c}aba\to 2bbbb\_$ where I am using the capital letter notation for pseudo-states in Table~\ref{equivTM1}. Another round of this will generate all the results of Table~\ref{equivTM1}.

\section{Formulating the condition for a repetition}
In these trees if on any branch, the final CS matches an earlier CS in such a way that the loop can be repeated (this might work after some symbols not involved in the loop itself are ignored) then the algorithm terminates the branch because continuing is a special case of what has already been done. If this happens, all the CS's that match the final CS should be listed in order in parentheses, so that many other results of the TM can be found easily.
Suppose \begin{equation}\label{branch}CS_{\rm 1}\stackrel{\alpha_1}{\to}CS_{\rm 2}\stackrel{\alpha_2}{\to}\ldots \end{equation} is such a branch that ends in a repeating loop and the pointer is at the right in each CS where $CS_{\it i}$ has length $\it i $ and in step ${\it i}$ from $CS_{\it i}$ to $CS_{{\it i}+{\rm 1}}$ the pointer reaches and uses ${\it r}({\it i})$ symbols (this excludes the last symbol arrived at that is not yet read). $CS_{\rm 1}$ is a CS of length 1 with the pointer on the right and is just one TM step away from the root which is a state and symbol pair. After ${\it l}_{\rm 2}-{\rm 1}$ steps in \eqref{branch} giving a CS of length ${\it i}={\it l}_{\rm 2}$ what is the condition for a repetition of an earlier CS of length ${\it i}={\it l}_{\rm 1}$? This involves ${\it l}_{\rm 2}-{\it l}_{\rm 1}$ steps in \eqref{branch}.

Because the symbols are added on the right, the tape positions will be counted going to the right and the leftmost position is position 1 in all the CS's.
The pointer starts at ${\it l}_{\rm 1}+{\rm 1}$ and first goes to ${\it l}_{\rm 1}+{\rm 2}$ via ${\it l}_{\rm 1}-{\it r}({\it l}_{\rm 1})+{\rm 2}$ (the symbol positions used go from $\it {l_{\rm 1}-r(l_{\rm 1})+{\rm 2}}$ to ${\it l_{\rm 1}+{\rm 1}}$ i.e. a segment of length ${\it r(l_{\rm 1}})$). The complete potentially repeating computation reaches the following extreme pointer positions in this order
${\it l}_{\rm 1}+{\rm 1},{\it l}_{\rm 1}+{\rm 2}-{\it r}({\it l}_{\rm 1}),{\it l}_{\rm 1}+{\rm 2},{\it l}_{\rm 1}+{\rm 3}-{\it r}({\it l}_{\rm 1}+{\rm 1}),\ldots {\it l}_{\rm 2}$ because in the final step to get $CS_{\it l_{\rm 2}}$ the pointer does not go beyond ${\it l}_{\rm 2}$. The range of the tape affected by the computation is from position {\it p} to ${\it l}_{\rm 2}$ inclusive (see Figure~\ref{fig01}) where
\begin{equation}\label{range}{\it p}=\begin{array}{@{}c}\text{min}\\{\it l}_{\rm 1}\le {\it i}\le {\it l}_{\rm 2}-{\rm 1}\end{array}\left\{{\it i}+{\rm 2}-{\it r}({\it i})
\right\}.\end{equation}
The repeating condition implies that the states match between the start and end of the computation and there is a pair of matching substrings of ${\it m}$ symbols
 in the two CS's such that each substring lies within the range {\it p} to ${\it l}_{\rm 2}$ and must include all the symbols in that range on the left hand end otherwise the computation could not be repeated due to a mismatch. 
Therefore ${\it p}={\it l}_{\rm 1}-{\it m}+{\rm 1}$ is the leftmost symbol position involved in the matching i.e. ${\it m}={\it l}_{\rm 1}-{\it p}+{\rm 1}$. The length of the potentially repeating rule is the length of tape involved in \eqref{range} i.e. ${\it t=l_{\rm 2}}-{\it p}+{\rm 1}$. Therefore ${\it t-m=l_{\rm 2}-l_{\rm 1}}\ge {\rm 1}$. One of the shortest possible examples is $3\un{c}\to 3c\_$. If there are no other symbols on the left, ${\it l_{\rm 1}}={\rm 0}$ and ${\it l_{\rm 2}}={\rm 1}$ and ${\it p}={\rm 1}$ therefore ${\it m}={\rm 0}$ and ${\it t}={\rm 1}$ so in general ${\it t}>{\it m}\ge {\rm 0}$.

The notation $|$ was introduced in the CS's to indicate the limit beyond which the pointer did not go to obtain the CS from the preceding one.
This is a visual indication of ${\it r}({\it i})$ which is the number of symbols between $|$ and the end of the string where the symbol $\_$ is, where ${\it i}$ is the length of the {\em preceding} CS.



\begin{figure}
%\begin{adjustbox}{width = 10cm,center}
\centering
\xymatrix @R = 0.1cm @C= 2mm{{\it i}+{\rm 2}-{\it r(i)}&{\it r(i)}&{\it i}\\
{\rm 4} & {\rm 2} & {\rm 4} && x&x&x&x&\_\\
{\rm 3} & {\rm 4} & {\rm 5} && x&x&x\ar @{} [r]|{|}&x&x&\_\\
{\rm 5} & {\rm 3} & {\rm 6} && x&x\ar @{} [r]|{|}&x&x&x&x&\_\\
{\rm 8} & {\rm 1} & {\rm 7} && x&x&x&x\ar @{} [r]|{|}&x&x&x&\_\\
{\text{minimum: }{\it p}={\rm 3}}&& {\rm 8} && x&x&x&x&x&x&x\ar @{} [r]|{|}&x&\_\\
&&&&&&\uparrow\\}
\caption{{\bf A schematic example of a repetition (states omitted)}. Here ${\it l_{\rm 1}}={\rm 4}$,${\it l_{\rm 2}}={\rm 8}$, and ${\it p}={\rm 3}$ therefore ${\it m}={\rm 2}$ and ${\it t}={\rm 6}$ and the repeating rule has the form $\widehat{xx}\un{x}xxx\to xxxx\widehat{xx}\_$ where the $x$'s represent any symbols, and the $\_$'s are where the symbols are added at the pointer position. The strings of symbols under the widehat\hspace{5pt}$\widehat{\hspace{5pt}}$ must 
 be the same. These are the ${\it m}$ symbols that are repeated. The $\uparrow$ is where ${\it p}={\rm 3}$ giving a visual indication of the end of range of the symbols that are involved in the repeating computation rule.
 }
\label{fig01}
%\end{adjustbox}
\end{figure}

\begin{longtable}{c|c|c|c|c}
\caption{A finite state machine going left derived from TM \label{equivTM1}\ref{tm2}}\\
A: $ 1\_ababa$&B: $1\_abaab$&C: $1\_abaaa$&D: $3\_babab$&E: $3\_babaa$\\
$a\to$ B&$a\to$ C&$a\to$ C&$a\to$ A&$a\to$ A\\
$b\to$ D&$b\to$ E&$b\to$ E&$b\to$ A&$b\to$ A\\
$c\to$ D&$c\to$ D&$c\to$ D&$c\to$ D&$c\to$ E\\
\end{longtable}


From this it appears that there are no IRR's of length $\ge$ 7 of the type RLR, then all such IRR's have type RLL, LRL, or LRR. 
If this is generally true, and if the TM reaches position 6 followed by position 1 it cannot subsequently reach position$\ge$ 7 because this would require a subsequence of CS's of the form $n\to 1\to n+1$ with $n=$ 6 which would be an IRR by lemma~\ref{lemma1} of type RLR of length ${\it n}+{\rm 1}$ contradicting the assumption. The pointer is then constrained to positions $\le$ 6, and if it reaches position 0 then because it has reached position 5 previously, the same argument can be applied showing that it cannot then reach position $\ge$ 6 etc.. 
This implies that the pointer is constrained to being in a moving window of length 6 that moves left by one space when the pointer moves just to its left. Because of this, if a snapshot is taken of its behaviour whenever the TM reaches just beyond the left hand end of the window, whatever symbol it finds there, the result will be at the next snapshot that the symbols of the window have changed depending on the previous symbols there and the new symbol. Therefore if the TM reaches position 6 followed by position 1 then the above argument involving the moving window applies. This condition of course will happen depending on the initial contents of the tape of the TM that could start the TM doing one of the iterations going right mentioned above.

Now it is obvious that this effective finite state machine is defined by all IRR's of the type LRL of length $\le{\it n}$ for some length {\it n}. This behaviour going left corresponds to the sequence $A=p\to 2\to p-1\to 1\to p-2\to 0$ etc. for some positive integer $p$ and requires $B$ (a subsequence of $A$) i.e. $2\to p-1\to 1$ to exist which is an IRR of type LRL of length $p$. Also the sequence $p-2\to 2\to p-1$ would have to exist which is an IRR of type RLR of length $(p-1)-2+1=p-2$ so for this TM $p$ could not be larger than 8 and the longest IRR of type RLR needed could not have length greater than 6.
This is an effective finite state machine with internal state corresponding to the set of symbols in the window and its actual machine state, and it continues indefinitely unless a stationary cycle occurs which would halt it.

In this example the sequence $6\to 1\to 7$ is impossible but $6\to 1\to 0$ and $6\to 1\to 5\to 0$ are not ruled out. 






\begin{figure}
\begin{adjustbox}{width = 14cm,center}
\centering
\xymatrix @R = 0.3cm{
& *+[F-:<3pt>]{\txt{Start}}\ar[d]\\
*+[F-:<3pt>]{\txt{TM~\ref{tm2} progresses by sequences of\\ steps each moving the pointer left by\\ one space and restricts the pointer\\ to positions in a window of length 6.
}} & *+[F-:<3pt>]{\txt{Has the pointer reached one position\\ then another 5 spaces to its left?}}\ar[l]|-{yes}\ar[d]|-{no}\\
& *+[F-:<3pt>]{\txt{Continue the TM by one step}}\ar@<-15pt>[u]
}
\caption{Summary of the results of the analysis of TM(\ref{tm2})}
\label{fig2}
\end{adjustbox}
\end{figure}

\begin{thebibliography}{99}
\bibitem{jhn2013}\href{https://www.longdom.org/articles/methods-for-understanding-turing-machine-computations.pdf}{Methods for Understanding Turing Machine Computations}
\bibitem{jhn2017}
\href{https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf}{Reverse engineering Turing Machines and the Collatz Conjecture}
\bibitem{tie}
\href{http://www.bluesky-home.co.uk/tie_v2_1.txt}{The previous version in D of the computer program for analysis of Turing Machines}
\bibitem{origins}\href{http://www.bluesky-home.co.uk/origins.txt}{Program for just doing the backward search for a single CS}
\bibitem{tie_v3_2}\href{http://www.bluesky-home.co.uk/tie_v3_2.txt}{The new program tie v3.2 for doing the computations in this paper}
\end{thebibliography} 


\end{document}