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