\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}}
%\date{2017-02-21} 
\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{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{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: 2022-08-13
\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

\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 here described in the analysis technique for non-terminating Turing Machines that I described earlier. The main idea is 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. The results of the computer program 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 in independently of the right hand halves, this should be done separately. The LIGR's have been shown define the generation all the IRR's of extendable type (LR or RL).
\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}

some results are from the old (5,5) TM. check this.
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 4 has been much improved and the IGR's for the IRR(3) and IRR(4) have been worked out in the new improved notation.

Theorem 4.1 has been added and this will remove some unnecessary duplication. The worked examples in section 6 need to be looked at again as do the lists of results in section 7.

A lot of the old material is now after the references so it can be viewed with links that still work but will probably not be in the paper.

This version of the paper has a new version of the program linked to it \cite{tie_v3_0}, (the old version is \cite{tie}).

 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
\begin{comment}
\section{Outline of a possible algorithm for TM analysis}
Looking at the many examples of IGR's here including those in the next section suggests the best practical method to analyse the TM is to repeatedly apply $F$ to results that generate the IRR(3). 

A typical instance involves applying $F$ to IRRP X as follows:

\begin{alg}\label{algorithm9.1}[Algorithm for applying $F$ to an IRRP $X$] Repeat while $X$ has not already had $F$ applied to it \{Truncate $X$ by 1 symbol putting the context pair at the end of a sequence or list that starts empty\}. Apply $F$ to $X$ truncated to length 1 as in the examples above or to the last but one result of this loop by applying the last context pair in the list to each member of $X$ that is not extendable as its LHS as described in Table~\ref{Table3} and Section~\ref{section7}. Repeat this recursively, unless already done, for any member of $X$ that is not extendable using the next context pair. Repeat till all the context has been applied. If the result of applying $F$ is no new results, this terminates this branch of the calculation. The procedure branches whenever there is more than one $X$ that is of non-extendable type (case 4). The must be a separate pointer to the list of contexts for each branch.

The intermediate results of this procedure may not be needed in the final analysis. They should be marked as such so that $F$ will not be applied to them at the next stage to generate IGR's for determining the $IRR({\it n})$. 
\end{alg}
\begin{Theorem}Algorithm~\ref{algorithm9.1} applied to an IRRP $X$ generates all the IGRs that define all the results of the application of $F$ to $X$ as described in Section~\ref{section4}.
\end{Theorem}
\begin{proof}
(Sketch) This is obvious because truncating $X$ truncates both the forward computation and backward search to that length and these calculations must be included in the full calculation for the original $X$. Therefore adding back the effect of the symbols truncated off systematically so that no options are forgotten must give the same result. This holds separately for each individual backward search path and forward computation possible.
\end{proof}
Note that in this algorithm it is the non-extendable IRRP's on the RHS that can have extra contexts applied to generate new IGR members. If the IRRP's of the right are extendable they can have $F$ applied using a new $\alpha$ to generate new IGR members.

Repeat this starting with each IRRP generated from the TM until $F$ has been applied to every IRRP generated. All the IGR's so obtained must be recorded including those that lead to no new IRRP's.

This may terminate because the final result is the IGR used to extend $X$ which can often be expected to be much shorter than $X$. See the example in Section~\ref{section4}. I will shortly try to construct a computer program to do this and check against the results obtained so far.

A result of the analysis for a TM will be that each IRRP has associated with it a set of pairs of context strings that generate the IRR's it corresponds to. 
\end{comment}
Another example and its proposed analysis
\begin{equation}\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}


\section{\label{sec2}Summary of the existing method to generate the IRR's}
From the definition of regular rules (RR) and irreducible regular rules (IRR) in \cite{jhn2013},
any computation of the TM can be represented by RR's (which are certain pairs of CS's linked by $\to$) chained together as a sequence of CS's starting with 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 at each step unless a stationary cycle occurs. If the RR is of type LR or RL the pointer swaps ends at that step of the chain and these RR's are also IRR's because if the pointer swaps ends there are no redundant symbols.
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$. 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.  
Any CS will be said to be reachable i.e. is an LHS of an IRR, if and only if it is the RHS of and IRR of type LR or RL with an additional symbol added at the pointer position, and this gives a recursive definition of the IRR's.

IRR's have been presented in 3 different ways and there should be no confusion:\newline
(1) The original presentation with 2 CS's: $LHS\to RHS$\newline
(2) IRR triplet with 3 CS's: $origin\to LHS\to RHS$\newline
(3) Abbreviated or IRR pair with 2 CS's: $origin\to\to RHS$\newline

If an RR is of type RR or LL it is related to an irreducible form (a 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) so it has type RR, then 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}. ${\it n}={\it p}$ holds if and only if $n'=p'$ and $n'\to o'$ is a single TM step, and the rule $n'\to p'$ shows that $p'$ is reachable therefore $n'\to p'\to o'$ represents an IRR of type LR, and of course the mirror image result applies to IRR's of type LL.

In general let $X$ be a member of IRR({\em 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$) 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) i.e. the pointer swaps ends between $A$ and $B$. (Likewise if it terminates in condition 2 i.e. doesn't swap ends, 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 LL and LR 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 RR and RL respectively.

If $B$ is reachable but forward computaton from it leads to a CS that has arisen before in this computation, this is an stationary cycle and the type of the IRR is then LC or RC and so $F$ applied to this is the empty set. 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, however much further back the backward search were to continue, it would not be possible 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.

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 RL, RR, LR or LL respectively{\em )} if and only if the origin indicated {\em (}the first member{\em )} is the first one arrived at after tracing the computation back from the LHS {\em (}the middle member{\em )} and the the pointer in the LHS does not occur again in that position in the reverse computation path from the LHS i.e there is no other CS $1$ or $n$ between the $1$ and the $n$. Furthermore any IRR of length {\em n} of one of the above types has one of these forms.\end{Lemma} 

Generating all the IRR 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 computaton 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. connot 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 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$). 

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 {\em n} 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$. Consider first the computation $A\alpha\to B\alpha\to C\alpha$ 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 and the origins $O_1(B\alpha)\ne\emptyset$ for it need to be found. 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 (RR, RL, LR, LL, RC, or LC) 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$. 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 LR or RL. Also, because an 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}+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 LR with origin having the pointer at the right) as above 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
\left.\mkern-30mu\begin{array}{ccc}\left.\begin{array}{c}\text{Cannot be used to}\\\text{ prove reachability  of } 1\end{array}\right\}&1&\to\\\text{Proves reachability of }1&n+1&\to\end{array}\right\}n\to 1\to n+1\left\{\begin{array}{ccc}\to &0&\text{type LL}\\\to &n+2&\text{type LR}\end{array}\right.
\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$ is found. The corresponding mirror image result for the LRL case is as follows:
\begin{equation}\label{irr_deriv2}\arraycolsep=4pt
\left.\mkern-30mu\begin{array}{ccc}\text{Proves reachability of }n+1&1&\to\\\left.\begin{array}{c}\text{Cannot be used to}\\\text{ prove reachability of }n+1\end{array}\right\}&n+1&\to\end{array}\right\}2\to n+1\to 1\left\{\begin{array}{ccc}\to &0&\text{type RL}\\\to &n+2&\text{type RR}\end{array}\right.
\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}. 

While deriving an IRR triplet of the form $n+1\to 1\to n+2$ in the notation of \eqref{irr_deriv1} from one of the form $n\to 1\to n+1$  the pointer moves in the backward search in general thus: $n\leftarrow n-k\leftarrow n+1$ (i.e. equivalent to $k+1\leftarrow 1\leftarrow k+2$ or where $k+2$ is the first CS of the form arrived at.) where the CS $n+1$ is the first arrival at such a CS in the backward search because the $n+1$ would terminate the backward search algorithm. It could not reach point $1$ because that would also terminate the backward search algorithm. Therefore ${\rm 0}\le {\it k}\le {\it n}-{\rm 2}$. It is interesting to note that the backward search in general takes the form of an IRR triplet of length ${\it k}+{\rm 1}$ run in reverse by lemma~\ref{lemma1} where $1\le {\it k}+1\le {\it n}-\rm 1$ but crucially only if the direction of computation could be is reversed so this might have no significance. 

In the remainder of this paper, this procedure will be adapted to the incomplete description of IRR's i.e. IRR patterns with $\ldots$ needed to make the analysis manageable for the example TM, that is expected to have an infinite number of IRR's.

This document describes my analysis techniques applied to the following Turing Machine

\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}

(TM) 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 and will help me refine the procedures for efficiently generating the irreducible regular rules (IRR) from a TM that allowed understandable descriptions of the behaviour of smaller TM's to be found.



\section{\label{sec3}Using IRR patterns}
IRR patterns (IRRP's) have been found to be very useful because they result in shortening of the lists of cases to be considered because sets of IRR's that match an IRRP often have similar derivations and can be dealt with together. For example in \eqref{irr_deriv1} (and similarly for \eqref{irr_deriv2}) that contains two derivations one of each of the forms $n+1\to n$ and $n+1\to n+2$, often involve one or a small number of TM steps and are indepedent of {\em n}. Also the treatment of IRR's in TM1 in \cite{jhn2017} where sets conforming to the IRRP's could be treated in the same way, allowed a proof of a general method for obtaining all the $IRR({\it n}+1)$ from the $IRR({\it n})$ for all sufficiently large {\em n} for this TM.

An IRRP is represented like an IRR but with $\ldots$ or $T_1$ and $T_2$ representing the arbitrary strings, because there are two of them in each IRRP that can be different but have the same length. The IRRP is the set of all results that would be obtained (they will be IRR's) by keeping the fixed values of the given symbols and making arbitrary substitutions for the arbitrary strings that can be any strings of symbols of arbitrary length including zero. 

An IRRP may be regarded as an abbreviation of an IRR (1) to a fixed length {\em k} of the given strings of symbols, where the symbol at the pointer in the origin is at one end and (2) the original LHS (the middle element in the triplet form of an IRR) is removed completely. The abbreviation is indicated by $\ldots$ or $T_1$ and $T_2$ in place of the deleted symbols in the origin and the RHS. This presentation has the property that the pointer position appears separately in the RHS column if and only if the IRR is of extendable type i.e. type RL or LR, otherwise it appears as an underscore under the $T_2$ indicating that the pointer should be under the first symbol of $T_2$ i.e. adjacent to one of the given symbols.

Table~\ref{ind1} is presented in doubled two-column format just for convenience, and has logically just two columns, Origin and RHS's. It was obtained by abbreviating all the IRR(3) to length ${\it k}={\rm 2}$. For this purpose, IRR's with many origins have a separate entry for each origin. This allows the origins to be unique for each row in the table but multiple RHS's from different IRRP's often combined into the same row of Table~\ref{ind1}.

An effect of the information loss resulting from representing the IRR's by IRRP's i.e. the truncation of the string of symbols from length {\em n} to length {\em k} that is independent of {\em n}, is that it completely alters the simple description of how to analyse a Turing Machine provided by Theorem~\ref{irr_ind_thm}. This may be thought of as the trade-off for the advantages described above. How this is dealt with is complicated and not easy to describe and is a major theme of this paper.

\begin{longtable}{ll|ll}
\caption{List of patterns for the IRR(3)\label{ind1}}\\
Origin&RHS's&Origin&RHS's\\\hline
$1\un{d}d\ldots$&$4\_cb\ldots$&$5\un{e}e\ldots$&$\{3\_bc\ldots,3ca\ldots\}$\\
$1\un{e}d\ldots$&$4\_cb\ldots$&$3\un{e}e\ldots$&$\{4bc\ldots,4\_ce\ldots\}$\\
$1\un{d}d\ldots$&$4\_ca\ldots$&$4\un{e}c\ldots$&$\{3cb\ldots,1cb\ldots\}$\\
$1\un{e}d\ldots$&$4\_ca\ldots$&$4\un{e}e\ldots$&$\{3cb\ldots,1cb\ldots\}$\\
$1\un{d}a\ldots$&$4\_ca\ldots$&$4\un{c}e\ldots$&$\{1ab\ldots,2\_ae\ldots\}$\\
$1\un{e}a\ldots$&$4\_ca\ldots$&$3\ldots b\un{c}$&$\{4\ldots cc\_,1\ldots bc\_,4\ldots ac\_\}$\\
$1\un{d}c\ldots$&$3\_ec\ldots$&$1\ldots b\un{c}$&$\{4\ldots cc\_,1\ldots bc\_,4\ldots ac\_\}$\\
$1\un{e}c\ldots$&$3\_ec\ldots$&$4\ldots b\un{a}$&$\{2\ldots ab\_,3\ldots bc\_\}$\\
$1\ldots c\un{c}$&$1\ldots bc\_$&$2\ldots b\un{e}$&$\{2\ldots ab\_,1\ldots bd\_,2\ldots db\_\}$\\
$4\ldots c\un{a}$&$3\ldots bc\_$&$1\ldots b\un{a}$&$\{2\ldots db\_,1\ldots ba\_,1\ldots bd\_\}$\\
$2\ldots c\un{e}$&$1\ldots bd\_$&$5\ldots b\un{a}$&$\{3\ldots cb\_,3\ldots cc,3\ldots ab\_\}$\\
$5\ldots c\un{b}$&$\{5\ldots cc,3\ldots cc,1\ldots bd\_\}$&$5\ldots b\un{b}$&$\{3\ldots cb\_,3\ldots cc,3\ldots ab\_\}$\\
$3\ldots a\un{d}$&$1\ldots bd\_$&$4\un{b}b\ldots$&$\{2ba\ldots,4\_ce\ldots\}$\\
$4\ldots a\un{d}$&$1\ldots bd\_$&$3\un{a}b\ldots$&$\{3ab\ldots,2\_ae\ldots\}$\\
$2\un{d}d\ldots$&$3\_bc\ldots$&$5\un{c}a\ldots$&$3db\ldots$\\
$2\un{d}e\ldots$&$3\_bc\ldots$&$5\un{e}a\ldots$&$3db\ldots$\\
$2\un{a}d\ldots$&$1ab\ldots$&$3\un{e}a\ldots$&$4\_ca\ldots $\\
$2\un{a}e\ldots$&$1ab\ldots$&$4\un{c}a\ldots$&$3ab\ldots$\\
$2\un{c}d\ldots$&$5\_cc\ldots$&$1\ldots d\un{c}$&$1\ldots bc\_$\\
$2\un{c}e\ldots$&$5\_cc\ldots$&$4\ldots d\un{a}$&$3\ldots bc\_$\\
$5\ldots a\un{d}$&$\{3\ldots bc\_,4\ldots cc\_\}$&$2\ldots d\un{e}$&$1\ldots bd\_$\\
$2\ldots a\un{b}$&$\{3\ldots bc\_,2\ldots ab\_\}$&$5\ldots d\un{b}$&$5\ldots cc$\\
$3\ldots a\un{b}$&$\{3\ldots bc\_,2\ldots ab\_\}$&$5\ldots d\un{d}$&$1\ldots bc\_$\\
$1\ldots a\un{b}$&$\{2\ldots ec,2\ldots db\_\}$&$2\ldots d\un{b}$&$1\ldots bd\_$\\
$3\ldots e\un{c}$&$4\ldots cc\_$&$3\ldots d\un{b}$&$1\ldots bd\_$\\
$1\ldots e\un{a}$&$2\ldots db\_$&$1\ldots d\un{b}$&$1\ldots ba\_$\\
$5\ldots e\un{a}$&$3\ldots cb\_$&$4\un{b}e\ldots$&$4\_cb\ldots$\\
$3\ldots b\un{d}$&$\{3\ldots aa\_,4\ldots cc\_\}$&$3\un{a}e\ldots$&$2\_ab\ldots$\\
$4\ldots b\un{d}$&$\{3\ldots aa\_,4\ldots cc\_\}$&$3\ldots d\un{d}$&$\{3\ldots cc\_,1\ldots bd\_\}$\\
$5\un{c}e\ldots$&$\{3\_bc\ldots,3ca\ldots\}$&$4\ldots d\un{d}$&$\{3\ldots cc\_,1\ldots bd\_\}$\\
\end{longtable}


Treating Table~\ref{ind1} at first as a hypothesis to be proved by induction for IRR of length ${\it n}\ge 3$  suggests (1) following the method in Section~\ref{sec2} to each of the patterns provided they are extendable i.e. of type LR or RL, and then (2) truncating the result to two symbols from the pointer at the new origin so generating another result of the same form as those already in Table~\ref{ind1}. This must be repeated as necessary to ensure closure, i.e. every member of IRRP$({\it n}+{\rm 1})$ truncated to length ${\it k}={\rm 2}$ must also appear as a member of IRRP(${\it n}$) also truncated to length ${\it k}={\rm 2}$. This results in Table~\ref{irr_2r}. Thus an infinite number of IRR could be captured by the resulting recursive description. In these tables the lazy abbreviation is used where $\ldots$ represents any string of symbols of length $\ge 1$ that could be different whenever is used, but really it should be done with say $T_1$ and $T_2$ to represent the two arbitrary strings ($S_1$ and $S_2$ are used later so this notation avoids ambiguity).

Thus every application of $F$ as described in Section~\ref{sec2} maps an IRRP in Table~\ref{irr_2r} that has ${\it k}={\rm 2}$ to another IRRP in Table~\ref{irr_2r} unless the backward search procedure to find new origins goes in the unexpected direction i.e. away from the symbol $\alpha$. The analysis for these cases will be taken as far as possible giving results with ${\it k}={\rm 3}$. This issue is taken up again in Section~\ref{sec4}. 

For example starting from the fifth result in Table~\ref{ind1}
\begin{equation}\label{addalpha1}1\un{d}aT_1\to\to4\_caT_2\end{equation} using the backward TM steps from $1\alpha\_$ in \eqref{rev1}, this gives
\begin{equation}\label{addalpha2}\begin{tabular}{lccc}deriving the origin&&RHS&$\alpha$\\
$\alpha A$&$\alpha C$&&\\
$1\alpha\un{d}aT_1\left\{\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}\right.$&
$\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$ and needs to be continued until the pointer reaches either end of the string, so it needs to be recorded that this result is incomplete for ${\it k}={\rm 2}$ and the results are truncated to
\begin{equation}\label{addalpha3}\begin{array}{l}2\un{d}dT'_1\to\to 3\_bcT'_2\\
2\un{a}dT'_1\to\to1ab\un{T'_2}\\
2\un{c}dT'_1\to\to 5\_ccT'_2\end{array}\end{equation} for $\alpha= a,c,d$ respectively, where $T'_1=aT_1$ and $T'_2=aT_2$ for $\alpha\in\{a,d\}$ are the new arbitrary strings. This appears against the IRRP \eqref{addalpha1} in set number 1 of \eqref{irr_2r} using the less precise $\ldots$ notation. 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 (not shown due to truncation), so this IRR has type RR and cannot be used to derive other IRR. These are examples of rules that generate IRR's of length ${\it n}+{\rm 1}$ from other IRR's of length ${\it n}$ and are expressed (for the case where the unknown symbols are on the right) in Table~\ref{irr_2r}  for ${\it k}={\rm 2}$. Collectively such rules will be referred to as IRR-generating rules (IGR) to distinguish them from computation rules. 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.




\fontsize{10}{10}\selectfont
\begin{longtable}{c|l@{\hspace{0.5em}}l|c|l@{\hspace{0.5em}}l}
\caption{IRRP's of length {\it n} and their derived IRRP's of length ${\it n}+{\rm 1}$, with the unknown symbols on the right.\label{irr_2r}}\\
set&\multicolumn{2}{c|}{IRRP(${\it n}$)}&$\alpha$&\multicolumn{2}{c}{IRRP(${\it n}+1$)}\\
number&Origin&RHS&&Origin&RHS\\
\hline
$1$&$1\un{d}a\ldots$&$4\_ca\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}d\ldots$&$1ab\ldots$\\
&&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline  
$2$&$1\un{d}c\ldots$&$3\_ec\ldots$&$a$&$2\un{d}d\ldots$&$3ca\ldots$\\
&&&$c$&$2\un{a}d\ldots$&$2\_ae\ldots$\\
&&&$d$&$2\un{c}d\ldots$&$5\_ce\ldots$\\\hline
$3$&$1\un{d}d\ldots$&$4\_ca\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}d\ldots$&$1ab\ldots$\\
&&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline
$4$&$1\un{d}d\ldots$&$4\_cb\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}d\ldots$&$3ab\ldots$\\
&&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline
$5$&$1\un{e}a\ldots$&$4\_ca\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}e\ldots$&$1ab\ldots$\\
&&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline
$6$&$1\un{e}c\ldots$&$3\_ec\ldots$&$a$&$2\un{d}e\ldots$&$3ca\ldots$\\
&&&$c$&$2\un{a}e\ldots$&$2\_ae\ldots$\\
&&&$d$&$2\un{c}e\ldots$&$5\_ce\ldots$\\\hline
$7$&$1\un{e}d\ldots$&$4\_ca\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}e\ldots$&$1ab\ldots$\\
&&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline
$8$&$1\un{e}d\ldots$&$4\_cb\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\
&&&$c$&$2\un{a}e\ldots$&$3ab\ldots$\\
&&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline
$9$&$2\un{a}d\ldots$&$2\_ae\ldots$&$b$&$1\un{d}a\ldots$&$4\_ca\ldots$\\
&&&$b$&$1\un{e}a\ldots$&$4\_ca\ldots$\\
&&&$\alpha$&$1\alpha a\un{a}\ldots$&$RHS$\\ \hline
$10$&$2\un{a}d\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$11$&$2\un{a}d\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$12$&$2\un{a}e\ldots$&$2\_ae\ldots$&$b$&$1\un{d}a\ldots$&$4\_ca\ldots$\\
&&&$b$&$1\un{e}a\ldots$&$4\_ca\ldots$\\
&&&$\alpha$&$5\alpha a \un{a}\ldots$&$RHS$\\\hline
$13$&$2\un{a}e\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$14$&$2\un{a}e\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$15$&$2\un{c}d\ldots$&$5\_cc\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\
&&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\
&&&$\alpha$&$1\alpha c\un{a}\ldots$&$RHS$\\\hline
$16$&$2\un{c}d\ldots$&$5\_ce\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\
&&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\
&&&$\alpha$&$1\alpha c\un{a}\ldots$&$RHS$\\\hline
$17$&$2\un{c}e\ldots$&$5\_cc\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\
&&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\
&&&$\alpha$&$5\alpha c\un{a}\ldots$&$RHS$\\\hline
$18$&$2\un{c}e\ldots$&$5\_ce\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\
&&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\
&&&$\alpha$&$5\alpha c\un{a}\ldots$&$RHS$\\\hline
$19$&$2\un{d}d\ldots$&$3\_bc\ldots$&$b$&$1\un{d}d\ldots$&$4\_cb\ldots$\\
&&&$b$&$1\un{e}d\ldots$&$4\_cb\ldots$\\
&&&$\alpha$&$1\alpha d\un{a}\ldots$&$RHS$\\\hline
$20$&$2\un{d}d\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline
$21$&$2\un{d}e\ldots$&$3\_bc\ldots$&$b$&$1\un{d}d\ldots$&$4\_cb\ldots$\\
&&&$b$&$1\un{e}d\ldots$&$4\_cb\ldots$\\
&&&$\alpha$&$5\alpha d\un{a}\ldots$&$RHS$\\\hline
$22$&$2\un{d}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline
$23$&$3\un{a}b\ldots$&$2\_ae\ldots$&$a$&$5\un{c}a\ldots$&$5\_cc\ldots$\\
&&&$a$&$5\un{e}a\ldots$&$5\_cc\ldots$\\
&&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\
&&&$c$&$4\un{c}a\ldots$&$3\_bc\ldots$\\
&&&$\alpha$&$4\alpha a\un{a}\ldots$&$RHS$\\\hline
$24$&$3\un{a}b\ldots$&$3\_bc\ldots$&$a$&$5\un{c}a\ldots$&$3cb\ldots$\\
&&&$a$&$5\un{e}a\ldots$&$3cb\ldots$\\
&&&$b$&$3\un{e}a\ldots$&$4\_cb\ldots$\\
&&&$c$&$4\un{c}a\ldots$&$2\_ab\ldots$\\
&&&$\alpha$&$4\alpha a\un{a}\ldots$&$RHS$\\\hline
$25$&$3\un{a}b\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$26$&$3\un{a}b\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$27$&$3\un{a}c\ldots$&$2\_ab\ldots$&$a$&$5\un{c}a\ldots$&$3db\ldots$\\
&&&$a$&$5\un{e}a\ldots$&$3db\ldots$\\
&&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\
&&&$c$&$4\un{c}a\ldots$&$3ab\ldots$\\
&&&$\alpha$&$2\alpha a\un{e}\ldots$&$RHS$\\\hline
$28$&$3\un{a}c\ldots$&$3\_bc\ldots$&$a$&$5\un{c}a\ldots$&$3cb\ldots$\\
&&&$a$&$5\un{e}a\ldots$&$3cb\ldots$\\
&&&$b$&$3\un{e}a\ldots$&$4\_cb\ldots$\\
&&&$c$&$4\un{c}a\ldots$&$2\_ab\ldots$\\
&&&$\alpha$&$2\alpha a\un{e}\ldots$&$RHS$\\\hline
$29$&$3\un{a}c\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$30$&$3\un{a}e\ldots$&$2\_ab\ldots$&$a$&$5\un{c}a\ldots$&$3db\ldots$\\
&&&$a$&$5\un{e}a\ldots$&$3db\ldots$\\
&&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\
&&&$c$&$4\un{c}a\ldots$&$3ab\ldots$\\
&&&$\alpha$&$5\alpha a\un{b}\ldots$&$RHS$\\\hline
$31$&$3\un{a}e\ldots$&$1db\ldots$&$\emptyset$&$\emptyset$\\
\hline
$32$&$3\un{e}a\ldots$&$4\_ca\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\
&&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\
&&&$b$&$3\un{e}e\ldots$&$4bc\ldots$\\
&&&$c$&$4\un{c}e\ldots$&$1ab\ldots$\\
&&&$\alpha$&$1\alpha e\un{c}\ldots$&$RHS$\\\hline
$33$&$3\un{e}a\ldots$&$4\_cb\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\
&&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\
&&&$b$&$3\un{e}e\ldots$&$2ba\ldots$\\
&&&$c$&$4\un{c}e\ldots$&$3ab\ldots$\\
&&&$\alpha$&$1\alpha e\un{c}\ldots$&$RHS$\\\hline
$34$&$3\un{e}e\ldots$&$4\_ce\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\
&&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\
&&&$b$&$3\un{e}e\ldots$&$3bc\ldots$\\
&&&$c$&$4\un{c}e\ldots$&$3\_bc\ldots$\\
&&&$\alpha$&$5\alpha e\un{b}\ldots$&$RHS$\\\hline
$35$&$3\un{e}e\ldots$&$2ba\ldots$&$\emptyset$&$\emptyset$\\\hline
$36$&$3\un{e}e\ldots$&$3bc\ldots$&$\emptyset$&$\emptyset$\\\hline
$37$&$3\un{e}e\ldots$&$4bc\ldots$&$\emptyset$&$\emptyset$\\\hline
$38$&$4\un{b}b\ldots$&$4\_ce\ldots$&$b$&$4\un{b}b\ldots$&$3bc\ldots$\\
&&&$c$&$3\un{a}b\ldots$&$3\_bc\ldots$\\\hline
$39$&$4\un{b}b\ldots$&$2ba\ldots$&$\emptyset$&$\emptyset$\\\hline
$40$&$4\un{b}b\ldots$&$3bc\ldots$&$\emptyset$&$\emptyset$\\\hline
$41$&$4\un{b}b\ldots$&$4bc\ldots$&$\emptyset$&$\emptyset$\\\hline
$42$&$4\un{b}c\ldots$&$4\_ca\ldots$&$b$&$4\un{b}b\ldots$&$4bc\ldots$\\
&&&$c$&$3\un{a}b\ldots$&$1ab\ldots$\\
&&&$\alpha$&$2\alpha b\un{b}\ldots$&$RHS$\\
&&&$\alpha$&$3\alpha b\un{b}\ldots$&$RHS$\\\hline
$43$&$4\un{b}c\ldots$&$4\_cb\ldots$&$b$&$4\un{b}b\ldots$&$2ba\ldots$\\
&&&$c$&$3\un{a}b\ldots$&$3ab\ldots$\\
&&&$\alpha$&$2\alpha b\un{b}\ldots$&$RHS$\\
&&&$\alpha$&$3\alpha b\un{b}\ldots$&$RHS$\\\hline
$44$&$4\un{b}e\ldots$&$4\_cb\ldots$&$b$&$4\un{b}b\ldots$&$2ba\ldots$\\
&&&$c$&$3\un{a}b\ldots$&$3ab\ldots$\\\hline
$45$&$4\un{b}e\ldots$&$4\_ce\ldots$&$b$&$4\un{b}b\ldots$&$3bc\ldots$\\
&&&$c$&$3\un{a}b\ldots$&$3\_bc\ldots$\\\hline
$46$&$4\un{c}a\ldots$&$2\_ab\ldots$&$b$&$4\un{b}c\ldots$&$4\_ca\ldots$\\
&&&$c$&$3\un{a}c\ldots$&$3ab\ldots$\\
&&&$\alpha$&$5\alpha c\un{d}\ldots$&$RHS$\\\hline
$47$&$4\un{c}a\ldots$&$3\_bc\ldots$&$b$&$4\un{b}c\ldots$&$4\_cb\ldots$\\
&&&$c$&$3\un{a}c\ldots$&$2\_ab\ldots$\\
&&&$\alpha$&$5\alpha c\un{d}\ldots$&$RHS$\\\hline
$48$&$4\un{c}a\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$49$&$4\un{c}e\ldots$&$2\_ae\ldots$&$b$&$4\un{b}c\ldots$&$4\_ca\ldots$\\
&&&$c$&$3\un{a}c\ldots$&$3\_bc\ldots$\\\hline
$50$&$4\un{c}e\ldots$&$3\_bc\ldots$&$b$&$4\un{b}c\ldots$&$4\_cb\ldots$\\
&&&$c$&$3\un{a}c\ldots$&$2\_ab\ldots$\\\hline
$51$&$4\un{c}e\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$52$&$4\un{c}e\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline
$53$&$4\un{e}c\ldots$&$2\_ec\ldots$&$b$&$4\un{b}e\ldots$&$4\_ce\ldots$\\
&&&$c$&$3\un{a}e\ldots$&$1db\ldots$\\
&&&$\alpha$&$2\alpha e\un{b}\ldots$&$RHS$\\
&&&$\alpha$&$3\alpha e\un{b}\ldots$&$RHS$\\\hline
$54$&$4\un{e}c\ldots$&$1cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$55$&$4\un{e}c\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$56$&$4\un{e}e\ldots$&$2\_ec\ldots$&$b$&$4\un{b}e\ldots$&$4\_ce\ldots$\\
&&&$c$&$3\un{a}e\ldots$&$1db\ldots$\\\hline
$57$&$4\un{e}e\ldots$&$1cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$58$&$4\un{e}e\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$59$&$5\un{c}a\ldots$&$5\_cc\ldots$&$a$&$4\un{e}c\ldots$&$2\_ec\ldots$\\\hline
$60$&$5\un{c}a\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$61$&$5\un{c}a\ldots$&$3db\ldots$&$\emptyset$&$\emptyset$\\\hline
$62$&$5\un{c}e\ldots$&$3\_bc\ldots$&$a$&$4\un{e}c\ldots$&$3cb\ldots$\\\hline
$63$&$5\un{c}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline
$64$&$5\un{e}a\ldots$&$5\_cc\ldots$&$a$&$4\un{e}e\ldots$&$2\_ec\ldots$\\\hline
$65$&$5\un{e}a\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline
$66$&$5\un{e}a\ldots$&$3db\ldots$&$\emptyset$&$\emptyset$\\\hline
$67$&$5\un{e}e\ldots$&$3\_bc\ldots$&$a$&$4\un{e}e\ldots$&$3cb\ldots$\\\hline
$68$&$5\un{e}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline
\end{longtable}
\fontsize{12}{14}\selectfont
\section{\label{section4}Reformulating the generation of new IRR's from existing ones in terms of IRR generating rules}
In order to understand how IRR's can be generated from others, the following IRR of length 6 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}\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, it generates IRR's as follows 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}\left.\begin{array}{l}1\un{d}T_{\rm 1}\\1\un{e}T_{\rm 1}\end{array}\right\}\to\to 3\_eT_{\rm 2}\\[15pt]
1\un{T}_1\to\to 3\_T_{\rm 2}\left\{\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}\right.\\[23pt]
2\un{c}dT_{\rm 1}\to\to 5\_T_{\rm 2}\stackrel{a}{\Rightarrow}\left.\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}\right\}\to\to2\_eT_{\rm 2}\\[30pt]
4\un{T}_{\rm 1}\to\to2\_eT_{\rm 2}\stackrel{c}{\Rightarrow} \left.\begin{array}{l}3\un{a}T_{\rm 1}\\4\un{b}T_{\rm 1}\end{array}\right\}\to\to2db\un{T}_{\rm 2}\end{array}.\end{equation}

For the derivation of \eqref{eq130}, the following subcases 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 (IRR generating rules) 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 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 donoted 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 RR 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 RR) 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$ 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.

\section{Definition of IGR's}
The general form of the derivation of an IRR from an existing one ($F$) can be expressed in more detail as follows. Start with the IRR pattern (IRRP) of type RL\begin{equation}\label{igr0}t_{\rm 1}\un{y_{\rm 1}}\ldots y_{{\it n}}\to\to t_{\rm 2}\_z_{\rm 1}\ldots z_{{\it n}}\end{equation} where ${\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 \left\{\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}\right.\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.

The point of the classification is to distinguish all the different types of cases 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} - 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 \left\{\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}\right..\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. Likewise for 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}=\left\{\begin{array}{ll}{\rm 1}&\text{ for } {\it j}_{\rm 1}={\rm 0}\\
{\it j}_{\rm 1}+{\rm 2}&\text{ otherwise}\end{array}\right.\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 remaining four combinations can be summarised as
\begin{equation}\label{igr_types}\begin{array}{l}
\left\{\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}\right\}\to\to \left\{\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}\right\}
\stackrel{\alpha}{\Rightarrow}\vspace{0.5em}\\
\left\{\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}\right\}\to\to 
\left\{\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}\right\}\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. Each of these is a type of IGR that can be obtained and are distinguished by different pairs $({\it j}_{\rm 1},{\it j}_{\rm 2})$.

The corresponding right-left reversed results starting from an IRRP set 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 \left\{\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}\right.\end{equation} 
Naturally, \eqref{r1} and \eqref{r2} and are still valid and \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 are the results expressed with the shortest strings of symbols possible (i.e. the $y$'s and $z$'s), with 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. The length of an IGR consists of the pair $({\it r}_{\rm 1},{\it r}_{\rm 2})$. These together with their left-right reversed forms are all the different types of IGR's. 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, using \eqref{rev1} 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}, except that a final reverse step that would lead to the pointer ending at the opposite end of the string from $\alpha$ is not done because that does not represent an IRR (c.f. \eqref{igr1}.3).

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 rew RHS, the pointer can obviously never move 
outside the strings of lengths ${\it r_{\rm 1}}$ and ${\it r_{\rm 2}}$ introduced above, and moreover 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 except that for 
the last machine step obtaining the new RHS that can take the pointer just outside it, the pointer ends up at one 
end of the string $T_{\rm 2}$ and is indicated by $\un{T_{\rm 2}}$ with the pointer position clear from the context. 
Therefore the number of symbols retained for each new origin found and RHS must be ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ as defined in Equations~\eqref{r1} and \eqref{r2}.

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. Note that in \eqref{igr_types} these results are still valid whatever the strings $T_{\rm 1}$ and $T_{\rm 2}$ and their lengths are.
 
A IGR could be defined to include all the possible results that can be derived for any possible value of $\alpha$ (an IGR member), and 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 IGR's 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. 

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 set 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 which 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 the IGR is 1 if the
original IRRP set (the LHS of the new IGR) was of type LRL because the pointer starts at 1 and is not affected by the  truncation of the symbols from the right. If the the original IRRP set was of type RLR, the pointer position
in its origin is initially at ${\it n}$ (i.e. the right hand end)
and is reduced as a result of applying 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} + 2}$ otherwise, which is ${\it j}_{\rm 1} + {\rm 1}$. This value can never be 1, so the value 1 is characteristic of the original IGR being of type LRL. This implies that the value $p = 1$ in an origin CS on the LHS of an IGR indicates, provided ${\it n}>1$, that the context strings ($T_1$ and $T_2$) are added on the right, and on the left otherwise. For the case ${\it n}=1$ this is obvious from the RHS of the IRRP\_set on the LHS of the 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 RL by an IGR with parameters ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ of type \eqref{igr_types}.1 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 RR can be derived by $F$ from another IRR of length ${\it n}$ of
   type RL by an IGR of type \eqref{igr_types}.2 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}any extendable IRR (type RL or LR) 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 LL or RR) 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.
\newline
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).
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.

Describe new program and how the IGR's were obtained starting with the ones with contexts present.
\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}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1\to\to 3\_bT_2$\\
3&$1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{a}baa\\1\un{a}bab\end{array}\right\}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}\left.\begin{array}{l}2\un{a}ccac\\2\un{a}ccbc\end{array}\right\}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}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3\_bababaT_2$\\
13&$1\un{c}aaT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}2\un{b}baa\\2\un{b}bab\end{array}\right\}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}\left.\begin{array}{l}3\un{c}ccac\\3\un{c}ccbc\end{array}\right\}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}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}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}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1\to\to 1\_aT_2$\\
24&$1\un{c}aaT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{a}baa\\1\un{a}bab\end{array}\right\}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}\left.\begin{array}{l}2\un{a}ccac\\2\un{a}ccbc\end{array}\right\}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&$2\un{c}aT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3\_babaT_2$\\
33&$1\un{c}aaT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}2\un{b}baa\\2\un{b}bab\end{array}\right\}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}\left.\begin{array}{l}3\un{c}ccac\\3\un{c}ccbc\end{array}\right\}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\_\left\{\begin{array}{l}\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\to\to 2T_2b\_\\\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1T_2b\_\end{array}\right.$\\
41&$1\un{T_1}\to\to 2T_2\_\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\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}\left.\begin{array}{l}2T_1aab\un{c}\\2T_1abb\un{c}\end{array}\right\}\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}\left.\begin{array}{l}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\right\}\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}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\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}\left.\begin{array}{l}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\right\}\to\to 3\un{T_2}bababa$\\
\end{longtable}

\fontsize{12}{12}\selectfont
In Table~\ref{table4} the numbers refer to IGR's in Table~\ref{table3}. The letters if present refer to the part of the IGR associated with that letter as the symbol above $\Rightarrow$ i.e. the symbol called $\alpha$, otherwise the whole IGR is referred to. The following number refers to the sub-part of the IGR with that numbered origin in the RHS of the IGR. 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 can be followed by any IGR on the right.
\fontsize{10}{10}\selectfont
\begin{longtable}{ll}
\caption{The relation `can be followed by'\label{table4}}\\
$1b1\to$ &$22,23,24,25,26,27,28,32,33,34,35,36,37$\\
$3b1,3b2,4b1,5b1,7b1,8b2\to$ &$22$\\
$\left.\begin{array}{l}2b1,2b2,6b1,6b2,9b1,13c1,13c2,14c1,15c1,\\17c1,18c1,33c1,33c2,34c1,35c1,37c1,38c1\end{array}\right\}\to$ &$29,31,38$\\
$12c1,12c2,16c1,16c2,36c1,36c2,39c1\to$ &$30,39$\\
$22b1\to$ &$1,2,3,4,5,6,7,10,11,12,13,14,15,16,18,19$\\
$23b1,23b2,27b1,27b2,30b1\to$ &$8,18$\\
$24b1,24b2,25,26,28,29\to$ &$1$\\
$32c1,30c2\to$ &$29,38$\\
$40a1,40a2\to$ &$42$\\
$41a1\to$ &$49,50,52,54$\\
$41a2\to$ &$44,49,50,51,52,54,55$\\
$42b1\to$ &$41,46$\\
$47b1\to$ &$41,45,48$\\
$50b1\to$ &$43,53$\\
$51a1,51a2,51a3\to$ &$49,52,54$\\
$51a4\to$ &$44,49,52,54,55$\\
\end{longtable}
\fontsize{12}{12}\selectfont
By examining these IGR's in Table~\ref{table3} and the compatibility relations in Table~\ref{table4} the following facts become evident:
\begin{itemize}
\item IGR's can be chained together by substitutions for the arbitrary strings $T_1$ and $T_2$.
\item Table~\ref{table4} is the restriction on which single IGR can be followed by another IGR resulting from the structure of the IGR's themselves.
\item Other restrictions result from the way in which sequences of substitutions operate.
\item By carrying out by hand the process called 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 the analysis of which IGR's can follow the sequence.
\item If by carrying out the process F to any sequence of IGR's to find which IGR's can be next in the sequence, there always results an IGR that has 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.
\end{itemize}

From Table~\ref{table4} IGR $22$ clearly plays an important role so I thought I would start there regarding the last point above. By restricting consideration to IGR $1$ followed by IGR $22$ i.e. $1\to 22$ fewer possibilities will result for the following IGR's.

I start to illustrate this process as follows. I say start because the computations get rapidly complicated and unwealdy because the notation and/terminology is not sufficient to express it succinctly, so nothing like a complete satisfactory result is produced, thus I stop after three subsubsections.
\subsubsection{$1\to 22$}
The sequence of IGR's $1\to 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$.
Applying the process F to the result of 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\left\{\begin{array}{l}\stackrel{\alpha = b}{\leftarrow}1\un{c}ccT_1\\\leftarrow 2\alpha c\un{c}T_1\end{array}\right..\end{equation}
Although it is possible logically to continue the backward search like this
\begin{equation}2\alpha c\un{c}T_1\leftarrow 2\alpha\un{b}cT_1\left\{\begin{array}{l}\stackrel{\alpha = b}{\leftarrow} 1\un{a}bcT_1\\\stackrel{\alpha = c}{\leftarrow}2\un{b}bcT_1\end{array}\right.\end{equation}
because the first of these reverse steps $2\alpha c\un{c}T_1$ cannot lead to any other result than the ones indicated because there is no TM step ending in $2\_\beta$ no matter what the symbol $\beta$ is, doing this will not necessarily generate new IGR's for the reason given in Section~\ref{sec2} (page 3). 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. Taking a further step back in the sequence of IGR's to be considered gives for example $22\to 1\to 22$.
\subsubsection{$22\to 1\to 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\to 22$ above. Apply $F$ to this starts by the backward search from $1\alpha\un{c}ccT_1$ giving
\begin{equation}\label{eq2}1\alpha\un{c}ccT_1\left\{\begin{array}{l}\leftarrow 2\alpha c\un{c}cT_1\leftarrow 2\alpha\un{b}ccT_1\left\{\begin{array}{l}\stackrel{b}{\leftarrow}1\un{a}bccT_1\\\stackrel{c}{\leftarrow}2\un{b} bccT_1\end{array}\right.\\\stackrel{b}{\leftarrow} 1\un{c}cccT_1\end{array}\right..\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 because the pointer has not reached them into $T_1$ or $T_2$ 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}
which bears an interesting relationship to $11$ and $17$. 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.

Now looking at the origins in the RHS in these results or equivalently the origins found in \ref{eq2}, the absence of a branch of the backward search taking the pointer to the opposite end of the string from $\alpha$, any special cases of $T_1$ and $T_2$ that would result from prior IGR's in the sequence could not affect the set of IGR's that could be next in the sequence. Thus the result \begin{equation}\ldots 22\to 1\to 22\stackrel{F}{\Rightarrow} \{1, 7, \eqref{eq1}\}\end{equation} is in a sense complete. As $1$ can also be preceded by $24b1$, $24b2$, $25$, $26$, $28$, $29$ so these cases should now be considered in turn as preceding $1\to 22$.

\begin{comment}The above comment on \eqref{res} implies that there are no special cases regarding regarding what symbols $T_1$ starts with that can generate another branch or extra case in \eqref{res} i.e. \eqref{res} is essentially complete. This special circumstance implies that if the same analysis ($F$) was applied to any sequence of IGR's that end in $1\to 22$, the equivalent results for the set of IGR's that can follow the sequence would be obtained that can also be expressed as $\{1,7,\eqref{new}\}$. 
\end{comment}

\subsubsection{$\ldots\to 1\to 22$}
This is \begin{equation}\label{3.22}1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{a}baa\\1\un{a}bab\end{array}\right\}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_abT_2.\end{equation}

$24b1\to 1\to 22$ gives the RHS $1\un{c}cabaaT_1\to\to 1\_abaT_2$. Applying $F$ gives
\begin{equation}1\alpha\un{c}cabaaT_1\left\{\begin{array}{l}\leftarrow 2\alpha c\un{c}abaaT_1\leftarrow 2\alpha\un{b}cabaaT_1\left\{\begin{array}{l}\stackrel{b}{\leftarrow}1\un{a}bcabaaT_1\\\stackrel{c}{\leftarrow}2\un{b}bcabaaT_1\end{array}\right.\\\stackrel{b}{\leftarrow}1\un{c}ccabaaT_1\end{array}\right.\end{equation}
When expressed in terms of the longest strings of symbols unaltered gives same result as above i.e.
\begin{equation}\ldots 24b1\to 1\to 22\stackrel{F}{\Rightarrow} \{1, 7, \eqref{eq1}\}.\end{equation}
$24b2\to 1\to 22$ gives a very similar result giving the same result when reduced to its shortest form i.e.
\begin{equation}\ldots 24b2\to 1\to 22\stackrel{F}{\Rightarrow} \{1, 7, \eqref{eq1}\}.\end{equation}
The same thing happens with the others that include all the possible IGR's preceding $1\to 22$ so the results can be written briefly as
\begin{equation}\ldots\{22, 24b1, 24b2, 25, 26, 28, 29\}\to 1\to 22\stackrel{F}{\Rightarrow} \{1, 7, \eqref{eq1}\}.\end{equation}
The reason for this is that they all involve tracing back from $1\alpha\un{c}c\ldots$ that does not involve the pointer reaching beyond the third symbol so the results are the same when reduced to the shortest form.

















\subsubsection{$3\to 22$}




This can be written as \begin{equation}\label{3.22}1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}\un{a}baa\\\un{a}bab\end{array}\right\}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_abT_2.\end{equation} after substituting
$\un{a}baaT_1$ respectively $\un{a}babT_1$ for $T_1$ and $bT_2$ for $T_2$ in IGR $22$.
Applying $F$ to the first part of this i.e. using $1\un{c}abaa$ as the origin to start from gives the long form result (without reducing the strings to minimal form)
\begin{equation}\label{3b1.22.long}1\un{c}abaaT_1\to\to 1\_abT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}cabaa\\2\un{a}cabaa\\2\un{a}cbbaa\end{array}\right\}T_1\to\to 3\_babT_2\\\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}cabaa\\3\un{c}cbbaa\end{array}\right\}T_1\to\to 2bbc\un{T_2}\end{array}\right..\end{equation}
By tracking the rightmost position of the pointer in each branch in the backward search starting from $1\alpha \un{c}abaaT_1$, the minimal forms of the results in \eqref{3b1.22.long} turn out to be $1$ and $2$ and the new one
\begin{equation}\label{extraIGR}1\un{c}aT_1\to\to 1\_abT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3bbc\un{T_2}.\end{equation}
Along with the above are the residual origins\begin{equation}\label{extra}\left.\begin{array}{l}3\alpha caab\un{a}\\3\alpha caab\un{b}\\3\alpha cabb\un{a}\\3\alpha cabb\un{b}\end{array}\right\}T_1\end{equation} derived from the first part of \eqref{3.22} i.e. $3b1\to 22$,
 which are the residual CS's where the pointer reached the opposite end of the string from $\alpha$. These are not included in the results of $F$ because they are not themselves new IGR's, but they are needed when the results are used as starting points for the calculation of $F$ for a special case of $3b1\to 22$ as occurs when there are extra IGR's preceding the sequence of IGR's considered, because this frequently results in $T_1$ being specialised by specifying the first few symbols of it.
This could result in an enlarged backward search tree. Thus in this case, if other previous history is specified before IGR $3$, more following IGR's might result. Importantly note that in the absence of residual origins, the set of IGR's as a result of $F$ cannot change as a result of specialising $T_1$ i.e. specifying previous IGR's in the sequence studied.
The residual origins \eqref{extra} be written as \begin{equation}3\alpha ca\left\{\begin{array}{l}a\\b\end{array}\right\}b\left\{\begin{array}{l}\un{a}\\\un{b}\end{array}\right\}T_1\end{equation}
where the symbols in the two arrays can be chosen independently.

Similarly applying $F$ to $3b2\to 22$ gives the long form result
\begin{equation}\label{3b2.22.long}1\un{c}ababT_1\to\to 1\_abT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}cabab\\2\un{a}cabab\\2\un{a}cbbab\end{array}\right\}T_1\to\to 3\_babT_2\\\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}cabab\\3\un{c}cbbab\end{array}\right\}T_1\to\to 2bbc\un{T_2}\end{array}\right.\end{equation} which is the same as \eqref{3b1.22.long} except that the symbol just before $T_1$ is $b$ instead of $a$, because the pointer is not interacting with this symbol. It can by truncation
to the minimum number of symbols be written as $\{1, 2, \eqref{extraIGR}\}$ as above. Likewise there are the residual origins \eqref{extra2} to be included that are affected by this change of symbol and are
\begin{equation}\label{extra2}\left.\begin{array}{l}1\alpha caba\un{b}\\1\alpha cabb\un{b}\\1\alpha cbba\un{b}\\1\alpha cbbb\un{b}\end{array}\right\}T_1\end{equation}
i.e. \begin{equation}1\alpha c\left\{\begin{array}{l}a\\b\end{array}\right\}b\left\{\begin{array}{l}a\\b\end{array}\right\}\un{b}T_1.\end{equation}
Thus the main results of this section can be summarised as
\begin{equation}3\to 22\stackrel{F}{\Rightarrow}\{1,2,\eqref{extraIGR}\}.\end{equation}

For extending \eqref{3.22} to include previous history note that the result \eqref{3.22} cannot be repeated because the strings do not match i.e. $3\to 22\to 3\to 22$ is not possible. Table~\ref{table4} shows that IGR $3$ can only be preceded by IGR $22$. Therefore any IRR's derived ending with $3\to 22$ must take the form $\ldots x\to 22\to 3\to 22$ where $x$ is not IGR $3$.

Reasoning from the other end shows that IGR $22$ with context $(b,b)$, $22(b,b)$, is $1\un{b}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}1\un{c}bT_1\to\to 1\_abT_2$ which cannot be followed by IGR $3$ because $1\un{c}bT_1$ does not match $1\un{c}aaT_1$, and $(b,b)$ is the context in which IGR $22$ appears in the set IRR(2) from which all IRR's are derived by IGR's.

\subsubsection{$22\to 3 \to 22$}
This can be written as \begin{equation}\label{22.3.22}1\un{a}aT_1\to\to 3\_T_2\stackrel{bbb}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_abaT_2.\end{equation}
Applying $F$ to $22\to 3b1\to 22$ gives the long form result (without reducing the strings to minimal form)
similar to \eqref{3b1.22.long} and differs from it only in that $T_2$ is replaced by $aT_2$:
\begin{equation}\label{22.3b1.22.long}1\un{c}abaaT_1\to\to 1\_abaT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}cabaa\\2\un{a}cabaa\\2\un{a}cbbaa\end{array}\right\}T_1\to\to 3\_babaT_2\\\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}cabaa\\3\un{c}cbbaa\end{array}\right\}T_1\to\to 3bbcb\un{T_2}\end{array}\right.\end{equation}
thus minimal forms of the results in \eqref{22.3b1.22.long} are $1$ and $2$ and the new one
\begin{equation}\label{extraIGR_2}1\un{c}aT_1\to\to 1\_abaT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3bbcb\un{T_2}.\end{equation}
In addition, the residual origins are the same as \eqref{extra} becuase the starting point for the backward search is the same.

Similarly applying $F$ to $22\to 3b2\to 22$ gives 
\begin{equation}\label{22.3b2.22.long}1\un{c}ababT_1\to\to 1\_abaT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}cabab\\2\un{a}cabab\\2\un{a}cbbab\end{array}\right\}T_1\to\to 3\_babaT_2\\\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}cabab\\3\un{c}cbbab\end{array}\right\}T_1\to\to 3bbcb\un{T_2}\end{array}\right..\end{equation} which is the same as \eqref{22.3b1.22.long} except that the symbol just before $T_1$ is $b$ instead of $a$, because the pointer is not interacting with this symbol. The results of this section can by truncation to the minimum number of symbols be written as $22\to 3\to 22\stackrel{F}{\Rightarrow}\{1, 2, \eqref{extraIGR_2}\}$ as above with the same two sets of residual origins \eqref{extra} and \eqref{extra2} to be included from both parts of \eqref{22.3.22} respectively.

In $22\to 3$, $T_1$ in $22$ must start with $aa$. This is inconsistent with $T_1$ starting with $c$ if $1$ precedes $22$, and $T_1$ starting with $ab$ if $22$ is preceded by any of $3$ $4$, $5$ and $7$, therefore $22\to 3$ can be preceded only by $8$, the only other option in Table~\ref{table4}.
\subsubsection{$8\to 22\to 3\to 22$}
This can be written as
\begin{equation}\label{8.22.3.22}2\un{a}T_1\to\to 1\_T_2\stackrel{8b}{\Rightarrow}1\un{a}aT_1\to\to 3\_bT_2\stackrel{b22\to 3\to 22}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_ababT_2\end{equation}
Now $F$ can be applied to this easily because the backward searching has already been done in the two cases above. In fact \eqref{8.22.3.22} only differs from \eqref{22.3.22} in that $T_2$ has the requirement to begin with $b$. Then it is easy to continue the computations of the RHS's to show that \begin{equation}\label{eq44}1\un{b}ababT_2\to 3\_bababT_2\text{ and }1\un{c}ababT_2\to 3bbbbb\un{T_2}.\end{equation}
and so $F$ applied to both parts of \eqref{8.22.3.22} are, in long form, \eqref{22.3b1.22.long} and \eqref{22.3b2.22.long} but with the $T_2$ strings modified as above, which will not affect the shortest forms of the $T_1$ strings. Reducing it to shortest form can be seen to yield the same result but with the $T_2$ strings modified i.e.
$1$, $2$ and \begin{equation}\label{extraIGR_1}1\un{c}aT_1\to\to 1\_ababT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3bbbbb\un{T_2}.\end{equation}
Therefore \begin{equation}8\to 22\to \{3b1,3b2\}\to 22\stackrel{F}{\Rightarrow}\{1,2,\eqref{extraIGR_1}\}.\end{equation}
The results \eqref{extra} and \eqref{extra2} continue to apply in these cases because the backward searches are the same.

Because of \eqref{extra} and \eqref{extra2}, this analysis is not complete.
Referring again to \eqref{table4} shows that $8$ can be preceded only by all parts of $23$, $27$ and $30$.
\subsubsection{$\{23,27,30\}\to 8\to 22\to 3\to 22$}
Consider first starting with $23$. When this is followed by \eqref{8.22.3.22} this gives the result
\begin{equation}\label{23.8.22.3.22}1\un{c}aT_1\to\to 3\_T_2\stackrel{b^5}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaaca\\1\un{c}ababca\\1\un{c}abaacb\\1\un{c}ababcb\end{array}\right\}T_1\to\to 1\_ababaT_2\end{equation}

Applying $F$ to the RHS of this can be started by doing the backward search first from $1\alpha\un{c}abaa$ and $1\alpha\un{c}abab$ as in \eqref{22.3.22} which have already been done. This resulted in \eqref{extra} and \eqref{extra2} together with results in \eqref{22.3b1.22.long} and \eqref{22.3b2.22.long}.  The latter involve the pointer returning to the left hand end of the string, and so the above results will be unaffected when the extra symbols $ca$ and $cb$ are added to the right and the results are expressed with the minimum number of symbols. The RHS of the RHS of \eqref{23.8.22.3.22} has the same form as the RHS of the RHS of \eqref{22.3.22} therefore the shortest form of these results of $F$ will be same as before which are $1$ and $2$. In addition to this there could be results from the continuation of the backward search from \eqref{extra} and \eqref{extra2} by appending to these the strings $ca$ and $cb$ on the right. 

First adding just $c$ to the right of \eqref{extra} gives just two results where the pointer reaches an end of the string: \begin{equation}\label{38_c}2\alpha caaab\un{c}T_1\text{ and }2\alpha caabb\un{c}T_1.\end{equation}
Again adding $a$ and $b$ in turn to the right hand end of the string and continuing the backward search gives in each case no resulting string where the pointer reaches an end. Therefore from \eqref{extra} there are no results of $F$. Now add $c$ to the right of \eqref{extra2} and continuing the backward search gives\begin{equation}\label{extra2_c}\left.\begin{array}{l}2\alpha cabab\un{c}\\2\alpha cabbb\un{c}\\2\alpha cbbab\un{c}\\2\alpha cbbbb\un{c}\end{array}\right\}T_1\end{equation}and \begin{equation}\label{extra3}1\un{a}bbccbcT_1\text{ with }\alpha = b\text{ and }2\un{b}bbccbcT_1\text { with }\alpha = c.\end{equation}
Now adding $a$ to the right of \eqref{extra2_c} and continuing the backward search gives
\begin{equation}\label{extra_ca}1\un{a}bbccacaT_1\text{ with }\alpha = b\text{ and }2\un{b}bbccacaT_1\text{ with }\alpha = c\end{equation}
Finally adding $b$ to the right of \eqref{extra2_c} and continuing the backward search gives
\begin{equation}\label{extra_cb}1\un{a}bbccacbT_1\text{ for }\alpha = b\end{equation}
The results \eqref{extra3} came from $1\un{c}ababc$ and involved the pointer moving between there and where it is in \eqref{extra2} with $c$ added on the right. In these paths the pointer cannot ever reach the end of the string because the backward searching algorithm halts when this happens, therefore the pointer can never get to the $c$ at the end, so this symbol is redundant and is the only one redundant, thus it must be removed. On the RHS's, putting $\alpha = b$ it is done in a single step. For $\alpha = c$, using \eqref{eq44}.2 it follows that \begin{equation}\label{eq_alpha_c}1\un{c}ababaT_2\to 3\_bababaT_2\end{equation} and this uses all the symbols written, therefore the following IGRs are obtained:
\begin{equation}1\un{c}ababT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccbT_1\to\to 3\_bT_2\end{equation}
which is $4$ and
\begin{equation}1\un{c}ababT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccbT_1\to\to 3\_bababaT_2.\end{equation} which is $14$.
Similarly from \eqref{extra_ca} in the backward searching, only the last symbol $a$ is redundant, and on the right, for $\alpha = b$ it is a single TM step, and for $\alpha = c$ \eqref{eq_alpha_c} applies, so the long form result
\begin{equation}1\un{c}ababcaT_1\to\to 1\_ababaT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow} 1\un{a}bbccacaT_1\to\to 3\_bababaT_2\\\stackrel{c}{\Rightarrow}2\un{b}bbccacaT_1\to\to 3\_bababaT_2\end{array}\right.\end{equation}
reduces to
\begin{equation}1\un{c}ababcT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccacT_1\to\to 3\_bT_2\end{equation}
i.e. $5$ and
\begin{equation}1\un{c}ababcT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccacT_1\to\to 3\_bababaT_2\end{equation} which is $15$.
The final result \eqref{extra_cb} again gives $5$ when expressed in the shortest form.
The results of this section so far can be summarised as \begin{equation}\label{summ23.8.22.3.22}\ldots 23\to 8\to 22\to 3\to 22\stackrel{F}{\Rightarrow}\{1,2,4,5,14,15\}\end{equation} because there are no residual origins with the pointer
oppsite $\alpha$, so no extra results that can occur as a result of any specialisations of $T_1$ and $T_2$ that would result from any prior IGR's in the sequence.

Next consider starting from $27$. When this is followed by \eqref{8.22.3.22} with the substitutions $T_1\to ccacT_1$ and $T_2\to aT_2$ it gives
\begin{equation}\label{27.8.22.3.22}1\un{c}abcT_1\to\to3\_T_2\stackrel{b^5}{\Rightarrow}\left\{\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}\left\{\begin{array}{l}ccac\\ccbc\end{array}\right\}T_1\to\to 1\_ababaT_2.\end{equation}

Because the RHS of this is a special case of the RHS of \eqref{22.3.22} the results of that section apply and the results $1$, $2$ will be unaffected by the extra symbols added after the results are reduced to minimal form. The former residual origins \eqref{extra} and \eqref{extra2} could give more results. Compared with \eqref{22.3.22}, the first extra $c$ to added to \eqref{extra} just gives \eqref{38_c} as above. The next $c$ added gives no extra results for the same reason as above. Now proceeding from \eqref{extra2}, the first $c$ added gives \eqref{extra2_c} and \eqref{extra3} as above. For the next $c$ added to these, \eqref{extra3} gives no new results but \eqref{extra2_c} does give just \begin{equation}\label{extra_cc}1\un{a}bbccacc\text{ for }\alpha = b\text{ and }2\un{b}bbccacc\text{ for }\alpha = c.\end{equation} By identifying the provenance of this result from $1\alpha\un{c}ababcc$ and noting that the final $c$ must be removed similar to the above argument, it follows that \eqref{extra_cc} reduces to the shortest forms which are again $5$ and $15$. Furthermore there are no more residual origins with the pointer opposite $\alpha$ so these results combined show that
\begin{equation}\label{summ27.8.22.3.22}\ldots 27\to 8\to 22\to 3\to 22\stackrel{F}{\Rightarrow}\{1,2,5,15\}\end{equation}

Consider starting from $30$. When this is followed by \eqref{8.22.3.22} this gives
\begin{equation}3\un{T_1}\to\to 3\_T_2\stackrel{b^5}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_ababaT_2.\end{equation} Again the backward search is as before and together with \eqref{eq_alpha_c} it is straightforward to show that $F$ applied to this gives $1$,$2$ and 
$12$ together with the residual origins \eqref{extra} and \eqref{extra2} as before. Therefore preceding IGR's must be considered for this case.
$30$ can be preceded by just $12$,$16$,$36$,$39$.
\subsubsection{$x\to 30\to 8\to 22\to 3\to 22$}
The RHS of this for $x = 12$ is \begin{equation}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}\left\{\begin{array}{l}cca\\ccb\end{array}\right\}T_1\to\to 1\_abababababaT_2.\end{equation}
Following very similar reasoning to the above shows that the result of $F$ for this is as in \eqref{summ27.8.22.3.22} with no residual origins. This is a consequence of $1\un{c}abab$ being followed by $cc$ and is also true for $x$ being $16$, $36$, but not $39$.
i.e. \begin{equation}\{12,16,36\}\to 30\to 8\to 22\to 3\to 22\stackrel{F}{\Rightarrow} \{1,2,5,15\}\end{equation}
$4\to 22\to 3$ is impossible therefore so is $4\to 22\to 3\to 22$.
\subsubsection{$39\to 30\to 8\to 22\to 3\to 22$}
This is \begin{equation}\label{39.30.8.22.3.22}3\un{T_1}\to\to 3\_babT_2\stackrel{c}{\Rightarrow}3\un{c}T_1\to\to 3\_babaT_2\stackrel{b^5}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}cT_1\to\to 1\_ababababaT_2\end{equation}

$F$ applied to this gives $1$,$2$,$4$,$14$ and \eqref{extra2_c}. Again because there are residual IGR's the search must continue back. The IGR's that can precede $39$ are $12$,$16$,$36$,$39$. In each of these cases, the LHS of the RHS has $c$ on the left. This implies that when substitutions are made into \eqref{39.30.8.22.3.22} to follow each of these cases in turn, $T_1$ is replaced by a string that begins with $c$. Therefore the RHS is of the form
\begin{equation}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}ccT_3\to\to 1\_ababaT_4\end{equation} where $T_3$ and $T_4$ are new strings dependent on $T_1$ and $T_2$ and on which case is being considered. Now applying $F$ the logic follows similarly to the analysis of \eqref{27.8.22.3.22} showing that the result is again $\{1,2,5,15\}$ i.e. \begin{equation}\ldots \{12,16,36,39\}\to 39\to 30\to 8\to 22\to 3\to 22\stackrel{F}{\Rightarrow}\{1,2,5,15\}.\end{equation}
Now there is no need to continue further back because there are now no residual origins.








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.
\begin{longtable}{c|c}
\caption{The IGR's and contexts that give on their RHS's all the IRR(2)\label{table5}}\\
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}

\section{Further simplification and LIGR's}
The reader will probably have noticed that while generating Table~\ref{table3}, the left and right halves of each IGR can be done almost independently, and the left hand sides (the LHS of the lhs and the LHS of the RHS) have a lot of repetition, many appearing multiple times, thus this presentation is far from optimal even though the results taken together do seem to provide a general process to generate and IRR from any other one. This latter observation is from the results of the computer program and does not constitute and general proof of this.

The aim of this section will be to show that if this process 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}
An LIGR or left IGR is the LHS of the LHS of an IGR, and the LHS 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}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1.\end{equation} Similarly
\begin{equation}\label{ligr2}1\alpha\un{c}aT_1\stackrel{\alpha =c}{\leftarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}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$. 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$.
This notation with the reverse facing arrow will be used because as usual the arrow indicates the direction of the computation of the TM. 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 matches an IRR (on its LHS), $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{Sequences of LIGR's}
A sequence of LIGR's is a chain of LIGR's that can follow each other written with $\rightarrow$ between them so for example if\begin{equation}L_1= 1\un{c}aT_1\stackrel{b}{\leftarrow}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1.\end{equation}
\begin{equation}L_2 = 2\un{T_1}\left\{\begin{array}{l}\stackrel{b}{\leftarrow}1\un{a}T_1\\\stackrel{c}{\leftarrow}2\un{b}T_1\end{array}\right.\end{equation}
\begin{equation}L_3 = 1\un{T_1}\stackrel{b}{\leftarrow}1\un{c}T_1\end{equation}
then
\begin{equation}\begin{array}{l} L_{1.2} = 1\un{c}aT_1\stackrel{b}{\leftarrow}2\un{a}cbT_1\\
L_{2.1} = 2\un{T_1}\stackrel{b}{\leftarrow}1\un{a}T_1\end{array}\end{equation}
and the chain $L_{1.2}\rightarrow L_{2.1}\rightarrow 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_1\leftarrow 2\un{a}cbT_1\leftarrow 1\un{a}acbT_1\leftarrow 1\un{c}aacbT_1\end{equation} so the combination is $1\un{c}aT_1\stackrel{bbb}{\leftarrow}1\un{c}aacbT_1.$

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. But for convenience some changes will be made. 
Now the value of $F$ will be defined as a pair, the first component being the set of LIGR's as possible next LIGR's in the sequence, and the second component being the set of residual CS's as defined above in the context of IGR's. The latter are result of the backward search where the pointer reaches the opposite end of the string from $\alpha$, that is next to the arbitrary string $T_1$.
 \begin{equation}F(\text{``sequence of LIGR's"},\alpha) = (\text{``Next LIGR's", ``Set of residual CS's"})\end{equation}

How is the result of $F$ affected by including an extra LIGR to the sequence?

Suppose an LIGR $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_1\stackrel{\alpha}{\leftarrow}s_2\un{z_1}\ldots z_{r+1}T_1.\end{equation}

Likewise let $X_2$ be\begin{equation}\label{ligr4}s'_1\un{y'_1}\ldots y'_{r'}T_1\stackrel{\alpha'}{\leftarrow}s'_2\un{z'_1}\ldots z'_{r'+1}T_1.\end{equation}
Then for the sequence $X_2\to 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. The result of $X_2\to X_1$ is
\begin{equation}\label{ligr5}s'_1\un{y'_1}\ldots y'_{r'}T_1\stackrel{\alpha'}{\leftarrow}s'_2\un{z'_1}\ldots z'_{r'+1}T_1 =s_1\un{y_1}\ldots y_rz'_{r+1}\ldots z'_{r'+1}T_1\stackrel{\alpha}{\leftarrow}s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{r'+1}T_1.\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_1$ 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. Also there may be results of this where the pointer ends up at the opposite end of the string from $\alpha$. These are the residual CS's in the result of $F$ applied to \eqref{ligr5}. Therefore it makes sense to introduce $\Delta F$ as the set of extra LIGR's in the result of $F$, as a result of adding an extra LIGR at the beginning of the sequence (the argument of $F$):
\begin{equation}\label{ligr6}\Delta F_1(Y_1,X_1\to X_2\ldots\to X_n)=F_1(Y_1\to X_1\ldots\to X_n)\setminus F_1(X_1\to X_2\ldots X_n).\end{equation}
Related to this is the set of residual CS's in this computation
\begin{equation}\label{ligr7}F_2(Y_1,X_1\to X_2\ldots\to X_n)=F_2(Y_1\to X_1\ldots\to X_n).\end{equation}
As another point of notation, 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 RHS of the combined LIGR and results from applying the backward search algorithm to its RHS. 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 RHS.

\subsection{\label{apply_f}Applying $F$ to sequences of LIGR's}
The following argument leads to 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 separately, so in the
general case above the extra symbols can also be called $z'_{r+1}\ldots z'_{r'+1}$ and one can write:
\begin{equation}\label{ligr7}\begin{array}{l}F_1(Y_1\to X_1\to X_2\ldots\to X_n)=F_1(s_2\un{z_1}\ldots z_{r+1}z'_{r+1}\ldots z'_{r'+1})\\
= \left[\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})\right]\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(X_1\to X_2\ldots\to X_n).$
Each step uses the residual CS's from the previous step. These residual CS'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 residual CS'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})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 a residual CS 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 $i = r+1$ initially, then this shows that the backward search starts from $F_2(s_2\un{z_1}\ldots z_{r+1})z'_{r+1}$ i.e. the set of residual CS's from the initial backward search for $X_1$ 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 a residual CS in $F_2(s_2,\un{z_1}\ldots z_{r+1}z'_{r+1})$. Then for $i = r+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 a residual CS 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 residual CS's in $F_2$ it terminates. All the new LIGR's are accumulated and any final residual CS's are noted. Naturally, there is an equivalent version of this if $\alpha$ is on the right.
\subsection{The procedure for finding the LIGR's for a TM}
The first step is to write down the LIGR's corresponding to the entries in the TM table. Each such entry could be associated with a single reverse TM step that could be involved in generating a new IRR from an old one, therefore every entry must be involved. The $\alpha$ value is the new symbol written. So for example $3\un{b}\to 1\_a$
implies that a reverse step from state 1 with $\alpha = a$ gives $3\un{b}$. This is represented as an LIGR with the notation $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{b}$ where $T_1$ is as usual the arbitrary string.

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 as usual. For this the methods of subsection~\ref{apply_f} applies. This result could be empty or one or more LIGRs some of which may be new ones to be added to the set. If this yields any residual CS's, this implies that an extra LIGR added at the beginning of the sequence could result in extra LIGR's as a result of this procedure as explained above. All possible preceding LIGR's, one at a time, must be prepended to the sequence being studied which is then checked for following LIGR's etc. and recursively. If such a sequence of LIGR's does not have any residual CS's in the result of $F$, the search continues from the next sequence of LIGR's to be checked in some pre-defined order. This continues until hopefully every sequence of LIGR's has been fully analysed to find all the possible subsequent LIGR's that are possible. In order to do this a list of LIGR's has to be maintained, and for each LIGR the set of LIGR's that can precede it must also be maintained.

\begin{Definition}
The 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}
Every IRR can be obtained by a chain of applications of $F$ from a member of IRR(2). Each application of $F$ on the LHS involves a backward search, and when this is shortened to its shortest form the result is an LIGR. This LIGR could therefore be obtained by applying $F$ to the previous chain of LIGR's involved in the derivation of the IRR. Therefore if the set $Z$ is closed under $F$, this LIGR is in $Z$. This proves that 

\begin{Theorem}
If there is a finite set $Z$ of LIGR's for a Turing Machine that is closed under $F$ as described above, then every IRR of extendable type can be obtained from a member of IRR(2) by a sequence of applications of members of $Z$.
\end{Theorem}
The other case when the closure algorithm does not terminate leading to an infinite set $Z$ closed under $F$
might be interesting.

The single step LIGR's are (directly from the machine table in the same order):
\begin{equation}\begin{array}{lcl}
\begin{array}{ll}
1&2\un{T_1}\stackrel{b}{\leftarrow}1\un{a}T_1\\
2&3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}\\
3&1\un{T_1}\stackrel{b}{\leftarrow}1\un{c}T_1\\
4&3\un{T_1}\stackrel{b}{\leftarrow}2\un{a}T_1\\
5&2\un{T_1}\stackrel{c}{\leftarrow}2\un{b}T_1\\
6&1\un{T_1}\stackrel{c}{\leftarrow}2T_1\un{c}\\
7&1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{a}\\
8&1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{b}\\
9&3\un{T_1}\stackrel{c}{\leftarrow}3\un{c}T_1
\end{array}

&\begin{array}{c}\text{{\rm which can be grouped}}\\\text{\rm together as}\end{array}&
\begin{array}{l}
1\un{T_1}\left\{\begin{array}{l}\stackrel{a}{\leftarrow}\left\{\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right.\\[10pt]\stackrel{c}{\leftarrow}2T_1\un{c}\end{array}\right.\\[30pt]1\un{T_1}\stackrel{b}{\leftarrow}1\un{c}T_1\\[10pt]

2\un{T_1}\left\{\begin{array}{l}\stackrel{b}{\leftarrow} 1\un{a}T_1\\\stackrel{c}{\leftarrow}2\un{b}T_1\end{array}\right.\\[20pt]

3\un{T_1}\left\{\begin{array}{l}\stackrel{b}{\leftarrow}2\un{a}T_1\\\stackrel{c}{\leftarrow}3\un{c}T_1\end{array}\right.\\[20pt]

3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}\end{array}\end{array}\end{equation}
From this it follows that the relation ``can be preceded by" among the 9 LIGR's can be represented by
\begin{equation}\begin{array}{ll}
1\text{\hspace{1cm}}&4,5\\
2\text{\hspace{1cm}}&7,8\\
3\text{\hspace{1cm}}&1,3\\
4\text{\hspace{1cm}}&9\\
5\text{\hspace{1cm}}&4,5\\
6\text{\hspace{1cm}}&2\\
7\text{\hspace{1cm}}&2\\
8\text{\hspace{1cm}}&2\\
9\text{\hspace{1cm}}&9
\end{array}\end{equation} because the RHS of the preceding LIGR must match the LHS of the original LIGR in state, string of symbols and direction. For example LIGR 1 can be preceded by LIGR 4 ($4\to 1$) having the effect
$3\un{T_1}\stackrel{b}{\leftarrow}2\un{a}T_1\stackrel{b}{\leftarrow}1\un{a}aT_1$. Applying $F$ to $1$ gives just
$1\alpha\un{a}T_1\stackrel{b}{\leftarrow}1\un{c}T_1$ i.e. LIGR $3$ and applying $F$ to the result of $4\to 1$ gives the calculation
\begin{equation}1\alpha\un{a}aT_1\left\{\begin{array}{l}\stackrel{b}{\leftarrow}1\un{c}aaT_1\\\leftarrow\left\{\begin{array}{l}3\alpha a\un{a}T_1\\3\alpha a\un{b}T_1\end{array}\right.\end{array}\right..\end{equation}
The first part of this is LIGR $3$, and the second part is a pair of residual CS's. By specialising this by giving the first symbol(s) of $T_1$, the first result will not generate any new IGR'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}\begin{array}{c}\ldots1\stackrel{F}{\to}\{3\}\\\ldots\to 4\to 1\stackrel{F}{\to}\{3\}\end{array}.\end{equation}
LIGR's that can precede $4$ are just $9$. The sequence $9\to 4\to 1$ gives $3\un{T_1}\stackrel{c}{\leftarrow}3\un{c}T_1\leftarrow 1\un{a}acT_1$. Applying $F$ to this gives 
 $1\alpha \un{a}acT_1\leftarrow\left\{\begin{array}{l}3\alpha a\un{a}cT_1\\3\alpha a\un{b}cT_1\end{array}\right.$
which can be written briefly as $3\alpha a\left\{\begin{array}{l}\un{a}\\\un{b}\end{array}\right\}cT_1$ in addition to $3$ as above. The computation cannot go back from there so there are no results of $F$ and it is
now it is clear that no preceding LIGR's specialising this $T_1$ can give any results of $F$, so the search for new results of $F$ stops in this branch of the grand search tree. 
The next sequence of LIGR's to be considered is $5\to 1$ i.e. $2\un{T_1}\leftarrow 2\un{b}T_1\leftarrow 1\un{a}bT_1.$
The computation of $F$ starts from $1\alpha\un{a}bT_1$ and gives no result other than LIGR $3$, so gives similarly \begin{equation}\ldots\to 5\to 1\stackrel{F}{\to}\{3\}\end{equation}
This exhausts all search trees starting from $1$. Next consider applying $F$ to sequences ending with $2$ which is 
$3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}.$ $F$ applied to this gives \begin{equation}\label{eq96}1T_1\un{b}\alpha\left\{\begin{array}{l}\stackrel{a}{\leftarrow} 3T_1b\left\{\begin{array}{l}\un{a}\\\un{b}\end{array}\right\}\\
\stackrel{c}{\leftarrow}2T_1b\un{c}\end{array}\right.\end{equation} which are LIGR's $6$,$7$, and $8$ so \begin{equation}\ldots2\stackrel{F}{\to}\{6,7,8\}.\end{equation} The last symbol of $T_1$ in \eqref{eq96} could affect this result so LIGR's preceding $2$ must be considered which are just $7$ and $8$.
The sequence $7\to 2$ is $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{a}\leftarrow 1T_1a\un{b}$ and applying $F$ gives no extra results because the pointer cannot move left in the reverse computation regardless of any other specialisations of $T_1$ resulting from preceding LIGR's therefore $\ldots7\to 2\stackrel{F}{\to}\{6,7,8\}$ and this branch of the grand search ends.

Consider $8\to 2$ which is $1\un{T_1}\stackrel{a}{\leftarrow} 3T_1\un{b}\leftarrow 1T_1b\un{b}$. $F$ gives $1T_1b\un{b}\alpha\leftarrow 1T_1\un{c}b\alpha$  in addition to $6$,$7$, and $8$ i.e.
\begin{equation}\ldots8\to 2\stackrel{F}{\to}\{6,7,8\}\end{equation}so can be potentially specialised further.
$8$ can only be preceded by $2$ so the next sequence to be considered in the grand search is $2\to 8\to 2$ which is $3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}\leftarrow 1T_1bb\un{b}$. $F$ applied to this gives \begin{equation}\label{282}1T_1bb\un{b}\alpha\leftarrow 1T_1b\un{c}b\alpha\leftarrow 1T_1\un{c}cb\alpha\end{equation} (that uses the reverse rule \begin{equation}\label{rev1}1b\un{c}\leftarrow 1\un{c}c\end{equation}) in addition to $6$,$7$, and $8$, which allows for its continuation in the grand search but generates no new results.
$2$ can be preceded by only $7$ and $8$. First $7\to 2\to 8\to 2$ gives $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{a}\leftarrow 1T_1abb\un{b}$ and applying $F$ gives \begin{equation}\label{7282}1T_1abb\un{b}\alpha\leftarrow 1T_1a\un{c}cb\alpha\leftarrow 2T_1ac\un{c}b\alpha\leftarrow 2T_1a\un{b}cb\alpha\end{equation} which can go no further. It was convenient to use \eqref{282} to get this result and shows that no preceding LIGR's can be added giving any new results.
The next sequence to be considered is $8\to2\to8\to2$ which is $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{b}\leftarrow 1T_1bbb\un{b}$. Applying $F$ gives
\begin{equation}\label{8282}1T_1bbb\un{b}\alpha\leftarrow 1T_1b\un{c}cb\alpha\leftarrow\left\{\begin{array}{l}2T_1bc\un{c}b\alpha\leftarrow 2T_1b\un{b}cb\alpha\leftarrow 1T_1\un{a}bcb\alpha\\1T_1\un{c}ccb\alpha\end{array}\right.\end{equation}
 (that uses the reverse rules\eqref{rev1} and \begin{equation}\label{rev2}1b\un{c}c\leftarrow 1\un{a}bc\end{equation}) 
 both these results being residual CS's. So the grand search continues with $2\to 8\to 2\to 8\to 2$ which is
$3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}\leftarrow 1T_1bbbb\un{b}$.
 Using the results \eqref{8282} the backward search $F$ gives
\begin{equation}1T_1b^4\un{b}\alpha\left\{\begin{array}{l}\leftarrow 1T_1b\un{a}bcb\alpha\leftarrow 1T_1\un{c}abcb\alpha\\\leftarrow1T_1b\un{c}ccb\alpha\left\{\begin{array}{l}\leftarrow 1T_1\un{c}cccb\alpha\\\leftarrow 2T_1bc\un{c}cb\alpha\leftarrow 2T_1b\un{b}ccb\alpha\leftarrow 1T_1\un{a}bccb\alpha\end{array}\right.\end{array}\right..\end{equation}

 (that uses reverse rules \eqref{rev1}, \eqref{rev2} and \begin{equation}\label{rev3}1b\un{a}\leftarrow1\un{c}a\end{equation}).
Again continuing this using the IGR's that can precede $2$, the first sequence to be considered is
$7\to 2\to 8\to 2\to8\to2$ which is $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{a}\leftarrow 1T_1ab^4\un{b}$
Applying $F$ to this gives
\fontsize{9}{9}\selectfont

\begin{equation}\label{728282}1T_1ab^4\un{b}\alpha\left\{\begin{array}{l}\leftarrow1T_1a\un{c}c^3b\alpha\leftarrow2T_1ac\un{c}ccb\alpha\leftarrow2T_1a\un{b}cccb\alpha\\
\leftarrow1T_1a\un{a}bccb\alpha\\\leftarrow1T_1a\un{c}abcb\alpha\leftarrow3T_1ac\left\{\begin{array}{l}\un{a}\\\un{b}\end{array}\right\}bcb\alpha\left\{\begin{array}{l}\leftarrow3T_1a\un{c}\left\{\begin{array}{l}a\\b\end{array}\right\}bcb\alpha\leftarrow1T_1ac\un{b}bcb\alpha\\
\leftarrow T_1ac\left\{\begin{array}{l}a\\b\end{array}\right\}\un{b}cb\alpha\left\{\begin{array}{l}\leftarrow1T_1ac\un{c}bcb\alpha\\\leftarrow2T_1ac\left\{\begin{array}{l}a\\b\end{array}\right\}b\un{c}b\alpha\end{array}\right.\end{array}\right.\end{array}\right.\end{equation}
\fontsize{12}{12}\selectfont
which gives no new results.
Next considering $8\to2\to8\to2\to8\to2$ which is $1\un{T_1}\leftarrow3T_1\un{b}\leftarrow1T_1b^5\un{b}$ applying $F$ gives
\begin{equation}\label{828282}1T_1b^5\un{b}\alpha\left\{\begin{array}{l}\leftarrow1T_1b\un{c}c^3b\alpha\left\{\begin{array}{l}\leftarrow1T_1\un{c}c^4b\alpha\\\leftarrow2T_1bc\un{c}ccb\alpha\leftarrow2T_1b\un{b}c^3b\alpha\leftarrow1T_1\un{a}bc^3b\alpha\end{array}\right.\\
\leftarrow1T_1b\un{a}bccb\alpha\leftarrow1T_1\un{c}abccb\alpha\\
\leftarrow1T_1b\un{c}abcb\alpha\left\{\begin{array}{l}\leftarrow1T_1\un{c}cabcb\alpha\\
\leftarrow1T_1\un{a}c\left\{\begin{array}{l}a\\b\end{array}\right\}bcb\alpha\\\leftarrow2T_1\un{a}cc\left\{\begin{array}{l}a\\b\end{array}\right\}cb\alpha
\end{array}\right.
\end{array}\right.
\end{equation} 
(that uses reverse rules \eqref{rev1},\eqref{rev2},\eqref{rev3} and \begin{equation}\label{rev4}1b\un{c}a\leftarrow 2\un{a}c\left\{\begin{array}{l}a\\b\end{array}\right\}\end{equation}
 and \begin{equation}\label{rev5}1b\un{c}abc\leftarrow 2\un{a}cc\left\{\begin{array}{l}a\\b\end{array}\right\}c\end{equation}) all these results being residual CS's requiring the computation in the grand search to continue. The derivation of \eqref{828282} requires the derivation of \eqref{rev4} and \eqref{rev5} the last of which needed 9 steps.

The reader will probably suspect by now that this process will never end.
To prove this by induction, assume that when $F$ is applied to the result of the sequence $(8\to 2)^k$, some residual CS's defining the set $S$ are obtained but no new LIGR's. The search must then continue from these residual CS's. Also assume that the set of LIGR's is just the set $1-9$ mentioned above. Then LIGR $8$ can only be preceded by LIGR $2$ which is $3\un{T_1}\stackrel{b}{\leftarrow}1T_1\un{b}$. Also assume that $(8\to 2)^k$ is $1\un{T_1}\leftarrow 1T_1b^{2k-1}\un{b}$ so $F$ gives $1T_1b^{2k-1}\un{b}\alpha\leftarrow S$. Assume that the first derivation step in $F$ can be obtained from the derivation of the residual CS's in $F$ applied to $2\to(8\to 2)^{k-1}$ has the form $1\un{T_1}b^{2k-1}\un{b}\alpha\leftarrow\leftarrow$ Also let $R$ be the set of reverse rules used to get $S$ in the shortest form possible.



Then $2\to(8\to 2)^k$ is $3\un{T_1}\leftarrow 1T_1\un{b}\leftarrow T_1b^{2k}\un{b}.$ Applying $F$ to this starts with the backward search from $T_1b^{2k}\un{b}\alpha\leftarrow bS\leftarrow S'$ say and assume that this just results in the residual CS's $S'$. This requires the computation to continue with an extra preceding LIGR, which are $7$ and $8$. Ignore the results with $7$ for now. $(8\to 2)^{k+1}$ is therefore $1\un{T_1}\stackrel{a}{\leftarrow}3T_1\un{b}\leftarrow T_1b^{2k+1}\un{b}$ and $F$ gives $T_1b^{2k+1}\un{b}\alpha\leftarrow bbS\leftarrow bS'\leftarrow S''$ say. let $R$ be the set of reverse rules used to get $S$
\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}{John Nixon 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{Tarjan's_paper}\href{https://doi.org/10.1137/0201010}{SIAM Journal on Computing, 1 (2): 146-160, Depth-First Search and Linear Graph Algorithms doi:10.1137/0201010}
\bibitem{Tarjan's_algorithm}
\href{http://bluesky-home.co.uk/Tarjan_v1_0.txt}{An implementation of Tarjan's strongly connected components algorithm in D}
\bibitem{tie_v3_0}\href{http://www.bluesky-home.co.uk/tie_v3_0.txt}{The new program tie v3.0 for doing the computations in this paper}
\end{thebibliography} 



\end{document}