\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 technique 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{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: 2024-10-03
\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}
It is now looking extremely complicated to complete Table~\ref{bigtable}. I still think this is possible but it is still far from done but I wanted to update everything.
Things to be corrected:
\begin{itemize}
\item section \ref{sec7} is incomplete eg Table~\ref{bigtable} is incomplete.
\item section \ref{sec8} needs some discussion because the two examples are so different.
\end{itemize}
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\ref{6} is an example of this while TM\ref{tm2} is not.
Table~\ref{table3} was reorganised (Table~\ref{table6}) in terms of LIGR's and RIGR's(Right IGR's).
This document is a work in progress. As such it is incomplete and still has errors and omissions. When brought to a state where I cannot easily find any improvements it will form my next paper on Turing Machine analysis.
Section 2 is a quite dense summary of the previous methods that lays the foundations of the developments to be described in this paper.
Section 3 introduces IRR patterns (IRRP's) as sets of IRR's conforming to the pattern. They have some common symbols in the origin and the RHS of the IRR and allow for any LHS.
Section 4 introduces IGR's in terms of IRRP's and illustrates the fact that IRR's of any length can be derived from sequences of IGR's by a sequence of substitutions.
In Section 5 the detailed description of an IGR is given and proves the generation of IRR's from IGR's. A computer algorithm is described for generating them all up to a given length for a TM and its results are shown for an example TM.
In Section 6 a necessary condition in the relation ``can be followed by" for IGR's was found. Further results are found for the set of IGR's that can follow a sequence of IGR's following each other (i.e. substituted into each other) hand calculation of which suggests a method for generating all of them for a TM though this appears practically impossible for the example TM because of the large number of cases to be considered. In Section 7 left IGR's or LIGR's are introduced because in section 6 the LHS and RHS of an IGR can be developed independently. An algorithm is illustrated by example for finding all the LIGR's for a TM based on the above ideas and results.
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
\section{\label{sec2}Basic definitions and summary of the existing method (F) to generate the IRR's for a TM}
A configuration set (CS) for a TM is a set of complete configurations (tape symbols with pointer position indicated, and the machine state of the TM) such that the CS is specified by giving a finite set of symbols in a set of contiguous pointer positions together with the machine state and such that the pointer position is where one of the given symbols is given or adjacent to one. In a CS all possible configurations that are consistent with the specified symbols and machine state are included. The notation is the specified symbol string with the pointer indicated by an underscore (it is just off the end of the symbol string) or an underline and the machine state on the left. For example with machine states 1,2,3, etc. and symbols lower case letters the following are CSs: $2a\un{b}ca$, $1\_aabbcac$. The length of the CS is the length of the symbol string which is finite.
A computation rule or rule is a pair of CS's linked by $\to$ indicating the forward direction of the computation. A reducible rule is one that has symbols that play no part in the computation i.e. any extra symbols added on the left or right of the strings at the left and right hand sides of a computation rule. From the definitions of regular rules (RR) and irreducible regular rules (IRR) in \cite{jhn2013},
any computation of the TM that ends with the pointer just off the end (i.e. adjacent to a symbol at the end) of the string of symbols specified at the start can be represented by RR's chained together as a sequence of CS's starting with one of length 1, where for each step in the chain a new symbol is read at a position where no symbol has yet been read at the pointer, thus the length of the string of symbols increases by 1 for each RR unless a stationary cycle occurs that ends such a sequence. All such CS's are by definition reachable. All single TM steps are RR's. If the RR is of type LR or RL as designated earlier (now the position of the pointer in the origin (see below) is included so these are now RLR and LRL respectively) the pointer swaps ends at that step of the chain and these RR's are also irreducible RR's (IRR's) because if the pointer swaps ends there are no redundant symbols i.e. the rule is irreducible. There are also IRR's that that don't swap ends.
If a CS called ``origin" is included with the LHS and RHS of the IRR it can be written in the triplet form as $origin\to LHS\to RHS$ for which the abbreviated form $origin\to\to RHS$ will be used if the LHS is not specified hence the changed designation of the type of an IRR. An origin (there could be many for the same LHS) of an IRR is a CS obtained by running the TM backwards starting from the LHS to a point such that the pointer position is at the opposite end of the string from where it is in the LHS.
If an RR is of type LRR or RLL it is related to an irreducible form (a possibly shorter IRR which only involves the symbols passed by the pointer during its execution) as follows.
Suppose the RR is represented by
$m\to n\to o$ where ${\it m}<{\it n}<{\it o}$ and ${\it n}+{\rm 1}={\it o}$ where italics represent the corresponding pointer positions for the CS's in typewriter font. Then the RR has type LRR because the start and end points of the i.e. the LHS and RHS have the pointer at the right hand end of the string. The rule $n\to o$ can be represented as $n'\to p'\to o'$ without any redundant symbols where ${\it m}\le {\it p}\le{\it n}<{\it o}$ and the primes indicate shortening of the strings by deleting the symbols below position {\it p} i.e. {\it p} is the leftmost pointer position in the computation from $n$ to $o$. ${\it n}={\it p}$ holds if and only if $n'=p'$ and $n'\to o'$ is a single TM step. If ${\it n}\ne {\it p}$ the rule $n'\to p'$ shows that $p'$ is reachable therefore $n'\to p'\to o'$ represents an IRR of type RLR, and of course the mirror image result applies to IRR's of type RLL.
In general let $X$ be a member of IRR({\em n}) i.e. the set of all IRR's with CS's of length ${\it n}$. Then $X$ can be represented as $A\to B\to C$ where the pointer swaps ends between $A$ and $B$ (thus this is either $1\to n$ or $n\to 1$ and is referred to as condition 1) to establish the reachability of $B$ necessary for $X$ to be an IRR. There may be more than one such CS $A$ for a single $B$ and the set of all such $A$ will be denoted by $O_1(B)$ (the same as $S(B)$ in \cite{jhn2017}), the 1 referring to the backward searching algorithm that terminates in condition 1 (see \cite{jhn2017} section 2.2). Likewise if it terminates in condition 2 i.e. the pointer comes back to where it was at the start of the backward search, the set of such endpoints will be denoted as $O_2(B)$, but these do not confer reachability and will not be referred to as origins. If the pointer is at the right in $A$ and at the left in $B$ then at $C$ it can be at the left or right so that $X$ must be represented as either of the triplet forms $n\to 1\to 0$ or $n\to 1\to n+1$ and having types RLL and RLR respectively. Likewise if the pointer is at the left in $A$ (the mirror image forms), $X$ must be represented by either of $1\to n\to n+1$ or $1\to n\to 0$, having types LRR and LRL respectively.
If $B$ is reachable but forward computation from it leads to a CS that has arisen before in this computation, this is a stationary cycle and the type of the IRR is then LC or RC. If the reverse computation path from $B$ leads to a stationary cycle, then this cycle must include $B$ to avoid a branch point in the forward computation that would not then be unique. Thus likewise the IRR is of type LC or RC.
From the definition of RR in the first paragraph of this section, if in the backward search from the LHS of an IRR, the pointer again reaches the same position it had in the LHS (condition 2), however much further back the backward search were to continue, it would not be possible from this alone to show that this LHS is indeed the LHS of an IRR. This is because if the computation is again run forward, this LHS has the pointer at the same point as a previous CS and is therefore not shown to be one of the list of CS's playing the special role in the above definition,
though it could possibly be shown to be one as a result of another backward search path. This is the justification of the terminating condition 2 in the backward search algorithm. See \cite{jhn2017} page 30.
This proves that
\begin{Lemma}\label{lemma1} The triplets $1\to n\to 0$, $1\to n\to n+1$, and $n\to 1\to n+1$, and $n\to 1\to 0$ representing TM computations each form an IRR {\em (}type LRL, LRR, RLR or RLL respectively{\em )} if and only if the origin indicated {\em (}the first member{\em )} is the first CS arrived at with the pointer in that position after tracing the computation back from the LHS {\em (}the middle member{\em )} and the pointer does not occur again in the position it had in the LHS in the reverse computation path from the LHS i.e there is no other CS $1$ or $n$ between the $1$ and the $n$ in the triplet forms above. Furthermore any IRR of length ${\it n}$ of one of the types RLL, RLR, LRL, LRR has one of these forms.\end{Lemma}
Generating all the IRR's based on Theorem 9.1 of \cite{jhn2013} starts with all single TM steps in the above notation $1\to 0$ (i.e. $\un{x}\to \_x$) or $1\to 2$ (i.e.
$\un{x}\to x\_$) where $x$'s represents an arbitrary symbol that could be different for each use. Every possible single symbol (called $\alpha$) is added at the pointer position in each RHS, and in each case the computation is taken as far as possible to get the new RHS unless a stationary cycle occurs. The resulting rule $LHS\to RHS$ is an IRR if it irreducible i.e. cannot be expressed with shorter strings of symbols. In the first case, adding $\alpha$ on the left and continuing the computation as far as possible gives results either of the form (i) $2\to 1\to 3$ or (ii) $2\to 1\to 0$ i.e. $\alpha\un{x}\to\un{\alpha}x\to xx\_\text{ or }\_xx$ respectively unless a stationary cycle is obtained. The results in case (i) are IRR's by Lemma~\ref{lemma1} because there can be no other CS's between the $2$ and the $1$ which is a single TM step. The results from (ii) are IRR's if and only if the first move beyond the $1$ is to $2$ i.e. the computation has the form $2\to 1\to 2 \to 0$ because this ensures that the rule $1\to 0$ contained in (ii) of length 2 is irreducible. Likewise for the mirror image case starting with a rule of the form $1\to 2$ adding the $\alpha$ on the right and continuing gives results of the form $1\to 2\to 0$ ($\in \text{IRR}(2)$) or of the form $1\to 2\to 3$ ($\in\text{IRR}(2)$ if and only if the first move from the $2$ is to $1$).
Consider extending this to the general case of generating all the IRR $Y$ of length ${\it n}+{\rm 1}$ based on the single IRR $X$ of length ${\it n}\ge {\rm 2}$ and having the form $n\to 1\to n+1$, which can be also be written as $A\to\ B\to C$ for some CS's $A$,$B$, and $C$. First the computation $A\alpha\to B\alpha\to C\alpha$ holds where $\alpha$ is any symbol the TM uses. Clearly by Theorems 5.4 and 9.1 of \cite{jhn2013} every such IRR $Y$ can be obtained starting from the LHS $B\alpha$ if an appropriate $\alpha$ can be found. The symbol $\alpha$ must be chosen so that $B\alpha$ is reachable i.e. $O_1(B\alpha)\ne\emptyset$. These are all the terminal CS's of length ${\it n}+{\rm 1}$ from the backward searching algorithm starting from $B\alpha$ and ending in condition (1). Each of these branches has a point where the pointer first reaches $n$ and this CS is $A\alpha$ because the $\alpha$ has yet played no part, so $O_1(B\alpha)=O_1(A\alpha)$, thus the backward search algorithm is applied to $A\alpha$, and identifying all possible values of $\alpha$ i.e. the values of $\alpha$ for which $O_1(A\alpha)\ne\emptyset$ by generating all its origins for each such $\alpha$. Also the forward computation from $C\alpha$ is continued as far as possible to generate the RHS of $Y$ and hence what its type is (LRR, LRL, RLR, RLL, LRC, or RLC) the last two cases coming from a stationary cycle in the forward computation from $C\alpha$.
If the pointer is at the left in $A$ and $C$ and the right in $B$ (the mirror image case) the added arbitrary symbol $\alpha$ will be on the left. This procedure for generating the all the IRR $Y$ of length {\em n}$+1$ like this from an IRR $X$ of length {\em n}, including the mirror image case where the triplet form of $X$ is $1\to n\to 0$, will denoted by the function $F$. $F$ applied to an IRR of type LC or RC is the empty set. This proves that
\begin{Theorem}\label{irr_ind_thm} Every member of IRR{\em (}${\it n}+{\rm 1}${\em )} can be obtained using $F$ from some $X\in\text{IRR}${\em (}n{\em )} of type RLR or LRL for ${\it n}\ge {\rm 2}$. Also, because forward computation is unique e.g. the RHS of an IRR is uniquely determined by is LHS, but the origins may be more than one, the sets of IRR obtained like this for different $X$ {\em (}different $B${\em )} must be disjoint i.e. $F^{-1}$ applied to a member of IRR{\em (}${\it n}+{\rm 1}${\em )} is a unique member of IRR{\em (}n{\em )}. The first part can be written symbolically as
\begin{equation}\label{irr_ind}\text{IRR}({\it n}+{\rm 1})=\bigcup _{X\in IRR({\it n})}\{ F(X)\}\end{equation}
\end{Theorem}
The following is the general outline showing an IRR triplet of length {\em n} of type RLR (type RLR with origin having the pointer at the right) and the possible types of result (except the cases where a stationary cycle occurs) of this argument for a given symbol $\alpha$ that could include a new IRR triplet of length ${\it n}+{\rm 1}$.
\begin{equation}\label{irr_deriv1}
%\arraycolsep=5pt
\mleft.
\mkern-10mu\begin{array}{lc@{}c}\begin{array}{@{}c@{}}\text{Cannot be used to}\\\text{prove reachability of } 1\end{array}&1&\to\\\text{Proves reachability of }1&n+1&\to\end{array}\mright\}n\to 1\to n+1\mleft\{\begin{array}{@{}ccc@{}}\to &0&\text{type RLL}\\\to &n+2&\text{type RLR}\end{array}\mright.
\end{equation}
The 3 central CS's refer to a member of IRR({\em n}), and the leftmost, central, and rightmost CS's refer to the corresponding member of IRR({\em n}$+1$) if reachability of the CS $1$ in the centre of \eqref{irr_deriv1} is found. The corresponding mirror image result for the LRL case is as follows:
\begin{equation}\label{irr_deriv2}
%\arraycolsep=4pt
\mleft.
\mkern-10mu
\begin{array}{l@{}c@{}r}\text{Proves reachability of }n+1&1&\to\\\begin{array}{@{}l}\text{Cannot be used to prove}\\\text{reachability of }n+1\end{array}&n+1&\to\end{array}\mright\}2\to n+1\to 1\mleft\{\begin{array}{ccc}\to &0&\text{type LRL}\\\to &n+2&\text{type LRR}\end{array}\mright.
\end{equation}
In this case note that because the $\alpha$ is added on the left, all the pointer positions in the IRR of length {\em n} have been increased by 1 when they appear in the embedded IRR of length {\em n}, so originally they would have been $1\to n\to 0$.
The above procedure allows the generation of all the IRR of a TM up to any given length and has been implemented \cite{tie}.
\section{\label{sec3}Introducing IRR patterns (IRRP's) and IGR's}
The derivation of IRR's from other ones (length ${\it n}$) following the procedure $F$ described above was found to often take the same form independent of ${\it n}$ provided ${\it n}$ is large enough. Then the obvious step is to describe these general results termed IRR generating rules (IGR's) so that they can be easily applied in any given case. These results have an LHS, the symbol $\alpha$ used in the derivation $F$, and an RHS that can match IRR's, and the existence of a member of IRR({\it n}) matching the LHS implies the existence of a corresponding member of IRR({\it n}+{\rm 1}) matching the RHS (or each of the parts of the RHS where there are more than one of them). The matching implies fixing the arbitrary strings $T_1$ and $T_2$. The general notation for an IGR is $LHS\stackrel{\alpha}\Rightarrow \{\text{set of RHS's}\}.$ Each of these RHS's and the LHS take the form of a generalised IRR (an IRRP or IRR pattern) in which two arbitrary strings appear, $T_1$ in the origin and $T_2$ in the RHS (of the IRRP), and the LHS (middle member of the IRRP) is omitted so that any LHS (of the IRRP) is matched.
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}
For example it is known that at least one IRR for this TM matches \begin{equation}\label{addalpha1}1\un{d}aT_1\to\to4\_caT_2.\end{equation} Using backward TM steps from \eqref{1} gives
\begin{equation}\label{addalpha2}\begin{tabular}{lccc}deriving the origin&old RHS&RHS&$\alpha$\\
$\alpha A$&$\alpha C$&&\\
$1\alpha\un{d}aT_1\mleft\{\begin{array}{@{}l@{}}
\stackrel{\alpha=a}{\leftarrow}2\un{d}daT_1\\
\stackrel{\alpha=c}{\leftarrow}2\un{a}daT_1\\
\stackrel{\alpha=d}{\leftarrow}2\un{c}daT_1\\
\end{array}\mright.$&
$\begin{array}{@{}l@{}}4\un{a}caT_2\\4\un{c}caT_2\\4\un{d}caT_2\\\end{array}$&
$\begin{array}{@{}l@{}}3\_bcaT_2\\1abc\un{T_2}\\5\_ccaT_2\end{array}$&$\begin{array}{@{}l@{}}a\\c\\d\end{array}$
\end{tabular}\end{equation}
of which the result for $\alpha=c$ has an RHS given where the pointer is at the first symbol of $T_2$. The results of $F$ are written as follows
\begin{equation}\label{addalpha3}\begin{array}{@{}l@{}}2\un{d}daT_1\to\to 3\_bcaT_2\\
2\un{a}daT_1\to\to1abc\un{T_2}\\
2\un{c}daT_1\to\to 5\_ccaT_2\end{array}\end{equation} for $\alpha= a,c,d$ respectively, and the complete IGR can be written as
\begin{equation}1\un{d}aT_1\to\to 4\_caT_2\mleft\{\begin{array}{@{}l@{}}\stackrel{a}{\Rightarrow}2\un{d}daT_1\to\to 3\_bcaT_2\\
\stackrel{c}{\Rightarrow}2\un{a}daT_1\to\to1abc\un{T_2}\\
\stackrel{d}{\Rightarrow}2\un{c}daT_1\to\to 5\_ccaT_2\end{array}\mright.\end{equation}
Note that in this argument, adding the arbitrary symbol $\alpha$ on the left (because the pointer in the origin is on the left) maintains the pointer being on the right hand end of the string of symbols in the LHS (not shown), and this property is implicit in an IRRP with the pointer at the left of the origin CS.
The result of this argument is that if an IRR of length ${\it n}$ conforms to \eqref{addalpha1}, then there are 3 more IRR's of length ${\it n}+{\rm 1}$ corresponding to \eqref{addalpha3} for $\alpha\in\{a,c,d\}$ respectively.
The second of these results in \eqref{addalpha3} has the pointer in the RHS on the right, so this IRR has type LRR and cannot be used to derive other IRR's. These are examples of rules that generate IRR's of length ${\it n}+{\rm 1}$ from other IRR's of length ${\it n}$. An IGR is defined as a logical implication having an IRRP on the left and sets of IRRP's on the right, one set for each value of $\alpha$ and the logical deduction follows the general procedure outlined in Theorem~\ref{irr_ind_thm}. Thus the strings with given symbols on the right of the implications are one symbol longer than those on the left.
To illustrate how an IRR can be derived from a member of IRR$({\rm 2})$ and a sequence of IGR's,
consider the following IRR of length 6 that was chosen from the computer program output and represented in $\text{Origin}\to\text{LHS}\to\text{RHS}$ format as follows:
\begin{equation}\label{eq130}3\un{a}ecccb\to1cadbd\un{b}\to 2dbdbdb\_.\end{equation}
The derivation of the first rule of \eqref{eq130} in single TM steps is
\begin{equation}\label{eq131}\begin{array}{@{}l@{}}3\un{a}ecccb\\4c\un{e}cccb\\5ca\un{c}ccb\\3caa\un{c}cb\\2ca\un{a}acb\\1cac\un{a}cb\\
2ca\un{c}dcb\\1cad\un{d}cb\\2cadb\un{c}b\\1cadbd\un{b}\end{array}.\end{equation}
Each time the pointer moves to where it has not been before while going backwards from the LHS, the derivation \eqref{eq131} generates IRR's as follows, followed by \eqref{eq130} in triplet and the abbreviated notation:
\begin{equation}\label{irr_array}\begin{array}{cc}\begin{array}{@{}l@{}}
2\un{c}b\to1d\un{b}\to5\_cd\in IRR(2)\\
1\un{d}cb\to 1bd\un{b}\to 3\_ecd\in IRR(3)\\
2\un{c}dcb\to 1dbd\un{b}\to 5\_cecd\in IRR(4)\\
4\un{e}cccb\to 1adbd\un{b}\to 2\_ececd\in IRR(5)\\\end{array}&
\begin{array}{@{}l@{}}2\un{c}b\to\to5\_cd\\1\un{d}cb\to\to3\_ecd\\2\un{c}dcb\to\to 5\_cecd\\4\un{e}cccb\to\to2\_ececd\end{array}\end{array}.
\end{equation}
This splitting up of the derivation of \eqref{eq130} results from the repeated application of $F$ to \eqref{irr_array}.1.
The abbreviated forms in \eqref{irr_array} can be obtained by applying in order the following results to the first of these IRR's $2\un{c}b\to\to5\_cd$.
\begin{equation}\label{f2_array}\begin{array}{@{}l@{}}2\un{T}_1\to\to 5\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}1\un{d}T_{\rm 1}\\1\un{e}T_{\rm 1}\end{array}\mright\}\to\to 3\_eT_{\rm 2}\\[15pt]
1\un{T}_1\to\to 3\_T_{\rm 2}\mleft\{\begin{array}{@{}l@{}}\stackrel{a}{\Rightarrow} 2\un{d}T_{\rm 1}\to\to 4c\un{T}_{\rm 2}\\\stackrel{c}{\Rightarrow} 2\un{a}T_{\rm 1}\to\to 2\_aT_{\rm 2}\\\stackrel{d}{\Rightarrow}2\un{c}T_{\rm 1}\to\to 5\_cT_{\rm 2}\end{array}\mright.\\[23pt]
2\un{c}dT_{\rm 1}\to\to 5\_T_{\rm 2}\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}4\un{e}ccT_{\rm 1}\\4\un{e}ecT_{\rm 1}\\5\un{c}adT_{\rm 1}\\5\un{e}adT_{\rm 1}\end{array}\mright\}\to\to2\_eT_{\rm 2}\\[30pt]
4\un{T}_{\rm 1}\to\to2\_eT_{\rm 2}\stackrel{c}{\Rightarrow} \mleft.\begin{array}{@{}l@{}}3\un{a}T_{\rm 1}\\4\un{b}T_{\rm 1}\end{array}\mright\}\to\to2db\un{T}_{\rm 2}\end{array}.\end{equation}
For the initial steps in the derivation of \eqref{eq130}, the following sub-cases of successive members of \eqref{f2_array} need to be applied in this order: 1, 3, 1, 1.
Equation \eqref{f2_array} contains examples of IGR's which allow one IRR to be derived from another by substituting for the $T_{\rm 1}$ and $T_{\rm 2}$ as the example shows, and express the application of the function $F$ in Theorem~\ref{irr_ind_thm} in a simpler form. The IGR's have two lengths, one associated with $T_{\rm 1}$ and one associated with $T_{\rm 2}$ and these are defined as the lengths of the corresponding strings on the RHS of the IGR thus for example the lengths of the IGR's in \eqref{f2_array} will be denoted by ${\rm (1,1), (1,1), (3,1), (1,2)}$ respectively.
The equations \eqref{f2_array} are in the shortest forms possible as can be verified from their derivations.
The symbols above the implication signs are the symbol added next to the pointer in the origin ($\alpha$) in the derivation of the IRR's from other ones as described in Section~\ref{sec2}, and are the first 4 symbols of the LHS of IRR \eqref{eq130} taken in reverse order. The results on the right in \eqref{f2_array} are all the results that can be derived from their LHS for that value of $\alpha$ and that length, though the third example is quite complicated and has other values of $\alpha$ ie. $b$ and $c$ with different lengths of results.
The IRRP on the RHS of the last member of \eqref{f2_array} is of type LRR and can be seen to not generate a new IRR directly. Applying the last member of \eqref{f2_array} to the last IRR of \eqref{irr_array} gives the initial result \begin{equation}3\un{a}ecccb\to1cadbd\un{b}\to2db\un{c}ecd\end{equation} which is not an IRR. Taking this computation as far a possible has to be an IRR (in this case having non-extendable type LRR) which is
\begin{equation}\label{final}3\un{a}ecccb\to\to 2dbdbdb\_\end{equation} and has $\alpha =c$ and is in agreement with \eqref{eq130}.
The derivations of \eqref{irr_array} and \eqref{final} illustrate the general procedure for deriving any IRR by repeated applications of $F$ i.e. applying a sequence of IGR's starting from a member of IRR(2).
This example suggests that if all the IGR's needed to generate the IRR$({\it n}+{\rm 1})$ from IRR$({\it n})$ were obtained, these could have lengths much less than ${\it n}+{\rm 1}$ and be fewer in number than the IRR$({\it n}+{\rm 1})$, and this might give a more compact way to represent the action of the TM. This will be followed up later, but many details need to be given first.
Every IGR represents the process of deriving a member of IRR$({\it n}+1)$ from a member of IRR$({\it n})$.
Therefore every such IGR can be obtained from another IGR (representing the process for deriving the member of IRR$({\it n})$ from a member of IRR$({\it n}-1)$) by an appropriate specialisation by adding the context symbols, applying $F$, then removing any redundant symbols as before. But the number of such context symbols needed seems to be unlimited.
\section{IRR generating rules (IGR's)}
\subsection{\label{sec4.1}Definition}
The general form of the derivation of an IRR from an existing one ($F$) can be expressed in detail as follows. Start with the IRR pattern (IRRP) of type LRL\begin{equation}\label{igr0}t_{\rm 1}\un{y_{\rm 1}}\ldots y_{{\it n}}T_{\rm 1}\to\to t_{\rm 2}\_z_{\rm 1}\ldots z_{{\it n}}T_{\rm 2}\end{equation} in which $T_{\rm 1}$ and $T_{\rm 2}$ have been omitted for brevity in much of this section. Here ${\it n}\ge {\rm 2}$ and the $t$'s are machine states and $y$'s and $z$'s are symbols.
Then proceed with $F$ i.e. add the symbol $\alpha$ to both sides where the pointer is in the RHS then the backward search gives the following types of results (excluding the stationary cycles)
which can be classified according to the rightmost position ${\it j}_{\rm 1}$ of the pointer relative to the symbol $y_{\rm 1}$
\begin{equation}\label{igr1}t_{\rm 1}\alpha \un{y_{\rm 1}}\ldots y_{\it n}\leftarrow \mleft\{\begin{array}{@{}l@{}}
t'_{\rm 1}\un{\alpha'}y_{\rm 1}\ldots y_{\it n}\text{ for }{\it j}_{\rm 1} = {\rm 0}\vspace{0.5em}\\
t'_{\rm 1}\un{\alpha'}y'_{\rm 1}\ldots y'_{{\it j}_{\rm 1}+{\rm 1}}y_{{\it j}_{\rm 1}+{\rm 2}}\ldots y_{\it n}\text{ for }{\rm 1}\le {\it j}_{\rm 1}\le {\it n-{\rm 2}}\vspace{0.5em}\\
t'_{\rm 1}\alpha y'_{\rm 1}\ldots y'_{{\it n}-{\rm 1}}\un{y'_{\it n}}\text{ for }{\it j}_{\rm 1}={\it n - {\rm 1}}\end{array}\mright.\end{equation} where the primes indicate a possible change in the symbol or state by the TM.
For the case ${\it n}={\rm 1}$, ${\it j}_{\rm 1}$ must be 0. Note that the form $t'_{\rm 1}\un{\alpha'}y'_{\rm 1}y_{\rm 2}\ldots y_{\it n}$ cannot arise because a single backward step to the right followed by two backward steps to the left could possibly alter $y_{\rm 1}$ and $y_{\rm 2}$ whereas a single backward step to the left has ${\it j}_{\rm 1}{\rm =0}$ as above.
The point of the classification is to enumerate all the different types of case that can arise after all the symbols that are not altered in the derivation are abstracted out. They are not mentioned explicitly and they form part of an arbitrary string (in this case $T_{\rm 1}$). The last reverse computation step in the last case giving ${\it j}_{\rm 1}={\it n} - {\rm 1}$ cannot not lead to a new IRR because this path and the CS reached does not imply the reachability of the LHS and so does not generate an IRR. If the LHS is reachable it must be because there is another origin with ${\it j}_{\rm 1} < {\it n} - {\rm 1}$. Therefore this case must be omitted for the purpose of generating IGR's, so ${\it j}_1$ can be restricted to the range ${\rm 0}\le {\it j}_{\rm 1}\le{\it n-{\rm 2}}$.
Similarly, for the computation of the new RHS, the results can be classified (again excluding stationary cycles) by the rightmost position ${\it j}_{\rm 2}$ of the pointer. So that this parameter also starts at 0, the pointer starts at position 0 at $\alpha$ and ends at position -${\rm 1}$ if it goes left and ends at position ${\it n}+{\rm 1}$ if it goes right giving the possibilities
\begin{equation}\label{igr2}t_{\rm 2}\un{\alpha}z_{\rm 1}\ldots z_{\it n}\to \mleft\{\begin{array}{@{}l@{}}t'_{\rm 2}\_\alpha' z'_{\rm 1}\ldots z'_{{\it j}_{\rm 2}}z_{{\it j}_{\rm 2}+{\rm 1}}\ldots z_{\it n}\text{ where }{\rm 0}\le {\it j}_{\rm 2}\le {\it n}\text{ or }\vspace{0.5em}\\ t'_{\rm 2}\alpha'z'_{\rm 1}\ldots z'_{\it n}\_\text{ if }{\it j}_{\rm 2}={\it n}+{\rm 1}\end{array}\mright..\end{equation}
This works whenever ${\it n}\ge{\rm 1}$.
If a stationary cycle occurred in \eqref{igr1} it would be noted, but it would have no effect on the general form of the possible results except that none of the forms of endpoint in \eqref{igr1} might result, because a stationary cycle would result in a closed circuit in the reverse search path from which paths ending in a type of endpoint in \eqref{igr1} or none could diverge. As noted earlier this would imply $t_1\alpha\un{y_1}\ldots y_{\it n}$ is in the closed circuit (to avoid a branch point in the forward computation implying it is not unique) so the derived IRR would have type RC. This implies a stationary cycle in the result of \eqref{igr2}.
The minimum number of symbols needed for the representation of \eqref{igr1} is easily seen to be
\begin{equation}\label{r1}{\it r}_{\rm 1}=\mleft\{\begin{array}{@{}l@{}l@{}}{\rm 1}&\text{ for } {\it j}_{\rm 1}={\rm 0}\\
{\it j}_{\rm 1}+{\rm 2}&\text{ otherwise}\end{array}\mright.\end{equation} provided ${\rm 0}\le {\it j}_{\rm 1}\le{\it n-{\rm 2}}$.
Similarly, the minimum number of symbols needed for the representation of the result of \eqref{igr2} is
\begin{equation}\label{r2}{\it r}_{\rm 2}=\text{min}({\it j}_{\rm 2}+{\rm 1},{\it n}+{\rm 1}).\end{equation}
The length of an IGR consists of the pair $({\it r}_{\rm 1},{\it r}_{\rm 2})$.
From \eqref{igr1} and \eqref{igr2} the remaining four combinations can be summarised as
\begin{equation}\label{igr_types}\begin{array}{@{}l@{}}
\mleft\{\begin{array}{@{}c@{}}t_{\rm 1}\un{T_{\rm 1}}\\
t_{\rm 1}\un{y}_{\rm 1}\ldots y_{{\it j}_{\rm 1}+1}T_{\rm 1}\end{array}\mright\}\to\to \mleft\{\begin{array}{@{}c@{}}
t_{\rm 2}\_z_{\rm 1}\ldots z_{{\it j}_{\rm 2}}T_{\rm 2}\\
t_{\rm 2}\_z_{\rm 1}\ldots z_{\it n}T_{\rm 2}\end{array}\mright\}
\stackrel{\alpha}{\Rightarrow}\vspace{0.5em}\\
\mleft\{\begin{array}{@{}c@{}}t'_{\rm 1}\un{\alpha'}T_{\rm 1}\\
t'_{\rm 1}\un{\alpha'}y'_{\rm 1}\ldots y'_{{\it j}_{\rm 1}+1}T_{\rm 1}\end{array}\mright\}\to\to
\mleft\{\begin{array}{@{}c@{}}t'_{\rm 2}\_\alpha'z'_{\rm 1}\ldots z'_{{\it j}_{\rm 2}}T_{\rm 2}\\
t'_{\rm 2}\alpha'z'_{\rm 1}\ldots z'_{\it n}\un{T_{\rm 2}}\end{array}\mright\}\end{array}.
\end{equation}
In this statement the top and bottom parts on the left of$\to\to$ can be combined independently with the top and bottom parts on the right of$\to\to$ i.e. there are four combinations possible. Of these the distinctions on the left of $\to\to$ do not change the type of the new IRR this being respectively LRL and LRR for the top and bottom parts on the right of $\to$. The IRR"s are also distinguished by different pairs $({\it j}_{\rm 1},{\it j}_{\rm 2})$. The type of an IGR is defined as the type of the IRR that it generates.
The corresponding right-left reversed results starting from an IRRP of type RLR also involve the parameters ${\it j}_{\rm 1}$ and ${\it j}_{\rm 2}$ obtained similarly but counting leftwards. Thus starting from
\begin{equation}\label{igr0.2}t_{\rm 1}y_{\it n}\ldots \un{y_{{\rm 1}}}\to\to t_{\rm 2}z_{\it n}\ldots z_{\rm 1}\_\end{equation}
likewise the following types of results are obtained
which can be classified according to the leftmost position relative to $y_{\rm 1}$, (${\it j}_{\rm 1}$) of the pointer. This satisfies ${\rm 0}\le {\it j}_{\rm 1}\le {\it n} - {\rm 1}$ and gives the following:
\begin{equation}\label{igr1.2}t_{\rm 1}y_{\it n}\ldots \un{y_{\rm 1}}\alpha\leftarrow \mleft\{\begin{array}{@{}l@{}}
t'_{\rm 1}y_{\it n}\ldots y_{\rm 1}\un{\alpha'}\text{ for }{\it j}_{\rm 1} = {\rm 0}\vspace{0.5em}\\
t'_{\rm 1}y_{\it n}\ldots y_{{\it j}_{\rm 1}+{\rm 2}}y'_{{\it j}_{\rm 1}+{\rm 1}}\ldots y'_{\rm 1}\un{\alpha'}\text{ for }{\rm 1}\le {\it j}_{\rm 1}\le {\it n}-{\rm 2}\vspace{0.5em}\\
t'_{\rm 1}\un{y'_{\it n}}y'_{{\it n} - {\rm 1}}\ldots y'_{\rm 1}\alpha \text{ for }{\it j}_{\rm 1}={\it n} -{\rm 1}\end{array}\mright.\end{equation}
Naturally, \eqref{r1} and \eqref{r2} and are still valid and all the types of result in \eqref{igr_types} have corresponding mirror image forms.
%and have the respective forms\\
%$1\to r_1\to 2\to n+1\to 1\to r_2\to 0$\\
%$1\to r_1\to 2\to n+1\to 1\to n+2$\\
%where the numbers (see \eqref{irr_deriv2}) indicate CS's where the pointer position is at some extreme points in the computation and $\alpha$ is this time at position 1 because it is the first symbol of the derived IRRP.
These types of result in \eqref{igr_types} are expressed with the shortest strings of symbols possible (i.e. the $y$'s and $z$'s). The strings $T_{\rm 1}$ and $T_{\rm 2}$ being arbitrary, so can be replaced by any strings. They do not have to have the same length.
These together with their left-right reversed forms are all the different types of IGR's possible.
Simple examples of these are in \eqref{f2_array}, and \eqref{igr1} and \eqref{igr2} indicate the general method for deriving them which is as follows. After the symbol $\alpha$ has been added to the origins on the left, reverse steps of the TM are made recursively, making sure that all possible reverse steps at each stage are done and stopping only when further reverse steps are impossible without the knowledge of what the strings $T_{\rm 1}$ and $T_{\rm 2}$ are, as described in Section~\ref{sec2}.
Thus an IGR is defined to have no redundant symbols where the pointer does not reach during its derivation. This is
analogous to IRR's being irreducible. In the derivation of the IGR from an IRR of length ${\it n}$, the backward search
to obtain the new origins and in the forward computation to obtain the new RHS, the pointer can obviously never move
outside the strings of lengths ${\it r_{\rm 1}}$ and ${\it r_{\rm 2}}$ introduced above except for the last TM step in the forward computation. In addition all these positions
of the pointer are reached during the derivation, the string of length ${\it r_{\rm 1}}$ for the derivation of a new
origin and the string of length ${\it r_{\rm 2}}$ for the derivation of the new RHS.
If the pointer ends up at one
end of the string $T_{\rm 2}$ ( indicated by $\un{T_{\rm 2}}$), the pointer position is clear from the context.
The pair of strings of symbols $(T_{\rm 1},T_{\rm 2})$ of lengths $({\it n}+{\rm 1}-{\it r_{\rm 1}},{\it n}+{\rm 1}-{\it r_{\rm 2}})$ respectively in \eqref{igr_types} that are not passed by the pointer during the derivation of an IGR from an IRR of length ${\it n}$ that is the basis of its LHS will be removed and listed as ``context pairs" so that the result is presented in its minimal form i.e. as an IGR in computer output.
A IGR could be defined to include all the possible results that can be derived for any possible value of $\alpha$ (an IGR member), i.e. all the possible origins for each $\alpha$, but if there is not likely to be confusion I will refer to such statements as IGR's as was done above. Thus an IGR would be the union over $\alpha$ of the IGR members.
An IGR member has the form (IRRP,$\alpha$) $\Rightarrow$ set of IRRP's, so the above results in \eqref{f2_array} could be described as IGR members. Thus it would be possible for different RHS's of the IGR to have different values of ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ corresponding to different values of $\alpha$, but these will be separated into different IGR's in the computer output.
\subsection{Computer representation and algorithms}
There can be a problem that occurs in the computer representation of the IGR's after the context strings have been separated out, which is to determine whether the original IRRP on its left is of type LRL or RLR. Provided ${\it n }>1$, it is not immediately obvious which is the case because the pointer positions and the parameter ${\it j}_{\rm 1}$ can be counted going either way, for example compare
\eqref{igr1} with \eqref{igr1.2}. The way it works is that a CS in the computer program output is represented as $CS(t,p,l,string)$ where $t$ is the machine state, $p$ is the pointer position counted from the left and is one for the symbol on the left, and is 0 for the position just to the left of this symbol, and is $l+{\rm 1}$ for the position just to the right of the string, where $l={\it n}$ is the length of the string. The string is spelled out inside quote marks in printed output. After the context strings have been split out of the derived IGR, the pointer position in the origin of the IRRP set on the LHS of \eqref{igr0} is 1 by convention if the
original IRRP (see \eqref{igr1}) (the LHS of the new IGR) was of type LRL or LRR because the pointer starts at 1 and is not affected by the truncation of the symbols from the right. If the original IRRP was of type RLR or RLL, the pointer position
in its origin (LHS of \eqref{igr0.2}) is initially by convention at ${\it n}$ (i.e. the right hand end)
and is reduced as a result of splitting out the context symbols. This for ${\it j}_{\rm 1}={\rm 0}$ is position ${\it n}$ minus the length of the string of symbols removed also ${\it n}$ i.e. {\rm 0}, and is ${\it n}$ minus the length of $y_{\it n}\ldots y_{{\it j}_{\rm 1} + {\rm 2}}$ otherwise, which is ${\it j}_{\rm 1} + {\rm 1}$. This value can never be 1, so
{\em
${\it j}_{\rm 1}=1$ is characteristic of the original IGR being of type LRL. This implies that the value $p = {\rm 1}$ in an origin CS on the LHS of an IGR in computer output indicates that the context strings ($T_{\rm 1}$ and $T_{\rm 2}$) are added on the right, and on the left otherwise.}
For the case ${\it n}={\rm 1}$ this is obvious from the RHS of the IRRP on the LHS of the IGR
which is of the form $t_{\rm 2}\_z_{\rm 1}$ or $t_{\rm 2}z_{\rm 1}\_$ according to whether the IGR is of type LRL or RLR respectively. This shows that this obvious convention for defining the pointer positions in the different cases distinguishes the LRL, LRR from the RLR, RLL types of IGR.
The above argument shows, when combined with Theorem~\ref{irr_ind_thm}, that\\
(1) every IRR of length ${\it n}+{\rm 1}$ of type RL can be derived by $F$ from another IRR of length ${\it n}$
of type LRL by an IGR with parameters ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ of type \eqref{igr_types}.1 (LRL \eqref{igr_types}) in satisfying
${\rm 1}\le\it r_{\rm 1}\le{\it n}$ and ${\rm 1}\le{\it r}_{\rm 2}\le{\it n}+{\rm 1}$ as described and\\(2)
every IRR of length ${\it n}+{\rm 1}$ of type LRR can be derived by $F$ from another IRR of length ${\it n}$ of
type LRL by an IGR of type \eqref{igr_types}.2 (LRR in \eqref{igr_types}) (with parameters ${\it r}_{\rm 1}$ and ${\it r}_{\rm 2}$ such
that ${\rm 1}\le\it r_{\rm 1}\le{\it n}$ and ${\it r}_{\rm 2}={\it n}+{\rm 1}$.
These can be applied recursively to show that
\begin{Theorem}\label{thm1}any extendable IRR (type LRL or RLR) of length $\ge {\it 3}$ can be obtained from a member of IRR(2) by a sequence of substitutions of IGR's as described here under case (1). Any non-extendable IRR (type RLL or LRR) can be obtained from a member of IRR(2) by the above substitutions (0 or more) followed by a single substitution step under case (2).
\end{Theorem}
This theorem is illustrated by the example at the beginning of this section.
This suggests the obvious process for generating the set of all the IGR's could start as follows after finding all the members of IRR(2). Essentially this was the method used in the latest version of the program \cite{tie_v3_2} to generate Table~\ref{table3}.
Find all the members of IRR(3) and the IGR's used to generate them from the IRR(2). These will be IGR's of lengths
$({\rm 1,1})$, $({\rm 1,2})$, $({\rm 1,3}), ({\rm 2,1})$, $({\rm 2,2})$, and $({\rm 2,3})$. Likewise the IRR(4) can be obtained from the IRR(3) and the IGR's summarising this can be added while not duplicating any IGR's already found etc.. This can be repeated to generate up to the IRR(${\it n}$). After a while hopefully to generate the ${\rm IRR}({\it n}+{\rm 1})$ from the ${\rm IRR}({\it n})$ will not require any IGR's that have not already been obtained for ${\it n}$ sufficiently large.
The following example was studied because the results from \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 results for the IGR's from TM \ref{tm2} were as follows in Table~\ref{table3} giving the maximum length of the computation rules as 10.
\newpage
\fontsize{10}{10}\selectfont
\begin{longtable}{ll}
\caption{IGR's generated by the computer program\label{table3}}\\
1&$1\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 3\_bT_2$\\
2&$1\un{c}aT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ca\\2\un{a}cb\end{array}\mright\}T_1\to\to 3\_bT_2$\\
3&$1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}1\un{a}baa\\1\un{a}bab\end{array}\mright\}T_1\to\to 3\_bT_2$\\
4&$1\un{c}ababT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccbT_1\to\to 3\_bT_2$\\
5&$1\un{c}ababcT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccacT_1\to\to 3\_bT_2$\\
6&$1\un{c}abcT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ccac\\2\un{a}ccbc\end{array}\mright\}T_1\to\to 3\_bT_2$\\
7&$1\un{c}cT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bcT_1\to\to 3\_bT_2$\\
8&$2\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 3\_bT_2$\\
9&$3\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}2\un{a}T_1\to\to 3\_bT_2$\\
10&$3\un{T_1}\to\to 1\_aT_2\stackrel{c}{\Rightarrow}3\un{c}T_1\to\to 2bb\un{T_2}$\\
11&$1\un{c}cT_1\to\to 1\_ababT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3bbbbb\un{T_2}$\\
12&$1\un{c}aT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ca\\3\un{c}cb\end{array}\mright\}T_1\to\to 3\_bababaT_2$\\
13&$1\un{c}aaT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{b}baa\\2\un{b}bab\end{array}\mright\}T_1\to\to 3\_bababaT_2$\\
14&$1\un{c}ababT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccbT_1\to\to 3\_bababaT_2$\\
15&$1\un{c}ababcT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccacT_1\to\to 3\_bababaT_2$\\
16&$1\un{c}abcT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ccac\\3\un{c}ccbc\end{array}\mright\}T_1\to\to 3\_bababaT_2$\\
17&$1\un{c}cT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3\_bababaT_2$\\
18&$2\un{T_1}\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3\_bababaT_2$\\
19&$1\un{c}cT_1\to\to 1\_ababcT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3bbbbbc\un{T_2}$\\
20&$1\un{c}aT_1\to\to 1\_abcT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ca\\3\un{c}cb\end{array}\mright\}T_1\to\to 1bbbb\un{T_2}$\\
21&$2\un{T_1}\to\to 1\_cT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 1bb\un{T_2}$\\
22&$1\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 1\_aT_2$\\
23&$1\un{c}aT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ca\\2\un{a}cb\end{array}\mright\}T_1\to\to 1\_aT_2$\\
24&$1\un{c}aaT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}1\un{a}baa\\1\un{a}bab\end{array}\mright\}T_1\to\to 1\_aT_2$\\
25&$1\un{c}ababT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccbT_1\to\to 1\_aT_2$\\
26&$1\un{c}ababcT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccacT_1\to\to 1\_aT_2$\\
27&$1\un{c}abcT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ccac\\2\un{a}ccbc\end{array}\mright\}T_1\to\to 1\_aT_2$\\
28&$1\un{c}cT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bcT_1\to\to 1\_aT_2$\\
29&$2\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 1\_aT_2$\\
30&$3\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}2\un{a}T_1\to\to 1\_aT_2$\\
31&$2\un{T_1}\to\to 3\_baT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3bbb\un{T_2}$\\
32&$1\un{c}aT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ca\\3\un{c}cb\end{array}\mright\}T_1\to\to 3\_babaT_2$\\
33&$1\un{c}aaT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2\un{b}baa\\2\un{b}bab\end{array}\mright\}T_1\to\to 3\_babaT_2$\\
34&$1\un{c}ababT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bbccbT_1\to\to 3\_babaT_2$\\
35&$1\un{c}ababcT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bbccacT_1\to\to 3\_babaT_2$\\
36&$1\un{c}abcT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ccac\\3\un{c}ccbc\end{array}\mright\}T_1\to\to 3\_babaT_2$\\
37&$1\un{c}cT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3\_babaT_2$\\
38&$2\un{T_1}\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3\_babaT_2$\\
39&$3\un{T_1}\to\to 3\_babT_2\stackrel{c}{\Rightarrow}3\un{c}T_1\to\to 3\_babaT_2$\\
40&$1\un{T_1}\to\to 1T_2\_\mleft\{\begin{array}{@{}l@{}}\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3T_1\un{a}\\3T_1\un{b}\end{array}\mright\}\to\to 2T_2b\_\\\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1T_2b\_\end{array}\mright.$\\
41&$1\un{T_1}\to\to 2T_2\_\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3T_1\un{a}\\3T_1\un{b}\end{array}\mright\}\to\to 3T_2b\_$\\
42&$3\un{T_1}\to\to 2T_2\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 2T_2c\_$\\
43&$1\un{T_1}\to\to 3T_2\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 3T_2c\_$\\
44&$3T_1bb\un{b}\to\to 3T_2\_\stackrel{c}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}2T_1aab\un{c}\\2T_1abb\un{c}\end{array}\mright\}\to\to 3T_2c\_$\\
45&$1\un{T_1}\to\to 2T_2b\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 3\un{T_2}bc$\\
46&$1\un{T_1}\to\to 2T_2c\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1T_2bb\_$\\
47&$3\un{T_1}\to\to 3T_2c\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 2T_2bb\_$\\
48&$1\un{T_1}\to\to 2T_2bb\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1\un{T_2}abc$\\
49&$3\un{T_1}\to\to 3T_2bb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 1\un{T_2}aba$\\
50&$3\un{T_1}\to\to 3T_2cb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3T_2bbb\_$\\
51&$3T_1bb\un{b}\to\to 3T_2cb\_\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\mright\}\to\to 3T_2bbb\_$\\
52&$3\un{T_1}\to\to 3T_2bbb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3\un{T_2}baba$\\
53&$1\un{T_1}\to\to 3T_2bbbbb\_\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3T_1\un{a}\\3T_1\un{b}\end{array}\mright\}\to\to 3\un{T_2}bababa$\\
54&$3\un{T_1}\to\to 3T_2bbbbb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3\un{T_2}bababa$\\
55&$3T_1bb\un{b}\to\to 3T_2bbbbb\_\stackrel{a}{\Rightarrow}\mleft.\begin{array}{@{}l@{}}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\mright\}\to\to 3\un{T_2}bababa$\\
\end{longtable}
\fontsize{12}{14}\selectfont
Theorem~\ref{thm1} demonstrates the importance of derivations of IRR's using chains of IGR's substituted into each other.
Connected with this is the relation `can be followed by' which restricts the possible sequences of substitutions of IGR's. This is given in Table~\ref{table4} and requires a match on the LHS and on the RHS in which the machine state and the symbol strings must match, as well as the direction for adding $\alpha$, and the first IGR must be of extendable type i.e. it must generate IRR's of type LRL or RLR.
In Table~\ref{table4} and later in the paper, the IGR's from TM~\ref{tm2} will be named by the numbers in Table~\ref{table3}. Alternatively a part or a sub-part of an IGR will be referred to by following that number by a letter that refers to the part of the IGR associated with that letter which is the symbol above $\Rightarrow$ i.e. the symbol called $\alpha$, possibly followed again by a number that determines the position of the CS in the list of CS's comprising the origin of the RHS of the IGR. For example the IGR
$1\un{T_1}\to\to 1T_2\_\stackrel{a}{\Rightarrow} 3T_1\un{b}\to\to 2T_2b\_$ is IGR 40a2. On the RHS of Table~\ref{table3} (to the right of $\to$) all parts and sub-parts of an IGR referenced are included. Every IGR on the left of $\to$ can be followed by any IGR on the right of $\to$ in the same row.
\fontsize{10}{10}\selectfont
\begin{longtable}{ll}
\caption{The relation `can be followed by'\label{table4}}\\
$1\to$ &$22,23,24,25,26,27,28,32,33,34,35,36,37$\\
$3b1,3b2,4,5,7,8\to$ &$22$\\
$\mleft.\begin{array}{@{}l@{}}2b1,2b2,6b1,6b2,9,13c1,13c2,14,15,\\17,18,33c1,33c2,34,35,37,38\end{array}\mright\}\to$ &$29,31,38$\\
$12c1,12c2,16c1,16c2,36c1,36c2,39\to$ &$30,39$\\
$22\to$ &$1,2,3,4,5,6,7,10,11,12,13,14,15,16,18,19$\\
$23b1,23b2,27b1,27b2,30\to$ &$8,18$\\
$24b1,24b2,25,26,28,29\to$ &$1$\\
$32c1,32c2\to$ &$29,38$\\
$40a1,40a2\to$ &$42$\\
$41a1\to$ &$49,50,52,54$\\
$41a2\to$ &$44,49,50,51,52,54,55$\\
$42\to$ &$41,46$\\
$47\to$ &$41,45,48$\\
$50\to$ &$43,53$\\
$51a1,51a2,51a3\to$ &$49,52,54$\\
$51a4\to$ &$44,49,52,54,55$\\
\end{longtable}
\fontsize{12}{14}\selectfont
By examining these IGR's in Table~\ref{table3} and the compatibility relations in Table~\ref{table4} the following facts become evident:
\begin{enumerate}
\item There are a relatively small number of distinct origins of the LHS's of these IGR's. Each of these together with the value of $\alpha$ necessarily gives rise to the same origin of the RHS of the IGR regardless of the RHS of the LHS of the IGR. For example $1\un{c}aT_{\rm 1}$ with $\alpha=b$ is always associated with $\mleft.\begin{array}{@{}l@{}}2\un{a}ca\\2\un{a}cb\end{array}\mright\}T_{\rm 1}$ in IGR's 2 and 23.
\item IGR's can be chained together by substitutions for the arbitrary strings $T_{\rm 1}$ and $T_{\rm 2}$.
\item In the chain of substitutions, there is a restriction on which IGR can follow another IGR; this results from the structure of the IGR's themselves. This information is given in Table~\ref{table4}.
\item Other restrictions result from the way in which sequences of substitutions operate.
\item By carrying out $F$ to the RHS of an IGR, it is sometimes possible to deduce that no previous IGR's to a sequence of them can affect which IGR's can follow the sequence.
\item If by carrying out $F$ to any sequence of IGR's to find which IGR's can be next in the sequence, there always results IGR's that have already been listed, then it would show that the set of IGR's found is sufficient to generate all the IRR's for the TM.
\item The starting points of these chains of IGR's to generate all the IRR's must be the IGR's involved in the IRR(2) together with their associated contexts. These are given in Table~\ref{table8}.
\begin{longtable}{c|c}
\caption{The IGR's and contexts that give on their RHS's all the IRR(2)\label{table8}}\\
IGR&Set of context pairs\\
\hline
$41$ &$(a,b)$\\
$22$&$(b,b)$\\
$40$&$(c,b)$\\
$8$&$(c,c)$\\
$9$&$(a,a),(b,a)$\\
$47$&$(c,)$\\
$45$&$(a,)$\\
$21$&$(c,)$\\
$10$&$(b,),(a,)$\\
\end{longtable}
\end{enumerate}
Temporarily disregarding property 1, and in the hope that Table~\ref{table3} would have property 6, manual calculation was started beginning with IGR $22$ because
from Table~\ref{table4}, IGR $22$ clearly plays an important role. By restricting at first consideration to IGR $1$ followed by IGR $22$ denoted by $1\cdot 22$ fewer possibilities will result for the following IGR's.
It was soon found that this is likely to get very unwieldy because of the large number of cases to be considered, Nevertheless it was instructive to try.
The first case to be considered was what IGR's that can follow $1\cdot 22$?
The sequence of IGR's $1\cdot 22$ is $1\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}1\un{c}cT_1\to\to 1\_abT_2$ obtained by substituting $cT_1$ for $T_1$ and $bT_2$ for $T_2$ in IGR $22$. The result of this is a composite IGR. The IRR's that it generates are a subset of the IRR's generated by looking for which IGR's follow IGR $22$ alone. By trying to apply $F$ to this general form, results dependent on the arbitrary strings $T_{\rm 1}$ and $T_{\rm 2}$ will be produced.
This starts by considering what CS's can lead to $1\alpha\un{c}cT_1$ for any symbol $\alpha$. It is easy to see that \begin{equation}\label{eq23}1\alpha\un{c}cT_1\mleft\{\begin{array}{@{}l@{}}\stackrel{\alpha = b}{\leftarrow}1\un{c}ccT_1\\\leftarrow 2\alpha c\un{c}T_1\end{array}\mright..\end{equation}
in one TM step in either case. The first of these will lead to the IRRP
$1\un{c}ccT_{\rm 1}\to\to 3\_babT_{\rm 2}$ because $1\un{b}abT_{\rm 2}\to 3\_babT_{\rm 2}$. The strings $ccT_{\rm 1}$ and $abT_{\rm 2}$ are not changed because the pointer does not enter them in the derivation of the IRRP, so the IGR used is $1\un{T_{\rm 1}}\to\to 1\_T_{\rm 2}\stackrel{b}{\Rightarrow} 1\un{c}T_{\rm 1}\to\to 3\_bT_{\rm 2}$ i.e. IGR $1$ in Table~\ref{table3}. The second result of \eqref{eq23} has reached condition 2 in the backward search if $T_{\rm 1}$ is the empty string, which implies that there is no point in continuing the backward search further in that case.
If $T_{\rm 1}$ is not the empty string, the general reasoning indicates that $T_{\rm 1}$ needs to be specialised further by prepending the sequence of IGR's $1\cdot 22$ with others, however the backward search can be logically continued giving
\begin{equation}2\alpha c\un{c}T_1\leftarrow 2\alpha\un{b}cT_1\mleft\{\begin{array}{@{}l@{}}\stackrel{\alpha = b}{\leftarrow} 1\un{a}bcT_1\\\stackrel{\alpha = c}{\leftarrow}2\un{b}bcT_1\end{array}\mright.\end{equation}
which is independent of $T_{\rm 1}$ because the first of these reverse steps from $2\alpha c\un{c}T_1$ cannot lead to any other result than the one indicated (because there is no TM step ending in $2\_\beta$ no matter what the symbol $\beta$ in $T_{\rm 1}$ is). This shows that if $T_{\rm 1}$ is not the empty string, the result will always be that condition 1 is reached, giving another IGR.
(Instead, expressing \eqref{eq23} as an IGR (shortest form) gives the same result as \ref{table3}.1 with $\un{T_1}$ replaced by $\un{c}cT_1$ and $T_2$ replaced by $abT_2$ after combining it with $1\un{b}abT_2\to 3\_babT_2$ and identifying
the longest strings of symbols that are not altered.)
Returning to the general argument,
taking a further step back in the sequence of IGR's to be considered gives for example $22\cdot 1\cdot 22$.
This sequence gives \begin{equation}
1\un{T_1}\to\to 3\_T_2\stackrel{22b}{\Rightarrow}1\un{c}T_1\to\to 1\_aT_2\stackrel{bb}{\Rightarrow}1\un{c}ccT_1\to\to 1\_abaT_2\end{equation} the second part of which comes from $1\cdot 22$ above. The symbols above the symbols $\Rightarrow$ respectively indicate IGR $22$ with $\alpha = b$ and as above ($1\cdot 22$) with two steps of IGR's with $\alpha = b$. Applying $F$ to this starts by the backward search from $1\alpha\un{c}ccT_1$ giving (e.g. using \eqref{eq23})
\begin{equation}\label{eq2}1\alpha\un{c}ccT_1\mleft\{\begin{array}{@{}l@{}}\leftarrow 2\alpha c\un{c}cT_1\leftarrow 2\alpha\un{b}ccT_1\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}bccT_1\\\stackrel{c}{\leftarrow}2\un{b} bccT_1\end{array}\mright.\\\stackrel{b}{\leftarrow} 1\un{c}cccT_1\end{array}\mright..\end{equation}
Combining this with $1\un{b}abaT_2\to 3\_babaT_2\text{ and }1\un{c}abaT_2\to 3babb\un{T_2}$ and absorbing any unchanged symbols into $T_1$ or $T_2$ because the pointer has not reached them gives the results $1$, $7$ and
\begin{equation}\label{eq1}1\un{c}cT_1\to\to 1\_abaT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3bbcb\un{T_2}.\end{equation}
[As an aside comment, Actually $17$ is a special case of $11$ which is itself a special case of \eqref{eq1} formed by successively decreasing the length of the string in the RHS by 1. Because in these three cases, $17$ uniquely has the pointer finishing at the $\alpha$ end of the string in RHS of the RHS, such a sequence as \eqref{eq1}, $11$ and $17$ cannot be continued by specialising $T_{\rm 2}$ and continuing the computation to the end in the RHS so any sequence of IGR's ending with $17$]
In \ref{eq2} because of the absence of a branch of the backward search taking the pointer to the opposite end of the string from $\alpha$, it implies that any special cases of $T_{\rm 1}$ that would result from prior IGR's in the sequence could not affect the new origins of IGR's that could be next in the sequence, only the RHS's could vary. This is because the general form of the derivation of a new origin follows the pattern in \eqref{eq2} whatever substitutes for $T_{\rm 1}$. Because $1$ can also be preceded by $24b1$, $24b2$, $25$, $26$, $28$, $29$, these cases could now be considered in turn preceding $1\cdot 22$.
These results are very complicated and the way forward seems unclear, because in the derivation of new IGR's by applying $F$, both the new origins then the new RHS's have to be found and there are a lot of different combinations of cases that can arise. Also the number of cases to be considered seems prohibitively large based on the relation `can be followed by' in Table~\ref{table4}.
The next two sections are very sketchy but might contain some good ideas.
\section{A modification of $F$ to be applied to generating IGR's from IGR's}
Can this procedure be made to work? It looked interesting but it doesn't work yet. Perhaps it can be shown to lead to a method based on the method in Section~\ref{sec7} to get the LIGR's from which the IGR's follow.
An obvious step to take is to attempt to directly derive Table~\ref{table3} starting from all the IGR's needed to derive the IRR(2) from the TM table without generating all the IRR's. The method is based on the procedure I called $F$ and will be modified as follows and denoted by $F^*$ because instead of explicit sequences of symbols, arbitrary strings $T_1$ and $T_2$ are involved. In the backward search to get the new origins, if the pointer reaches adjacent to the arbitrary string $T_1$, the two cases $T_1=\varepsilon$ and $T_1\ne\varepsilon$ need to be considered separately where $\varepsilon$ is the empty string. In the first case the computation halts because this is what happens with $F$, but in the second case, the backward search continues but the CS's with the pointer adjacent to $T_1$ are recorded, until it is stopped by
(i) no further backward TM steps being possible, (ii) the pointer reaching $\alpha$ or (iii) a stationary cycle is found. In the forward computation of the new RHS, the presence of the arbitrary string $T_2$ merely stops the computation where the pointer reaches the end of $T_2$.
Another reason for a change to $F$ is because for the simplest case with ${\it r}_{\rm 1}={\rm 1}$ i.e. an IGR of the form $\cdots\Rightarrow t\un{y}T_1\rightarrow\cdots$ to start with, $F^*$ starts from the backward search beginning with $t\alpha\un{y}T_1$ from which at most one reverse TM step can be done giving say $t'\un{\alpha'}yT_1$, so the symbol $y$ is not involved and can be put into $T_1$, so the derived IGR has $t'\un{\alpha'}T'_1$, and ${\it r}_{\rm 1}'={\rm 1}$ as is ${\it r}_{\rm 1}$ thus derived IGR's must always have ${\it r}_{\rm1}={\rm 1}$ which is obviously not going to generate all the results in Table~\ref{table3}. To solve this while maximising the generality of the results i.e. involving the contexts to the minimal extent possible, try involving the context symbol on the left only if ${\it r}_{\rm 1}={\rm 1}$.
Therefore the general procedure I propose for a TM is to first generate the set IRR(2). These can be abbreviated to IGR's with length (1,1) by taking out the context pair and will be put into the set $S$ but they should be kept in initially. Then the following procedure is repeated until hopefully it comes to an end with no more members to be processed. Take the next unmarked member of $S$, mark it and apply $F^*$ to it generating new IGR's (for both cases $T_1=\varepsilon$ and $T_1\ne\varepsilon$) that are added to $S$ if either are different from all the existing members of $S$.
On studying how this works, a problem was found arising when applying $F^*$ to IGR 40.1 in Table~\ref{table3}, which itself arises with the context pair $(c,b)$ i.e. the IRR $3c\un{d}\to\to 2bb\_$. The origins are $3T_1\un{a}$ and $3T_1\un{b}$ which are written more succinctly as $3T_1\un{d}$ and the context symbol on the left is $c$. So putting this back in starting the procedure $F^*$ gives the CS $3T_1c\un{d}\alpha$ from which the backward search gives
$3T_1c\un{d}\alpha\mleft\{\begin{array}{@{}l@{}}\stackrel{\alpha=b}{\leftarrow} 1T_1cd\un{b}\\\leftarrow3T_1\un{c}d\alpha\stackrel{d=b,T_1\ne\varepsilon}{\leftarrow}1T_1c\un{b}\alpha\mleft\{\begin{array}{@{}l@{}}\stackrel{\alpha=a}{\leftarrow}3T_1cb\un{d}
\\\stackrel{\alpha=c}{\leftarrow}2T_1cb\un{c}\end{array}\mright.\\
\end{array}\mright.$.
On the right $F^*$ gives $\mleft\{\begin{array}{@{}l@{}} 2T_2bb\un{a}\to 3T_2bbb\_\\2T_2bb\un{b}\to 2T_2bbc\_\\
2T_2bb\un{c}\to 1\un{T_2}abc\end{array}\mright.$ which can be shortened, by absorbing symbols that cannot be changed because the pointer does not reach them into $T_1$ or $T_2$, gives the following:
\begin{equation}\label{fstar}\begin{array}{@{}l@{}}
3T_1c\un{d}\to\to 2T_2\_\stackrel{\alpha=a,T_1\ne\varepsilon}{\Rightarrow} 3T_1cb\un{d}\to\to 3T_2b\_\\
3T_1c\un{d}\to\to 2T_2\_\stackrel{T_1=\varepsilon}{\Rightarrow}3\un{c}d\alpha\\
3\un{T_1}\to\to 2T_2\_\stackrel{\alpha=b,T_1\ne\varepsilon}{\Rightarrow} 1T_1\un{b}\to\to 2T_2c\_\\
3T_1c\un{d}\to\to 2T_2bb\_\stackrel{\alpha=c,T_1\ne\varepsilon}{\Rightarrow} 2T_1cb\un{c}\to\to 1\un{T_2}abc\end{array}.\end{equation}
The results \eqref{fstar}.1, \eqref{fstar}.3 and \eqref{fstar}.4 are IGR's expressed more fully involving the condition $T_1\ne\varepsilon$ and \eqref{fstar}.2 just gives an RCS.
The computer program output shows that the application of $F^*$ to IGR 40.1 does not appear in the analysis of this TM because IGR 40.1 only appears once in the set of full IGR's (with contexts) having the context pair $(c,b)$. This implies that the above analysis only applies with $T_1=\varepsilon$ invalidating the reasoning requiring the right hand halves of \eqref{fstar}.1 and \eqref{fstar}.4 to be IRR patterns involved in the analysis of TM1.
\section{Introducing LIGR's}
Returning to property 1 of Table~\ref{table3}, it appears that the left and right hand halves of the RHS of each IGR can be derived independently (it is only $\alpha$ that connects them), and the left hand sides (the origin of the LHS and the origin of the RHS) have a lot of repetition, many appearing multiple times, thus the presentation in Table~\ref{table3} is far from optimal although the list of IGR's given there for generating any IRR from the IRR(2) does now seem to be complete and can can be derived systematically up to any given length of the IRR's.
What is hinted at above is that there could be an alternative algorithm to generate the IGR's directly from each other by applying $F$ in these general cases for arbitrary strings $T_{\rm 1}$ and $T_{\rm 2}$. This became extremely complicated because of dealing with new origins and RHS's together. It is this that I want to arrive at by just considering at first the derivation of new origins for the IGR's, for which I introduce the new concept of LIGR (Left IGR) because the RHS's can always be filled in later just with forward computations.
The aim of this section will be to demonstrate this algorithm before formulating it precisely and hopefully show that if it does come to an end, then the LIGR's so obtained from a Turing Machine will be sufficient rules to allow the computation of all the IRR's to any level desired. Unfortunately in the present example it has as yet proved too difficult to complete this analysis.
\subsection{LIGR's\label{5.1}}
An LIGR or left IGR is the origin of the LHS of an IGR, and the origin of the RHS of the same IGR, combined with the symbol $\alpha$. For example IGR's $2$, $23$ have the common LIGR
\begin{equation}\label{ligr1}1\alpha\un{c}aT_1\stackrel{\alpha = b}{\leftarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ca\\2\un{a}cb\end{array}\mright\}T_1.\end{equation} Similarly
\begin{equation}\label{ligr2}1\alpha\un{c}aT_1\stackrel{\alpha =c}{\leftarrow}\mleft.\begin{array}{@{}l@{}}3\un{c}ca\\3\un{c}cb\end{array}\mright\}T_1\end{equation}
is common to IGR's $12$ and $20$. These examples show that in common with IGR's, LIGR's can have parts (labelled by $\alpha$) and sub-parts that will be labelled in lexicographical order of the strings with the most significant symbol (sorted first) being where the pointer is. Also the symbol $\alpha$ may be omitted for brevity because it is always at the opposite end of the string from $T_1$, which in the context of LIGR's will be called just $T$ because $T_{\rm 2}$ is not involved. For example if \eqref{ligr1} and \eqref{ligr2} are treated as parts of the complete LIGR $X$ then \eqref{ligr1} is $X.b$ and \eqref{ligr2} is $X.c$. The length of an LIGR will be the length of the symbol string on its right, which is one more than the length of the symbol string on the left assuming $\alpha$ is omitted.
This notation with the reverse facing arrow will be used because as usual the arrows ($\leftarrow$ or $\to$) indicate the direction of the computation of the TM as distinct from logical derivation indicated by $\Rightarrow$. Thus LIGR's are also reverse computation rules, but very special ones because they arise in the context of IGR's.
There are obvious advantages of treating IGR's in this way as can be seen in the drastically shortened list of results (12 LIGR's from Table~\ref{table3} not counting parts and sub-parts separately). Moreover if an LIGR (on its LHS) matches the origin of an IRR, $F$ applied to this IRR has as origins the result of the substitution for $T_1$ in the RHS of the LIGR, and its RHS can be computed directly from the original RHS using alpha of the LIGR. Thus the RHS's can be filled in later and do not need to be recorded in the rule for generating new IRR's from existing ones.
\subsection{Associativity of composition}
Underlying this is the assumption that the operation $\cdot$ is associative. This is such a basic result that it might never be questioned being regarded as obvious. It means that for any LIGR's $L_1$,$L_2$ and $L_3$ the following is true:
\begin{equation}\label{assoc} (L_1\cdot L_2)\cdot L_3 = L_1\cdot(L_2\cdot L_3)\end{equation}
which implies that for any string of LIGR's, the compositions can be done in any order provided the sequence of LIGR's is maintained e.g.
$L_1\cdot((L_2\cdot L_3)\cdot L_4) = (L_1\cdot L_2)\cdot (L_3\cdot L_4)$.
Suppose $L_i = x_{i1}\un{y_{i1}}\ldots y_{i\hspace{1pt}r_i}T_i\leftarrow x_{i2}\un{y'_{i1}}\ldots y'_{i\hspace{1pt}r_i+1}T_i$ for $1\le i\le 3$ (general notation where $\alpha$ is on the left; it works similarly if $\alpha$ is on the right).
To show this first note that the meaning of an LIGR is that the CS on the left can be replaced by the CS on the right regardless of the arbitrary string denoted by $T$ or $T$ with a subscript. To apply an LIGR, the string $T$ is chosen to match the given CS if possible. If it matches, it can be replaced by the corresponding string on the right with the same chosen substring $T$.
Thus the composition of the three LIGR's written out in full as
\begin{equation}\begin{array}{l}
L_1 = x_{11}\un{y_{11}}\ldots y_{1\hspace{1pt}r_1}T_1\leftarrow x_{12}\un{y'_{11}}\ldots y'_{1\hspace{1pt}r_1+1}T_1\\
L_2 = x_{21}\un{y_{21}}\ldots y_{2\hspace{1pt}r_2}T_2\leftarrow x_{22}\un{y'_{21}}\ldots y'_{2\hspace{1pt}r_2+1}T_2\\
L_3 = x_{31}\un{y_{31}}\ldots y_{3\hspace{1pt}r_3}T_3\leftarrow x_{32}\un{y'_{31}}\ldots y'_{3\hspace{1pt}r_3+1}T_3\end{array}\end{equation}
requires the matching of $L_2$ and $L_3$ by choosing $T_2$ and $T_3$ for the given $T_1$ such that
\begin{equation}\label{only}\begin{array}{l}
x_{21}=x_{12},\un{y_{21}}\ldots y_{2\hspace{1pt}r_2}T_2 = \un{y'_{11}}\ldots y'_{1\hspace{1pt}r_1+1}T_1\\
x_{31}=x_{22},\un{y_{31}}\ldots y_{3\hspace{1pt}r_3}T_3 = \un{y'_{21}}\ldots y'_{2\hspace{1pt}r_2+1}T_2\end{array}\end{equation}
Although there are 9 cases here because $r_2$ can be greater, equal, or less than $r_1+1$, and likewise for $r_3$ and $r_2+1$, \ref{only} is the {\em only} condition needed regardless of the order of composition, therefore this order does not affect the result.
\subsection{\label{5.2}Sequences of LIGR's and $F$}
A sequence of LIGR's is a chain of LIGR's that can follow each other written with $\cdot$ between them so for example if\begin{equation}L_1= 1\un{c}aT\stackrel{b}{\leftarrow}\mleft.\begin{array}{@{}l@{}}2\un{a}ca\\2\un{a}cb\end{array}\mright\}T.\end{equation}
\begin{equation}L_2 = 2\un{T}\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}T\\\stackrel{c}{\leftarrow}2\un{b}T\end{array}\mright.\end{equation}
\begin{equation}L_3 = 1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\end{equation}
then
\begin{equation}\begin{array}{@{}l@{}} L_{1.2} = 1\un{c}aT\stackrel{b}{\leftarrow}2\un{a}cbT\\
L_{2.1} = 2\un{T}\stackrel{b}{\leftarrow}1\un{a}T\end{array}\end{equation}
and the chain $L_{1.2}\cdot L_{2.1}\cdot L_3$ is the the result of the three substitutions of the LHS performed in that sequence giving
\begin{equation}\label{ligr}1\un{c}aT\leftarrow 2\un{a}cbT\leftarrow 1\un{a}acbT\leftarrow 1\un{c}aacbT\end{equation} so the combination is $1\un{c}aT\stackrel{bbb}{\leftarrow}1\un{c}aacbT.$
Similarly to the way in which $F$ was applied to sequences of IGR's combined together, this can obviously be done for sequences of LIGR's.
%\begin{comment}
begin comment//put this back temporarily
Now the result of $F$ will be defined as a pair $(F_{\rm 1},F_{\rm 2})$, the first component $F_{\rm 1}$ being the set of LIGR's as possible n'ext LIGR's in the sequence, and the second component $F_{\rm 2}$ being the set of RCS's.
%\end{comment}
end comment//put this back temporarily
The result of $F$ applied to a sequence of LIGR's of length 1 cannot give rise to any residual CS's because there is not enough ``room" and can be affected by adding an extra LIGR to the beginning of the sequence. To show this
suppose an LIGR or a sequence of LIGR's combined as above $X_1$ with $\alpha$ on the left has a sub-part of the form
\begin{equation}s_1\label{ligr3}\un{y_1}\ldots y_rT\stackrel{\alpha}{\leftarrow}s_2\un{z_1}\ldots z_{r+1}T.\end{equation}
Likewise let $X_2$ be\begin{equation}\label{ligr4}s'_1\un{y'_1}\ldots y'_{r'}T\stackrel{\alpha'}{\leftarrow}s'_2\un{z'_1}\ldots z'_{r'+1}T.\end{equation}
Then for the sequence $X_2\cdot X_1$ to be possible requires, $s'_2 = s_1$ and $\un{y_1}\ldots y_r$ is a substring of $\un{z'_1}\ldots z'_{r'+1}$ on the left, and $\alpha$ is on the left for $X_{\rm 2}$ too. The result of $X_2\cdot X_1$ is
\begin{equation}\label{ligr5}s'_1\un{y'_1}\ldots y'_{r'}T\stackrel{\alpha'}{\leftarrow}s'_2\un{z'_1}\ldots z'_{r'+1}T =s_1\un{y_1}\ldots y_rz'_{r+1}\ldots z'_{r'+1}T\stackrel{\alpha}{\leftarrow}s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{r'+1}T.\end{equation}
Comparing \eqref{ligr3} with \eqref{ligr5} shows the effect on $X_1$ of preceding it with $X_2$ which is to add extra symbols next to $T$ in its right hand member. Therefore the results of the backward search starting from the RHS of \eqref{ligr3} are reproduced when started from the RHS of \eqref{ligr5} and shortened to the shortest form provided the pointer ends up at $\alpha$; these give rise to LIGR's. In addition there may be some extra LIGR's resulting from the pointer reaching the extra symbols which may be classified by the position of the rightmost symbol reached. Crucially, this happens only when $F$ applied to $X_{\rm 1}$ leads to cases in the backward search when the pointer ends up at the opposite end of the string from $\alpha$ i.e. condition 2 is reached because the above searches can then be truncated when they reach the opposite end from $\alpha$. These were termed residual CS's (RCS's) because they are cases that do not lead directly to any more IGR's and LIGR's but indicate the possibility of them if the sequence of LIGR's to which $F$ is applied increases in length as a result of a preceding LIGR appended to the sequence in question.
Finally, there may be results of this where the pointer ends up at the opposite end of the string from $\alpha$ i.e. the pointer goes right when the rightmost symbol is reached.
These are the new RCS's in the result of $F$ applied to \eqref{ligr5} and will be designated as $F_2(X_{\rm 2}\cdot X_{\rm 1})$.
Therefore it makes sense to introduce $\Delta F_{\rm 1}$ as the set of extra LIGR's from $F$, as a result of adding an extra LIGR $Y_{\rm 1}$ at the beginning of the sequence where $S=X_{\rm 1}\cdot X_{\rm 2}\ldots\cdot X_{\rm n}$ is a sequence of LIGR's:
\begin{equation}\label{ligr6}\Delta F_1(Y_1,S)=F_1(Y_1\cdot S)\setminus F_1(S).\end{equation}
In this notation the result of the preceding paragraph can be written as \begin{equation}F_{\rm 2}(S)=\emptyset\Rightarrow \Delta F_1(Y_1,S)=\emptyset.\end{equation} The converse is not true because it could be that there are some reverse search paths that go beyond the symbols in $S$ but none of them go back to $\alpha$. In this case $F_{\rm 2}(Y_{\rm 1}\cdot S)\ne\emptyset$ or some of these reverse search paths just reach an end because at some point no reverse TM step is possible.
Here the result of $F$ applied to a sequence of LIGR's was split into two components $F=(F_{\rm 1},F_{\rm 2})$.
Also the result of $F$ for a collection of LIGR's in a sequence is defined as the result of $F$ for the combined LIGR, which actually only depends on the its RHS and results from applying the backward search algorithm to it. A consequence of this is that the arguments of $F$ can be written in different ways e.g. the sequence of LIGR's can be replaced by the equivalent sequence of symbols in the RHS of the combined LIGR.
\subsection{\label{apply_f}Evaluating \eqref{ligr6} one extra symbol at a time}
The following is a description of the above calculation taken one symbol at a time. It can be applied when several symbols are added in one step from a single LIGR as was the original intention, or when a sequence of LIGR's is added that each contribute just one symbol etc..
The result of \eqref{ligr6} can obviously be obtained by adding each symbol one at a time and accumulating the results for each extra symbol added. Suppose the extra symbols added to the starting CS $s_2\un{z_1}\cdots z_{r+1}$ from $S$ as a result of preceding it with $Y_1$ are $z'_{r+1}\ldots z'_{r'+1}$ then one can write:
\begin{equation}\label{ligr7}\begin{array}{@{}l@{}}F_1(Y_1\cdot S)=F_1(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{r'+1})\\
= \mleft[\bigcup_{i=r+1}^{i=r'+1}
\Delta F_1(z'_i,s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{i-1})\mright]\cup F_1(s_2\un{z_1}\ldots z_{r+1})\end{array}\end{equation}
where the first term of the union is \eqref{ligr6} and the second term is $F_1(S).$
Each step corresponding to one term in the multiple union uses the RCS's from the previous step. These RCS's with the single extra symbol are the starting points of the continuing backward search which would of course stop if at some point there were no more RCS's.
In more detail, in order to calculate \begin{equation}\Delta F_1(z'_i,s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{i-1})\end{equation}
which is by definition \begin{equation}F_1(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_i)\setminus F_1(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{i-1}),\end{equation}
in the backward search the pointer must reach $z'_i$ before ending up at the right or left end (otherwise duplicate results are obtained that are to be eliminated), therefore the backward search can start from \begin{equation}F_2(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{i-1})\un{z'_i}\end{equation} where the last symbol is concatenated to the residual results of $F_2$.
If the pointer reaches $\alpha$ the result is a new LIGR otherwise it gives an RCS which is in
\begin{equation}F_2(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_i).\end{equation}
Putting ${\it i = r}+{\rm 1}$ initially, then this shows that the backward search starts from $F_2(s_2\un{z_1}\ldots z_{r+1})\un{z'_{r+1}}$ i.e. the set of RCS's from the initial backward search for $S$ each appended with the first extra symbol $z'_{r+1}$ on the right. If the pointer reaches $\alpha$ as the backward search continues, this gives a new LIGR otherwise it gives an RCS in $F_2(s_2\un{z_1}\ldots z_{r+1}z'_{r+1})$ if the pointer reaches the opposite end of the string of symbols, or comes to a point where the backward search can go no further or end in an infinite stationary loop. Then for ${\it i = r}+{\rm 2}$, the backward search starts from this appended with $z'_{r+2}$ on the right. Again the backward search continues either the pointer reaches $\alpha$ giving a new LIGR, or away from it giving an RCS in $F_2(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}z'_{r+2})$ etc..
This continues until all the new symbols have been added and all possible backward search paths are followed at each stage. If at any stage there are no RCS's in $F_2$ it terminates. All the new LIGR's are accumulated and any final RCS's are noted. Naturally, there is an equivalent version of this if $\alpha$ is on the right.
It follows from this that the calculation of the combined results of $\Delta F$ applied to any sequence of LIGR's that can precede $S$ is also given by going back one symbol at a time and finding $\Delta F$ in each case without any restriction on the new symbol added other than up to that point $F_2\ne\emptyset$. This might be a better general algorithm than the one following, but in the example for TM~\ref{tm2} I use a mixture of both strategies.
\section{\label{sec7}The procedure for finding the LIGR's for a TM}
This is extremely complicated and is very hard to describe so the reader is not expected to understand it immediately. For this reason I attempt to do so here in this section and then the procedure is applied to TM \eqref{tm2} in detail in Section \ref{5.5} when it should become clearer.
comment: This should start from the LIGR's involved (LIGR(2)) in getting the IRR(2) from the TM steps. The IGR(2) have been found already in the computer program. The LIGR(2) have already been found in \eqref{ligr_2}.
\begin{alg}\label{alg5.1}
The algorithm $F$ applied repeatedly can generate all the IRR's starting with members of IRR(2) therefore
the first step is to find $L$ the set of LIGR's corresponding to the formation of the members of IRR(3) from those of IRR(2) by applying $F$. Doing this starts with putting the arbitrary symbol $\alpha$ at one end of the pair of symbols in the origin of the member of IRR(2) and the backward search starts with the pointer at the middle symbol. A single reverse TM step gives a member of IRR(3) if the pointer moves to $\alpha$ and if it goes the other way condition 2 occurs giving an RCS, so only one symbol is involved therefore the reduced form (the LIGR) that results (if the pointer goes to $\alpha$) must have length 1. The RHS of each of these LIGR's of length 1 already is an RCS because the pointer is already adjacent to $T$.
Next the LIGR's involved in forming the IRR$({\it n}+{\rm 1})$ from the IRR$({\it n})$ need to be found for all ${\it n}\ge{\rm 3}$. This can be done by searching for all LIGR's that can follow sequences of LIGR's that have already been found. This involves applying $F$ to an arbitrary sequence $S$ of such of LIGR's substituted into each other as in Section~\ref{5.2}. This has to be done until closure i.e. until no more LIGR's can be found if this is repeated one more time. For this, as shown in Section~\ref{5.2}, $\Delta F_1$ and $F_2$ need to be found only if the previous $F_2\ne\emptyset$
i.e. only if $F$ applied to $S$ gives $F_2(S)\ne\emptyset$, carry out $F$ to obtain $\Delta F_1(X\cdot S)$ and $F_2(X\cdot S)$ for each LIGR $X$ that can precede $S$ where the requirement for precedence is given in \eqref{ligr5}. This calculation can start from the previous $F_2$ with the substitution made for $T$ indicated by $X$. This condition will be met for each of the initial set of LIGR's in $L$ because as shown above their RHS's each have the form of an RCS. Any new LIGR's from $\Delta F_1(X\cdot S)$ are added to $L$. For any members of $F_2(X\cdot S)$ apply this algorithm recursively i.e. with $X\cdot S$ taking the place of $S$ above etc.. It is expected that this algorithm will terminate because the matching criterion for new LIGR's that can be prepended to the sequence gets increasingly stringent as the length of the strings increases. If this happens repeat this algorithm the ``grand search" with the new enlarged set $L$ of LIGR's. This should in fact be just to add to the previous results instead of repeating them because the previous LIGR's are still in $L$. Repeat this ``grand search" until the set of extra LIGR's added to $L$ in one cycle is empty.
\end{alg}
The main part of this algorithm is to find, for each sequence of LIGR's that can be substituted into each other in sequence as in \eqref{ligr}, what the next LIGR in the sequence could be by applying the backward search i.e. $F$ as usual. For this $\Delta F_1$ and $F_2$ need to be found only if the previous $F_2\ne\emptyset$.
The result of $\Delta F_1$ adds to the set of LIGR's if any new ones have been found and the grand search continues back only if the current $F_2\ne\emptyset$.
To obtain $\Delta F_1$ the methods of subsection~\ref{apply_f} apply if needed. If $F_2=\emptyset$ then the grand search continues with the next possible sequence of LIGR's according to the following: the current first LIGR in the sequence is replaced by its successor if there is one according to a defined ordering. If not, go back one step down the grand search tree by deleting the current first member of the sequence and repeat this procedure.
LIGR, or one or more LIGR's are produced some of which may be new ones to be added to the set.
If this also yields any RCS's, this implies that an extra LIGR added at the beginning of the sequence could result in extra LIGR's as a result of applying $F$. All possible preceding LIGR's one at a time must be prepended to the sequence being studied which is checked for following LIGR's using $F$ etc. and recursively. If such a sequence of LIGR's does not have any RCS's in the result of $F$, the grand search continues from the next sequence of LIGR's to be checked in some pre-defined order. This continues until, if this procedure terminates, every possible sequence of LIGR's has been analysed to find all the possible subsequent LIGR's that are possible. In order to do this the current set of LIGR's has to be maintained together with the set of LIGR's that can precede each LIGR.
\begin{Definition}
A finite set of LIGR's $Z$ is closed under $F$ if for any sequence of members of $Z$ that can be substituted into one another in sequence as in \eqref{ligr}, the backward search $F$ applied to the result of this generates results that are each a member of the set $Z$.
\end{Definition}
\begin{Theorem}\label{Theorem_5.3}
If there is a finite set $Z$ of LIGR's for a Turing Machine that is closed under $F$ as described above and includes all the LIGR's involved in obtaining the set IRR(3) from the set IRR(2) then every IRR for that TM can be obtained from a member of IRR(2) by a sequence of applications of LIGR's each in $Z$ as described in Section~\ref{5.2}.
\end{Theorem}
It is also obvious that no LIGR's could be removed from this set $Z$ and $Z$ still have this property because members of $Z$ are only put there when they are required.
\begin{proof}
Consider deriving the members of IRR(4) from IRR(3). This can be done by applying $F$ to each member of IRR(3) and accumulating all the results. Applying $F$ gives results that come from members of $Z$ because any LIGR following an LIGR in $Z$ is also in $Z$ by the closure property. Likewise deriving members of IRR(5) involve applying $F$ to members of IRR(4) that themselves have been derived using a pair of LIGR's. Again all such derivations of LIGR's that can follow this sequence are in $Z$ by the closure property etc..
\end{proof}
This all assumes that $Z$ is finite.
The case if the closure algorithm does not terminate leading to an infinite set $Z$ closed under $F$
might be interesting.
The remainder of this section contains the application of Algorithm~\ref{alg5.1} to the example \eqref{tm2}.
The results are not all presented in the order in which they were derived i.e. there are forward references to LIGR's that have not yet been derived. This is because $L$ is increasing in size as the algorithm proceeds and to avoid duplication, the results are presented assuming the current $L$ is the final one and in the order determined by the grand search i.e.``depth first" (if not the results will be added to). This all assumes that the final $L$ is finite.
It will be useful to use the symbol $d$ in the remainder of this paper to mean either $a$ or $b$. This arose as an abbreviation useful for TM \eqref{tm2}. Each instance of $d$ will be independent of any other one in a CS, so that all combinations are possible. If the combinations that are possible are a subset of these, this is more complicated and alternatives will be given in braces, but this does not usually happen. This will allow many cases to be considered simultaneously so speeding up the computations. When doing reverse computations, all possible reverse steps from any of the combinations will be included.
That there is a finite number of LIGR's has been strongly suggested in the present case by the computer results that established Table~\ref{table3} using any value of the maximum length of the strings involved ({\it n}) between 10 and 16 and show the same result. The computations rapidly increase in number and time taken as {\it n} increases.
Checking the arguments requires the derivation route from the initial LIGR's in $L$ to all the final ones which will be given so that the results can all be checked.
The following are the 9 LIGR's that arise from the derivation of the IRR(2) from the single TM steps:
\begin{equation}\label{ligr_2}\begin{array}{lcl}
1&2\un{T}\stackrel{b}{\leftarrow}1\un{a}T\\
2&3\un{T}\stackrel{b}{\leftarrow}1T\un{b}\\
3&1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\\
4&2\un{T}\stackrel{c}{\leftarrow}2\un{b}T\\
5&1\un{T}\stackrel{c}{\leftarrow}2T\un{c}\\
6&1\un{T}\stackrel{a}{\leftarrow}3T\un{a}\\
7&1\un{T}\stackrel{a}{\leftarrow}3T\un{b}\\
8&3\un{T}\stackrel{c}{\leftarrow}3\un{c}T\\
9&3\un{T}\stackrel{b}{\leftarrow}2\un{a}T\\
\end{array}.\end{equation}
The relation ``can possibly be preceded by" on the LIGR's is also being discovered continually as the LIGR's are being discovered. The criterion is that the RHS of the preceding LIGR must match the LHS of the original LIGR in state, string of symbols and direction. The relation ``can possibly be preceded by" initially among the 7 LIGR's is given by
\begin{equation}\begin{array}{@{}l@{}l@{}}
1\text{\hspace{1cm}}&4,9\\
2\text{\hspace{1cm}}&6,7\\
3\text{\hspace{1cm}}&1,3\\
4\text{\hspace{1cm}}&4,9\\
5\text{\hspace{1cm}}&2\\
6\text{\hspace{1cm}}&2\\
7\text{\hspace{1cm}}&2\\
8\text{\hspace{1cm}}&8\\
9\text{\hspace{1cm}}&8\\
\end{array}.\end{equation}
\subsubsection{A few useful lemmas}
There are several important lemmas that speed up the computation of the results in this section that are conveniently collected here. In all these $x$ is a state and $T_1$ and $T_2$ are strings.
\begin{Lemma}
Suppose $\alpha$ is on the left and $\un{T_1}$ has the pointer at its leftmost symbol then:\newline
If $F$ applied to $x\un{T_1}$ gives no RCS's then $F$ applied to $x\un{T_1}T_2$ gives no RCS's.\newline The mirror image version with $\alpha$ on the right is:\newline
If $F$ applied to $x\un{T_1}$ gives no RCS's then $F$ applied to $xT_2\un{T_1}$ gives no RCS's.
\end{Lemma}
\begin{proof}
Start by assuming that applying $F$ to $x\un{T_1}T_2$ with $\alpha$ on the left gives some RCS's, then there is a sequence of reverse TM steps starting from $x\alpha \un{T_1}T_2$ leading to a CS with the pointer at the right hand end. Then truncating the starting CS by $T_2$ results in a truncated set of reverse TM steps leading to another CS which is the RCS for applying $F$ to $x\un{T_1}$. This contradicts the assumption therefore $F$ applied to $x\un{T_1}T_2$ gives no RCS's.
\end{proof}
\begin{Lemma}\label{lemma_ex}
If applying $F$ to $x\alpha\un{T_1}$ gives a set $L_1$ of LIGR's then applying $F$ to $x\alpha\un{T_1}T_2$ gives a set $L_2$ of LIGR's such that $L_2\supseteq L_1$.
The mirror image version is:\newline
If applying $F$ to $x\un{T_1}\alpha$ gives a set $L_1$ of LIGR's then applying $F$ to $xT_2\un{T_1}\alpha$ gives a set $L_2$ of LIGR's such that $L_2\supseteq L_1$.
\end{Lemma}
\begin{proof}
Applying $F$ to $x\un{T_1}$ gives a set of LIGR's determined by a set of reverse TM steps taking the pointer from where it starts in $x\alpha\un{T_1}$ to a CS with the pointer at $\alpha$. By replacing the string $T_1$ by $T_1T_2$ these reverse TM steps can still be carried out with the string $T_2$ playing no role, but in addition there could be more such sequences of reverse TM steps giving rise to more LIGR's.
\end{proof}
Note that this result can sometimes be used to identify LIGR's produced by the program ``new origins" using the values of $j_1$ produced.
\begin{Lemma}If $F$ applied to $x\un{T_1}$ gives has an LIGR with the parameter value $j_1$ which is the maximum number of pointer positions away from $\alpha$ -1 in the sequence of CS's involved in the proof of the LIGR as defined in Section~\ref{sec4.1}, then $F$ applied $x\un{T_1}$ truncated to a string of length $j_1+1$ including $\alpha$ has some RCS's and is the longest such truncation guaranteed to have some RCS's. The truncation is such that it removes the symbols furthest from $\alpha$.\end{Lemma}
\begin{proof} This is obvious.\end{proof}
\begin{Lemma}
If applying $F$ to $x\un{T_1}$ generates the LIGR's $L$ and no RCS's then applying $F$ to $x\un{T_1}T_2$ generates likewise only the LIGR's $L$.\end{Lemma}
\newpage
Note that these LIGR's all appear in the final set but the numbering is slightly changed in the final set due to
the use of $d$ meaning $a$ or $b$ and other LIGR's including those of length 1 being found.
While carrying out the main argument in Section~\ref{5.5} the following results emerged and are collected here for convenience because they may need to be referred to anywhere throughout the main argument. They arose as induction hypotheses to deal with endlessly repeating situations that arose during the application of Algorithm~\ref{alg5.1} to TM~\ref{tm2} or other complex situations arising there and so simplify the presentation of this.
\begin{Lemma}\label{lemma_1}
The reversed TM cannot cross where the symbol $a$ is while going left, or even arrive at it.
\end{Lemma}
\begin{proof}
There is no reverse TM step of the form $xa\_\leftarrow CS$ therefore
the pointer cannot get left of or arrive at where the $a$ is, which is maintained.\end{proof}
\begin{Lemma}\label{lemma_2}
The reversed TM cannot cross where the symbol $c$ is while going right.
\end{Lemma}
\begin{proof}
If the pointer is just left of the symbol $c$ i.e. in the CS $\_c$ a reverse step to the right is only possible if it is to the CS $2\un{c}$ (using $2\un{c}\to 1\_c$ in reverse). The next reverse TM step (if one is possible) must be to the left because there are no TM steps of the form $CS\to 2\_y$. Thus the symbol $c$ is maintained and the pointer has not crossed it.\end{proof}
\begin{Lemma}\label{sequence}
A consequence of \eqref{lemma_1} is that an $a$ in the CS string to the left of the pointer restricts the search for LIGR's and RCS's to the substring to the right of the $a$. Therefore if starting from a CS that is actually a set of CS's (i.e. it contains symbols $d$ that can be $a$ or $b$) it is possible treat this as a set of nested cases where in each case one more of the $d$'s is replaced by $b$ (starting from the $d$ to the immediate left of the pointer), and the $d$ to the immediate left of this $d$ (if it exists) is $a$. This starts with the $d$ to the immediate left of the pointer being $a$, and proceeds going left by one $d$ at a time. The first case has the simplest analysis under $F$, and ends with choosing all the $d$'s to be $b$. In these analyses, Lemma~\ref{lemma_ex} implies that each set of LIGR's produced is a superset of the preceding case. Also the set of RCS's produced will be empty except possibly for the last case where all the $d$'s were replaced by $b$. Therefore applying $F$ to the original set of CS's simply results in the set of LIGR's and RCS's from the final case where all the $d$'s are $b$.
\end{Lemma}
\begin{proof}This is obvious. See the examples in Section~\ref{Sequences ending with LIGR 7}\end{proof}
\begin{Lemma}\label{lemma2}
The backward search from any CS of the form $1Tadb\un{a}aa\alpha$
cannot lead to any new LIGR's or RCS's provided the string $T$ contains the symbol $a$.
\end{Lemma}
\begin{proof} This is by continuing the backward search from there. This gives the following tree
\begin{equation}1Tadb\un{a}aa\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tad\un{c}a^3\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}3Tadc\un{d}a^2\alpha\leftarrow 3Tad\un{c}da^2\alpha\leftarrow \mleft\{\begin{array}{@{}l@{}}2Ta\un{a}cda^2\alpha\\1Tadc\un{b}a^2\alpha *\end{array}\mright.\\1Ta\un{c}ca^3\alpha\end{array}\mright.\\3Tadba\un{d}a\alpha\end{array}\mright.\end{equation}
\begin{equation}1Tadc\un{b}a^2\alpha\leftarrow3Tadcb\un{d}a\alpha\leftarrow 2Tadc\un{a}da\alpha\leftarrow
2Tad\un{b}ada\alpha\leftarrow 1Ta\un{a}bada\alpha\end{equation}where the computation stopped whenever either no reverse TM step is possible, or when by Lemmas ~\eqref{lemma_1} or \eqref{lemma_2} the pointer cannot go beyond the string as a result of continued backward searching. Because all branches of the tree do eventually lead to a halt, no LIGR's or RCS's can result from further backward searching.
\end{proof}
\begin{Lemma}\label{lemma3}
Backward searching starting from any CS of the form $1Td\un{c}abada\alpha$ leads to exactly the following set of CS's regardless of the arbitrary string $T$ in addition to possible CS's with the pointer at the left depending on $T$:
\begin{equation}\begin{array}{@{}l@{}}
1Tdca^2dbd\un{b}\\3Tdca^3db\un{d}\\2Tdca^3db\un{c}\\1Tdcdbdbd\un{b}\\3Tdcdcbdb\un{d}\\2Tdcdcbdb\un{c}\\3Tdcdbadb\un{d}\\2Tdcdbadb\un{c}\end{array}\end{equation}
These are related to the set of LIGR's in {\rm \eqref{newligrs1}.15-19}.
\end{Lemma}
\newpage
\begin{proof}
The backward search stops if either (1) the pointer can be shown not to get to the right because of $cx$ on the right of the pointer or (2) no further backward TM steps are possible or (3) the end of the known symbols on the string is reached or (4) a stationary cycle is reached. The numbers after * indicate continuations.
\begin{equation}\begin{array}{@{}l@{}}1Td\un{c}abada\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\un{c}cabada\alpha\\3Tdc\un{d}
bada\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}3Td\un{c}dbada\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}2T\un{a}cdbada\alpha\\1Tdc\un{b}
bada\alpha\end{array}\mright.\\ 1Tdcd\un{b}ada\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdc\un{c}
bada\alpha\\3Tdcdb\un{d}da\alpha *1
\end{array}\mright.\end{array}
\mright.\end{array}\mright.\\[40pt]
*1\leftarrow\mleft\{\begin{array}{@{}l@{}}2Tdcd\un{a}dda\alpha\leftarrow 1Tdc\un{a}adda\alpha\leftarrow3Tdca\un{d}dda\alpha\leftarrow 1Tdcad\un{b}da\alpha*2\\1Tdcdbd\un{b}a\alpha*5\end{array}\mright.\\[20pt]
*2\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdca\un{c}bda\alpha\\3Tdcadb\un{d}a\alpha\leftarrow2Tdcad\un{a}da\alpha\leftarrow1Tdca\un{a}ada\alpha\leftarrow3Tdcaa\un{d}da\alpha*3\end{array}\mright.\\[20pt]
*3\leftarrow 1Tdcaad\un{b}a\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdcaa\un{c}ba\alpha\\3Tdcaadb\un{d}
\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}2dca^2d\un{a}d\alpha\leftarrow1Tdcaa\un{a}ad\alpha*4\\1Tdca^2dbd\un{b}\end{array}
\mright.\end{array}\mright.\\[30pt]
*4\leftarrow3Tdca^3\un{d}d\alpha\leftarrow1Tdca^3d\un{b}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdca^3\un{c}b\alpha\\3Tdca^3db\un{d}\\2Tdca^3db\un{c}\end{array}\mright.\\[20pt]
*5\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdcdb\un{c}ba\alpha\leftarrow 1Tdcd\un{c}cba\alpha\\
3Tdcdbdb\un{d}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}2Tdcdbd\un{a}d\alpha\leftarrow1Tdcdb\un{a}ad\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}
1Tdcd\un{c}aad\alpha*6\\3Tdcdba\un{d}d\alpha*8\end{array}\mright.\\1Tdcdbdbd\un{b}\end{array}\mright.\end{array}\mright.\\[30pt]
*6\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdc\un{c}caad\alpha\\3Tdcdc\un{d}ad\alpha\leftarrow3Tdcd\un{c}dad\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}2Tdc\un{a}cdad\alpha\\1Tdcdc\un{b}ad\alpha\leftarrow 3Tdcdcb\un{d}d\alpha*7\end{array}\mright.\end{array}\mright.\\[25pt]
*7\leftarrow\mleft\{\begin{array}{@{}l@{}}2Tdcdc\un{a}dd\alpha\leftarrow2Tdcd\un{b}
add\alpha\leftarrow1Tdc\un{a}badd\alpha\\[10pt]1Tdcdcbd\un{b}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdcdcb\un{c}
b\alpha\leftarrow1Tdcdc\un{c}cb\alpha\\3Tdcdcbdb\un{d}\\2Tdcdcbdb\un{c}\end{array}\mright.\end{array}\mright.\\[35pt]
*8\leftarrow1Tdcdbad\un{b}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tdcdba\un{c}b\alpha\\3Tdcdbadb\un{d}\\2Tdcdbadb\un{c}\end{array}\mright.\end{array}\end{equation}
\end{proof}
Note forward reference to Table~\ref{bigtable}.
\begin{Lemma}\label{lemma5}
If in a row of Table~\ref{bigtable}, some LIGR's are produced then in another row with the RHS of ``its affect" differing only by the symbol next to the string $T$, the same set of LIGR's is produced.
\end{Lemma}
\begin{proof}
Suppose a backward search gives \begin{equation}\label{lem_1}ST\beta\un{T_1}\alpha\leftarrow A\end{equation} in the Table~\ref{bigtable} where the pointer is at the right hand end of ${T_1}$ where $A$ is a set of RCS's and LIGR's. Then this will be based on \begin{equation}\label{lem_2}ST\un{T_1}\alpha\leftarrow S_1T\un{T_2}\alpha\end{equation} (an RCS) that may be also in the same table where in \eqref{lem_1} and \eqref{lem_2} the pointer is at the left hand end of $T_2$, and $\alpha$ and $\beta$ are arbitrary symbols (with $\alpha$ and $T$ having their usual roles) and $T_1$ and $T_2$ (as is $T$) are arbitrary strings of symbols and $S$ and $S_1$ are arbitrary states. This is because truncating the string to the right of $T$ by one symbol on the left will convert any LIGR's arising only because of that last symbol to RCS's. This will be done several times if necessary to get the required line of the grand search. Therefore \eqref{lem_1} can be written as \begin{equation}\label{lem_3}ST\beta\un{T_1}\alpha\leftarrow S_1T\beta\un{T_2}\alpha\leftarrow A.\end{equation} If the pointer does not reach $\beta$ in this derivation, it follows from this that $\beta$ can be replaced by any other symbol say $\gamma$\begin{equation}\label{lem_4}ST\gamma\un{T_1}\alpha\leftarrow S_1T\gamma\un{T_2}\alpha\leftarrow\mleft\{S_2T\un{\delta} T_2\alpha, A\mright\}.\end{equation} where the first member of the set on the right (an RCS) is there if and only if in the TM table $S_2\un{\delta}\to S_1\gamma\_$, and $\gamma$ and $\delta$ are also arbitrary symbols. If \eqref{lem_1} does not lead to any RCS's then the derivation cannot have the pointer reaching $\beta$ then the derivation is followed as in the proof of \eqref{lem_3} except that $\beta$ is replaced by $\gamma$ and the pointer never reaches $\gamma$ leading to the same LIGR's after the unused symbol $\gamma$ has been removed and no RCS's. If $\beta$ is reached in \eqref{lem_3} then follow the reverse steps that lead to the pointer reaching $\beta$ giving some RCS's that could be different from those in \eqref{lem_3}.
As long as $\beta$ is not reached by the pointer, the symbols to the right of $\beta$ are independent of $\beta$. Therefore if the backward search from \eqref{lem_1} is completed, the corresponding results with a different value of $\beta$ are obtained by (1) assessing whether or not the single step to $\beta$ is possible from the start or from any point where the pointer reaches one space to the right of $\beta$ and if so including the RCS obtained, and (2) taking the results that don't take the pointer to $\beta$ and replacing $\beta$ by the new symbol. This leaves the LIGR's unchanged after the symbol in place of $\beta$ that plays no part in the calculations is removed.
\end{proof}
\begin{Lemma}\label{lemma_6}
Any RCS of the form $2T\un{b}b^{n+1}add\alpha$ does not lead to any LIGR's for $n\ge 0$.
\end{Lemma}
\begin{proof}
For convenience let the string $b^{n+1}add\alpha$ be denoted by $S$ because it remains the same throughout the proof and note that the leftmost symbol of $S$ is $b$ if $n\ge 0$.
Add an arbitrary symbol $\beta$ on the left according to the procedure described in section~\ref{apply_f} and continue the backward search from there gives\newline
$2T\beta\un{b}S\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\un{a}bS\\2T\un{b}bS\end{array}\mright.$. The second case is as above with $n$ increased by 1.
Repeat this for the first case giving $1T\beta\un{a}bS\leftarrow1T\un{c}abS$. Repeat this argument again gives
\begin{equation}1T\beta\un{c}abS\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\un{c}cabS\text{ }*\\3T\beta c\un{d}bS\leftarrow\mleft\{\begin{array}{@{}l@{}}3T\beta \un{c}dbS\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\beta c\un{b}bS\\2T\un{a}cdbS\text{ }*\\3T\un{c}cdbS\text{ }*\end{array}\mright.\\1T\beta cd\un{b}S\leftarrow 1T\beta c\un{c}bS\\\end{array}\mright.\end{array}\mright.\end{equation}
In this search tree, $*$ indicates that by Lemma~\ref{lemma_2} the pointer can never reach $\alpha$ i.e. no new LIGR's can result from further additions of symbols. Because this search tree is complete it follows that the backward search from $2T\un{b}b^{n+1}add\alpha$ cannot lead to an LIGR unless the backward search from $2T\un{b}b^{n+2}add\alpha$ also leads to an LIGR. This gives an infinite regress showing that no RCS of this form can lead to an LIGR for $n\ge 0$.
\end{proof}
\subsection{\label{5.5}The main argument}
Because of the fact that LIGR's result from backward searches where the pointer starts and ends up at $\alpha$, any such result can be usefully classified by the parameter ${\it j}_{\rm 1}$ in \eqref{igr1.2}, the maximum number of reverse TM steps away from $\alpha$ during the computation. The resulting LIGR will have length (on the right) equal to ${\it j}_{\rm 1}+2$ because the symbol where the computation starts and $\alpha$ have to be included. Obviously if a substring involved in such a computation is the same between two strings (obtained by truncation from opposite $\alpha$), the results obtained such that the pointer never leaves that substring will also be the same, therefore the set of all LIGR's and their lengths obtained from a given string allows the set of LIGR's and their lengths to be obtained from any substring of the string by truncating it from the end opposite $\alpha$. This is just the subset given by ${\it j}_{\rm 1}\le$ the length of the substring $-2$. The values of ${\it j}_{\rm 1}$ are given by the program \cite{origins} to facilitate obtaining the LIGR's.
Due to the problem with presenting this and the forward references mentioned above,
in the following the numbers of LIGR's refer to the LIGR's listed in \eqref{newligrs1} which is the most up to date list of LIGR's obtained by Algorithm~\ref{alg5.1} applied to TM \eqref{tm2}.
Rather than repeating the phrase ``Applying $F$ to the sequence of LIGR's $X$ gives $\ldots$" on many occasions it will be shortened to $X\stackrel{F}{\Rightarrow}\ldots$.
\subsubsection{Sequences ending with LIGR $1$}
Applying $F$ to $1$ gives just
$1\alpha\un{a}T\stackrel{b}{\leftarrow}1\un{c}aT$ i.e. LIGR $3$ i.e. $1\stackrel{F}{\Rightarrow} 3$. Clearly applying $F$ to an LIGR of length 1 as is done here could possibly lead to more results if $T$ is specialised by giving a symbol at one end of the string (here the left end) therefore preceding LIGR's must be considered. LIGR 1 can be preceded by LIGR $4$ giving $4\cdot 1$ having the combined effect
$3\un{T}\stackrel{b}{\leftarrow}2\un{a}T\stackrel{b}{\leftarrow}1\un{a}aT$ i.e. $3\un{T}\stackrel{bb}{\leftarrow}1\un{a}aT$ and $4\cdot 1\stackrel{F}{\Rightarrow}3$ because $F$ gives the calculation
\begin{equation}\label{4to1}1\alpha\un{a}aT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{c}aaT\\\leftarrow\mleft\{\begin{array}{@{}l@{}}3\alpha a\un{a}T\\3\alpha a\un{b}T\end{array}\mright.\end{array}\mright.\text{ i.e. }1\alpha\un{a}aT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{c}aaT\\\leftarrow
3\alpha a\un{d}T\end{array}\mright.\end{equation}
The first part of this is LIGR $3$, and the second part is a pair of RCS's. By specialising this by giving the first symbol(s) of $T$, the first result will not generate any new LIGR's after reducing the result to its shortest form, the result will merely be replicated, but for the second part it is possible that the reverse computation could take the pointer back to $\alpha$ and so generate more new LIGR's so the search has to continue back, so we have thus far \begin{equation}\label{eq53}\begin{array}{@{}c@{}}\ldots1\stackrel{F}{\Rightarrow}\{3\}\\\ldots\cdot 4\cdot 1\stackrel{F}{\Rightarrow}\{3\}\end{array}.\end{equation}
The second member of this is related to its first member because any results of $F$ from the first part must be included in the results of the second part as happens here but the RCS's are not the primary result of $F$ and are not included in \eqref{eq53}.2. There are RCS's so any LIGR's that can precede $4\cdot 1$ must be considered and $F$ must be applied to all these.
The LIGR's that can precede $4$ are just $8$,$10$ and $21$. The sequence $8\cdot 4\cdot 1$ gives $3\un{T}\stackrel{c}{\leftarrow}3\un{c}T\leftarrow 1\un{a}acT$. Applying $F$ to this starts from (from \eqref{4to1} with the substitution given by LIGR $8$)
$1\alpha \un{a}acT\leftarrow3\alpha a\un{d}cT$
in addition to $3$ as above and $\Delta F_1$ is just the result of this backward search from
$3\alpha a\un{d}cT$ and because the computation cannot go back from there $\Delta F_1(8,4\cdot 1)=\emptyset$ and $F_2(8\cdot 4\cdot 1)=\emptyset$. Therefore there are no results of $F$ and it is
now it is clear that no preceding LIGR's specialising this $T$ can give any results of $F$, so the search for new results of $F$ stops in this branch of the grand search tree.
The sequences $10\cdot 4\cdot 1$ have the effect $1\un{c}aT\leftarrow 1\un{a}accdT$ and applying $F$ gives $1\alpha\un{a}accdT\leftarrow 3\alpha a\un{d}ccdT$ from which there are no further backward steps so there are no new LIGR's or RCS's and these branches of the grand search end i.e. $\Delta F_1(10\cdot4\cdot 1)=F_2(10\cdot 4\cdot 1)=\emptyset$. $21\cdot4\cdot1$ has the effect $1\un{c}abcT\leftarrow 1\un{a}ac^3dcT$ and $F$ applied to this by \eqref{4to1} gives $1\alpha\un{a}ac^3dcT\leftarrow\mleft\{\begin{array}{@{}l@{}}3\alpha a\un{a}c^3dcT\\3\alpha a\un{b}c^3dcT\end{array}\mright.$
which by Lemma~\ref{lemma_2} cannot lead to an LIGR.
This completes the analysis for all sequences that can precede $4\cdot 1$ therefore
the next sequence of LIGR's to be considered is $5\cdot 1$ i.e. $2\un{T}\leftarrow 2\un{b}T\leftarrow 1\un{a}bT.$
The computation of $F$ starts from $1\alpha\un{a}bT$ and gives no result other than LIGR $3$, so
$\Delta F_1(5,1)=F_2(5\cdot 1)=\emptyset$. Next $9\cdot 1$ must be considered which is $1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{a}acdT$. \begin{equation}9\cdot 1\stackrel{F}{\Rightarrow} 1\alpha\un{a}acdT\leftarrow\mleft\{\begin{array}{@{}l@{}}1\un{c}aacdT\\3\alpha a\un{d}cdT\end{array}\mright..\end{equation} which is also a special case of \eqref{4to1}. The first of these is just LIGR $3$ and the second cannot continue, so there are no new LIGR's from preceding $1$ by $9$ i.e. $\Delta F_1(9,1)=F_2(9\cdot 1)=\emptyset$. It is not too difficult to show that similar results hold for all the other LIGR's that could precede LIGR $1$ and all the results starting with $F$ applied to $5\cdot 1$ can be summarised as
\begin{equation}\Delta F_1(\{5,9,12,14,20\}, 1)=F_2(\{5,9,12,14,20\}\cdot 1)=\emptyset.\end{equation}
This exhausts all search trees in the grand search starting from LIGR $1$.
\subsubsection{Sequences ending with LIGR $2$}
Next consider applying $F$ to sequences ending with $2$ which is
$3\un{T}\stackrel{b}{\leftarrow}1T\un{b}.$ $F$ applied to this gives \begin{equation}\label{eq96}1T\un{b}\alpha\mleft\{\begin{array}{@{}l@{}}\stackrel{a}{\leftarrow} 3Tb\un{d}\\
\stackrel{c}{\leftarrow}2Tb\un{c}\end{array}\mright.\end{equation} which are LIGR's $6$ and $7$ so \begin{equation}2\stackrel{F}{\Rightarrow}\{6,7\}.\end{equation} The last symbol of $T$ in \eqref{eq96} could affect this result so LIGR's preceding $2$ must be considered which are just $7$,$16$,$18$,$22$,$24$ and$26$.
The sequence $7\cdot 2$ is $1\un{T}\stackrel{a}{\leftarrow}3T\un{d}\leftarrow 1Td\un{b}$ and applying $F$ gives
the same set i.e. LIGR's $6,7$ and no RCS's i.e. $\Delta F_1(7,2)=F_2(7\cdot 2)=\emptyset$.
This is because the pointer cannot move left in the reverse computation regardless of any other specialisations of $T$ resulting from preceding LIGR's. Consider $7\cdot 2$ which is $1\un{T}\stackrel{a}{\leftarrow} 3T\un{d}\leftarrow 1Td\un{b}$. $F$ gives $1Td\un{b}\alpha\leftarrow 1T\un{c}b\alpha$ in addition to $6$ and $7$ and so can be potentially specialised further i.e. $\Delta F_1(7, 2)=\emptyset$ and $F_2(7\cdot 2)=1T\un{c}b\alpha$.
LIGR $7$ can only be preceded by $2$ and $15$ so the next sequence to be considered in the grand search is $2\cdot7\cdot 2$ which is $3\un{T}\stackrel{b}{\leftarrow}1T\un{b}\leftarrow 1Tbd\un{b}$. $F$ applied to this gives \begin{equation}\label{282}1Tbd\un{b}\alpha\leftarrow 1Tb\un{c}b\alpha\leftarrow 1T\un{c}cb\alpha\end{equation} i.e.
$\Delta F_1(2, 7\cdot 2)=\emptyset$ and $F_2(2\cdot 7\cdot 2)=1T\un{c}cb\alpha$.
This RCS by Lemma~\eqref{lemma_2} cannot lead to any new LIGR's because the pointer can never reach $\alpha$ by the reverse TM computation however many preceding LIGR's are added to the sequence. Therefore there is no point in continuing grand search along this branch. This is a short cut that was not anticipated in the general algorithm \ref{alg5.1}. Next consider $15\cdot7\cdot2$ having the effect
$3Tb^5\un{a}\leftarrow 1Tc\mleft\{\begin{array}{@{}c@{}}db\\aa\end{array}\mright\}dbdbd\un{b}$.
Applying $F$ to this gives a result of the same form as in \eqref{282} therefore the same conclusion follows and the grand search continues from $16\cdot 2$ which has the effect $3Tb^5\un{a}\leftarrow 1Tca^3dbd\un{b}$. Applying $F$ to this gives some results of the form \eqref{282} not leading to any new results as above or with the symbol $a$ in the rightmost but one position. This is of the form $1Tba\un{b}$ having no preceding TM step to the left in $F$ hence $F$ applied to this gives $\Delta F_1=F_2=\emptyset$.
The sequence $18\cdot2$ has the effect $3Tb^5\un{a}\leftarrow 3Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{d}\leftarrow 1Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}dbd\un{b}$.
Applying $F$ to this gives\newline
$1Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}dbd\un{b}\alpha\stackrel{b}{\leftarrow}1Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{c}b\alpha\leftarrow 1Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}d\un{c}cb\alpha$. There is no point going any further with the algorithm $F$ because from this CS, by Lemma~\eqref{lemma_2} it is not possible for the pointer to get to $\alpha$ regardless of any preceding LIGR's i.e. no new LIGR's can result from this, another unanticipated short cut to Algorithm~\ref{alg5.1}. Similar results all hold for $\{22,24,26\}\cdot2$ which lead to applying the backward search from a CS of the form $1Tdbd\un{b}\alpha$.
\subsubsection{Sequences ending with LIGR $3$}
Consider sequences of LIGR's ending with $3$ which is $1\un{T}\stackrel{b}{\leftarrow}1\un{c}T$. Applying $F$ starts from $1\alpha\un{c}T\stackrel{b}{\leftarrow}1\un{c}cT$ showing that $3\stackrel{F}{\Rightarrow}\{3\}.$ The LIGR $3$ can be preceded by $1$, $3$, $11$ and $13$. The sequence $1\cdot3$ is $2\un{T}\leftarrow1\un{a}T\leftarrow 1\un{c}aT.$
Applying $F$ starts from $1\alpha\un{c}aT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{c}caT\\
\leftarrow3\alpha c\un{d}T\end{array}\mright.$ showing that two new RCS's are the only extra results of preceding $3$ with $1$. The sequence $4\cdot 1\cdot 3$ is $3\un{T}\leftarrow 2\un{a}T\leftarrow 1\un{c}aaT$. Applying $F$ gives
\begin{equation}\label{413}1\alpha\un{c}aaT\leftarrow3\alpha c\un{d}aT\leftarrow\ldots\mleft\{\begin{array}{@{}l@{}}\leftarrow3\alpha cb\un{d}T\\\stackrel{b}{\leftarrow}2\un{a}cdaT\\
\stackrel{c}{\leftarrow}3\un{c}cdaT\end{array}\mright..\end{equation} where the pointer does not reach the $a$ adjacent to $T$ during this computation of the last two parts therefore this shortens to
\begin{equation}1\un{c}aT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}2\un{a}cdT\\\stackrel{c}{\leftarrow} 3\un{c}cdT\end{array}\mright.\end{equation} which are new LIGR's and will be numbered $9$ and $10$ respectively, and the RCS's which require further backward searching.
The sequence $8\cdot 4\cdot 1\cdot 3$ is $3\un{T}\leftarrow 3\un{c}T\leftarrow1\un{c}aacT$. Applying $F$ gives
\begin{equation}\label{9to4to1}1\alpha\un{c}aacT\leftarrow3\alpha cb\un{d}cT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}badcT\\\stackrel{c}{\leftarrow}2\un{b}badcT\end{array}\mright.\end{equation} after a few steps. These when abbreviated are
\begin{equation}1\un{c}aaT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}badT\\\stackrel{c}{\leftarrow}2\un{b}badT\end{array}\mright.\end{equation}
which will be numbered LIGR's $11$ and $12$ respectively. Also there are now no RCS's, so this branch of the grand search ends.
The sequence $10\cdot 4\cdot 1\cdot 3$ has the effect $1\un{c}aT\leftarrow 1\un{c}aaccdT$ and $F$ gives, using \eqref{413},
\begin{equation}1\alpha\un{c}aaccdT\leftarrow 3\alpha cb\un{d}ccdT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow} 1\un{a}badccdT\\\stackrel{c}{\leftarrow}2\un{b}badccdT\end{array}\mright.\end{equation} produces only $11$ and $12$ again and no new RCS's.
The analysis for $21\cdot4\cdot1\cdot3$ is similar with the same result.
Next consider $5\cdot 1\cdot 3$ with the effect $2\un{T}\leftarrow1\un{c}abT$. Then applying $F$ gives
\begin{equation}\label{5to1to3}1\alpha\un{c}abT\leftarrow3\alpha c\un{d}bT\leftarrow \mleft\{\begin{array}{@{}l@{}}3\alpha \un{c}dbT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow} 2\un{a}c
dbT\\\stackrel{c}{\leftarrow}3\un{c}cdbT\end{array}\mright.\\1\alpha cd\un{b}T\end{array}\mright.\end{equation} apart from CS's for which there is no preceding CS. This gives two results which reduce to LIGR's $9$ and $10$ and an RCS.
$4\cdot 5\cdot 1\cdot 3$ is $3\un{T}\leftarrow 1\un{c}abaT$ and $F$ gives
\begin{equation}1\alpha\un{c}abaT\leftarrow1\alpha cd\un{b}aT\leftarrow3\alpha cdb\un{d}T
\end{equation} from \eqref{5to1to3}. This RCS requires going back in the grand search.
The next sequence $7\cdot 4\cdot 5\cdot 1\cdot 3$ is $3\un{T}\leftarrow 1\un{c}abacT$. $F$ gives
\begin{equation}\label{94513}1\alpha \un{c}abacT\leftarrow3\alpha cdb\un{d}cT\stackrel{5}{\leftarrow}2\alpha cadb\un{c}T.\end{equation} By Lemma~\ref{lemma_1} because of the $a$ on the left of the pointer, no new LIGR's can result if this branch of the grand search is continued.
For $10\cdot 4\cdot 5\cdot 1\cdot 3$ which has the effect $1\un{c}aT\leftarrow 1\un{c}abaccdT$, $F$ can start (by \eqref{94513}) from $2\alpha cadb\un{c}cdT$ and again by Lemma~\ref{lemma_1} no LIGR's can result from this branch. The same holds for $21\cdot4\cdot5\cdot1\cdot3$.
Consider $5\cdot 5\cdot 1\cdot 3$, $F$ can start from $1\alpha\un{c}abbT\leftarrow 1\alpha cd\un{b}bT\leftarrow 1\alpha c\un{c}bbT$ from which there are no RCS's or LIGR's. Applying $F$ to $9\cdot 5\cdot 1\cdot 3$ can start from $1\alpha\un{c}abacaT\leftarrow1\alpha cd\un{b}acaT\leftarrow \mleft\{\begin{array}{@{}l@{}}1\un{c}cabacdT\\2\un{a}cdbacdT\\3\un{c}cdbacdT\end{array}\mright.$ where other branches terminate due to Lemmas~\ref{lemma_1} and \ref{lemma_2} giving LIGR's $3,9,10$.
$12\cdot 5\cdot 1\cdot 3$ is $1\un{c}aaT\leftarrow 2\un{b}badT\leftarrow 1\un{c}ab^3cadT$
$F$ gives $1\alpha \un{c}abcaaT\leftarrow 1\alpha cd\un{b}caaT\leftarrow\mleft\{\begin{array}{@{}l@{}}2\un{a}ccdcaaT\\3\un{c}ccdcaaT\\2\alpha cca\un{c}aaT\end{array}\mright.$ where the last result cannot give any LIGR's.
These can be shortened to the new LIGR's $20$ and $21$ respectively.
$12\cdot 5\cdot 1\cdot 3$ is $1\un{c}aaT\leftarrow 2\un{b}badT\leftarrow 1\un{c}abbbadT$.
$F$ gives $1\alpha \un{c}abbbabT\leftarrow \mleft\{\begin{array}{@{}l@{}}2\un{a}cdb^3adT\\3\un{c}cdb^3adT\end{array}\mright.$ shortening to LIGR's $9$ and $10$.
$14\cdot 5\cdot 1\cdot 3$ is $1\un{c}cT\leftarrow 2\un{b}bcT\leftarrow 1\un{c}ab^3cT$. $F$ gives
$1\alpha\un{c}ab^3cT\leftarrow 1\alpha cd\un{b}bbcT\leftarrow 1\alpha c\un{c}b^3cT$ no new results.
$9\cdot 1\cdot 3$ is $1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{c}aacdT$ $F$ gives
$1\alpha\un{c}aacdT\leftarrow3\alpha c\un{d}acdT\leftarrow\mleft\{\begin{array}{@{}l@{}}2\un{a}cdacdT\\3\un{c}cdacdT\\1\un{a}badcdT\\2\un{b}badcdT\end{array}\mright.$. These shorten to the LIGR's $9-12$ already found and no RCS's.
$12\cdot 1\cdot 3$ is $1\un{c}aaT\leftarrow 2\un{b}badT\leftarrow 1\un{c}abbadT$ $F$ gives
$1\alpha\un{c}abbaaT\leftarrow 3\alpha c\un{d}bbaaT\leftarrow\mleft\{\begin{array}{@{}l@{}}2\un{a}cdbbaaT\\3\un{c}cdbbaaT\end{array}\mright.$ which shorten to LIGR's $9,10$ with no RCS's.
$14\cdot 1\cdot 3$ is $1\un{c}cT\leftarrow 2\un{b}bcT\leftarrow 1\un{c}abbcT$. $F$ gives results that shorten to LIGR's $9,10$ again.
The sequence $3\cdot 3$ has the effect $1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\leftarrow 1\un{c}cT$. $F$ gives $1\alpha\un{c}cT\leftarrow 2\alpha c\un{c}T$ an RCS so continue.
$1\cdot 3\cdot 3$ has the effect $2\un{T}\stackrel{b}{\leftarrow}1\un{a}T\leftarrow 1\un{c}caT$
\begin{equation}1\alpha\un{c}caT\leftarrow 2\alpha c\un{c}aT\leftarrow 2\alpha \un{b}caT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}bcaT\\\stackrel{c}{\leftarrow}2\un{b}bcaT\end{array}\mright.\end{equation}
This shortens to\begin{equation}\label{eq114}1\un{c}cT\mleft\{\begin{array}{@{}l@{}}\leftarrow1\un{a}bcT\\\leftarrow 2\un{b}bcT\end{array}\mright.\end{equation} without any RCS's. Equation \eqref{eq114} will be called LIGR's $13$ and $14$ respectively.
Consider the sequence $3\cdot 3\cdot 3$ with effect $1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\leftarrow 1\un{c}ccT$
\begin{equation}1\alpha\un{c}ccT\leftarrow2\alpha c\un{c}cT\leftarrow2\alpha\un{b}ccT\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow} 1\un{a}bccT\\\stackrel{c}{\leftarrow} 2\un{b}bccT\end{array}\mright.\end{equation} which shortens to $13$ and $14$ above, without any RCS's.
Next consider $11\cdot 3$ which is $1\un{c}aaT\leftarrow 1\un{a}badT\leftarrow 1\un{c}abadT$. Applying $F$ gives
\begin{equation}1\alpha\un{c}abadT
\leftarrow \mleft\{\begin{array}{@{}l@{}}
\stackrel{b}{\leftarrow}2\un{a}cdbadT\\\stackrel{c}{\leftarrow}3\un{c}cdbadT\\
%3\alpha\un{c}\left\{\begin{array}{@{}l@{}}a\\b\end{array}\mright\}baaT\left\{\begin{array}{@{}l@{}} \stackrel{b}{\leftarrow}2\un{a}c\left\{\begin{array}{@{}l@{}}a\\b\end{array}\mright\}baaT\\\stackrel{c}{\leftarrow}3\un{c}c\left\{\begin{array}{@{}l@{}}a\\b\end{array}\mright\}baaT\\\end{array}\mright.
\leftarrow1\alpha cdbd\un{b}T\end{array}\mright.
\end{equation}
The minimal forms of the first two results are the LIGR's $9$ and $10$. The sequence $13\cdot 3$ is $1\un{c}cT\leftarrow 1\un{a}bcT\leftarrow 1\un{c}abcT$. $F$ gives
\begin{equation}\label{eq117}1\alpha\un{c}abcT\leftarrow\mleft\{\begin{array}{@{}l@{}}2\un{a}cdbcT\\
3\un{c}cdbcT\\
2\alpha cdb\un{c}T
\end{array}\mright.\end{equation}
which when shortened give LIGR's $9$ and $10$ and an RCS. Only $3$ can precede $13$ and $3\cdot 13\cdot 3$ is $1\un{c}T\leftarrow 1\un{c}cT\leftarrow 1\un{c}abcT$. Note that here an extra symbol $c$ was needed in order that the RHS of $3$ matched the LHS of $13\cdot 3$. $F$ gives the same result as above. Of the LIGR's that can precede $3$ only $3$ is compatible because of the symbol $c$ on left and this gives $3\cdot 3\cdot 13\cdot 3$ which is $1\un{T}\leftarrow 1\un{c}T\leftarrow 1\un{c}abcT$ which again gives the same result of $F$.
$1\cdot 3\cdot 3\cdot 13\cdot 3$ is $2\un{T}\leftarrow 1\un{a}T\leftarrow 1\un{c}abcaT$. $F$ gives
no RCS's and LIGR's $20$ and $21$. $3\cdot 3\cdot3\cdot13\cdot3$ is $1\un{T}\leftarrow1\un{c}T\leftarrow1\un{c}abccT$. $F$ gives LIGR's $20$ and $21$ and no RCS's, and likewise for $11\cdot 3\cdot3\cdot 13\cdot 3$. It is now obvious that the same result will come from $13\cdot3\cdot3\cdot13\cdot3$ because it starts from a CS that shares in common with the previous case the string beyond which the computation to get these results does not go.
The sequences $11\cdot 3\cdot13\cdot3$ are $13\cdot3\cdot13\cdot3$ are not possible because of other compatibility restrictions based non-adjacent LIGR's.
$28\cdot 3$ and $30\cdot 3$ both under $F$ give results of the form
\begin{equation}1\alpha\un{c}a\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow} 1\un{c}ca\ldots\\\leftarrow 3\alpha c\un{d}\ldots x\end{array}\mright.\end{equation} showing that $F$ only gives $3$ and no RCS's.
\subsubsection{Sequences ending with LIGR $4$}
LIGR $4$ is $3\un{T}\stackrel{b}{\leftarrow}2\un{a}T$. $F$ gives
\begin{equation}2\alpha\un{a}T\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}aT\\\stackrel{c}{\leftarrow}2\un{b}aT\end{array}\mright.\end{equation} which shortens to $1$ and $5$, and this result could depend on the leftmost symbol of $T$ because right-moving reverse steps could occur.
Therefore LIGR's preceding $4$ must be considered.
$8\cdot 4$ is $3\un{T}\leftarrow 3\un{c}T\leftarrow 2\un{a}cT$, and applying $F$ gives no LIGR's or RCS's.
$10\cdot 4$ is $1\un{c}aT\leftarrow3\un{c}cdT\leftarrow 2\un{a}ccdT$ and $F$ gives no LIGR's or RCS's.
Therefore these results show that $\{8,10\}\cdot 4\stackrel{F}{\Rightarrow}\{1,5\}$ only.
\subsubsection{Sequences ending with LIGR $5$}
LIGR $5$ is $2\un{T}\leftarrow 2\un{b}T$ and applying $F$ gives $2\alpha\un{b}T\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}1\un{a}bT\\\stackrel{c}{\leftarrow}2\un{b}bT\end{array}\mright.$
which shortens to $1$ and $5$ so $5\stackrel{F}{\Rightarrow}\{1,5\}$.
The sequence $4\cdot 5$ is $3\un{T}\leftarrow 2\un{a}T\leftarrow 2\un{b}aT$. Applying $F$ starts from $2\alpha\un{b}aT$ and gives no new LIGR's and no RCS's. This is likewise true for $5$,$9$ and $12$ $14$ and $20$ preceding $5$ and all follow from the fact that $2\_a$ and $2\_b$ cannot be arrived at from a step of the TM, so all sequences ending with $\{4,5,9,12,14,20\}\cdot 5\stackrel{F}{\Rightarrow}\{1,5\}$.
\subsubsection{Sequences ending with LIGR $6$}
LIGR $6$ is $1\un{T}\leftarrow 2T\un{c}$. Applying $F$ gives
$2T\un{c}\alpha\leftarrow\emptyset$. A left-moving reverse step could occur depending on the rightmost symbol of $T$ so this needs to be specialised by considering all possible previous LIGR's i.e $2$ and $15$. The sequence
$2\cdot 6$ is $3\un{T}\leftarrow1T\un{b}\leftarrow 2Tb\un{c}$ and applying $F$ gives $2Tb\un{c}\alpha\leftarrow 1T\un{a}c\alpha$. By Lemma~\ref{lemma_2} this cannot lead to new LIGR's because $\alpha$ can never be reached by the pointer however the string is extended by preceding LIGR's in the sequence. Likewise for $15\cdot 6$.
Note that Lemma~\ref{lemma_2} was first discovered after studying this case in particular applying $F$ to sequences of the form $2\cdot (8\cdot 2)^k\cdot 6$ using an induction argument.
\subsubsection{Sequences ending with LIGR 7}\label{Sequences ending with LIGR 7}
Next follows an example of Lemma~\ref{sequence}.
** The sequence $15\cdot 7$ has combined effect $3Tb^5\un{a}\leftarrow 3Tc\left\{\begin{array}{@{}l@{}}db\\ca\end{array}\right\}dbdb\un{d}$.
If the last but one $d$ is $a$ the only possible reverse search paths are confined to the string $b\un{d}$ restricting the set of LIGR's produced and no RCS's can be produced. If the last but one $d$ is $b$ and the last but two $d$ is $a$, then the CS ends with $3abbb\un{d}$. Again no RCS's can be produced and the LIGR's produced are a superset of those produced in the above case by Lemma~\ref{lemma_ex}. Now suppose the rightmost $d$'s are both $b$ and the lower element of the array is taken, then the first $a$ will again prevent any RCS's being produced and the LIGR's will be from $3bbbb\un{d}$ again a superset of the preceding case. Now taking the upper element in the array with the first $d$ being $a$ gives again no RCS's and the LIGR's are again a superset of the preceding case. Finally, this leaves the case $3Tcb^6\un{d}\alpha$
which generates LIGR's which are again a superset of those from the preceding case.
Using this as starting point with the two cases where the $d$ is $a$ or $b$ gives, using the program ``new origins", a long list of results with the case $a$ the long 42 LIGR parts produced exactly account for LIGR's $15-19$, and the LIGR $2$ corresponds to the single result with $y.j1=1$. The 19 RCS's all have a $c$ that must be crossed to get to $\alpha$ which is impossible because of Lemma~\ref{lemma_2}, therefore these RCS's can be ignored because they can never lead to more LIGR's.
The case $3Tcb^6\un{b}$ needs to be considered too. Applying the program again and using Lemma~\ref{sequence} gives LIGR 2 and 24 other LIGR parts which correspond to LIGR's 22-27, and no RCS's except those having a $c$ that needs to be crossed (i.e. not at the left end).
A very similar argument works for applying $F$ to any sequence of LIGR's that have an effect (column 2 of \ref{bigtable}) originating from a CS of the form $3T(bd)^3\un{d}$ showing that the same LIGR's are produced and no usable RCSs. This applies to the following sequences: $\{16,18,22,24,26\}\cdot(2\cdot 7)^3, 15\cdot (7\cdot 2)^2\cdot 7, \{16,18,22,24,26\}\cdot 2\cdot 7\cdot 2\cdot 7, 15\cdot 7\cdot 2\cdot 7$.
Similar arguments also work for the remaining cases ending with LIGR 7 summarised in the following tables.
\begin{longtable}{llll}
\caption{LIGR's and RCS's \label{x.2.7}}\\
LIGR sequence & CS analysed& RCS's produced & LIGR's produced\\\hline
$16\cdot 2\cdot 7$ & $\leftarrow 3Tca^3dbdb\un{d}$&$\emptyset$&$\begin{array}{@{}l@{}}\text{from }3Tab^4\un{d}\subseteq \text{from }3Tb^6\un{d}=\\\{2,15-19,22-27\}\end{array}$\\[10pt]
$18\cdot 2\cdot 7$&$\leftarrow 3Tcd\left\{\begin{array}{@{}l@{}}ba\\cb\end{array}\right\}dbdb\un{d}$&$\text{none useful}$&$\begin{array}{@{}l@{}}\text{from }3Tcdcb^5\un{d}=\\\{2,15-19,22-27\}\end{array}$ (see Table~\ref{table3})\\[10pt]
$22\cdot 2\cdot 7$&$\leftarrow 3Tadbdb\un{d}$&$\emptyset$&$\text{from }3Tab^4\un{d}$\\
$24\cdot 2\cdot 7$&$\leftarrow 3Tcbdbdb\un{d}$&$\text{none useful}$&$\text{from }3Tcb^5\un{d}\subseteq\text{from }3Tcdcb^5\un{d}$\\
$26\cdot 2\cdot 7$&$\leftarrow 3Tcadbdbdb\un{d}$&$\emptyset$&$\text{from }3Tab^6\un{d}=\text{from }3Tb^6\un{d}$\\
\end{longtable}
\begin{longtable}{rrl|rrl}
\caption{IGR's generated by the computer program\label{table3}}\\
\multicolumn{3}{c}{$3Tcdcb^5\un{a}$}
&\multicolumn{3}{c}{$3Tcdcb^5\un{b}$}\\
$j_1$&\#& LIGR's&$j_1$&\#& LIGR's\\\hline
0&1&$2$&0&1&$2$\\
5&42&$15-19$&2&6&$22,23$\\
&&&3&6&$24,25$\\
&&&5&12&$26,27$\\
\end{longtable}
In Table~\ref{x.2.7} ``CS analysed" refers to the rightmost CS in the expression for the effect of the LIGR sequence, to which $F$ is applied. In the column for the RCS's produced, the phrase ``none useful" means
that all the RCS's contain a $c$ that would have to be passed to generate an LIGR (by Lemma~\ref{lemma_2}), therefore because this is impossible, there can be no new LIGR's derived by using any of these RCS's in the procedure for generating all the LIGR's. In the last column, the set of LIGR's produced is the same as the set of LIGR's produced from other CS's that follow the ``from". These and the other results can be derived by using Lemmas \ref{lemma_ex}, \ref{lemma_1}, and \ref{sequence}. In Table~\ref{table3} the CS's to which $F$ is applied head the two composite columns. The results for the LIGR's are given in the body of the table. The parameter $j_1$ is as in
section \ref{sec4.1}. The column headed $\#$ is the number of LIGR parts produced by the program ``new origins" and the column headed LIGR's gives the identification numbers of the sets of LIGR's as defined in \ref{newligrs1}.
Note that the general algorithm would not find this and would probably continue indefinitely because it could not show that these RCS's could not lead to any new LIGR's.
\subsubsection{Sequences ending with LIGR $\ge8$}
In Table~\ref{bigtable}, if the there are $\cdots$ in column 1, anything in column 3 will exclude RCS's that have been followed up and are also included in that row, so for example if column 3 had $\emptyset$ then no follow up results are needed in other rows just as if column 1 had no $\cdots$.
LIGR $8$ is $3\un{T}\leftarrow 3\un{c}T$ and $3\alpha\un{c}T\mleft\{\begin{array}{@{}l@{}}\stackrel{b}{\leftarrow}2\un{a}cT\\\stackrel{c}{\leftarrow}3\un{c}cT\end{array}\mright.$ shortens to $4$ and $8$ so $\ldots8\stackrel{F}{\to}\{4,8\}$ but because the left end symbol of $T$ is not specified, specialising it by including previous LIGR's could generate more results. $8\cdot 8$ is $3\un{T}\leftarrow3\un{c}T\leftarrow3\un{c}cT$ and $3\alpha\un{c}cT$ gives nothing new so $\ldots8\cdot 8\stackrel{F}{\to}\{4,8\}$.
Similarly it follows that $10\cdot 8$ and $21\cdot 8$ under $F$ produce no new results, so $\ldots\{8,10,21\}\cdot 8\stackrel{F}{\to}\{4,8\}$.
In a similar manner also the following can be easily established
$\ldots\{9\}\stackrel{F}{\to}\{1,5\}$\\
$\ldots\{10\}\stackrel{F}{\to} \{4,8\}$\\
$\ldots\{11\}\stackrel{F}{\to} \{3\}$\\
$\ldots\{12\}\stackrel{F}{\to}\{1,5\}$\\
$\ldots\{13\}\stackrel{F}{\to}\{3\}$\\
$\ldots\{14\}\stackrel{F}{\to}\{1,5\}$\\
In all these cases, $F$ produces results that cannot, when specialised to the cases where $T$ has particular forms, generate any new LIGR's from them. This results from the pointer not reaching next to the arbitrary string $T$ at any point in these derivations. These are examples of the absence of RCS's in the result of $F$ not giving any new LIGR's by specialising the original LIGR sequence by preceding it with another LIGR.
LIGR $24$ can be preceded by $7(b),18/19,24,26$. $7(b)$ preceding $24$ makes no difference to the result because
$7(b)\cdot 24$ has the effect $1\un{T}\leftarrow 3T\un{b}\leftarrow 3T^*cbdb\un{d}$ only if $T$ ends in $bbb$ i.e. $T=T^*bbb$. Because $18/19$ in $18/19\cdot24$ must have the origin in state 3, its effect is $3Tb^5\un{a}\leftarrow 3Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{d}\leftarrow 3T^*cbdb\un{d}$ with $T^*=Tcdc$ i.e. $3Tcdccbdb\un{d}$ and $24\cdot24$ is $3Tb^3\un{b}\leftarrow3Tcbdb\un{d}\leftarrow 3T^*cbdb\un{d}$ where $T^* = Tc$ i.e. $3Tccbdb\un{d}$. Likewise $26\cdot24$ is $3Tb^5\un{b}\leftarrow 3Tcadcbdb\un{d}$. Also in each of these the second $d$ from the right must actually be $b$ otherwise no RCS's are obtained by Lemma~\ref{lemma_1}. Thus these results are all special cases of $3Tccbbb\un{d}$ and $3Tcadcbbb\un{d}$ which need $F$ to be applied to them in Table~\ref{bigtable}. To make this easier a computer program \cite{origins} was written based on a slightly modified version of the function ``origins" appearing in \cite{tie_v3_2} to obtain the results of all possible backward searches with the TM starting from any given input CS. This showed that the following CS's gave or not RCS's as follows starting from $3Tccbbb\un{d}$. The case when $d=b$ gives\newline
begin comment
%\begin{comment}
$3Tb\un{a}$ yes
$3Tab\un{a}$ no
$3Tbb\un{a}$ yes
$3Tbbb\un{a}$ yes
$3Tcbbb\un{a}$ yes
$3Tacbbb\un{a}$ no
$3Tbcbbb\un{a}$ yes
$3Tabcbbb\un{a}$ no
$3Tbbcbbb\un{a}$ yes
$3Tabbcbbb\un{a}$ no
$3Tbbbcbbb\un{a}$ yes
$3Tabbbcbbb\un{a}$ no
$3Tbbbbcbbb\un{a}$ no
$3Tcbbbcbbb\un{a}$ no
$3Tcbbcbbb\un{a}$ no
$3Tcbcbbb\un{a}$ no
$3Tccbbb\un{a}$ no
$3Tcbb\un{a}$ no
$3Tcb\un{a}$ yes
$3Tacb\un{a}$ no
$3Tbcb\un{a}$ yes
$3Tabcb\un{a}$ no
$3Tbbcb\un{a}$ yes
$3Tabbcb\un{a}$ no
$3Tbbbcb\un{a}$ no
$3Tcbbcb\un{a}$ no
%\end{comment}
\\end comment
$3Tccbbb\un{b}$ yes\\
$3Taccbbb\un{b}$ no\\
$3Tbccb^3\un{b}$ yes\\
$3Tabccb^3\un{b}$ no\\
$3Tbbccb^3\un{b}$ yes\\
$3Tabbccb^3\un{b}$ no\\
$3Tbbbccb^3\un{b}$ no\\
$3Tcbbccb^3\un{b}$ no\\
$3Tcbccb^3\un{b}$ no\\
$3Tcccb^3\un{b}$ yes\\
$3Tac^3b^3\un{b}$ no\\
$3Tbc^3b^3\un{b}$ yes\\
$3Tabc^3b^3\un{b}$ no\\
$3Tbbc^3b^3\un{b}$ yes\\
$3Tabbc^3b^3\un{b}$ no\\
$3Tbbbc^3b^3\un{b}$ no\\
$3Tcbbc^3b^3\un{b}$ no\\
$3Tcbc^3b^3\un{b}$ no\\
$3Tc^4b^3\un{b}$ yes etc.\\
This sequence of results was obtained by systematically searching in a similar manner to the main argument in section 5.5.
By this point it looks as if a cycle could have been obtained. The reason for this was not difficult to find, it is because
$3Tccbbb\un{b}\alpha\leftarrow 2T\un{b}bbadb\alpha$ (only this RCS because of Lemma~\ref{lemma_2}) together with LIGR's $2,22-25$ identified by using the $j1$ values, and it is possible to substitute $T=T^*c^n$ and derive \begin{equation}\label{3ccbbbb}3T^*c^{n+2}b^3\un{b}\alpha\leftarrow \mleft\{\begin{array}{@{}l@{}}
2T^*c^n\un{b}bbadb\alpha\leftarrow 2T^*\un{b}b^{n+2}adb\alpha\\1T^*c^{n+2}b^4\un{b}\text{ etc.}\end{array}\mright.\text{ (1 RCS and LIGR's }2,22-25)\end{equation} for all $n\ge0$.\\
Also going back gives $3T^*ac^{n+2}b^3\un{b}\alpha\leftarrow$ no RCS's,\\
$3T^*bc^{n+2}b^3\un{b}\alpha\leftarrow 1T^*\un{a}b^{n+3}adb\alpha$ (1 RCS), and going back gives\\
$3T^*abc^{n+2}b^3\un{b}\alpha\leftarrow$ no RCS's by Lemma~\ref{lemma_1},\\
$3T^*bbc^{n+2}b^3\un{b}\alpha\leftarrow 1T^*\un{c}ab^{n+3}adb\alpha$ (1 RCS), and going back gives\\
$3T^*abbc^{n+2}b^3\un{b}\alpha\leftarrow$ no RCS's by Lemma~\ref{lemma_1},\\
$3T^*b^3c^{n+2}b^3\un{b}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\un{c}cab^{n+3}adb\alpha\\1Tbc\un{b}b^{n+3}adb\alpha\\2T\un{a}cdb^{n+3}adb\alpha\\1Tbc\un{c}b^{n+3}adb\alpha\end{array}\mright.\text{ (no usable RCS's)}$\\
$3T^*cbbc^{n+2}b^3\un{b}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1T^*cc\un{c}b^{n+3}adb\alpha\\3T^*\un{c}cdb^{n+3}adb\alpha\\1T^*cc\un{b}b^{n+3}adb\alpha\end{array}\mright.\text{ (no usable RCS's)}$\\
$3T^*cbc^{n+2}b^3\un{b}\alpha\leftarrow 1T^*c\un{a}b^{n+3}adb\alpha\text{ (no RCS's)}$.\\
$3T^*cc^{n+2}b^3\un{b}\alpha$ i.e. \eqref{3ccbbbb} with $n$ increased by 1.\\
In each of these short derivations only a few reverse steps of the TM are needed where as always Lemma~\ref{lemma_1} and Lemma~\ref{lemma_2} rule out continuing on many branches (each branch is represented by a final CS to help verify the results). All possible RCS's are indicated at each stage and no more LIGR's were found.
To find the RCS's associated with $3T^*cc^{n+2}b^3\un{b}\alpha$, the last CS to be examined, this is the same as the CS on the LHS of \eqref{3ccbbbb} with $n$ increased by 1. This results in an infinite regress showing that no LIGR's result from
$3T^*c^{n+2}b^3\un{b}\alpha$ other than those found at the start i.e. $2,22-25$.
The same type of argument can be applied to the case where the last $d$ is $a$. This time the negative results for RCS's for the case where the starting CS contains any $a$'s (see Lemma~\ref{lemma_1}) will not be mentioned.\\
$3Tc^{n+2}b^3\un{a}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1Tc^{n+2}b^3a\un{b}\\3Tc^{n+2}ba\un{d}a\alpha\\3Tc^{n+1}\un{c}cda^2\alpha\\2T\un{b}b^{n+2}ada\alpha\end{array}\mright.$ i.e. 1 LIGR ($2$) and 1 RCS\\
Going back gives $3Tbc^{n+2}b^3\un{a}\alpha\leftarrow 1T\un{a}b^{n+3}ada\alpha$ (1 RCS)\\
Going back gives $3Tbbc^{n+2}b^3\un{a}\alpha\leftarrow 1T\un{c}ab^{n+3}ada\alpha$ (1 RCS)\\
Going back gives $3Tb^3c^{n+2}b^3\un{a}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}1T\un{c}cab^{n+3}ada\alpha\\2T\un{a}cdb^{n+3}ada\alpha\\1Tbc\un{b}b^{n+3}ada\alpha\\1Tbc\un{c}b^{n+3}ada\alpha\end{array}\mright.$ (no usable RCS's)\\
$3Tcb^2c^{n+2}b^3\un{a}\alpha\leftarrow\mleft\{\begin{array}{@{}l@{}}3T\un{c}cdn^{n+3}ada\alpha\\1Tcc\un{b}b^{n+3}ada\alpha\\1Tcc\un{c}b^{n+3}ada\alpha\end{array}\mright.$ (no usable RCS's)\\
$3Tcbc^{n+2}b^3\un{a}\alpha\leftarrow 1Tc\un{a}b^{n+3}ada\alpha$ (no RCS's)\\
$3Tc^{n+3}b^3\un{a}\alpha$ is as above with $n\to n+1$ showing in all that only 1 LIGR ($2$) results from $3T c^{n+2}b^3\un{a}\alpha$ for an arbitrary string $T$.
Applying a similar argument to $3Tcadcbbb\un{d}$ does not yield any RCS's regardless of whether either $d$ is $a$ or $b$. In all of these results the LIGR's generated are the same $2$,$22-25$ because these results have $j1=0,2\text{ or }3$ only and these LIGR's must be obtained because the starting $CS$ is of the form $3T^*bbbb$. This shows that any sequence of LIGR's ending with $24$ under $F$ only gives LIGR's $2,22-25$. The remaining results in Table~\ref{bigtable} were obtained with the program \cite{origins} but could be obtained similarly to the above.
\newpage
Summary of the analysis for the TM.
\newpage
In the following the results will be written according to the notation\newline $\ldots X_1/\{Y_i\}\to X_2/\{Y_{i+1}\}\to\ldots$. This means $F$ is applied to the sequence of LIGR's $S$, that begins with $X_1$, substituted into each other as above. This gives LIGR's $\Delta F=\{Y_{i}\}$ and in general some RCS's. There is a set of LIGR's $X_2$ that can precede $S$ and each such $X_2$ defines a separate branch of the tree rooted by the original LIGR at the start. Branching points can be indicated by braces. Applying $F$ again starts from each of the above RCS's with the substitution for $T$ given by $X_2$ i.e. $S$ is replaced by $X_2\cdot S$. The result of this backward search gives again the set of LIGR's $\Delta F_1$ which is $\{Y_{i+1}\}$. In general, there can be many members of $Y_i$, $Y_{i+1}$ etc. for each sequence $S$, which can be written as a comma separated list in braces. Also because ${Y_i}=\emptyset$ is so frequent, $/\emptyset$ will be omitted if it occurs. A branch of the tree terminates when the set of RCS's above is $\emptyset$ or if there are no such LIGR's $X_2$.
\begin{equation}
1/3\to \left\{\begin{array}{l}4\to \left\{\begin{array}{l}8\\10\\
21\end{array}\right.\\5\\9\\12\\14\\20\end{array}\right.\end{equation}
\begin{equation}
2/\{6,7\}\to \left\{\begin{array}{l}7\to\left\{\begin{array}{l}2\\15\end{array}\right.\\16\\18\\22\\24\\26\end{array}\right.\end{equation}
\begin{equation}3/3\to \left\{\begin{array}{l}1\to \left\{\begin{array}{l}4/\{9,10\}\to \left\{\begin{array}{l}8/\{11,12\}\\10/\{11,12\}\\21/\{11,12\}\end{array}\right.\\5/\{9,10\}\to \left\{\begin{array}{l}4\to\left\{\begin{array}{l}
8\\10\\21\end{array}\right.\\
5\\9\\12\\14\\20\end{array}\right.\\9/\{9,10,11,12\}\\12/\{9,10\}\\14/\{9,10\}\\20/\{9,10\}\end{array}\right.\\\to 11/\{13,14\}\to \left\{\begin{array}{l}3/\{13,14\}\to \left\{\begin{array}{l}1/\{9,10\}\to\left\{\begin{array}{l}4\\9\\20\end{array}\right.\\3\\11\\13\end{array}\right.\end{array}\right.\\
13/\{9,10\}\to \left\{\begin{array}{l}3\to\left\{\begin{array}{l}3\to\left\{\begin{array}{l}1/\{20,21\}\end{array}\right.\\3\to\left\{\begin{array}{l}3\\11\\13\end{array}\right.\end{array}\right.\end{array}\right.
\end{array}\right.\end{equation}
\begin{equation}4/\{1,5\}\to\left\{\begin{array}{l}8\\10\\21\end{array}\right.\end{equation}
\begin{equation}5/\{1,5\}\to\left\{\begin{array}{l}4\\5\\9\\12\\14\\20\end{array}\right.\end{equation}
\begin{equation}6\to \left\{\begin{array}{l}2\\15\end{array}\right.\end{equation}
\begin{equation}7/\{2\}\to 2\to 7\to 2\to 7\to 2\to \left\{\begin{array}{l}7\\16\\18\\22\\24\\26\end{array}\right.\end{equation}
%$3\to \left\{\begin{array}{l}1/\{13,14\}\\3/\{13,14\}\end{array}\right.\end{array}\right.\\11/\{9,10\}\\13/\{9,10\}\to\begin{array}{l}3\to\left\{\begin{array}{l}3\end{array}\right.\\11/\{9,10\}
%\end{array}\right.$
This version of the table is cut down to the minimum.
The last but one column gives just all RCS's.
Check associativity of $\cdot$
\fontsize{8}{8}\selectfont
\begin{longtable}{@{}l@{\,\,}l@{\,\,}l@{\,\,}l}
\caption{The RCS's and LIGR's resulting from $F$ applied to sequences of LIGR's}\label{bigtable}\\
%\multicolumn{2}{c}{testing}&\multicolumn{2}{Results of $F$}\\
%\setlength{\tabcolsep}{0pt}
$\begin{array}{@{}l@{}}\text{Possible sequences}\\\text{ of LIGR's}\end{array}$&It's effect&$\begin{array}{@{}l@{}}\text{The RCS's}\\\text{excluding}\\\text{those because of}\\\text{Lemmas \ref{lemma_1} and \ref{lemma_2}}\end{array}$&LIGR's produced by $F$\\[5pt]
$1$&$2\un{T}\stackrel{b}{\leftarrow}1\un{a}T$&$1\un{c}aT$&$3$\\[5pt]
$4\cdot1$&$3\un{T}\stackrel{b}{\leftarrow}2\un{a}T\stackrel{b}{\leftarrow}1\un{a}aT$&$
3\alpha a\un{d}T$&$3$\\[5pt]
$8\cdot 4\cdot 1$&$3\un{T}\stackrel{c}{\leftarrow}3\un{c}T\leftarrow 1\un{a}acT$&$\emptyset$&$3$\\[5pt]
$10\cdot 4\cdot 1$&$1\un{c}aT\leftarrow3\un{c}cdT\leftarrow1\un{a}accdT$&$\emptyset$&$3$\\
$21\cdot4\cdot1$&$1\un{c}abcT\leftarrow 3\un{c}ccdcT\leftarrow1\un{a}ac^3dcT$&$\emptyset$&$3$\\[5pt]
$5\cdot 1$&$2\un{T}\leftarrow 2\un{b}T\leftarrow 1\un{a}bT$&$\emptyset$&$3$\\[5pt]
$9\cdot 1$&$1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{a}acdT$&$\emptyset$&$3$\\[5pt]
$12\cdot1$&$1\un{c}aaT\leftarrow2\un{b}badT\leftarrow 1\un{a}bbadT$&$\emptyset$&$3$\\[5pt]
$14\cdot1$&$1\un{c}cT\leftarrow 2\un{b}bcT\leftarrow 1\un{a}bbcT$&$\emptyset$&$3$\\[5pt]
$20\cdot1$&$1\un{c}abcT\leftarrow2\un{a}ccdcT\leftarrow1\un{a}accdcT$&$\emptyset$&$3$\\[5pt]
$2$&$3\un{T}\stackrel{b}{\leftarrow}1T\un{b}$&$\mleft\{\begin{array}{@{}l@{}} 3Tb\un{d}\\
2Tb\un{c}\end{array}\mright.$&$\{6,7\}$\\[5pt]
$7a\cdot 2$&$1\un{T}\stackrel{a}{\leftarrow}3T\un{a}\leftarrow 1Ta\un{b}$&$\emptyset$&$\{6,7\}$\\[5pt]
$7b\cdot 2$&$1\un{T}\stackrel{a}{\leftarrow}3T\un{a}\leftarrow 1Tb\un{b}$&$1T\un{c}b\alpha$&$\{6,7\}$\\[5pt]
$2\cdot7b\cdot 2$&$3\un{T}\stackrel{b}{\leftarrow}1T\un{b}\leftarrow 1Tbb\un{b}$&$1T\un{c}cb\alpha$&$\{6,7\}$\\[5pt]
$15\cdot7\cdot2$&$\begin{array}{@{}l@{}l@{}}3Tb^5\un{a}\leftarrow 1Tc\mleft\{\begin{array}{@{}c@{}}db\\aa\end{array}\mright\}dbd\un{b}\\\leftarrow 1Tc\mleft\{\begin{array}{@{}c@{}}db\\aa\end{array}\mright\}dbdbb\un{b}\end{array}$&$\emptyset$&$\{6,7\}$\\[23pt]
$16\cdot 2$&$\begin{array}{@{}l@{}l@{}}3Tb^5\un{a}\leftarrow 3Tc\mleft\{\begin{array}{@{}c@{}}db\\aa\end{array}\mright\}dbdb\un{b}\\\leftarrow 1Tc\mleft\{\begin{array}{@{}c@{}}db\\aa\end{array}\mright\}dbdbb\un{b}\end{array}$&$\emptyset$&$\{6,7\}$\\[23pt]
$18\cdot2$&$\begin{array}{@{}l@{}l@{}}3Tb^5\un{a}\leftarrow 3Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{d}\leftarrow\\1Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}dbd\un{b}\end{array}
$&$\emptyset$&$\{6,7\}$\\[5pt]
$\{22,24,26\}\cdot2$&$\leftarrow 1T^*dbd\un{b}$&$\emptyset$&$\{6,7\}$\\[5pt]
$3$&$1\un{T}\stackrel{b}{\leftarrow}1\un{c}T$&$1\un{c}cT$&$3$\\[5pt]
$1\cdot3$&$2\un{T}\leftarrow 1\un{a}T\leftarrow 1\un{c}aT$&$3\alpha c\un{d}T$&$3$\\[5pt]
$4\cdot1\cdot3$&$3\un{T}\leftarrow 2\un{a}T\leftarrow 1\un{c}aaT$&$3\alpha cb\un{d}T$&$\{3,9,10\}$\\[5pt]
$8\cdot 4\cdot 1\cdot 3$&$3\un{T}\leftarrow 3\un{c}T\leftarrow1\un{c}aacT$&$\emptyset$&$\{3,9,10,11,12\}$\\[5pt]
$10\cdot 4\cdot 1\cdot 3$&$\begin{array}{@{}l@{}}1\un{c}aT\leftarrow 3\un{c}cdT\\\leftarrow1\un{c}aaccdT\end{array}$&$\emptyset$&$\{3,9,10,11,12\}$\\[5pt]
$21\cdot4\cdot1\cdot3$&$\begin{array}{@{}l@{}}1\un{c}abcT\leftarrow3\un{c}ccdcT\\\leftarrow1\un{c}aac^3dcT\end{array}$&$\emptyset$&$\{3,9,10,11,12\}$\\[5pt]
$5\cdot 1\cdot 3$&$2\un{T}\leftarrow2\un{b}T\leftarrow1\un{c}abT$&$1\alpha cd\un{b}T$&$\{3,9,10\}$\\[5pt]
$4\cdot 5\cdot 1\cdot 3$&$3\un{T}\leftarrow 2\un{a}T\leftarrow 1\un{c}abaT$&$3\alpha cdb\un{d}T$&$\{3,9,10\}$\\[5pt]
$8\cdot4\cdot5\cdot1\cdot3$&$3\un{T}\leftarrow 3\un{c}T\leftarrow1\un{c}abacT$&$2\alpha cadb\un{c}T$&$\{3,9,10\}$\\[5pt]
$10\cdot 4\cdot 5\cdot 1\cdot 3$&$1\un{c}aT\leftarrow 3\un{c}cdT\leftarrow 1\un{c}abaccdT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$21\cdot4\cdot5\cdot1\cdot3$&$\begin{array}{@{}l@{}}1\un{c}abcT\leftarrow3\un{c}c^2dcT\\\leftarrow1\un{c}abac^3dcT\end{array}$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$5\cdot 5\cdot 1\cdot 3$&$2\un{T}\leftarrow2\un{b}T\leftarrow 1\un{c}abbT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$9\cdot 5\cdot 1\cdot 3$&$1\un{c}aT\leftarrow2\un{a}cdT\leftarrow 1\un{c}abacdT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$12\cdot 5\cdot 1\cdot 3$&$1\un{c}aaT\leftarrow 2\un{b}badT\leftarrow 1\un{c}ab^3adT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$14\cdot 5\cdot 1\cdot 3$&$1\un{c}cT\leftarrow 2\un{b}bcT\leftarrow 1\un{c}ab^3cT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$20\cdot5\cdot1\cdot3$&$\begin{array}{@{}l@{}}1\un{c}abcT\leftarrow2\un{a}ccdcT\\\leftarrow1\un{c}abaccdcT\end{array}$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$9\cdot 1\cdot 3$&$1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{c}aacdT$&$\emptyset$&$\{3,9,10,11,12\}$\\[5pt]
$12\cdot1\cdot3$&$1\un{c}aaT\leftarrow2\un{b}badT\leftarrow1\un{c}abbadT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$14\cdot1\cdot3$&$1\un{c}cT\leftarrow 2\un{b}bcT\leftarrow 1\un{c}cabbcT$&$\emptyset$&$\{3,9,10\}$\\[5pt]
$20\cdot1\cdot3$&$\begin{array}{@{}l@{}}1\un{c}abcT\leftarrow2\un{a}ccdcT\\\leftarrow1\un{c}aaccdcT\end{array}$&$\emptyset$&$\{3,9,10,11,12\}$\\[5pt]
$3\cdot 3$&$1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\leftarrow 1\un{c}cT$&$2\alpha c\un{c}T$&$\{3\}$\\[5pt]
$1\cdot 3\cdot 3$&$2\un{T}\stackrel{b}{\leftarrow}1\un{a}T\leftarrow 1\un{c}caT$&$\emptyset$&$\{3,13,14\}$\\[5pt]
$3\cdot 3\cdot 3$&$1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\leftarrow 1\un{c}ccT$&$\emptyset$&$\{3,13,14\}$\\[5pt]
$11\cdot 3$&$1\un{c}aaT\leftarrow 1\un{a}badT\leftarrow1\un{c}abaaT$&
$3\alpha cadb\un{d}T$&$\{3,9,10\}$\\
$11\cdot 3$&$1\un{c}aaT\leftarrow 1\un{a}badT\leftarrow1\un{c}ababT$&
$1\alpha cdbd\un{b}T$&$\{3,9,10\}$\\
$3\cdot 11\cdot 3$&$1\un{a}a\un{T}\leftarrow 1\un{c}aaT\leftarrow 1\un{c}abadT$&Same results&\\
$1\cdot 3\cdot 11\cdot 3$&$2\un{a}T\leftarrow 1\un{a}aT\leftarrow 1\un{c}abadT$&Same results&\\
$3\cdot 3\cdot 11\cdot 3$&No match&&\\
$11\cdot 3\cdot 11\cdot 3$&No match&&\\
$13\cdot 3\cdot 11\cdot 3$&No match&&\\
$4\cdot 1\cdot 3\cdot 11\cdot 3$&$3\un{T}\leftarrow 2\un{a}T\leftarrow 1\un{c}abadT$&Same results&\\
$9\cdot 1\cdot 3\cdot 11\cdot 3$&$1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{c}abaacdT$&$\emptyset$&$\{3,9,10\}$\\
$9\cdot 1\cdot 3\cdot 11\cdot 3$&$1\un{c}aT\leftarrow 2\un{a}cdT\leftarrow 1\un{c}ababcdT$&$\emptyset$&$\{3,9,10,28,29,30,31\}$\\
$20\cdot 1\cdot 3\cdot 11\cdot 3$&$1\un{c}abcT\leftarrow2\un{a}ccdcT\leftarrow 1\un{a}accdcT$&$\emptyset$&$\{3\}$\\
$13\cdot 3$&$1\un{c}cT\leftarrow 1\un{a}bcT\leftarrow 1\un{c}abcT$&$2\alpha cdb\un{c}T$&$\{3,9,10\}$\\[5pt]
$3\cdot 13\cdot 3$&$1\un{c}T\leftarrow 1\un{c}cT\leftarrow 1\un{c}abcT$&$2\alpha cdb\un{c}T$&$\{3,9,10\}$\\[5pt]
$3\cdot 3\cdot 13\cdot 3$&$1\un{T}\leftarrow 1\un{c}T\leftarrow 1\un{c}abcT$&$2\alpha cdb\un{c}T$&$\{3,9,10\}$\\[5pt]
$1\cdot 3\cdot 3\cdot 13\cdot 3$&$2\un{T}\leftarrow 1\un{a}T\leftarrow 1\un{c}abcaT$&
$\emptyset$&$\{3,9,10,20,21\}$\\[5pt]
$\begin{array}{@{}l@{}}\{3,11,13\}\\\cdot 3\cdot3\cdot13\cdot3\end{array}$&$1\un{T}\leftarrow1\un{c}T\leftarrow1\un{c}abccT$&$\emptyset$&$\{3,9,10,20,21\}$\\[5pt]
$4$&$3\un{T}\leftarrow2\un{a}T$&$\mleft\{\begin{array}{@{}l@{}}1\un{a}aT\\2\un{b}aT\end{array}\mright.$&$\{1,5\}$\\[5pt]
$8\cdot 4$&$3\un{T}\leftarrow 3\un{c}T\leftarrow 2\un{a}cT$&$\emptyset$&$\{1,5\}$\\[5pt]
$10\cdot4$&$1\un{c}aT\leftarrow3\un{c}cdT\leftarrow2\un{a}ccdT$&$\emptyset$&$\{1,5\}$\\[5pt]
$21\cdot4$&$1\un{c}abcT\leftarrow3\un{c}ccdcT\leftarrow2\un{a}c^3dcT$&$\emptyset$&$\{1,5\}$\\[5pt]
$5$&$2\un{T}\leftarrow 2\un{b}T$&$\mleft\{\begin{array}{@{}l@{}}1\un{a}bT\\2\un{b}bT\end{array}\mright.$&$\{1,5\}$\\[5pt]
$\begin{array}{@{}l@{}}\{4,5,9,12,14,20\}\end{array}\cdot 5$&$3\un{T}\leftarrow 2\un{a}T\leftarrow \left\{\begin{array}{@{}l@{}}2\un{b}a\ldots T\\2\un{b}b\ldots T\end{array}\right.$&$\emptyset$&$\{1,5\}$\\[5pt]
$6$&$1\un{T}\leftarrow 2T\un{c}$&$\emptyset$&$\emptyset$\\[5pt]
$\{2,15\}\cdot 6$&$3\un{T}\leftarrow1T\un{b}\leftarrow 2T\ldots b\un{c}$&$\emptyset$&$\emptyset *$\\[5pt]
$7$&$1\un{T}\leftarrow 3T\un{d}$&$1Td\un{b}$&$\{2\}$\\[5pt]
$2\cdot 7$&$3\un{T}\leftarrow 1T\un{b}\leftarrow 3Tb\un{d}$&$2T\un{a}a\alpha$&$\{2\}$\\[5pt]
$7\cdot 2\cdot 7$&$1\un{T}\leftarrow3T\un{d}\leftarrow 3Tdb\un{d}$&$1T\un{a}ad\alpha$&$\{2\}$\\[5pt]
$2\cdot 7\cdot 2\cdot 7$&$3\un{T}\leftarrow 3Tbdb\un{d}$&$1T\un{c}aad\alpha$&$\{2,22,23\}$\\[5pt]
$7\cdot 2\cdot 7\cdot 2\cdot 7$&$1\un{T}\leftarrow 3Tdbdb\un{d}$&$1T\un{a}badd\alpha$&$\{2,22-25\}$\\[5pt]
$2\cdot 7\cdot 2\cdot 7\cdot 2\cdot 7$&$3\un{T}\leftarrow 3Tbdbdb\un{d}$&$1T\un{c}abadd\alpha$&$\{2,22-25\}$\\[5pt]
I think LIGR's 22-27 in the results& in the following are wrong here&&\\
$7\cdot 2\cdot 7\cdot 2\cdot 7\cdot 2\cdot 7$&$1\un{T}\leftarrow 3Tdbdbdb\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\[5pt]
$\begin{array}{@{}l@{}}\{16,18,22,24,26\}\cdot(2\cdot7)^3\end{array}$&$\leftarrow3T(db)^3\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\[5pt]
$15\cdot 7\cdot 2\cdot 7 \cdot 2\cdot 7$&$\leftarrow 3Tc\mleft\{\begin{array}{@{}l@{}}db\\aa\end{array}\mright\}dbdbdbdb\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\
$\begin{array}{@{}l@{}}\{16,18,22,24,26\}\\\cdot2\cdot7\cdot2\cdot7\end{array}$&$3Tb^5\un{d}\leftarrow 3Tcd\ldots dbdbdb\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\[5pt]
$15\cdot7\cdot2\cdot7$&$3Tb^5\un{a}\leftarrow 3Tc\mleft\{\begin{array}{@{}l@{}}db\\aa\end{array}\mright\}dbdbdb\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\[5pt]
$\begin{array}{@{}l@{}}\{16,18,22,24,26\}\cdot 2\cdot 7\end{array}$&&&$\{2,15-19,22-25\}$\\
&$1\un{T}\leftarrow 3Tdbdbdb\un{a}$&$\emptyset$&$\{2,15-19\}$\\[5pt]
&$1\un{T}\leftarrow 3Tdbdbdb\un{b}$&$\emptyset$&$\{2,22-27\}$\\[5pt]
$15\cdot7$&$3Tb^5\un{a}\leftarrow 3Tc\mleft\{\begin{array}{@{}l@{}}db\\aa\end{array}\mright\}dbdb\un{d}$&$\emptyset$&$\{2,15-19,22-27\}$\\[5pt]
$8$&$3\un{T}\leftarrow 3\un{c}T$&$\mleft\{\begin{array}{@{}l@{}}
2\alpha\un{a}cT\\
3\alpha\un{c}cT\end{array}\mright.$&$\{4,8\}$\\[5pt]
$\{8,10,21\}\cdot 8$&$\leftarrow3\un{c}cT$&$
\emptyset$&$\{4,8\}$\\[5pt]
$9$&$1\un{c}aT\leftarrow 2\un{a}cdT$&$
\emptyset$&$\{1,5\}$\\[5pt]
$10$&$1\un{c}aT\leftarrow3\un{c}cdT$&$
\emptyset$&$\{4,8\}$\\[5pt]
$11$&$1\un{c}aaT\leftarrow1\un{a}badT$&$
\emptyset$&$\{3\}$\\[5pt]
$12$&$1\un{c}aaT\leftarrow 2\un{b}badT$&$
\emptyset$&$\{1,5\}$\\[5pt]
$13$&$1\un{c}cT\leftarrow1\un{a}bcT$&$
\emptyset$&$\{3\}$\\[5pt]
$14$&$1\un{c}cT\leftarrow2\un{b}bcT$&$\emptyset$&$\{1,5\}$\\[5pt]
$15$&$3Tb^5\un{a}\leftarrow 1Tc\mleft\{\begin{array}{@{}l@{}}db\\aa\end{array}\mright\}dbd\un{b}$&$
\emptyset$&$\{6,7\}$\\[5pt]
$16$&$3Tb^5\un{a}\leftarrow 3Tca^3db\un{d}$&$
\emptyset$&$\{2,22,23\}$\\[5pt]
$17$&$3Tb^5\un{a}\leftarrow 2Tca^3db\un{c}$&$\emptyset$&$\emptyset$\\[5pt]
$18$&$3Tb^5\un{a}\leftarrow 3Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{d}$&$\emptyset$&$\{2,22-25\}$\\[5pt]
$19$&$3Tb^5\un{a}\leftarrow 2Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{c}$&$\emptyset$&$\{2,22-25\}$\\[5pt]
$20$&$1\un{c}abcT\leftarrow 2\un{a}ccdcT$&$\emptyset$&$\{1,5\}$\\[5pt]
$21$&$1\un{c}abcT\leftarrow3\un{c}ccdcT$&$\emptyset$&$\{4,8\}$\\[5pt]
$22$&$3Tbb\un{b}\leftarrow3Tadb\un{d}$&$\emptyset$&$\{2,22,23\}$\\[5pt]
$23$&$3Tbb\un{b}\leftarrow2Tadb\un{c}$&$\emptyset$&$\emptyset$\\[5pt]
$(7\cdot 2)^3\cdot 7\cdot 24$&$3Tb^3cb^3\un{d}$&$\emptyset$&$\{2,22-25\}$\\[5pt]
$(7\cdot 2)^3\cdot 7\cdot 24\cdot 24$&$\leftarrow 3bdccbdb\un{d}$&$\emptyset$&$\{2,22-25\}$\\[5pt]
$25$&$3Tb^3\un{b}\leftarrow2Tcbdb\un{c}$&$\emptyset$&$\emptyset$\\[5pt]
$\cdots26$&$3Tb^5\un{b}\leftarrow 3Tcadbdb\un{d}$&$\emptyset$&$\{2,22-25\}$\\[5pt]
$27$&$3Tb^5\un{b}\leftarrow 2Tcadbdb\un{c}$&$\emptyset$&$\emptyset$\\[5pt]
\end{longtable}
* See Lemma~\ref{lemma_2}\\
** See start of section dealing with sequences ending with 7a
%$x$&$3\cdot19$&$1\un{c}T\leftarrow1\un{c}cT\leftarrow2\un{b}bccT$&&$\emptyset$\\[5pt]
%&&&$\leftarrow2Tca^3dba\un{b}ada\alpha$&$\emptyset$\\[5pt]
% if the rightmost $d=b$. This by Lemma~\ref{lemma3} gives no new results. If that $d=a$ the backward search gives starting from $3Tca^3dbab^3\un{a}\alpha\leftarrow1Tca^3dba\un{c}a^3\alpha$ (by \eqref{2827}) gives just $2Tca^3dba\un{b}ada\alpha$ after 6 steps and stops so there are no new RCS's or LIGR's produced.
\fontsize{12}{14}\selectfont
The set of LIGR's is
\begin{equation}\label{newligrs1}
\begin{array}{@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
1&2\un{T}\stackrel{b}{\leftarrow}1\un{a}T\\
2&3\un{T}\stackrel{b}{\leftarrow}1T\un{b}\\
3&1\un{T}\stackrel{b}{\leftarrow}1\un{c}T\\
4&3\un{T}\stackrel{b}{\leftarrow}2\un{a}T\\
5&2\un{T}\stackrel{c}{\leftarrow}2\un{b}T\\
6&1\un{T}\stackrel{c}{\leftarrow}2T\un{c}\\
7&1\un{T}\stackrel{a}{\leftarrow}3T\un{d}\\
8&3\un{T}\stackrel{c}{\leftarrow}3\un{c}T\\
9&1\un{c}aT\stackrel{b}{\leftarrow}2\un{a}cdT\\
10&1\un{c}aT\stackrel{c}{\leftarrow}3\un{c}cdT\\
11&1\un{c}aaT\stackrel{b}{\leftarrow}1\un{a}badT\\
12&1\un{c}aaT\stackrel{c}{\leftarrow}2\un{b}badT\\
13&1\un{c}cT\stackrel{b}{\leftarrow}1\un{a}bcT\\
14&1\un{c}cT\stackrel{c}{\leftarrow}2\un{b}bcT\\
15&3Tb^5\un{a}\stackrel{b}{\leftarrow} 1Tc\mleft\{\begin{array}{@{}c@{}}d
b\\aa\end{array}\mright\}d
bd
\un{b}\\[20pt]
16&3Tb^5\un{a}\stackrel{a}{\leftarrow} 3Tca^3db\un{d}\\[20pt]
17&3Tb^5\un{a}\stackrel{c}{\leftarrow} 2Tca^3db\un{c}\\[20pt]
18&3Tb^5\un{a}\stackrel{a}{\leftarrow} 3Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{d}\\
19&3Tb^5\un{a}\stackrel{c}{\leftarrow} 2Tcd\mleft\{\begin{array}{@{}l@{}}ba\\cb\end{array}\mright\}db\un{c}\\
20&1\un{c}abcT\stackrel{b}{\leftarrow} 2\un{a}ccdcT\\
21&1\un{c}abcT\stackrel{c}{\leftarrow}3\un{c}ccdcT\\
22& 3Tbb\un{b}\stackrel{a}{\leftarrow}3Tadb\un{d}\\
23& 3Tbb\un{b}\stackrel{c}{\leftarrow}2Tadb\un{c}\\
24& 3Tb^3\un{b}\stackrel{a}{\leftarrow}3Tcbdb\un{d}\\
25& 3Tb^3\un{b}\stackrel{c}{\leftarrow}2Tcbdb\un{c}\\
26& 3Tb^5\un{b}\stackrel{a}{\leftarrow} 3Tcadbdb\un{d}\\
27& 3Tb^5\un{b}\stackrel{c}{\leftarrow} 2Tcadbdb\un{c}\\
28& 1\un{c}ababT\stackrel{b}{\leftarrow} 1\un{a}bbccbT\\
29& 1\un{c}ababT\stackrel{c}{\leftarrow} 2\un{b}bbccbT\\
30& 1\un{c}ababcT\stackrel{b}{\leftarrow} 1\un{a}bbccacT\\
31& 1\un{c}ababcT\stackrel{c}{\leftarrow} 2\un{b}bbccacT\\
\end{array}
\end{equation}
Because new LIGR's have been found, the ``can possibly be preceded by" relation needs to be updated as follows
\begin{equation}\label{cbpb}\begin{array}{@{}l@{}l@{}}
1,5\text{\hspace{1cm}}&4,5,9,12,14,20,29,31\\
2\text{\hspace{1cm}}&7,16,18,22,24,26\\
3\text{\hspace{1cm}}&1,3,11,13\\
4,8\text{\hspace{1cm}}&8,10,21\\
6,7\text{\hspace{1cm}}&2,15,28,30\\
9-14,20,21\text{\hspace{1cm}}&3\\
15,16,17,18,19\text{\hspace{1cm}}&7\\
20,21&3\\
22,23&7,16,22,24,26\\
24,25&7,18,24,26\\
26,27&7\\
\end{array}\end{equation}
The word ``possibly" is included because there may be other symbols in either of the strings $T$ that prevent a match of the sequences. Note that this refers to the order of the LIGR's which is reverse order of the TM computation.
The results summarised in Table~\ref{bigtable} will show that (when complete and correct) the set of LIGR's $1-31$ is closed under $F$ and therefore by Theorem~\ref{Theorem_5.3} these are sufficient to derive all the IRR's from the IRR(2).
\section{\label{sec8}Return to the IGR's and their significance}
The IGR's in Table~\ref{table3} can be expressed in a more organised way in the Table~\ref{table6}. Importantly the LIGR's involved on the left hand side and obtained from the computer calculation, agree with the very long calculation in the preceding section summarised in Table~\ref{bigtable}.
The following is the table of the distinct RIGR's in Table~\ref{table6} with the $\alpha$ values put back in and the redundant symbols $T_2$ representing arbitrary strings removed.
\fontsize{8}{8}\selectfont
\begin{longtable}{lllll}
\caption{The set of RIGR's\label{table5}}\\
$\begin{array}{lllll}
1\un{a}\to 2b\_&1\un{b}\to 3\_b&1\un{c}\to 1b\_&1\un{c}a\to 2bb\_&1\un{c}abab\to 3b^5\_\\
1\un{c}ababa\to 3\_bababa&1\un{c}ababc\to 3bbbbbc\_&1\un{c}abc\to 1bbbb\_&1\un{c}c\to 1bb\_&2\un{a}\to 3b\_\\
2\un{b}\to 2c\_&2b\un{c}\to 3\_bc&2bb\un{c}\to 1\_abc&2c\un{c}\to 1bb\_&3b^5\un{a}\to 3\_bababa\\
3cb\un{a}\to 3bbb\_&3\un{b}\to 1\_a&3bb\un{b}\to 1\_aba&3bbb\un{b}\to 3\_baba&3bbbbb\un{b}\to 3\_bababa\\
3cb\un{b}\to 3bbb\_&3c\un{b}\to 2bb\_&3\un{c}\to 3c\_&3\un{c}ba\to 3bbb\_&3\un{c}bab\to 3\_baba\end{array}$
\end{longtable}
\fontsize{12}{14}\selectfont
\newpage
\fontsize{11}{11}\selectfont
\begin{longtable}{@{}lcc@{}}
\caption{The table of IGR's (Table~\ref{table3}) re-expressed in terms of LIGR's and RIGR's\label{table6}}\\
$\alpha$&LIGR&RIGR\\
$b$&$\begin{array}{@{}lll@{}}
1\un{T_1}&\leftarrow &1\un{c}T_1\\
2\un{T_1}&\leftarrow&1\un{a}T_1\\
3\un{T_1}&\leftarrow&2\un{a}T_1\\
1\un{c}aT_1&\leftarrow&2\un{a}cdT_1\\
1\un{c}cT_1&\leftarrow&1\un{a}bcT_1\\
1\un{c}aaT_1&\leftarrow&1\un{a}badT_1\\
1\un{c}abcT_1&\leftarrow&2\un{a}ccdcT_1\\
1\un{c}ababT_1&\leftarrow&1\un{a}bbccbT_1\\
1\un{c}ababcT_1&\leftarrow&1\un{a}bbccacT_1\\
\end{array}$&$\begin{array}{@{}l@{}}1\_T_2\to 3\_bT_2\\
3\_T_2\to 1\_aT_2\end{array}$\\[50pt]\hline
$c$&$3\un{T_1}\leftarrow3\un{c}T_1$&$\begin{array}{@{}lll@{}}1\_aT_2&\to& 2bb\un{T_2}\\3\_babT_2&\to& 3\_babaT_2\end{array}$\\[10pt]\hline
$c$&$2\un{T_1}\leftarrow2\un{b}T_1$&$\begin{array}{@{}lll@{}}1\_cT_2&\to& 1bb\un{T_2}\\3\_baT_2&\to& 3bbb\un{T_2}\\3\_babT_2&\to& 3\_babaT_2\\
1\_ababaT_2&\to& 3\_bababaT_2\\\end{array}$\\[20pt]\hline
$a$&$1\un{T_1}\leftarrow3T_1\un{d}$&$\begin{array}{@{}lll@{}}1T_2\_&\to& 2T_2b\_\\2T_2\_&\to& 3T_2b\_\\3T_2b^5\_&\to& 3\un{T_2}bababa\end{array}$\\[15pt]\hline
$c$&$1\un{T_1}\leftarrow2T_1\un{c}$&$\begin{array}{@{}lll@{}}1T_2\_&\to& 1T_2b\_\\3T_2\_&\to& 3T_2c\_\\2T_2b\_&\to& 3\un{T_2}bc\\2T_2c\_&\to& 1T_2bb\_\\2T_2bb\_&\to& 1\un{T_2}abc\\
\end{array}$\\[25pt]\hline
$b$&$3\un{T_1}\leftarrow1T_1\un{b}$&$\begin{array}{@{}lll@{}}2T_2\_&\to& 2T_2c\_\\3T_2c\_&\to& 2T_2bb\_\\3T_2bb\_&\to& 1\un{T_2}aba\\3T_2cb\_&\to& 3T_2bbb\_\\3T_2bbb\_&\to& 3\un{T_2}baba\\3T_2bbbbb\_&\to& 3\un{T_2}bababa\end{array}$\\[30pt]\hline
$c$&$1\un{c}cT_1\leftarrow2\un{b}bcT_1$&$\begin{array}{@{}lll@{}}3\_babT_2&\to& 3\_babaT_2\\1\_ababT_2&\to& 3b^5\un{T_2}\\1\_ababaT_2&\to& 3\_bababaT_2\\1\_ababcT_2&\to& 3bbbbbc\un{T_2}\end{array}$\\[20pt]\hline
$c$&$1\un{c}aT_1\leftarrow3\un{c}cdT_1$&$\begin{array}{@{}lll@{}}1\_abcT_2&\to& 1bbbb\un{T_2}\\3\_babT_2&\to& 3\_babaT_2\\1\_ababaT_2&\to& 3\_bababaT_2\end{array}$\\[15pt]\hline
$c$&$\begin{array}{@{}lll@{}}
1\un{c}aaT_1&\leftarrow&2\un{b}badT_1\\
1\un{c}abcT_1&\leftarrow&3\un{c}ccdcT_1\\
1\un{c}ababT_1&\leftarrow&2\un{b}bbccbT_1\\
1\un{c}ababcT_1&\leftarrow&2\un{b}bbccacT_1\\
\end{array}$&$\begin{array}{@{}lll@{}}3\_babT_2&\to& 3\_babaT_2\\1\_ababaT_2&\to& 3\_bababaT_2\end{array}$\\[20pt]\hline
$c$&$3T_1bb\un{b}\leftarrow 2T_1adb\un{c}$&$3T_2\_\to 3T_2c\_$\\[10pt]\hline
$a$&$3T_1bb\un{b}\leftarrow 3T_1adb\un{d}$&$\begin{array}{@{}lll@{}}3T_2cb\_\to3T_2bbb\_\\3T_2b^5\_\to 3\un{T_2}bababa\end{array}$\\[10pt]
\end{longtable}
\fontsize{12}{14}\selectfont
Notice that the complete Table~\ref{table6} consisting of 11 blocks has the property that within each block every LIGR combines with every RIGR to form an IGR. Here the LIGR is $CS1\leftarrow CS3$ and the RIGR is $CS2\to CS4$ i.e. the IGR is $CS1\to\to CS2\Rightarrow CS3\to\to CS4$ provided $CS1\to\to CS2$ has the type LRL or RLR.
The last condition is automatically satisfied because within each block in Table~\ref{table6} $CS1$ and $CS2$ both have the pointer on the same side (and strings $T_1,T_2$).
The result with IGR's $4,5,14,15$ omitted (corresponding to $8.1$ and $9.1$ in block $1$, and $3.2$ and $4.2$ in block $9$ of Table~\ref{table6}) occurred when the program was run with ${\it n}={\rm 9}$. In this case the incomplete Table~\ref{table6} does not have the above property.
Can the IGR's be obtained directly (based on applying the process called $F$ directly starting from the single TM steps) or based on the LIGR's without first obtaining the IRR's to a length unknown beforehand as was done in the computer program \cite{tie_v3_2}? Note that this computer algorithm is very inefficient.
It follows from the fact that each IGR has two independent parts (its LIGR and its RIGR) once the value of $\alpha$ is fixed that
if $w$ and $x$ are LIGR's, and $y$ and $z$ are RIGRs, all with the same value of $\alpha$ that
\begin{equation}(w,y),(x,y),(w,z)\in IGR \Rightarrow (x,z)\in IGR\end{equation} again with the same value of $\alpha$ and where the ordered pairs of an LIGR and an RIGR are combined to give IGR's as above i.e.\begin{Theorem} given that $(w,y)\in IGR$, any LIGR $x$ such that $(x,y)\in IGR$ can be paired with any RIGR $z$ such that $(w,z)\in IGR$ to give another result $(x,z)\in IGR$, again with the same value of $\alpha$, thus the structure of Table~\ref{table6} is general.
\end{Theorem}
\subsection{Obtaining information about a TM from its IGR's}
Table~\ref{table9} shows the frequencies of the different types of IRR's obtained from the computer program \cite{tie_v3_2} applied to TM1. Here I have included the TM table itself regarding the steps to the right
as RLR and those to the left as LRL.
\begin{longtable}{rrrrrr}
\caption{The frequencies of the different types of IRR's\label{table9}}\\
length&RLL&RLR&LRL&LRR&total\\
\hline
1&0&5&4&0&9\\
2&1&4&4&3&12\\
3&2&2&4&2&10\\
4&1&2&5&1&9\\
5&0&3&0&1&13\\
6&3&2&16&1&22\\
7&30&0&0&30&0\\
8&0&0&56&0&56\\
9&0&0&106&0&106\\
10&0&0&201&0&201\\
\end{longtable}
Each IGR in Table~\ref{table3} is a logical implication from the existence of one IRR to another, each containing the arbitrary strings $T_1$ and $T_2$. For example $IGR55$ on the right gives an IRR of type $RLL$ if $|T_2|=0$. Its length is $|T_1|+4=|T_2|+6$ but needs completion (i.e. further computation as far as possible) if $|T_2|>0$. $IGR51$ gives an IRR of type RLR and requires $|T_1|+4=|T_2|+3$ which is its length.
The set of IGR's in Table~\ref{table3} is divided into two parts because the left hand members either represent an IRR of type LRL or RLR (extendable IRR's). The corresponding right hand members represent IRR's of four types such that each IGR is of one of four types as follows:
$LRL\Rightarrow LRL$, $LRL\Rightarrow LRR$, $RLR\Rightarrow RLR$, $RLR\Rightarrow RLL$.
The relation ``could be followed by" is true where the right hand member of the first IGR matches the left hand member of the second one for suitable strings $T_1$ and $T_2$. Thus in many cases the matching will be conditional and this relation will include all possible matches between the IGR's so that the absence of such a relation definitely rules out any possible match.
The relation ``could be followed by" implies one IGR can follow the other logically to generate a new IRR's from a given one. For example IGR $41$ can be followed by IGR $50$ provided the last symbol of $T_2$ is $c$. Because of this any such relation needs to be verified for the particular case in question.
[ delete? In the case that the number of IGR's is finite as in this example (\ref{tm2}), the absence of IRR's of type RLR of length {\it n} for all sufficiently large ${\it n}$ would follow from the absence of a closed cycle of IGR's of type $RLR\Rightarrow RLR$ that can be repeated indefinitely.]
This relation can be represented by a directed graph (digraph) where the nodes are IGR's and is also separated into two parts because of the two types of extendable IRR's.
The existence of any circuits should be established for each part of the digraph separately. The existence of such a circuit implies that (provided it can be iterated indefinitely) the number of IRR's of extendable type generated from the TM is infinite. This implies the existence of IRR's of this type for arbitrary large length (${\it n}$). The other case of the absence of a circuit implies their number is finite at least when the number of IGR's is finite.
The search for such closed cycles can be done following from the relation on IGR's defined by ``could be followed by" that is easily obtained either from Table~\ref{table3} by matching the state and the symbols in the neighbourhood of the pointer and has been programmed.
For the example TM \ref{tm2}, there were no circuits for the digraph of IRR's of type RLR but there were circuits for IRR's of type LRL showing that arbitrarily long IRR's of type LRL could exist but not for IRR's of type RLR.
The two circuits of length 1 involve respectively IGR's $38c1$ and $39c1$.
IGR $38$ iterated twice gives $2\un{T_1}\to\to3\_babT_2 \stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3\_babaT_2\stackrel{c}{\Rightarrow}2\un{b}bT_1\to\to 3\_babaaT_2$ and it can be clearly iterated ${\it n}$ times giving
$2\un{b}b^{{\it n}-1}T_1\to\to 3\_baba^{\it n}T_2$. In order to determine $T_1$ and $T_2$, the table of IRR's generated from the TM shows that an example of IGR $38$ (IRR of length $5$ number $5$ found by searching for IRR's of the form of the RHS of IGR$38$) has context pair $(bbcb,a)$ showing that $T_1=bbcb$ and $T_2=a$ corresponding to the IRR $2\un{b}bcb\to\to 3\_baba$. Therefore a result of the iteration of $38$ is
$2\un{b}b^{{\it n}-1}bbcb\to\to 3\_baba^{{\it n}+1}$ for ${\it n}\ge 0$. There are many other examples of $(T_1,T_2)$ which could be used here such as anything resulting from applying IGR$14$ because this matches the RHS of $38$. Another example of this is $2\un{b}bcac\to\to 3\_babac$ giving the result $2\un{b}b^{{\it n}-1}bbcccb\to\to 3\_baba^{{\it n}+2}b$ for ${\it n}\ge 0$.
Similarly IGR $39$ iterated ${\it n}$ times gives
$3\un{c}c^{{\it n}-1}T_1\to\to 3\_baba^{\it n}T_2$ and an example is $T_1=ca^3$ and $T_2 = a$.
An example of a circuit of length 2 is $22\cdot7$. IGR $22$ is $1\un{T_1}\to\to 3\_T_2\stackrel{22 b}{\Rightarrow}1\un{c}T_1\to\to 1\_aT_2$. If $T_1$ begins with $c$ then $22\cdot 7$ can
be written as $1\un{c}T_1\to\to 3\_T_2\stackrel{22 b}{\Rightarrow}1\un{c}cT_1\to\to 1\_aT_2\stackrel{7 b}{\Rightarrow}1\un{a}bcT_1\to\to 3\_baT_2$. However this clearly does not iterate because $1\un{a}bc$ does not match $1\un{c}$. This also happens with $1\cdot 26$.
An example of a circuit of length 2 that does iterate is $1\cdot 22$ which gives $1\un{T_1}\to\to 1\_T_2\stackrel{1 b}{\Rightarrow}1\un{c}T_1\to\to 3\_bT_2\stackrel{22}{\Rightarrow}1\un{c}cT_1\to\to 1\_abT_2$. This iterates to get $1\un{c}^{2\it n}T_1\to\to1\_(ab)^{\it n}T_2$. An example of the first IRR is $1\un{c}b\to\to 1\_ab$. In this case $T_1=cb$ and $T_2=ab$ therefore $1\un{c}^{2\it n}cb\to\to 1\_(ab)^{{\it n}+1}$.
In these examples, if the middle element of the IRR, the LHS, was added back, the first part of them indicate a recurring move to the right, so there are examples of this.
Because there are no circuits in the digraph of RLR type IGR's, all the IRR's of type RLR are obtained by starting with the RLR IRR's of length 2 and applying all the IGR's of type $RLR\Rightarrow RLR$ until this can be done no more. These IGR's are just those numbered $40-44,46,47,50,51$. Of these IGR's $43,44,46$ do not match any others. The IGR's of type RLR generating the IRR(2) are just $40$ with context $(c,b)$, $41$ with context $(a,b)$ and $47$ with context $(c,)$. Carrying this out gives the results in the diagram following where the counts for the numbers of distinct IRR's for each length are given in the top two rows. The frequencies match the IRR results of the computer program and therefore the computer results for the cycles of the IGR's validate the results concerning the moving window behaviour of the TM guessed from Table~\ref{table7}.
\begin{figure}
\begin{adjustbox}{width = 10cm,center}
\centering
\xymatrix @R = 0.3cm{
{\it n}&1 & 2 & 3 & 4 & 5 & 6\\
{\it m}&5 & 4 & 2 & 2 & 3 & 2\\
& & & & 7x & 10\ar[r]|-{44} &20x\\
& 5\ar[r]|-{40a}\ar[dr]|-{40c}& 8\ar[r]|-{42} & 7\ar[ur]|-{46}\ar[r]|-{41} &9\ar[ur]|-{51}\ar[r]|-{50}\ar[rd]|-{44} & 11\ar[r]|-{43} & 21x\\
& & 6x& & & 13x &\\
& 6\ar[r]|-{41} & 12x &&&&\\
& 9\ar[r]|-{47}& 9\ar[r]|-{41} & 8x & & &\\
& 7x &&&&&\\
& 8x &&&&&\\}
\caption{{\bf Provenance of the IRR's of type RLR and lengths up to 6}. An IRR of length 1 is just a single TM step of type being defined as RLR (or LR) if it goes right and LRL (or RL) if it goes left. {\it n} is the length of the IRRs, {\it m} is the number of IRR's of type RLR (i.e. LR) of length {\it n}. Only this type of IRR's are shown.
Each of the numbers in larger font indicates an IRR of the given length {\it n} given in \eqref{irr1-6}. The numbers in smaller font are the IGR's in Table~\ref{table3} needed to generate the IRR on the right of the arrow from the one on its left with letter after it (if present) being $\alpha$. An IRR labelled $x$ indicates that no IGR can generate any new IRR of type RLR from it.}
\label{fig1}
\end{adjustbox}
\end{figure}
These two results taken together show that arbitrarily long IRR's of type LRL exist but within them, the pointer can move no more than 6 spaces to the left so for example a sequence of CS's of the form $1\to 10\to 0$ can exist but not if it is of the form $1\to 9\to x\to 10\to 0$ with $x\le 4$ because this has a subsequence of the form $9\to x\to 10$ which is an IRR of type RLR of length $10-x+1\ge7$. If $9>x>4$ as soon as the pointer after reaching $10$ reaches $5$ then the moving window argument applies. Note that this does not stop the TM moving arbitrarily far to the right eg with one of the iterations above following IRR $6.21$ such as when all the symbols to its right are $c$'s.
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 is 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.\\ Refer to IRR's of type LRL with\\length less than or equal to 6.\eqref{irr1-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}
\fontsize{11}{11}\selectfont
\begin{equation}\label{irr1-6}\begin{array}{ccc}
%\\[-50pt]
\begin{array}{cl}
&TM\text{ }table (n=1)\\[5pt]
1& 3\un{a}\to 1\_a\\
2& 3\un{b}\to 1\_a\\
3& 2\un{c}\to 1\_c\\
4& 1\un{b}\to 3\_b\\
5& 1\un{c}\to 1b\_\\
6& 1\un{a}\to 2b\_\\
7& 2\un{b}\to 2c\_\\
8& 2\un{a}\to 3b\_\\
9& 3\un{c}\to 3c\_\\
\hline
&length = 2\\
1& 1\un{c}b\to\to 1\_ab\\
2& 2\un{a}a\to\to 3\_ba\\
3& 2\un{a}b\to\to 3\_ba\\
4& 2a\un{c}\to\to 3\_bc\\
5& 1\un{a}c\to\to 3\_bc\\
6& 2c\un{c}\to\to 1bb\_\\
7& 2\un{b}c\to\to 1bb\_\\[5pt]
8& \begin{array}{@{}l@{}}3c\un{a}\\3c\un{b}\end{array}\to\to 2bb\_\\[10pt]
9& 1c\un{b}\to\to 2bb\_\\
10& 3\un{c}a\to\to 2bb\_\\
11& 3\un{c}b\to\to 2bb\_\\[5pt]
12& \begin{array}{@{}l@{}} 3a\un{a}\\3a\un{b}\end{array}\to\to 3bb\_\\[10pt]
\hline
&length = 3\\[5pt]
1& \begin{array}{@{}l@{}} 1aa\un{b}\\1ab\un{b}\end{array}\to\to 1\_aba\\[10pt]
2& 1\un{a}aa\to\to 1\_aba\\
3& 1\un{a}ab\to\to 1\_aba\\
4& 2cb\un{c}\to\to 1\_abc\\
5& 1\un{c}ac\to\to 1\_abc\\
6& 1\un{c}cb\to\to 3\_bab\\[5pt]
7& \begin{array}{@{}l@{}}1ca\un{b}\\1cb\un{b}\end{array}\to\to 2bbc\_\\[10pt]
8& \begin{array}{@{}l@{}}3cb\un{a}\\3cb\un{b}\end{array}\to\to 3bbb\_\\[10pt]
9& 2\un{b}aa\to\to 3bbb\_\\
10& 2\un{b}ab\to\to 3bbb\_\\
\end{array} &
\begin{array}{cl}
\hline
&length = 4\\[5pt]
1& \begin{array}{@{}l@{}}1\un{c}ccb\\1\un{a}bcb\end{array}\to\to 1\_abab\\[10pt]
2& \begin{array}{@{}l@{}}1cba\un{b}\\1cbb\un{b}\end{array}\to\to 3\_baba\\[10pt]
3& 2\un{b}bcb\to\to 3\_baba\\
4& 1\un{c}aaa\to\to 3\_baba\\
5& 1\un{c}aab\to\to 3\_baba\\[5pt]
6& \begin{array}{@{}l@{}}1\un{c}cac\\2\un{a}cac\\2\un{a}cbc\end{array}\to\to 3\_babc\\[15pt]
7& \begin{array}{@{}l@{}}2cab\un{c}\\2cbb\un{c}\end{array}\to\to 1bbbb\_\\[10pt]
8& \begin{array}{@{}l@{}}3\un{c}cac\\3\un{c}cbc\end{array}\to\to 1bbbb\_\\[10pt]
9& \begin{array}{@{}l@{}}3cab\un{a}\\3cab\un{b}\\3cbb\un{a}\\3cbb\un{b}\end{array}\to\to 3bbcb\_\\[10pt]
\hline
&length = 5\\[5pt]
1& 1\un{a}bbcb\to\to 1\_ababa\\[5pt]
2& \begin{array}{@{}l@{}}1\un{c}caaa\\2\un{a}caaa\\2\un{a}cbaa\\1\un{a}baaa\\1\un{a}baba\end{array}\to\to 1\_ababa\\[25pt]
3& \begin{array}{@{}l@{}}1\un{c}caab\\2\un{a}cdab\\1\un{a}badb\end{array}\to\to 1\_ababa\\[15pt]
4& \begin{array}{@{}l@{}}1\un{c}ccac\\1\un{a}dcac\\1\un{a}acbc\end{array}\to\to 1\_ababc\\[15pt]
5& 2\un{b}bbcb\to\to 3\_babaa\\[5pt]
6&\begin{array}{@{}l@{}}3\un{c}cdaa\\2\un{b}bada\end{array}\to\to 3\_babaa\\[10pt]
7&\begin{array}{@{}l@{}}3\un{c}cdab\\2\un{b}badb\end{array}\to\to 3\_babaa\\[10pt]
8&\begin{array}{@{}l@{}}1\un{c}cccb\\1\un{a}bccb\\1\un{c}abcb\end{array}\to\to 3\_babab\\[15pt]
9& \begin{array}{@{}l@{}}2\un{b}dcac\\2\un{b}acbc\end{array}\to\to 3\_babac\\[10pt]
10& 3cadb\un{d}\to\to 3bbbbb\_\\
11& 1cdbd\un{b}\to\to 3bbbbb\_\\
12& 2\un{b}bccb\to\to 3bbbbb\_\\
13& 2cadb\un{c}\to\to 3bbcbc\_\\
\end{array} &
\begin{array}{cl}
\hline
&length = 6\\[5pt]
1& 1\un{a}bbbcb\to\to 1\_ababaa\\[5pt]
2& \begin{array}{@{}l@{}}2\un{a}ccdaa\\1\un{a}bbada\end{array}\to\to 1\_ababaa\\[10pt]
3& \begin{array}{@{}l@{}}2\un{a}ccdab\\1\un{a}bbadb\end{array}\to\to 1\_ababaa\\[10pt]
4& \begin{array}{@{}l@{}}1\un{c}c^4b\\1\un{a}bcccb\\1\un{c}abccb\\1\un{c}cabcb\\2\un{a}ccdcb\\2\un{a}cdbcb\end{array}\to\to 1\_ababab\\[35pt]
5& \begin{array}{@{}l@{}}1\un{a}bdcac\\1\un{a}bacbc\end{array}\to\to 1\_ababac\\[10pt]
6& 2\un{b}bbbcb\to\to 3\_babaaa\\[5pt]
7& \begin{array}{@{}l@{}}3\un{c}ccdaa\\2\un{b}bbada\end{array}\to\to 3\_babaaa\\[10pt]
8& \begin{array}{@{}l@{}}3\un{c}ccdab\\2\un{b}bbadb\end{array}\to\to 3\_babaaa\\[10pt]
9& \begin{array}{@{}l@{}}2\un{b}bcccb\\3\un{c}cdbcb\\3\un{c}ccdcb\end{array}\to\to 3\_babaab\\[15pt]
10& \begin{array}{@{}l@{}}2\un{b}bdcac\\2\un{b}bacbc\end{array}\to\to 3\_babaac\\[10pt]
11& 3caadb\un{d}\to\to 3\_bababa\\
12& 1cadbd\un{b}\to\to 3\_bababa\\
13& 3cdbdb\un{d}\to\to 3\_bababa\\
14& 1\un{c}abbcb\to\to 3\_bababa\\[5pt]
15& \begin{array}{@{}l@{}}1\un{a}dcaaa\\1\un{c}abada\\1\un{a}acbaa\\1\un{c}ccaaa\end{array}\to\to 3\_bababa\\[20pt]
16& \begin{array}{@{}l@{}}2\un{b}acdaa\\2\un{b}bcaaa\end{array}\to\to 3\_bababa\\[10pt]
17& \begin{array}{@{}l@{}}1\un{a}dcaab\\1\un{c}abadb\\1\un{a}acbab\\1\un{c}ccaab\end{array}\to\to 3\_bababa\\[20pt]
18& \begin{array}{@{}l@{}}2\un{b}dcaab\\2\un{b}acbab\end{array}\to\to 3\_bababa\\[10pt]
19& \begin{array}{@{}l@{}}1\un{c}cccac\\1\un{a}bccac\\1\un{c}adcac\\1\un{c}aacbc\end{array}\to\to 3\_bababc\\[20pt]
20& 2caadb\un{c}\to\to 3b^5c\_\\
21& 2cdbdb\un{c}\to\to 3b^5c\_\\
22& 2\un{b}bccac\to\to 3b^5c\_\\
\end{array}
\end{array}\end{equation}
\fontsize{12}{14}\selectfont
The IRR's of \eqref{irr1-6} includes many examples of different IRR's with the same RHS's and examples where
many origins correspond to one RHS. The distinction between these cases is because two IRR's are the same if and only if they have the same middle member (originally known as the LHS) and is omitted for brevity.
$40\to(b,)42\to(bb,c)41\to 51$ These specialisations remove the conditions that otherwise would apply to
the connections between the IGR's. Can this be done systematically to all the IGR's?
$1\un{T_1}bb\to\to 2T_2c\_$,$3T_1\un{b}\to\to 2T_2\_$
%\begin{equation}
%41\left\{\begin{array}{l}a1\to 50\to 43x\\
%a2\to\left\{\begin{array}{l}
%44\left\{\begin{array}{l}c1x\\c2x\end{array}\mright.\\
%50\to 43x\\
%\to 51\left\{\begin{array}{l}a1x\\a2x\\a3x\\a4x\end{array}\mright.\\
%\end{array}\mright.\end{equation}
%\begin{equation}(c,b)40\left\{\begin{array}{l}{\{a1,a2\}\to 42\to
%46x\end{array}\mright.\\
%c1x\end{array}\mright.\end{array}\mright.\end{equation}
Show this gives rise to finite state machine behaviour and relate it to ${\it n}_L$ and ${\it n}_R$ in my first TM paper.
If the IGR's are related by ``can be followed by" it is not necessarily true that is $A\to B$ and $B\to C$ then $A\to B\to C$. What are the extra conditions? If they could all be found then all the conditions for closed cycles could be found.
Find all IGR's $x$ such that $x\to x$.
Combining RLR iterations with LRL iterations for a TM with cycles in both cases. This would give rise to possibly repeating cycles that might be describable as a simulated TM.
\subsection{Approaches to the analysis of a simpler example with quite a different behaviour}
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}
\begin{longtable}{cccccc}
\caption{The frequencies of the different types of IRR's\label{table7}}\\
length({\it n})&RLL&RLR&LRL&LRR&total\\
\hline
1&0&3&3&0&6\\
2&1&1&3&0&5\\
3&1&1&2&1&5\\
4&1&1&2&0&4\\
5&1&1&2&1&5\\
6&1&1&2&1&5\\
\end{longtable}
For this TM the computer program \cite{tie_v3_2} gave the results in Table~\ref{table7}
and it appears that the frequencies in the row for ${\it n}=5$ are then repeated indefinitely for larger values of ${\it n}$ which was checked to $\it n$ up to 20. The results for the IRR's up to length 8 are given in \eqref{irr2-10}
\fontsize{10}{10}\selectfont
\begin{equation}\label{irr2-10}\begin{array}{ll}
&TM\text{ }table (n=1)\\[5pt]
1& 1\un{a}\to 2b\_\\
2& 1\un{b}\to 2\_a\\
3& 2\un{a}\to 1b\_\\
4& 2\un{b}\to 2\_a\\
5& 3\un{a}\to 3a\_\\
6& 3\un{b}\to 1\_b\\
\hline
&length = 2\\
1& 3a\un{b}\to1\un{a}b\to 2\_aa\\
2& 2\un{a}b\to1b\un{b}\to 2\_aa\\
3& 1\un{a}b\to2b\un{b}\to 2\_aa\\
4& 3\un{a}b\to3a\un{b}\to 2\_aa\\
5& \mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}a\un{b}\to 2\un{a}a\to 2bb\_\\
\hline
&length = 3\\
1& 3ab\un{b}\to2\un{a}ab\to 2\_aaa\\
2& 1\un{a}ab\to 1bb\un{b}\to 2\_aaa\\
3& 2\un{a}ab\to 2bb\un{b}\to2\_aaa\\
4& \mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab\un{b}\to 2\un{a}aa\to 1bbb\_\\
5& 3\un{a}ab\to 3aa\un{b}\to1bbb\_\\
\hline
&length = 4\\
1&3abb\un{b}\to 2\un{a}aab\to 2\_aaaa\\
2&2\un{a}aab\to 1bbb\un{b}\to 2\_aaaa\\
3&1\un{a}aab\to 2bbb\un{b}\to 2\_aaaa\\
4&\mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}abb\un{b}\to 2\un{a}aaa\to 2bbbb\_\\
\hline
&length = 5\\
1&3abbb\un{b}\to 2\un{a}aaab\to 2\_aaaaa\\
2&1\un{a}aaab\to 1bbbb\un{b}\to 2\_aaaaa\\
3&2\un{a}aaab\to 2bbbb\un{b}\to 2\_aaaaa\\
4&\mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}abbb\un{b}\to2\un{a}aaaa\to 1bbbbb\_\\
5& 3\un{a}aabb\to 1abbb\un{b}\to 1bbbbb\_\\
\hline
&length = 6\\
1&3abbbb\un{b}\to2\un{a}aaaab\to 2\_aaaaaa\\
2&2\un{a}aaaab\to 1bbbbb\un{b}\to 2\_aaaaaa\\
3&1\un{a}aaaab\to 2bbbbb\un{b}\to 2\_aaaaaa\\
4&\mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}abbbb\un{b}\to 2\un{a}aaaaa\to 2bbbbbb\_\\
5&3\un{a}aabab\to 2abbbb\un{b}\to2bbbbbb\_\\
\hline
&length = 7\\
1& 3ab^5\un{b}\to 2\un{a}a^5b\to 2\_a^7\\
2& 1\un{a}a^5b\to 1b^6\un{b}\to 2\_a^7\\
3& 2\un{a}a^5b\to 2b^6\un{b}\to 2\_a^7\\
4& \mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^5\un{b}\to 2\un{a}a^6\to 1b^7\_\\
5& 3\mleft.\begin{array}{@{}l@{}}\un{a}aabaab\\\un{a}aaabbb\end{array}\mright\}\to 1ab^5\un{b}\to 1b^7\_\\
\hline
&length = 8\\
1& 3ab^6\un{b}\to 2\un{a}a^6b\to 2\_a^8\\
2& 2\un{a}a^6b\to 1b^7\un{b}\to 2\_a^8\\
3& 1\un{a}a^6b\to 2b^7\un{b}\to 2\_a^8\\
4& \mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^6\un{b}\to 2\un{a}a^7\to 2b^8\_\\
5& 3\mleft\{\begin{array}{@{}l@{}}\un{a}aabaaab\\\un{a}aaabbab\\\un{a}aaababb\end{array}\mright\}\to 2ab^6\un{b}\to 2b^8\_\\
\end{array}\end{equation}
\fontsize{12}{14}\selectfont
and the number of distinct extra IGR's needed to obtain the IRR's of length 2, 3, etc. are : 5 3 1 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16.
The strongly connected components with more than one element are just two with
\begin{equation}\begin{array}{@{}l@{}}
SCC1 =\left\{\begin{array}{@{}l@{}}1\un{T_1}\to\to2\_T_2\stackrel{b}{\Rightarrow} 2\un{a}T_1\to\to 2\_aT_2\\
2\un{T_1}\to\to 2\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 2\_aT_2\end{array}\right.\\[20pt]
SCC2 =\left\{\begin{array}{@{}l@{}}2\un{T_1}\to\to1T_2\_\stackrel{a}{\Rightarrow} 2T_1\un{b}\to\to 2T_2b\_\\
2\un{T_1}\to\to 2T_2\_\stackrel{a}{\Rightarrow}2T_1\un{b}\to\to 1T_2b\_\end{array}\right.
\end{array}.\end{equation}
Before going any further it will be very convenient to introduce a symbol ${\it p}(1,2,{\it n})=\left\{\begin{array}{@{}l@{}}1\text{ {\it n }odd}\\2\text{ {\it n }even}\end{array}\right\}$ where {\it p} stands for parity and the arguments are the {\it symbols} for the TM state not the integers 1 and 2 and so this will be used in place of a particular TM state.
From the computer program output, the IGR's appear to be infinite in number as well as the IRR's but with a more complicated structure.
Thus it seems to indicate that the IRR's are simpler to characterise than the IGR's, so the analysis will start there. From the computer output, there seems to be a general result \eqref{tm3_irrsf} for the IRR({\it n}) which is as follows:
\begin{equation}\label{tm3_irrsf}\begin{array}{@{}l@{\hspace{10pt}}l@{}}
\mleft.\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^{{\it n}-2}\un{b}\to2\un{a}a^{{\it n}-1}\to
{\it p}(1,2,{\it n})
b^{\it n}\_& {\it n}\ge2\\
3ab^{{\it n}-2}\un{b}\to
2\un{a}a^{{\it n}-2}b\to 2\_a^{\it n}& {\it n}\ge3\\
1\un{a}a^{{\it n}-2}b\to {\it p}(1,2,{\it n})
b^{{\it n}-1}\un{b}\to 2\_a^{\it n}& {\it n}\ge 2\\
2\un{a}a^{{\it n}-2}b\to {\it p}(2,1,{\it n})
b^{{\it n}-1}\un{b}\to 2\_a^{\it n}& {\it n}\ge2\\
3\un{a}{\it s}_{{\it n}-1}(a,b)\to {\it p}(1,2,{\it n})
ab^{{\it n}-2}\un{b}\to {\it p}(1,2,{\it n})
b^{\it n}\_& {\it n}\ge5\\
\end{array}\end{equation}
where ${\it s}_{{\it n}-1}(a,b)$ is the set of all sequences of $a$ and $b$ of length ${\it n}-1$ such that $3\un{a}{\it s}_{{\it n}-1}(a,b)\to {\it p}(1,2,{\it n})
ab^{{\it n}-2}\un{b}$ but is not characterised any further yet.
\begin{proof}
To prove this by induction using results for ${\it n}\le 5$ that are easily checked in the computer output Table~\ref{irr2-10}:
first $F$ needs to applied to \eqref{tm3_irrsf}.1,3,4 only, because \eqref{tm3_irrsf}.2 and \eqref{tm3_irrsf}.5 are not of extendable type. After proving these by induction, then the others will follow.
The backward search gives, writing each step unless otherwise indicated:
\begin{equation}\label{1.1}1ab^{{\it n}-2}\un{b}\alpha\left\{\begin{array}{@{}l@{}}\stackrel{\alpha =b}{\leftarrow}3ab^{{\it n}-2}b\un{b}\\
\leftarrow 2ab^{{\it n}-3}\un{a}b\alpha\leftarrow 1ab^{{\it n}-4}\un{a}ab\alpha \leftarrow 2ab^{{\it n}-5}\un{a}aab\alpha \ldots p(2,1,{\it n})a\un{a}a^{{\it n}-3}b\alpha \leftarrow\emptyset\end{array}\right..\end{equation}
Likewise
\begin{equation}\label{1.2}2ab^{{\it n}-2}\un{b}\alpha \mleft\{\begin{array}{@{}l@{}}\stackrel{\alpha=a}{\leftarrow} \mleft\{\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^{{\it n}-2}b\un{b}\\
\leftarrow 1ab^{{\it n}-3}\un{a}b\alpha \leftarrow\mleft\{\begin{array}{@{}l@{}}2ab^{{\it n}-4}\un{a}ab\alpha
\leftarrow \mleft\{\begin{array}{@{}l@{}}1ab^{{\it n}-5}\un{a}aab\alpha (1)\\
\mleft\{\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^{{\it n}-4}a\un{b}b\alpha
\mleft\{\begin{array}{@{}l@{}}\stackrel{1}{\leftarrow} 3ab^{{\it n}-4}ab\un{b}\alpha \leftarrow \emptyset\\
\stackrel{2}{\leftarrow}\emptyset\end{array}\mright.\\
\end{array}\mright.\\
3ab^{{\it n}-3}a\un{b}\alpha \leftarrow 3ab^{{\it n}-3}\un{a}b\alpha \leftarrow\emptyset\end{array}\mright.\end{array}\mright..
\end{equation}
Here there is a cycle of length 2 that ends at (1) when $\it n$ is odd by reaching $1a\un{a}a^{{\it n}-3}b\alpha$ from which no further backward steps are possible. If $\it n$ is even it is very complicated.
The results \eqref{1.1} and \eqref{1.2} can be summarised by
\begin{equation}\begin{array}{@{}l@{}}
1ab^{{\it n}-2}\un{b}\alpha \stackrel{b}{\leftarrow}3ab^{{\it n}-1}\un{b}\\
2ab^{{\it n}-2}\un{b}\alpha\left\{\begin{array}{@{}l@{}}
\leftarrow \mleft\{\begin{array}{@{}l@{}}1\\2\end{array}\mright\}ab^{{\it n}-1}\un{b}\\
\stackrel{{\it n}\text{ even}}{\leftarrow} 3\un{a}{\it s}_{{\it n}-1}(a,b)\alpha\\
\stackrel{{\it n}\text{ odd}}{\leftarrow}\emptyset\end{array}\right.
\end{array}\end{equation}
The first of these gives the IRR \eqref{tm3_irrsf}.2 with ${\it n}$ increased by 1 and the second gives both parts of \eqref{tm3_irrsf}.1 with ${\it n}$ increased by 1 using the following results \eqref{nplus1} (that are very easy to show) to get the RHS's:
\begin{equation}\label{nplus1}\begin{array}{@{}l@{}}1b^{\it n}\un{a}\to 2b^{{\it n}+1}\_\\1b^{\it n}\un{b}\to 2\_a^{{\it n}+1}\\2b^{\it n}\un{a}\to 1b^{{\it n}+1}\_\\2b^{\it n}\un{b}\to 2\_a^{{\it n}+1}\\2\un{b}a^{\it n}\to 2\_a^{{\it n}+1}\\
2\un{a}a^{\it n}\to {\it p}(2,1,{\it n})b^{{\it n}+1}\_\end{array}\end{equation} together with ${\it p}(2,1,{\it n})={\it p}(1,2,{\it n}+1)$.
Applying $F$ to \eqref{tm3_irrsf}.3 gives \eqref{tm3_irrsf}.4 with ${\it n}\to {\it n}+1$ and vice versa with $\alpha = b$.
Putting $\alpha=a$ on the left of \eqref{tm3_irrsf}.4 gives
${\it p}(1,2,{\it n}+1)ab^{{\it n}-1}\un{b}\to 2\un{a}a^{\it n}\to {\it p}(1,2,{\it n}+1)b^{{\it n}+1}\_$
which contains the right hand half of \eqref{tm3_irrsf}.5 and because the conditions of Lemma~\ref{lemma1} are satisfied it is an IRR of type RLR with ${\it n}\to {\it n}+1$.
This together with \eqref{irr2-10} establishes \eqref{tm3_irrsf} by induction.\end{proof}
These middle elements (LHS) in\eqref{tm3_irrsf} were included for clarity. They are a record of the successive values of $\alpha$ used in the chain of applications of $F$ starting from the single TM steps.
In this proof, the middle elements just need $\alpha$ to be added at the appropriate end, and the new RHS is just found from the original RHS and $\alpha$ by taking the computation as far as possible.
These results for the IRR's can now be expressed in terms of the IGR's that generate them. These IGR's were implicit in the above proof.
Directly from \eqref{tm3_irrsf}.2 with $\alpha$ added gives \begin{equation}2\alpha \un{a}a^{{\it n}-2}\mleft\{\begin{array}{@{}l@{}}\leftarrow 3\alpha ab^{{\it n}-2}\un{b}\\\stackrel{b}{\leftarrow}1\un{a}a^{{\it n}-1}b\end{array}\mright.\end{equation}
\begin{figure}[h]
\begin{adjustbox}{width = 10cm,center}
\centering
\xymatrix @R = 0.3cm{
1.1(RLR)\ar[dr]^1& 1.2(RLR)\ar @{}|{}@(ul,ur)|-*=0@{>}^3\ar[l]_2 & 3(LRL)\ar[r]<2pt>^4 & 4(LRL)\ar[d]^6\ar[l]<2pt>^5\\
& 2(RLL) & & 5(LRR)\\}
\caption{{\bf The relationship between the IGR's in \eqref{tm3_igrs} and the parts of \eqref{tm3_irrsf} for consecutive values of ${\it n}$}.
The nodes in larger font are IRR's in \eqref{tm3_irrsf} numbered consecutively and the type of the IRR appears in parentheses after the IRR number. Each arrow corresponds to an IGR in \eqref{tm3_igrs} including the one relating \eqref{tm3_irrsf}.1.2 to itself and are also numbered consecutively. IGR's 1 and 6 generate IRR's of non-extendable type.
The two disconnected parts correspond to $SCC2$ and $SCC1$ respectively. To these the two relationships in \eqref{tm3_igrs}.\{7,8\} must be added.}
\label{fig3}
\end{adjustbox}
\end{figure}
The IGR's are as follows in \eqref{tm3_igrs}. The last two don't involve $T_1$ and $T_2$ because each is used only in a single context as shown given by specifying and including the values of the arbitrary strings into the IGR's. If there are more than one array in an IGR, the top values go together to get one result, and the bottom ones to get another result.
\newpage
\begin{equation}\label{tm3_igrs}\begin{array}{@{}l@{}}
1\un{T_1}\to\to \left\{\begin{array}{@{}l@{}}1\\2\end{array}\right\}T_2b^{\it n}\_\stackrel{b}{\Rightarrow}3T_1\un{b}\to\to 2\un{T_2}a^{{\it n}+1}\text{ for }{\it n}\ge0\\
2\un{T_1}\to\to \left\{\begin{array}{@{}l@{}}1\\2\end{array}\right\}T_2\_\stackrel{a}{\Rightarrow}1T_1\un{b}\to\to \left\{\begin{array}{@{}l@{}}2\\1\end{array}\right\}T_2b\_\\
2\un{T_1}\to\to \left\{\begin{array}{@{}l@{}}1\\2\end{array}\right\}T_2\_\stackrel{a}{\Rightarrow}2T_1\un{b}\to\to \left\{\begin{array}{@{}l@{}}2\\1\end{array}\right\}T_2b\_\\
1\un{T_1}\to\to 2\_T_2\stackrel{b}{\Rightarrow }2\un{a}T_1\to\to 2\_aT_2\\
2\un{T_1}\to\to 2\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 2\_aT_2\\
\begin{array}{l}2\un{a}a^{{\it n}-2}bT_1\to\to 2\_a^{\it n}T_2\stackrel{a}{\Rightarrow}\\3\un{a}{\it s}_{{\it n}-1}(a,b)T_1\to\to p(1,2,{\it n}+1)b^{{\it n}+1}\un{T_2}\text{ for }{\it n}\ge 4\end{array}\\
3\un{b}\to\to 1\_b\stackrel{a}{\Rightarrow}3\un{a}b\to\to 2\_aa\\
3\un{a}b\to\to 2\_aa\stackrel{a}{\Rightarrow}3\un{a}ab\to\to 1bbb\_\\
\end{array}.\end{equation}
Therefore the LIGR's found are as follows:
\begin{equation}\begin{array}{l}
1\un{T}\stackrel{b}{\leftarrow} 3T\un{b}\\
2\un{T}\stackrel{a}{\leftarrow} 1T\un{b}\\
2\un{T}\stackrel{a}{\leftarrow} 2T\un{b}\\
1\un{T}\stackrel{b}{\leftarrow} 2\un{a}T\\
2\un{T}\stackrel{b}{\leftarrow} 1\un{a}T\\
2\un{a}a^{{\it n}-2}bT\stackrel{a}{\leftarrow}3\un{a}{\it s}_{{\it n}-1}(a,b)T\\
3\un{b}\stackrel{a}{\leftarrow} 3\un{a}b\\
3\un{a}b\stackrel{a}{\leftarrow} 3\un{a}ab
\end{array}.\end{equation}
The result \eqref{tm3_igrs}.6 can, from the computer results for ${\it n}= $ 4 and 5, be shortened by absorbing the $b$ on the extreme left into the arbitrary string $T_1$ because the pointer does not reach that far during the computation. Attempting to prove this generally seems a bit difficult.
The LIGR's found by the computer program when {\it n} is 6 are as follows:
\begin{equation}\begin{array}{@{}l@{}}
1\un{T}\leftarrow 3T\un{b}\\
2\un{T}\leftarrow \mleft\{\begin{array}{@{}l@{}}1T\un{b}\\2T\un{b}\end{array}\mright.\\
1\un{T}\leftarrow 2\un{a}T\\
2\un{T}\leftarrow 1\un{a}T\\
2\un{a}aaT\leftarrow 3\un{a}aabT\\
3\un{T}\leftarrow 3\un{a}T\\\end{array}\end{equation}
However by combining the results of \ref{tm3_irrsf} with the single steps of the TM itself, it is quite easy to come up with the following description of the TM:
\begin{longtable}{l|l|l|l}
\caption{Equivalent description of TM \label{equiv}\ref{6}}\\
A: $ 2\_a^{\it n}$&B: $1b^{\it n}\_$&C: $2b^{\it n}\_$&D: $3a^{\it n}\_$\\
$a\to$ B\dag ($\it n$ even)&$a\to$ C&$a\to$ B&$a\to$ D\\
$a\to$ C\dag ($\it n$ odd)&$b\to$A\dag &$b\to$ A\dag &$b\to$ B*.\\
$b\to$ A&&&\\
\end{longtable}
Here each column corresponds to the CS at its head labelled from A to D. The meaning of the entries in the body of the table is that if the symbol on the left is at the pointer in the CS, the result of the following computation is the CS indicated on the right with $\it n$ replaced by ${\it n} + $1. The symbol \dag indicates that the pointer swaps sides and the result at * is actually $1a^{{\it n}-2}bbb\_$ if ${\it n}>2$ so that the new $\it n$ is now 3. The other cases are dealt with by $3\un{a}b\to 3a\un{b}\to 2\_aa$, $3b\un{b}\to 2\_ab$, and $3\un{a}ab\to 3aa\un{b}\to 1bbb\_$. Notice that when the pointer swaps ends going right, only $b$'s are produced, and if it swaps ends and goes left only $a$'s are produced. Also the TM cannot reach a configuration in D by steps in Table~\ref{6} unless it started from a configuration in D, so its description should start from D. As long as the new symbol is $a$ the TM continues to the right. If a $b$ is reached, it goes to a configuration in B, from where successive $a$'s alternate between CS's B and C. If a $b$ is reached in either B or C then it swaps sides leaving $a$'s and getting to A. Then more $b$'s just leave it in A, but an $a$ makes it swap sides to B or C according to whether $\it n$ is even or odd respectively. Thus the description of TM \eqref{tm2} is clearly explained as an expanding cycle, which to me seems a satisfactory place to leave the general analysis of this example.
In general the question remains that because IRR \eqref{tm3_irrsf}.2 cannot generate any new IRR's with $F$, how does this result relate to others to which it must relate because of neighbouring symbols. For example if $a$ is added on the left and the computation is continued with \ref{nplus1} it gives\newline
$3aab^{{\it n}-2}\un{b}\to 2a\un{a}a^{{\it n}-2}b\to2\un{a}a^{\it n}\to {\it p}(2,1,{\it n})b^{{\it n}+1}\_$ which (ignoring the intermediate step) by lemma~\ref{lemma1} is not an IRR (at least for ${\it n}=\text{3}$). Putting $b^{\it k}$ on the left of \eqref{tm3_irrsf}.2 gives $3b^{\it k}ab^{{\it n}-1}\un{b}\to\to 2b^{{\it k}-1}\un{b}a^{{\it n}+1}\to 2\_a^{{\it n}+{\it k}+1}$ and again putting $a$ on the left gives $3ab^{\it k}ab^{{\it n}-1}\un{b}\to 2\un{a}a^{{\it n}+{\it k}+1}\to {\it p}(2,1,{\it n}+{\it k}+1)b^{{\it n}+{\it k}+2}\_$.
This shows that there can be other methods than $F$ for generating IRR's form others that increase the length of the IRR by 1.
Following up on this idea gives an apparently general method of analysis that seems to generalise \eqref{equiv}.
Let $x$ be an IRR of length ${\it n}$ of type RLL i.e. of type $n\to 1\to 0$ (see the notation of Section~\ref{sec2}).
Then if the computation can be continued thus $n\to 1\to 0\to n+1$ by adding a symbol on the left, then there is a CS $n'$ which is the last to be arrived at out of the CS's (if there are more than one of them) that occur with the pointer at position ${\it n}$ before the CS $0$ is reached. Therefore the computation $n'\to 0\to n+1$ which by Lemma~\ref{lemma1} is also an IRR of type RLR has length ${\it n}+$1, and $n\to n'\to 0\to n+1$ is a valid computation. If instead the computation continues to the left, it gives a result of the form $n\to 1\to 0\to -1$ which is of the form $n\to 0\to -1$. Again a CS $n''$ (the last to be arrived at before arriving at the CS $0$ with the pointer at position $\it n$) exists that may or may not be the same as $n$, and the computation $n''\to 0\to -1$ exists which is an IRR of type RLL and length ${\it n}+$1, and $n\to n''\to 0\to -1$ is a valid computation. The only way of avoiding either of these possibilities is if the computation after the CS $0$ continues indefinitely with the pointer in the range $[\rm 0,\it n]$. Because there are a finite number of CS's involved, the sequence of CS's representing the computation must eventually repeat a CS therefore a stationary cycle occurs after the computation reaches CS $0$.
This result in either of these other cases could be called $G(x)$ where $G$ is a method other than $F$ for generating IRR's from IRR's.
The result of the previous paragraph (and of course its right-left reversed form) can be combined with the results of Section~\ref{sec2} to show how an infinite sequence of IRR's of lengths increasing by one at each step can be derived that is prevented only the presence of stationary cycles or the absence of new origins. They can be chained together because the truncations can be undone.
In this sequence the IRR's that start on the right, symbols are added on the left by $G$ and on the right by $F$ and if they started on the left it would of course be reversed. Therefore the pointer generally goes back and forth with ever increasing sweeps across the string of symbols on the tape (though it may not happen in every case), extending in both directions if both $F$ and $G$ continue to be involved.
These results for IRR's starting on the right can be symbolised as follows:
\begin{equation}
\begin{array}{l}
\exists RLR({\it n})\Rightarrow \forall(\alpha \text{ used by the TM})\{\text{no new origin found using }\alpha \text{ in }F\text{ }\vee \\\hspace{20pt}
\exists RLR({\it n}+1)\vee \exists RLL({\it n}+1)\vee \exists \text{ stationary cycle}\}\\
\exists RLL({\it n})\Rightarrow \exists RLR({\it n}+1)\vee \exists RLL({\it n}+1)\vee \exists\text{ a stationary cycle}\end{array}
\end{equation}
An equivalent (mirror image) idea relating IRR's of types LRL, LRR exists which should generate the same thing from the other end ie. IRR's starting at the left. These are both approaching the description of the TM behaviour as a sequence of expanding cycles from opposite ends but represent the same reality. Involved in general (as shown by the analysis of TM \ref{tm2}) are both stationary cycles where the TM effectively stops, and sequences of symbols which the reversed TM cannot cross which can prevent a new origin being found.
It seems to me that this will generate the interpretive cycle of a TM that has been shown to have this behaviour.
\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}