\documentclass[12pt,twoside]{article} \renewcommand{\baselinestretch}{1} \setcounter{page}{1} \setlength{\textheight}{21.6cm} \setlength{\textwidth}{14cm} \setlength{\oddsidemargin}{1cm} \setlength{\evensidemargin}{1cm} \pagestyle{myheadings} \thispagestyle{empty} \markboth{\small{John Nixon}}{\small{Developments in the analysis technique for non-terminating Turing Machines}} %\date{2017-02-21} \usepackage{caption} \usepackage{verbatim} %allows some sections to be temporarily commented out, which was %useful for correcting compilation errors that caused a problem with the long captions in two %tables (search for 'comment' to find them) \usepackage{enumitem} \usepackage{amssymb} \usepackage{longtable} \usepackage{float} \usepackage{subfigure} \usepackage{multirow} \usepackage{bigstrut} \usepackage{bigdelim} %\usepackage{cmll} \usepackage{pifont} \usepackage[utf8]{inputenc}% add accented characters directly \restylefloat{figure} \restylefloat{table} \usepackage{booktabs} \usepackage{hyperref}%The inclusion of package hyperref converts all the references to equations etc. to internal links \usepackage{array} \usepackage{mathtools}% includes amsmath \usepackage{amscd} \usepackage{amsthm} %\usepackage{MnSymbol} \everymath{\mathtt{\xdef\tmp{\fam\the\fam\relax}\aftergroup\tmp}} \everydisplay{\mathtt{\xdef\tmp{\fam\the\fam\relax}\aftergroup\tmp}} \begin{document} \setbox0\hbox{$x$} \newcommand{\un}{\underline} %\centerline{\bf Mathematica Aeterna, Vol. x, 201x, no. xx, xxx - xxx}%uncomment this in published version Date: 2022-05-20 \centerline{} \centerline{} \centerline {\Large{\bf Turing Machines}} \centerline{} %\centerline{\bf {John Nixon}} %\centerline{} %\centerline{Brook Cottage} %\centerline{The Forge, Ashburnham} %\centerline{Battle, East Sussex} %\centerline{TN33 9PH, U.K.} %Email: John.h.nixon1@gmail.com %Date: 2017-01-11 \newtheorem{Theorem}{\quad Theorem}[section] \newtheorem{Definition}[Theorem]{\quad Definition} \newtheorem{Corollary}[Theorem]{\quad Corollary} \newtheorem{Lemma}[Theorem]{\quad Lemma} \newtheorem{Example}[Theorem]{\quad Example} \newtheorem{alg}[Theorem]{\quad Algorithm} \newcounter{Hypothesis} \newtheorem{hyp}[Hypothesis]{Hypothesis} \begin{abstract} Developments are here described in the analysis technique for non-terminating Turing Machines that I described earlier. The main idea is the introduction of IRR patterns i.e. constraints satisfied by large sets of IRRs (Irreducible Regular Rules) and the logical relationships between them as a result of the general method for deriving IRR's from others described in my earlier paper. These logical relationships will be referred to as IGR's (IRR Generating Rules). IGR's have been reduced to their minimal form in a way analogous to the way in which regular rules were reduced to IRR's by taking out symbol strings that played no essential role. In the case of IGR's these symbol strings (actually pairs) will be referred to as context pairs. A new version of my computer program extending the previous analysis is described and is freely available. \end{abstract} {\bf Mathematics Subject Classification:} 68Q25 \\ {\bf Keywords:} Turing Machine (TM), Irreducible Regular Rule (IRR), IRR Generating Rule (IGR) \section{Introduction} some results are from the old (5,5) TM. check this. This document is a work in progress. As such it is incomplete and still has errors and omissions. When brought to a state where I cannot easily find any improvements it will form my next paper on Turing Machine analysis. Section 2 is a quite dense summary of the previous methods that lays the foundations of the developments to be described in this paper. Section 4 has been much improved and the IGR's for the IRR(3) and IRR(4) have been worked out in the new improved notation. Theorem 4.1 has been added and this will remove some unnecessary duplication. The worked examples in section 6 need to be looked at again as do the lists of results in section 7. A lot of the old material is now after the references so it can be viewed with links that still work but will probably not be in the paper. This version of the paper has a new version of the program linked to it \cite{tie_v3_0}, (the old version is \cite{tie}). A lot of material has been removed to 2017's \href{http://www.bluesky-home.co.uk/2017_Turing_notes.pdf}{Notes on Turing Machines}. These notes are now mostly superseded, but there may be a little there that is of use. Comments are welcome. Please send them to john.h.nixon1@gmail.com \begin{comment} \section{Outline of a possible algorithm for TM analysis} Looking at the many examples of IGR's here including those in the next section suggests the best practical method to analyse the TM is to repeatedly apply $F$ to results that generate the IRR(3). A typical instance involves applying $F$ to IRRP X as follows: \begin{alg}\label{algorithm9.1}[Algorithm for applying $F$ to an IRRP $X$] Repeat while $X$ has not already had $F$ applied to it \{Truncate $X$ by 1 symbol putting the context pair at the end of a sequence or list that starts empty\}. Apply $F$ to $X$ truncated to length 1 as in the examples above or to the last but one result of this loop by applying the last context pair in the list to each member of $X$ that is not extendable as its LHS as described in Table~\ref{Table3} and Section~\ref{section7}. Repeat this recursively, unless already done, for any member of $X$ that is not extendable using the next context pair. Repeat till all the context has been applied. If the result of applying $F$ is no new results, this terminates this branch of the calculation. The procedure branches whenever there is more than one $X$ that is of non-extendable type (case 4). The must be a separate pointer to the list of contexts for each branch. The intermediate results of this procedure may not be needed in the final analysis. They should be marked as such so that $F$ will not be applied to them at the next stage to generate IGR's for determining the $IRR({\it n})$. \end{alg} \begin{Theorem}Algorithm~\ref{algorithm9.1} applied to an IRRP $X$ generates all the IGRs that define all the results of the application of $F$ to $X$ as described in Section~\ref{section4}. \end{Theorem} \begin{proof} (Sketch) This is obvious because truncating $X$ truncates both the forward computation and backward search to that length and these calculations must be included in the full calculation for the original $X$. Therefore adding back the effect of the symbols truncated off systematically so that no options are forgotten must give the same result. This holds separately for each individual backward search path and forward computation possible. \end{proof} Note that in this algorithm it is the non-extendable IRRP's on the RHS that can have extra contexts applied to generate new IGR members. If the IRRP's of the right are extendable they can have $F$ applied using a new $\alpha$ to generate new IGR members. Repeat this starting with each IRRP generated from the TM until $F$ has been applied to every IRRP generated. All the IGR's so obtained must be recorded including those that lead to no new IRRP's. This may terminate because the final result is the IGR used to extend $X$ which can often be expected to be much shorter than $X$. See the example in Section~\ref{section4}. I will shortly try to construct a computer program to do this and check against the results obtained so far. A result of the analysis for a TM will be that each IRRP has associated with it a set of pairs of context strings that generate the IRR's it corresponds to. \end{comment} Another example and its proposed analysis \begin{equation}\begin{array}{c} 1\un{a}\to 2b \_\\ 1\un{b}\to 3\_b\\ 1\un{c}\to 1b\_\\ 2\un{a}\to 3b\_\\ 2\un{b}\to 2c\_\\ 2\un{c}\to 1\_c\\ 3\un{a}\to 1\_a\\ 3\un{b}\to 1\_a\\ 3\un{c}\to 3c\_\\ \end{array}\end{equation} \section{\label{sec2}Summary of the existing method to generate the IRR's} From the definition of regular rules (RR) and irreducible regular rules (IRR) in \cite{jhn2013}, any computation of the TM can be represented by RR's (which are certain pairs of CS's linked by $\to$) chained together as a sequence of CS's starting with length 1, where for each step in the chain a new symbol is read at a position where no symbol has yet been read at the pointer, thus the length of the string of symbols increases by 1 at each step unless a stationary cycle occurs. If the RR is of type LR or RL the pointer swaps ends at that step of the chain and these RR's are also IRR's because if the pointer swaps ends there are no redundant symbols. If a CS called ``origin" is included with the LHS and RHS of the IRR it can be written in the triplet form as $Origin\to LHS\to RHS$. An origin (there could be many for the same LHS) of an IRR is a CS obtained by running the TM backwards starting from the LHS to a point such that the pointer position is at the opposite end of the string from where it is in the LHS. Any CS will be said to be reachable i.e. is an LHS of an IRR, if and only if it is the RHS of and IRR of type LR or RL with an additional symbol added at the pointer position, and this gives a recursive definition of the IRR's. IRR's have been presented in 3 different ways and there should be no confusion:\newline (1) The original presentation with 2 CS's: $LHS\to RHS$\newline (2) IRR triplet with 3 CS's: $origin\to LHS\to RHS$\newline (3) Abbreviated or IRR pair with 2 CS's: $origin\to\to RHS$\newline If an RR is of type RR or LL it is related to an irreducible form (a shorter IRR which only involves the symbols passed by the pointer during its execution) as follows. Suppose the RR is represented by $m\to n\to o$ where ${\it m}<{\it n}<{\it o}$ and ${\it n}+{\rm 1}={\it o}$ (where italics represent the corresponding pointer positions for the CS's in typewriter font) so it has type RR, then the rule $n\to o$ can be represented as $n'\to p'\to o'$ without any redundant symbols where ${\it m}\le {\it p}\le{\it n}<{\it o}$ and the primes indicate shortening of the strings by deleting the symbols below position {\it p}. ${\it n}={\it p}$ holds if and only if $n'=p'$ and $n'\to o'$ is a single TM step, and the rule $n'\to p'$ shows that $p'$ is reachable therefore $n'\to p'\to o'$ represents an IRR of type LR, and of course the mirror image result applies to IRR's of type LL. In general let $X$ be a member of IRR({\em n}). Then $X$ can be represented as $A\to B\to C$ where the pointer swaps ends between $A$ and $B$ (thus this is either $1\to n$ or $n\to 1$) to establish the reachability of $B$ necessary for $X$ to be an IRR. There may be more than one such CS $A$ for a single $B$ and the set of all such $A$ will be denoted by $O_1(B)$ (the same as $S(B)$ in \cite{jhn2017}), the 1 referring to the backward searching algorithm that terminates in condition 1 (see \cite{jhn2017} section 2.2) i.e. the pointer swaps ends between $A$ and $B$. (Likewise if it terminates in condition 2 i.e. doesn't swap ends, the set of such endpoints will be denoted as $O_2(B)$, but these do not confer reachability and will not be referred to as origins.) If the pointer is at the right in $A$ and at the left in $B$ then at $C$ it can be at the left or right so that $X$ must be represented as either of the triplet forms $n\to 1\to 0$ or $n\to 1\to n+1$ and having types LL and LR respectively. Likewise if the pointer is at the left in $A$ (the mirror image forms), $X$ must be represented by either of $1\to n\to n+1$ or $1\to n\to 0$, having types RR and RL respectively. If $B$ is reachable but forward computaton from it leads to a CS that has arisen before in this computation, this is an stationary cycle and the type of the IRR is then LC or RC and so $F$ applied to this is the empty set. If the reverse computation path from $B$ leads to a stationary cycle, then this cycle must include $B$ to avoid a branch point in the forward computation that would not then be unique. Thus likewise the IRR is of type $LC$ or $RC$. From the definition of RR in the first paragraph of this section, if in the backward search from the LHS of an IRR, the pointer again reaches the same position it had in the LHS, however much further back the backward search were to continue, it would not be possible to show that this LHS is indeed the LHS of an IRR. This is because if the computation is again run forward, this LHS has the pointer at the same point as a previous CS and is therefore not shown to be one of the list of CS's playing the special role in the above definition, though it could possibly be shown to be one as a result of another backward search path. This is the justification of the terminating condition 2 in the backward search algorithm. This proves that \begin{Lemma}\label{lemma1} The triplets $1\to n\to 0$, $1\to n\to n+1$, and $n\to 1\to n+1$, and $n\to 1\to 0$ representing TM computations each form an IRR {\em (}type RL, RR, LR or LL respectively{\em )} if and only if the origin indicated {\em (}the first member{\em )} is the first one arrived at after tracing the computation back from the LHS {\em (}the middle member{\em )} and the the pointer in the LHS does not occur again in that position in the reverse computation path from the LHS i.e there is no other CS $1$ or $n$ between the $1$ and the $n$. Furthermore any IRR of length {\em n} of one of the above types has one of these forms.\end{Lemma} Generating all the IRR based on Theorem 9.1 of \cite{jhn2013} starts with all single TM steps in the above notation $1\to 0$ (i.e. $\un{x}\to \_x$) or $1\to 2$ (i.e. $\un{x}\to x\_$) where $x$'s represents an arbitrary symbol that could be different for each use. Every possible single symbol (called $\alpha$) is added at the pointer position in each RHS, and in each case the computaton is taken as far as possible to get the new RHS unless a stationary cycle occurs. The resulting rule $LHS\to RHS$ is an IRR if it irreducible i.e. connot be expressed with shorter strings of symbols. In the first case, adding $\alpha$ on the left and continuing the computation as far as possible gives results either of the form (i) $2\to 1\to 3$ or (ii) $2\to 1\to 0$ i.e. $\alpha\un{x}\to\un{\alpha}x\to xx\_\text{ or }\_xx$ respectively unless a stationary cycle is obtained. The results in case (i) are IRR by Lemma~\ref{lemma1} because there can be no other CS's between the $2$ and the $1$ which is a single TM step. The results from (ii) are IRR's if and only if the first move beyond the $1$ is to $2$ i.e. the computation has the form $2\to 1\to 2 \to 0$ because this ensures that the rule $1\to 0$ contained in (ii) of length 2 is irreducible. Likewise for the mirror image case starting with a rule of the form $1\to 2$ adding the $\alpha$ on the right and continuing gives results of the form $1\to 2\to 0$ ($\in \text{IRR}(2)$) or of the form $1\to 2\to 3$ ($\in\text{IRR}(2)$ if and only if the first move from the $2$ is to $1$). Extending this to the general case of generating recursively all the IRR $Y$ of length ${\it n}+{\rm 1}$ based on the single IRR $X$ of length {\em n} and having the form $n\to 1\to n+1$, consider first the computation $A\alpha\to B\alpha\to C\alpha$ where $\alpha$ is any symbol the TM uses. Clearly by Theorems 5.4 and 9.1 of \cite{jhn2013} every such IRR $Y$ can be obtained starting from the LHS $B\alpha$ if an appropriate $\alpha$ can be found. The symbol $\alpha$ must be chosen so that $B\alpha$ is reachable and the origins $O_1(B\alpha)\ne\emptyset$ for it need to be found. These are all the terminal CS's of length ${\it n}+{\rm 1}$ from the backward searching algorithm starting from $B\alpha$ and ending in condition (1). Each of these branches has a point where the pointer first reaches $n$ and this CS is $A\alpha$ because the $\alpha$ has yet played no part, so $O_1(B\alpha)=O_1(A\alpha)$, thus the backward search algorithm is applied to $A\alpha$, and identifying all possible values of $\alpha$ i.e. the values of $\alpha$ for which $O_1(A\alpha)\ne\emptyset$ by generating all its origins for each such $\alpha$. Also the forward computation from $C\alpha$ is continued as far as possible to generate the RHS of $Y$ and hence what its type is (RR, RL, LR, LL, RC, or LC) the last two cases coming from a stationary cycle in the forward computation from $C\alpha$. If the pointer is at the left in $A$ and $C$ and the right in $B$ (the mirror image case) the added arbitrary symbol $\alpha$ will be on the left. This procedure for generating the all the IRR $Y$ of length {\em n}$+1$ like this from an IRR $X$ of length {\em n}, including the mirror image case where the triplet form of $X$ is $1\to n\to 0$, will denoted by the function $F$. This proves that \begin{Theorem}\label{irr_ind_thm} Every member of IRR{\em (}${\it n}+{\rm 1}${\em )} can be obtained using $F$ from some $X\in\text{IRR}${\em (}n{\em )} of type LR or RL. Also, because an the RHS of an IRR is uniquely determined by is LHS, but the origins may be more than one, the sets of IRR obtained like this for different $X$ {\em (}different $B${\em )} must be disjoint i.e. $F^{-1}$ applied to a member of IRR{\em (}${\it n}+{\rm 1}${\em )} is a unique member of IRR{\em (}n{\em )}. The first part can be written symbolically as \begin{equation}\label{irr_ind}\text{IRR}({\it n}+1)=\bigcup _{X\in IRR({\it n})}\{ F(X)\}\end{equation} \end{Theorem} The following is the general outline showing an IRR triplet of length {\em n} of type RLR (type LR with origin having the pointer at the right) as above and the possible types of result (except the cases where a stationary cycle occurs) of this argument for a given symbol $\alpha$ that could include a new IRR triplet of length ${\it n}+{\rm 1}$. \begin{equation}\label{irr_deriv1}\arraycolsep=5pt \left.\mkern-30mu\begin{array}{ccc}\left.\begin{array}{c}\text{Cannot be used to}\\\text{ prove reachability of } 1\end{array}\right\}&1&\to\\\text{Proves reachability of }1&n+1&\to\end{array}\right\}n\to 1\to n+1\left\{\begin{array}{ccc}\to &0&\text{type LL}\\\to &n+2&\text{type LR}\end{array}\right. \end{equation} The 3 central CS's refer to a member of IRR({\em n}), and the leftmost, central, and rightmost CS's refer to the corresponding member of IRR({\em n}$+1$) if reachability of the CS $1$ is found. The corresponding mirror image result for the LRL case is as follows: \begin{equation}\label{irr_deriv2}\arraycolsep=4pt \left.\mkern-30mu\begin{array}{ccc}\text{Proves reachability of }n+1&1&\to\\\left.\begin{array}{c}\text{Cannot be used to}\\\text{ prove reachability of }n+1\end{array}\right\}&n+1&\to\end{array}\right\}2\to n+1\to 1\left\{\begin{array}{ccc}\to &0&\text{type RL}\\\to &n+2&\text{type RR}\end{array}\right. \end{equation} In this case note that because the $\alpha$ is added on the left, all the pointer positions in the IRR of length {\em n} have been increased by 1 when they appear in the embedded IRR of length {\em n}, so originally they would have been $1\to n\to 0$. The above procedure allows the generation of all the IRR of a TM up to any given length and has been implemented \cite{tie}. While deriving an IRR triplet of the form $n+1\to 1\to n+2$ in the notation of \eqref{irr_deriv1} from one of the form $n\to 1\to n+1$ the pointer moves in the backward search in general thus: $n\leftarrow n-k\leftarrow n+1$ (i.e. equivalent to $k+1\leftarrow 1\leftarrow k+2$ or where $k+2$ is the first CS of the form arrived at.) where the CS $n+1$ is the first arrival at such a CS in the backward search because the $n+1$ would terminate the backward search algorithm. It could not reach point $1$ because that would also terminate the backward search algorithm. Therefore ${\rm 0}\le {\it k}\le {\it n}-{\rm 2}$. It is interesting to note that the backward search in general takes the form of an IRR triplet of length ${\it k}+{\rm 1}$ run in reverse by lemma~\ref{lemma1} where $1\le {\it k}+1\le {\it n}-\rm 1$ but crucially only if the direction of computation could be is reversed so this might have no significance. In the remainder of this paper, this procedure will be adapted to the incomplete description of IRR's i.e. IRR patterns with $\ldots$ needed to make the analysis manageable for the example TM, that is expected to have an infinite number of IRR's. This document describes my analysis techniques applied to the following Turing Machine \begin{equation}\label{1} \begin{tabular}{lllll} $1\un{a}\to 2\_d$&$2\un{a}\to 1c\_$&$3\un{a}\to 4c\_$&$4\un{a}\to 3\_b$&$5\un{a}\to 2\_e$\\ $1\un{b}\to 4\_d$&$2\un{b}\to 4\_c$&$3\un{b}\to 4\_c$&$4\un{b}\to 4b\_$&$5\un{b}\to 3\_e$\\ $1\un{c}\to 3\_a$&$2\un{c}\to 1d\_$&$3\un{c}\to 2\_a$&$4\un{c}\to 3c\_$&$5\un{c}\to 3a\_$\\ $1\un{d}\to 2b\_$&$2\un{d}\to 1a\_$&$3\un{d}\to 5\_c$&$4\un{d}\to 5\_c$&$5\un{d}\to 4\_a$\\ $1\un{e}\to 2b\_$&$2\un{e}\to 3\_c$&$3\un{e}\to 3b\_$&$4\un{e}\to 5a\_$&$5\un{e}\to 3a\_$\\ \end{tabular} \end{equation} (TM) which was generated randomly with 5 states and 5 symbols. This TM, being much larger than any that I have analysed before, has proved to be a much more challenging case and will help me refine the procedures for efficiently generating the irreducible regular rules (IRR) from a TM that allowed understandable descriptions of the behaviour of smaller TM's to be found. \section{\label{sec3}Using IRR patterns} IRR patterns (IRRP's) have been found to be very useful because they result in shortening of the lists of cases to be considered because sets of IRR's that match an IRRP often have similar derivations and can be dealt with together. For example in \eqref{irr_deriv1} (and similarly for \eqref{irr_deriv2}) that contains two derivations one of each of the forms $n+1\to n$ and $n+1\to n+2$, often involve one or a small number of TM steps and are indepedent of {\em n}. Also the treatment of IRR's in TM1 in \cite{jhn2017} where sets conforming to the IRRP's could be treated in the same way, allowed a proof of a general method for obtaining all the $IRR({\it n}+1)$ from the $IRR({\it n})$ for all sufficiently large {\em n} for this TM. An IRRP is represented like an IRR but with $\ldots$ or $T_1$ and $T_2$ representing the arbitrary strings, because there are two of them in each IRRP that can be different but have the same length. The IRRP is the set of all results that would be obtained (they will be IRR's) by keeping the fixed values of the given symbols and making arbitrary substitutions for the arbitrary strings that can be any strings of symbols of arbitrary length including zero. An IRRP may be regarded as an abbreviation of an IRR (1) to a fixed length {\em k} of the given strings of symbols, where the symbol at the pointer in the origin is at one end and (2) the original LHS (the middle element in the triplet form of an IRR) is removed completely. The abbreviation is indicated by $\ldots$ or $T_1$ and $T_2$ in place of the deleted symbols in the origin and the RHS. This presentation has the property that the pointer position appears separately in the RHS column if and only if the IRR is of extendable type i.e. type RL or LR, otherwise it appears as an underscore under the $T_2$ indicating that the pointer should be under the first symbol of $T_2$ i.e. adjacent to one of the given symbols. Table~\ref{ind1} is presented in doubled two-column format just for convenience, and has logically just two columns, Origin and RHS's. It was obtained by abbreviating all the IRR(3) to length ${\it k}={\rm 2}$. For this purpose, IRR's with many origins have a separate entry for each origin. This allows the origins to be unique for each row in the table but multiple RHS's from different IRRP's often combined into the same row of Table~\ref{ind1}. An effect of the information loss resulting from representing the IRR's by IRRP's i.e. the truncation of the string of symbols from length {\em n} to length {\em k} that is independent of {\em n}, is that it completely alters the simple description of how to analyse a Turing Machine provided by Theorem~\ref{irr_ind_thm}. This may be thought of as the trade-off for the advantages described above. How this is dealt with is complicated and not easy to describe and is a major theme of this paper. \begin{longtable}{ll|ll} \caption{List of patterns for the IRR(3)\label{ind1}}\\ Origin&RHS's&Origin&RHS's\\\hline $1\un{d}d\ldots$&$4\_cb\ldots$&$5\un{e}e\ldots$&$\{3\_bc\ldots,3ca\ldots\}$\\ $1\un{e}d\ldots$&$4\_cb\ldots$&$3\un{e}e\ldots$&$\{4bc\ldots,4\_ce\ldots\}$\\ $1\un{d}d\ldots$&$4\_ca\ldots$&$4\un{e}c\ldots$&$\{3cb\ldots,1cb\ldots\}$\\ $1\un{e}d\ldots$&$4\_ca\ldots$&$4\un{e}e\ldots$&$\{3cb\ldots,1cb\ldots\}$\\ $1\un{d}a\ldots$&$4\_ca\ldots$&$4\un{c}e\ldots$&$\{1ab\ldots,2\_ae\ldots\}$\\ $1\un{e}a\ldots$&$4\_ca\ldots$&$3\ldots b\un{c}$&$\{4\ldots cc\_,1\ldots bc\_,4\ldots ac\_\}$\\ $1\un{d}c\ldots$&$3\_ec\ldots$&$1\ldots b\un{c}$&$\{4\ldots cc\_,1\ldots bc\_,4\ldots ac\_\}$\\ $1\un{e}c\ldots$&$3\_ec\ldots$&$4\ldots b\un{a}$&$\{2\ldots ab\_,3\ldots bc\_\}$\\ $1\ldots c\un{c}$&$1\ldots bc\_$&$2\ldots b\un{e}$&$\{2\ldots ab\_,1\ldots bd\_,2\ldots db\_\}$\\ $4\ldots c\un{a}$&$3\ldots bc\_$&$1\ldots b\un{a}$&$\{2\ldots db\_,1\ldots ba\_,1\ldots bd\_\}$\\ $2\ldots c\un{e}$&$1\ldots bd\_$&$5\ldots b\un{a}$&$\{3\ldots cb\_,3\ldots cc,3\ldots ab\_\}$\\ $5\ldots c\un{b}$&$\{5\ldots cc,3\ldots cc,1\ldots bd\_\}$&$5\ldots b\un{b}$&$\{3\ldots cb\_,3\ldots cc,3\ldots ab\_\}$\\ $3\ldots a\un{d}$&$1\ldots bd\_$&$4\un{b}b\ldots$&$\{2ba\ldots,4\_ce\ldots\}$\\ $4\ldots a\un{d}$&$1\ldots bd\_$&$3\un{a}b\ldots$&$\{3ab\ldots,2\_ae\ldots\}$\\ $2\un{d}d\ldots$&$3\_bc\ldots$&$5\un{c}a\ldots$&$3db\ldots$\\ $2\un{d}e\ldots$&$3\_bc\ldots$&$5\un{e}a\ldots$&$3db\ldots$\\ $2\un{a}d\ldots$&$1ab\ldots$&$3\un{e}a\ldots$&$4\_ca\ldots $\\ $2\un{a}e\ldots$&$1ab\ldots$&$4\un{c}a\ldots$&$3ab\ldots$\\ $2\un{c}d\ldots$&$5\_cc\ldots$&$1\ldots d\un{c}$&$1\ldots bc\_$\\ $2\un{c}e\ldots$&$5\_cc\ldots$&$4\ldots d\un{a}$&$3\ldots bc\_$\\ $5\ldots a\un{d}$&$\{3\ldots bc\_,4\ldots cc\_\}$&$2\ldots d\un{e}$&$1\ldots bd\_$\\ $2\ldots a\un{b}$&$\{3\ldots bc\_,2\ldots ab\_\}$&$5\ldots d\un{b}$&$5\ldots cc$\\ $3\ldots a\un{b}$&$\{3\ldots bc\_,2\ldots ab\_\}$&$5\ldots d\un{d}$&$1\ldots bc\_$\\ $1\ldots a\un{b}$&$\{2\ldots ec,2\ldots db\_\}$&$2\ldots d\un{b}$&$1\ldots bd\_$\\ $3\ldots e\un{c}$&$4\ldots cc\_$&$3\ldots d\un{b}$&$1\ldots bd\_$\\ $1\ldots e\un{a}$&$2\ldots db\_$&$1\ldots d\un{b}$&$1\ldots ba\_$\\ $5\ldots e\un{a}$&$3\ldots cb\_$&$4\un{b}e\ldots$&$4\_cb\ldots$\\ $3\ldots b\un{d}$&$\{3\ldots aa\_,4\ldots cc\_\}$&$3\un{a}e\ldots$&$2\_ab\ldots$\\ $4\ldots b\un{d}$&$\{3\ldots aa\_,4\ldots cc\_\}$&$3\ldots d\un{d}$&$\{3\ldots cc\_,1\ldots bd\_\}$\\ $5\un{c}e\ldots$&$\{3\_bc\ldots,3ca\ldots\}$&$4\ldots d\un{d}$&$\{3\ldots cc\_,1\ldots bd\_\}$\\ \end{longtable} Treating Table~\ref{ind1} at first as a hypothesis to be proved by induction for IRR of length ${\it n}\ge 3$ suggests (1) following the method in Section~\ref{sec2} to each of the patterns provided they are extendable i.e. of type LR or RL, and then (2) truncating the result to two symbols from the pointer at the new origin so generating another result of the same form as those already in Table~\ref{ind1}. This must be repeated as necessary to ensure closure, i.e. every member of IRRP$({\it n}+{\rm 1})$ truncated to length ${\it k}={\rm 2}$ must also appear as a member of IRRP(${\it n}$) also truncated to length ${\it k}={\rm 2}$. This results in Table~\ref{irr_2r}. Thus an infinite number of IRR could be captured by the resulting recursive description. In these tables the lazy abbreviation is used where $\ldots$ represents any string of symbols of length $\ge 1$ that could be different whenever is used, but really it should be done with say $T_1$ and $T_2$ to represent the two arbitrary strings ($S_1$ and $S_2$ are used later so this notation avoids ambiguity). Thus every application of $F$ as described in Section~\ref{sec2} maps an IRRP in Table~\ref{irr_2r} that has ${\it k}={\rm 2}$ to another IRRP in Table~\ref{irr_2r} unless the backward search procedure to find new origins goes in the unexpected direction i.e. away from the symbol $\alpha$. The analysis for these cases will be taken as far as possible giving results with ${\it k}={\rm 3}$. This issue is taken up again in Section~\ref{sec4}. For example starting from the fifth result in Table~\ref{ind1} \begin{equation}\label{addalpha1}1\un{d}aT_1\to\to4\_caT_2\end{equation} using the backward TM steps from $1\alpha\_$ in \eqref{rev1}, this gives \begin{equation}\label{addalpha2}\begin{tabular}{lccc}deriving the origin&&RHS&$\alpha$\\ $\alpha A$&$\alpha C$&&\\ $1\alpha\un{d}aT_1\left\{\begin{array}{l} \stackrel{\alpha=a}{\leftarrow}2\un{d}daT_1\\ \stackrel{\alpha=c}{\leftarrow}2\un{a}daT_1\\ \stackrel{\alpha=d}{\leftarrow}2\un{c}daT_1\\ \end{array}\right.$& $\begin{array}{l}4\un{a}caT_2\\4\un{c}caT_2\\4\un{d}caT_2\\\end{array}$& $\begin{array}{l}3\_bcaT_2\\1abc\un{T_2}\\5\_ccaT_2\end{array}$&$\begin{array}{l}a\\c\\d\end{array}$ \end{tabular}\end{equation} of which the result for $\alpha=c$ has an RHS given where the pointer is at the first symbol of $T_2$ and needs to be continued until the pointer reaches either end of the string, so it needs to be recorded that this result is incomplete for ${\it k}={\rm 2}$ and the results are truncated to \begin{equation}\label{addalpha3}\begin{array}{l}2\un{d}dT'_1\to\to 3\_bcT'_2\\ 2\un{a}dT'_1\to\to1ab\un{T'_2}\\ 2\un{c}dT'_1\to\to 5\_ccT'_2\end{array}\end{equation} for $\alpha= a,c,d$ respectively, where $T'_1=aT_1$ and $T'_2=aT_2$ for $\alpha\in\{a,d\}$ are the new arbitrary strings. This appears against the IRRP \eqref{addalpha1} in set number 1 of \eqref{irr_2r} using the less precise $\ldots$ notation. Note that in this argument, adding the arbitrary symbol $\alpha$ on the left (because the pointer in the origin is on the left) maintains the pointer being on the right hand end of the string of symbols in the LHS (not shown), and this property is implicit in an IRRP with the pointer at the left of the origin CS. The result of this argument is that if an IRR of length ${\it n}$ conforms to \eqref{addalpha1}, then there are 3 more IRR's of length ${\it n}+{\rm 1}$ corresponding to \eqref{addalpha3} for $\alpha\in\{a,c,d\}$ respectively. The second of these results in \eqref{addalpha3} has the pointer in the RHS on the right (not shown due to truncation), so this IRR has type RR and cannot be used to derive other IRR. These are examples of rules that generate IRR's of length ${\it n}+{\rm 1}$ from other IRR's of length ${\it n}$ and are expressed (for the case where the unknown symbols are on the right) in Table~\ref{irr_2r} for ${\it k}={\rm 2}$. Collectively such rules will be referred to as IRR-generating rules (IGR) to distinguish them from computation rules. An IGR is defined as a logical implication having an IRRP on the left and sets of IRRP's on the right, one set for each value of $\alpha$ and the logical deduction follows the general procedure outlined in Theorem~\ref{irr_ind_thm}. Thus the strings with given symbols on the right of the implications are one symbol longer than those on the left. \fontsize{10}{10}\selectfont \begin{longtable}{c|l@{\hspace{0.5em}}l|c|l@{\hspace{0.5em}}l} \caption{IRRP's of length {\it n} and their derived IRRP's of length ${\it n}+{\rm 1}$, with the unknown symbols on the right.\label{irr_2r}}\\ set&\multicolumn{2}{c|}{IRRP(${\it n}$)}&$\alpha$&\multicolumn{2}{c}{IRRP(${\it n}+1$)}\\ number&Origin&RHS&&Origin&RHS\\ \hline $1$&$1\un{d}a\ldots$&$4\_ca\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}d\ldots$&$1ab\ldots$\\ &&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline $2$&$1\un{d}c\ldots$&$3\_ec\ldots$&$a$&$2\un{d}d\ldots$&$3ca\ldots$\\ &&&$c$&$2\un{a}d\ldots$&$2\_ae\ldots$\\ &&&$d$&$2\un{c}d\ldots$&$5\_ce\ldots$\\\hline $3$&$1\un{d}d\ldots$&$4\_ca\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}d\ldots$&$1ab\ldots$\\ &&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline $4$&$1\un{d}d\ldots$&$4\_cb\ldots$&$a$&$2\un{d}d\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}d\ldots$&$3ab\ldots$\\ &&&$d$&$2\un{c}d\ldots$&$5\_cc\ldots$\\\hline $5$&$1\un{e}a\ldots$&$4\_ca\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}e\ldots$&$1ab\ldots$\\ &&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline $6$&$1\un{e}c\ldots$&$3\_ec\ldots$&$a$&$2\un{d}e\ldots$&$3ca\ldots$\\ &&&$c$&$2\un{a}e\ldots$&$2\_ae\ldots$\\ &&&$d$&$2\un{c}e\ldots$&$5\_ce\ldots$\\\hline $7$&$1\un{e}d\ldots$&$4\_ca\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}e\ldots$&$1ab\ldots$\\ &&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline $8$&$1\un{e}d\ldots$&$4\_cb\ldots$&$a$&$2\un{d}e\ldots$&$3\_bc\ldots$\\ &&&$c$&$2\un{a}e\ldots$&$3ab\ldots$\\ &&&$d$&$2\un{c}e\ldots$&$5\_cc\ldots$\\\hline $9$&$2\un{a}d\ldots$&$2\_ae\ldots$&$b$&$1\un{d}a\ldots$&$4\_ca\ldots$\\ &&&$b$&$1\un{e}a\ldots$&$4\_ca\ldots$\\ &&&$\alpha$&$1\alpha a\un{a}\ldots$&$RHS$\\ \hline $10$&$2\un{a}d\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline $11$&$2\un{a}d\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $12$&$2\un{a}e\ldots$&$2\_ae\ldots$&$b$&$1\un{d}a\ldots$&$4\_ca\ldots$\\ &&&$b$&$1\un{e}a\ldots$&$4\_ca\ldots$\\ &&&$\alpha$&$5\alpha a \un{a}\ldots$&$RHS$\\\hline $13$&$2\un{a}e\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline $14$&$2\un{a}e\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $15$&$2\un{c}d\ldots$&$5\_cc\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\ &&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\ &&&$\alpha$&$1\alpha c\un{a}\ldots$&$RHS$\\\hline $16$&$2\un{c}d\ldots$&$5\_ce\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\ &&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\ &&&$\alpha$&$1\alpha c\un{a}\ldots$&$RHS$\\\hline $17$&$2\un{c}e\ldots$&$5\_cc\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\ &&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\ &&&$\alpha$&$5\alpha c\un{a}\ldots$&$RHS$\\\hline $18$&$2\un{c}e\ldots$&$5\_ce\ldots$&$b$&$1\un{d}c\ldots$&$3\_ec\ldots$\\ &&&$b$&$1\un{e}c\ldots$&$3\_ec\ldots$\\ &&&$\alpha$&$5\alpha c\un{a}\ldots$&$RHS$\\\hline $19$&$2\un{d}d\ldots$&$3\_bc\ldots$&$b$&$1\un{d}d\ldots$&$4\_cb\ldots$\\ &&&$b$&$1\un{e}d\ldots$&$4\_cb\ldots$\\ &&&$\alpha$&$1\alpha d\un{a}\ldots$&$RHS$\\\hline $20$&$2\un{d}d\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline $21$&$2\un{d}e\ldots$&$3\_bc\ldots$&$b$&$1\un{d}d\ldots$&$4\_cb\ldots$\\ &&&$b$&$1\un{e}d\ldots$&$4\_cb\ldots$\\ &&&$\alpha$&$5\alpha d\un{a}\ldots$&$RHS$\\\hline $22$&$2\un{d}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline $23$&$3\un{a}b\ldots$&$2\_ae\ldots$&$a$&$5\un{c}a\ldots$&$5\_cc\ldots$\\ &&&$a$&$5\un{e}a\ldots$&$5\_cc\ldots$\\ &&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\ &&&$c$&$4\un{c}a\ldots$&$3\_bc\ldots$\\ &&&$\alpha$&$4\alpha a\un{a}\ldots$&$RHS$\\\hline $24$&$3\un{a}b\ldots$&$3\_bc\ldots$&$a$&$5\un{c}a\ldots$&$3cb\ldots$\\ &&&$a$&$5\un{e}a\ldots$&$3cb\ldots$\\ &&&$b$&$3\un{e}a\ldots$&$4\_cb\ldots$\\ &&&$c$&$4\un{c}a\ldots$&$2\_ab\ldots$\\ &&&$\alpha$&$4\alpha a\un{a}\ldots$&$RHS$\\\hline $25$&$3\un{a}b\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline $26$&$3\un{a}b\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $27$&$3\un{a}c\ldots$&$2\_ab\ldots$&$a$&$5\un{c}a\ldots$&$3db\ldots$\\ &&&$a$&$5\un{e}a\ldots$&$3db\ldots$\\ &&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\ &&&$c$&$4\un{c}a\ldots$&$3ab\ldots$\\ &&&$\alpha$&$2\alpha a\un{e}\ldots$&$RHS$\\\hline $28$&$3\un{a}c\ldots$&$3\_bc\ldots$&$a$&$5\un{c}a\ldots$&$3cb\ldots$\\ &&&$a$&$5\un{e}a\ldots$&$3cb\ldots$\\ &&&$b$&$3\un{e}a\ldots$&$4\_cb\ldots$\\ &&&$c$&$4\un{c}a\ldots$&$2\_ab\ldots$\\ &&&$\alpha$&$2\alpha a\un{e}\ldots$&$RHS$\\\hline $29$&$3\un{a}c\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $30$&$3\un{a}e\ldots$&$2\_ab\ldots$&$a$&$5\un{c}a\ldots$&$3db\ldots$\\ &&&$a$&$5\un{e}a\ldots$&$3db\ldots$\\ &&&$b$&$3\un{e}a\ldots$&$4\_ca\ldots$\\ &&&$c$&$4\un{c}a\ldots$&$3ab\ldots$\\ &&&$\alpha$&$5\alpha a\un{b}\ldots$&$RHS$\\\hline $31$&$3\un{a}e\ldots$&$1db\ldots$&$\emptyset$&$\emptyset$\\ \hline $32$&$3\un{e}a\ldots$&$4\_ca\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\ &&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\ &&&$b$&$3\un{e}e\ldots$&$4bc\ldots$\\ &&&$c$&$4\un{c}e\ldots$&$1ab\ldots$\\ &&&$\alpha$&$1\alpha e\un{c}\ldots$&$RHS$\\\hline $33$&$3\un{e}a\ldots$&$4\_cb\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\ &&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\ &&&$b$&$3\un{e}e\ldots$&$2ba\ldots$\\ &&&$c$&$4\un{c}e\ldots$&$3ab\ldots$\\ &&&$\alpha$&$1\alpha e\un{c}\ldots$&$RHS$\\\hline $34$&$3\un{e}e\ldots$&$4\_ce\ldots$&$a$&$5\un{c}e\ldots$&$3\_bc\ldots$\\ &&&$a$&$5\un{e}e\ldots$&$3\_bc\ldots$\\ &&&$b$&$3\un{e}e\ldots$&$3bc\ldots$\\ &&&$c$&$4\un{c}e\ldots$&$3\_bc\ldots$\\ &&&$\alpha$&$5\alpha e\un{b}\ldots$&$RHS$\\\hline $35$&$3\un{e}e\ldots$&$2ba\ldots$&$\emptyset$&$\emptyset$\\\hline $36$&$3\un{e}e\ldots$&$3bc\ldots$&$\emptyset$&$\emptyset$\\\hline $37$&$3\un{e}e\ldots$&$4bc\ldots$&$\emptyset$&$\emptyset$\\\hline $38$&$4\un{b}b\ldots$&$4\_ce\ldots$&$b$&$4\un{b}b\ldots$&$3bc\ldots$\\ &&&$c$&$3\un{a}b\ldots$&$3\_bc\ldots$\\\hline $39$&$4\un{b}b\ldots$&$2ba\ldots$&$\emptyset$&$\emptyset$\\\hline $40$&$4\un{b}b\ldots$&$3bc\ldots$&$\emptyset$&$\emptyset$\\\hline $41$&$4\un{b}b\ldots$&$4bc\ldots$&$\emptyset$&$\emptyset$\\\hline $42$&$4\un{b}c\ldots$&$4\_ca\ldots$&$b$&$4\un{b}b\ldots$&$4bc\ldots$\\ &&&$c$&$3\un{a}b\ldots$&$1ab\ldots$\\ &&&$\alpha$&$2\alpha b\un{b}\ldots$&$RHS$\\ &&&$\alpha$&$3\alpha b\un{b}\ldots$&$RHS$\\\hline $43$&$4\un{b}c\ldots$&$4\_cb\ldots$&$b$&$4\un{b}b\ldots$&$2ba\ldots$\\ &&&$c$&$3\un{a}b\ldots$&$3ab\ldots$\\ &&&$\alpha$&$2\alpha b\un{b}\ldots$&$RHS$\\ &&&$\alpha$&$3\alpha b\un{b}\ldots$&$RHS$\\\hline $44$&$4\un{b}e\ldots$&$4\_cb\ldots$&$b$&$4\un{b}b\ldots$&$2ba\ldots$\\ &&&$c$&$3\un{a}b\ldots$&$3ab\ldots$\\\hline $45$&$4\un{b}e\ldots$&$4\_ce\ldots$&$b$&$4\un{b}b\ldots$&$3bc\ldots$\\ &&&$c$&$3\un{a}b\ldots$&$3\_bc\ldots$\\\hline $46$&$4\un{c}a\ldots$&$2\_ab\ldots$&$b$&$4\un{b}c\ldots$&$4\_ca\ldots$\\ &&&$c$&$3\un{a}c\ldots$&$3ab\ldots$\\ &&&$\alpha$&$5\alpha c\un{d}\ldots$&$RHS$\\\hline $47$&$4\un{c}a\ldots$&$3\_bc\ldots$&$b$&$4\un{b}c\ldots$&$4\_cb\ldots$\\ &&&$c$&$3\un{a}c\ldots$&$2\_ab\ldots$\\ &&&$\alpha$&$5\alpha c\un{d}\ldots$&$RHS$\\\hline $48$&$4\un{c}a\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $49$&$4\un{c}e\ldots$&$2\_ae\ldots$&$b$&$4\un{b}c\ldots$&$4\_ca\ldots$\\ &&&$c$&$3\un{a}c\ldots$&$3\_bc\ldots$\\\hline $50$&$4\un{c}e\ldots$&$3\_bc\ldots$&$b$&$4\un{b}c\ldots$&$4\_cb\ldots$\\ &&&$c$&$3\un{a}c\ldots$&$2\_ab\ldots$\\\hline $51$&$4\un{c}e\ldots$&$1ab\ldots$&$\emptyset$&$\emptyset$\\\hline $52$&$4\un{c}e\ldots$&$3ab\ldots$&$\emptyset$&$\emptyset$\\\hline $53$&$4\un{e}c\ldots$&$2\_ec\ldots$&$b$&$4\un{b}e\ldots$&$4\_ce\ldots$\\ &&&$c$&$3\un{a}e\ldots$&$1db\ldots$\\ &&&$\alpha$&$2\alpha e\un{b}\ldots$&$RHS$\\ &&&$\alpha$&$3\alpha e\un{b}\ldots$&$RHS$\\\hline $54$&$4\un{e}c\ldots$&$1cb\ldots$&$\emptyset$&$\emptyset$\\\hline $55$&$4\un{e}c\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline $56$&$4\un{e}e\ldots$&$2\_ec\ldots$&$b$&$4\un{b}e\ldots$&$4\_ce\ldots$\\ &&&$c$&$3\un{a}e\ldots$&$1db\ldots$\\\hline $57$&$4\un{e}e\ldots$&$1cb\ldots$&$\emptyset$&$\emptyset$\\\hline $58$&$4\un{e}e\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline $59$&$5\un{c}a\ldots$&$5\_cc\ldots$&$a$&$4\un{e}c\ldots$&$2\_ec\ldots$\\\hline $60$&$5\un{c}a\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline $61$&$5\un{c}a\ldots$&$3db\ldots$&$\emptyset$&$\emptyset$\\\hline $62$&$5\un{c}e\ldots$&$3\_bc\ldots$&$a$&$4\un{e}c\ldots$&$3cb\ldots$\\\hline $63$&$5\un{c}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline $64$&$5\un{e}a\ldots$&$5\_cc\ldots$&$a$&$4\un{e}e\ldots$&$2\_ec\ldots$\\\hline $65$&$5\un{e}a\ldots$&$3cb\ldots$&$\emptyset$&$\emptyset$\\\hline $66$&$5\un{e}a\ldots$&$3db\ldots$&$\emptyset$&$\emptyset$\\\hline $67$&$5\un{e}e\ldots$&$3\_bc\ldots$&$a$&$4\un{e}e\ldots$&$3cb\ldots$\\\hline $68$&$5\un{e}e\ldots$&$3ca\ldots$&$\emptyset$&$\emptyset$\\\hline \end{longtable} \fontsize{12}{14}\selectfont \section{\label{section4}Reformulating the generation of new IRR's from existing ones in terms of IRR generating rules} In order to understand how IRR's can be generated from others, the following IRR of length 6 was chosen from the computer program output and represented in $\text{Origin}\to\text{LHS}\to\text{RHS}$ format as follows: \begin{equation}\label{eq130}3\un{a}ecccb\to1cadbd\un{b}\to 2dbdbdb\_.\end{equation} The derivation of the first rule of \eqref{eq130} in single TM steps is \begin{equation}\begin{array}{l}3\un{a}ecccb\\4c\un{e}cccb\\5ca\un{c}ccb\\3caa\un{c}cb\\2ca\un{a}acb\\1cac\un{a}cb\\ 2ca\un{c}dcb\\1cad\un{d}cb\\2cadb\un{c}b\\1cadbd\un{b}\end{array}.\end{equation} Each time the pointer moves to where it has not been before while going backwards from the LHS, it generates IRR's as follows in triplet and the abbreviated notation: \begin{equation}\label{irr_array}\begin{array}{cc}\begin{array}{l} 2\un{c}b\to1d\un{b}\to5\_cd\in IRR(2)\\ 1\un{d}cb\to 1bd\un{b}\to 3\_ecd\in IRR(3)\\ 2\un{c}dcb\to 1dbd\un{b}\to 5\_cecd\in IRR(4)\\ 4\un{e}cccb\to 1adbd\un{b}\to 2\_ececd\in IRR(5)\\\end{array}& \begin{array}{l}2\un{c}b\to\to5\_cd\\1\un{d}cb\to\to3\_ecd\\2\un{c}dcb\to\to 5\_cecd\\4\un{e}cccb\to\to2\_ececd\end{array}\end{array}. \end{equation} This splitting up of the derivation of \eqref{eq130} results from the repeated application of $F$ to \eqref{irr_array}.1. The abbreviated forms in \eqref{irr_array} can be obtained by applying in order the following results to the first of these IRR's $2\un{c}b\to\to5\_cd$. \begin{equation}\label{f2_array}\begin{array}{l}2\un{T}_1\to\to 5\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{d}T_{\rm 1}\\1\un{e}T_{\rm 1}\end{array}\right\}\to\to 3\_eT_{\rm 2}\\[15pt] 1\un{T}_1\to\to 3\_T_{\rm 2}\left\{\begin{array}{l}\stackrel{a}{\Rightarrow} 2\un{d}T_{\rm 1}\to\to 4c\un{T}_{\rm 2}\\\stackrel{c}{\Rightarrow} 2\un{a}T_{\rm 1}\to\to 2\_aT_{\rm 2}\\\stackrel{d}{\Rightarrow}2\un{c}T_{\rm 1}\to\to 5\_cT_{\rm 2}\end{array}\right.\\[23pt] 2\un{c}dT_{\rm 1}\to\to 5\_T_{\rm 2}\stackrel{a}{\Rightarrow}\left.\begin{array}{l}4\un{e}ccT_{\rm 1}\\4\un{e}ecT_{\rm 1}\\5\un{c}adT_{\rm 1}\\5\un{e}adT_{\rm 1}\end{array}\right\}\to\to2\_eT_{\rm 2}\\[30pt] 4\un{T}_{\rm 1}\to\to2\_eT_{\rm 2}\stackrel{c}{\Rightarrow} \left.\begin{array}{l}3\un{a}T_{\rm 1}\\4\un{b}T_{\rm 1}\end{array}\right\}\to\to2db\un{T}_{\rm 2}\end{array}.\end{equation} For the derivation of \eqref{eq130}, the following subcases of successive members of \eqref{f2_array} need to be applied in this order: 1, 3, 1, 1. Equation \eqref{f2_array} contains examples of IGR's (IRR generating rules) which allow one IRR to be derived from another by substituting for the $T_{\rm 1}$ and $T_{\rm 2}$ as the example shows, and express the application of the function $F$ in Theorem~\ref{irr_ind_thm} in a simpler form. The IGR's have two lengths, one associated with $T_{\rm 1}$ and one associated with $T_{\rm 2}$ and these the lengths of the corresponding strings on the RHS of the IGR thus for example the lengths of the IGR's in \eqref{f2_array} will be donoted by ${\rm (1,1), (1,1), (3,1), (1,2)}$ respectively. The equations \eqref{f2_array} are in the shortest forms possible as can be verified from their derivations. The symbols above the implication signs are the symbol added next to the pointer in the origin ($\alpha$) in the derivation of the IRR's from other ones as described in Section~\ref{sec2}, and are the first 4 symbols of the LHS of IRR \eqref{eq130} taken in reverse order. The results on the right in \eqref{f2_array} are all the results that can be derived from their LHS for that value of $\alpha$ and that length, though the third example is quite complicated and has other values of $\alpha$ ie. $b$ and $c$ with different lengths of results. The IRRP on the RHS of the last member of \eqref{f2_array} is of type RR and can be seen to not generate a new IRR directly. Applying the last member of \eqref{f2_array} to the last IRR of \eqref{irr_array} gives the initial result \begin{equation}3\un{a}ecccb\to1cadbd\un{b}\to2db\un{c}ecd\end{equation} which is not an IRR. Taking this computation as far a possible has to be an IRR (in this case having non-extendable type RR) which is \begin{equation}\label{final}3\un{a}ecccb\to\to 2dbdbdb\_\end{equation} and has $\alpha =c$ and is in agreement with \eqref{eq130}. The derivations of \eqref{irr_array} and \eqref{final} illustrate the general procedure for deriving any IRR by repeated applications of $F$ starting from a member of IRR(2). This example suggests that if all the IGR's needed to generate the IRR$({\it n}+{\rm 1})$ from IRR$({\it n})$ were obtained, these could have lengths much less than ${\it n}+{\rm 1}$ and be fewer in number than the IRR$({\it n}+{\rm 1})$, and this might give a more compact way to represent the action of the TM. This will be followed up later, but many details need to be given first. \section{Definition of IGR's} The general form of the derivation of an IRR from an existing one ($F$) can be expressed in more detail as follows. Start with the IRR pattern (IRRP) of type RL\begin{equation}\label{igr0}t_{\rm 1}\un{y_{\rm 1}}\ldots y_{{\it n}}\to\to t_{\rm 2}\_z_{\rm 1}\ldots z_{{\it n}}\end{equation} where ${\it n}\ge {\rm 2}$ and the $t$'s are machine states and $y$'s and $z$'s are symbols. Then proceed with $F$ i.e. add the symbol $\alpha$ to both sides where the pointer is in the RHS then the backward search gives the following types of results (excluding the stationary cycles) which can be classified according to the rightmost position ${\it j}_{\rm 1}$ of the pointer relative to the symbol $y_{\rm 1}$ \begin{equation}\label{igr1}t_{\rm 1}\alpha \un{y_{\rm 1}}\ldots y_{\it n}\leftarrow \left\{\begin{array}{l} t'_{\rm 1}\un{\alpha'}y_{\rm 1}\ldots y_{\it n}\text{ for }{\it j}_{\rm 1} = {\rm 0}\vspace{0.5em}\\ t'_{\rm 1}\un{\alpha'}y'_{\rm 1}\ldots y'_{{\it j}_{\rm 1}+{\rm 1}}y_{{\it j}_{\rm 1}+{\rm 2}}\ldots y_{\it n}\text{ for }{\rm 1}\le {\it j}_{\rm 1}\le {\it n-{\rm 2}}\vspace{0.5em}\\ t'_{\rm 1}\alpha y'_{\rm 1}\ldots y'_{{\it n}-{\rm 1}}\un{y'_{\it n}}\text{ for }{\it j}_{\rm 1}={\it n - {\rm 1}}\end{array}\right.\end{equation} where the primes indicate a possible change in the symbol or state by the TM. For the case ${\it n}={\rm 1}$, ${\it j}_{\rm 1}$ must be 0. The point of the classification is to distinguish all the different types of cases that can arise after all the symbols that are not altered in the derivation are abstracted out. They are not mentioned explicitly and they form part of an arbitrary string (in this case $T_{\rm 1}$). The last reverse computation step in the last case giving ${\it j}_{\rm 1}={\it n} - {\rm 1}$ cannot not lead to a new IRR because this path and the CS reached does not imply the reachability of the LHS and so does not generate an IRR. If the LHS is reachable it must be because there is another origin with ${\it j}_{\rm 1} < {\it n} - 1$. Therefore this case must be omitted for the purpose of generating IGR's, so ${\it j}_1$ can be restricted to the range ${\rm 0}\le {\it j}_{\rm 1}\le{\it n-{\rm 2}}$. Similarly, for the computation of the new RHS, the results can be classified (again excluding stationary cycles) by the rightmost position ${\it j}_{\rm 2}$ of the pointer. So that this parameter also starts at 0, the pointer starts at position 0 at $\alpha$ and ends at position $-{\rm 1}$ if it goes left and ends at position ${\it n}+{\rm 1}$ if it goes right giving the possibilities \begin{equation}\label{igr2}t_{\rm 2}\un{\alpha}z_{\rm 1}\ldots z_{\it n}\to \left\{\begin{array}{l}t'_{\rm 2}\_\alpha' z'_{\rm 1}\ldots z'_{{\it j}_{\rm 2}}z_{{\it j}_{\rm 2}+{\rm 1}}\ldots z_{\it n}\text{ where }{\rm 0}\le {\it j}_{\rm 2}\le {\it n}\text{ or }\vspace{0.5em}\\ t'_{\rm 2}\alpha'z'_{\rm 1}\ldots z'_{\it n}\_\text{ if }{\it j}_{\rm 2}={\it n}+{\rm 1}\end{array}\right..\end{equation} This works whenever ${\it n}\ge{\rm 1}$. If a stationary cycle occurred in \eqref{igr1} it would be noted, but it would have no effect on the general form of the possible results except that none of the forms of endpoint in \eqref{igr1} might result, because a stationary cycle would result in a closed circuit in the reverse search path from which paths ending in a type of endpoint in \eqref{igr1} or none could diverge. As noted earlier this would imply $t_1\alpha\un{y_1}\ldots y_{\it n}$ is in the closed circuit (to avoid a branch point in the forward computation implying it is not unique) so the derived IRR would have type RC. Likewise for a stationary cycle in the result of \eqref{igr2}. The minimum number of symbols needed for the representation of \eqref{igr1} is easily seen to be \begin{equation}\label{r1}{\it r}_{\rm 1}=\left\{\begin{array}{ll}{\rm 1}&\text{ for } {\it j}_{\rm 1}={\rm 0}\\ {\it j}_{\rm 1}+{\rm 2}&\text{ otherwise}\end{array}\right.\end{equation} provided ${\rm 0}\le {\it j}_{\rm 1}\le{\it n-{\rm 2}}$. Similarly, the minimum number of symbols needed for the representation of the result of \eqref{igr2} is \begin{equation}\label{r2}{\it r}_{\rm 2}=\text{min}({\it j}_{\rm 2}+{\rm 1},{\it n}+{\rm 1}).\end{equation} The remaining four combinations can be summarised as \begin{equation}\label{igr_types}\begin{array}{l} \left\{\begin{array}{c}t_{\rm 1}\un{T_{\rm 1}}\\ t_{\rm 1}\un{y}_{\rm 1}\ldots y_{{\it j}_{\rm 1}+1}T_{\rm 1}\end{array}\right\}\to\to \left\{\begin{array}{c} t_{\rm 2}\_z_{\rm 1}\ldots z_{{\it j}_{\rm 2}}T_{\rm 2}\\ t_{\rm 2}\_z_{\rm 1}\ldots z_{\it n}T_{\rm 2}\end{array}\right\} \stackrel{\alpha}{\Rightarrow}\vspace{0.5em}\\ \left\{\begin{array}{c}t'_{\rm 1}\un{\alpha'}T_{\rm 1}\\ t'_{\rm 1}\un{\alpha'}y'_{\rm 1}\ldots y'_{{\it j}_{\rm 1}+1}T_{\rm 1}\end{array}\right\}\to\to \left\{\begin{array}{c}t'_{\rm 2}\_\alpha'z'_{\rm 1}\ldots z'_{{\it j}_{\rm 2}}T_{\rm 2}\\ t'_{\rm 2}\alpha'z'_{\rm 1}\ldots z'_{\it n}\un{T_{\rm 2}}\end{array}\right\}\end{array}. \end{equation} In this statement the top and bottom parts on the left of$\to\to$ can be combined independently with the top and bottom parts on the right of$\to\to$ i.e. there are four combinations possible. Each of these is a type of IGR that can be obtained and are distinguished by different pairs $({\it j}_{\rm 1},{\it j}_{\rm 2})$. The corresponding right-left reversed results starting from an IRRP set of type RLR also involve the parameters ${\it j}_{\rm 1}$ and ${\it j}_{\rm 2}$ obtained similarly but counting leftwards. Thus starting from \begin{equation}\label{igr0.2}t_{\rm 1}y_{\it n}\ldots \un{y_{{\rm 1}}}\to\to t_{\rm 2}z_{\it n}\ldots z_{\rm 1}\_\end{equation} likewise the following types of results are obtained: which can be classified according to the leftmost position relative to $y_{\rm 1}$, ${\it j}_{\rm 1}$ of the pointer. This satisfies ${\rm 0}\le {\it j}_{\rm 1}\le {\it n} - {\rm 1}$ and gives the following: \begin{equation}\label{igr1.2}t_{\rm 1}y_{\it n}\ldots \un{y_{\rm 1}}\alpha\leftarrow \left\{\begin{array}{l} t'_{\rm 1}y_{\it n}\ldots y_{\rm 1}\un{\alpha'}\text{ for }{\it j}_{\rm 1} = {\rm 0}\vspace{0.5em}\\ t'_{\rm 1}y_{\it n}\ldots y_{{\it j}_{\rm 1}+{\rm 2}}y'_{{\it j}_{\rm 1}+{\rm 1}}\ldots y'_{\rm 1}\un{\alpha'}\text{ for }{\rm 1}\le {\it j}_{\rm 1}\le {\it n}-{\rm 2}\vspace{0.5em}\\ t'_{\rm 1}\un{y'_{\it n}}y'_{{\it n} - {\rm 1}}\ldots y'_{\rm 1}\alpha \text{ for }{\it j}_{\rm 1}={\it n} -{\rm 1}\end{array}\right.\end{equation} Naturally, \eqref{r1} and \eqref{r2} and are still valid and \eqref{igr_types} have corresponding mirror image forms. %and have the respective forms\\ %$1\to r_1\to 2\to n+1\to 1\to r_2\to 0$\\ %$1\to r_1\to 2\to n+1\to 1\to n+2$\\ %where the numbers (see \eqref{irr_deriv2}) indicate CS's where the pointer position is at some extreme points in the computation and $\alpha$ is this time at position 1 because it is the first symbol of the derived IRRP. These are the results expressed with the shortest strings of symbols possible (i.e. the $y$'s and $z$'s), with the strings $T_{\rm 1}$ and $T_{\rm 2}$ being arbitrary, so can be replaced by any strings. They do not have to have the same length. The length of an IGR consists of the pair $({\it r}_{\rm 1},{\it r}_{\rm 2})$. These together with their left-right reversed forms are all the different types of IGR's. Simple examples of these are in \eqref{f2_array}, and \eqref{igr1} and \eqref{igr2} indicate the general method for deriving them which is as follows. After the symbol $\alpha$ has been added to the origins on the left, reverse steps of the TM are made recursively, using \eqref{rev1} making sure that all possible reverse steps at each stage are done and stopping only when further reverse steps are impossible without the knowledge of what the strings $T_{\rm 1}$ and $T_{\rm 2}$ are, as described in Section~\ref{sec2}, except that a final reverse step that would lead to the pointer ending at the opposite end of the string from $\alpha$ is not done because that does not represent an IRR (c.f. \eqref{igr1}.3). Thus an IGR is defined to have no redundant symbols where the pointer does not reach during its derivation. This is analogous to IRR's being irreducible. In the derivation of the IGR from an IRR of length ${\it n}$, the backward search to obtain the new origins and in the forward computation to obtain the rew RHS, the pointer can obviously never move outside the strings of lengths ${\it r_{\rm 1}}$ and ${\it r_{\rm 2}}$ introduced above, and moreover all these positions of the pointer are reached during the derivation, the string of length ${\it r_{\rm 1}}$ for the derivation of a new origin and the string of length ${\it r_{\rm 2}}$ for the derivation of the new RHS except that for the last machine step obtaining the new RHS that can take the pointer just outside it, the pointer ends up at one end of the string $T_{\rm 2}$ and is indicated by $\un{T_{\rm 2}}$ with the pointer position clear from the context. Therefore the number of symbols retained for each new origin found and RHS must be ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ as defined in Equations~\eqref{r1} and \eqref{r2}. The pair of strings of symbols $(T_{\rm 1},T_{\rm 2})$ of lengths $({\it n}+{\rm 1}-{\it r_{\rm 1}},{\it n}+{\rm 1}-{\it r_{\rm 2}})$ respectively in \eqref{igr_types} that are not passed by the pointer during the derivation of an IGR from an IRR of length ${\it n}$ that is the basis of its LHS will be removed and listed as ``context pairs" so that the result is presented in its minimal form i.e. as an IGR in computer output. Note that in \eqref{igr_types} these results are still valid whatever the strings $T_{\rm 1}$ and $T_{\rm 2}$ and their lengths are. A IGR could be defined to include all the possible results that can be derived for any possible value of $\alpha$ (an IGR member), and all the possible origins for each $\alpha$, but if there is not likely to be confusion I will refer to such statements as IGR's as was done above. Thus an IGR would be the union over $\alpha$ of the IGR members. An IGR member has the form (IRRP,$\alpha$) $\Rightarrow$ set of IRRP's, so the above IGR's could be described as IGR members. Thus it would be possible for different RHS's of the IGR to have different values of ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ corresponding to different values of $\alpha$, but these will be separated into different IGR's. There can be a problem that occurs in the computer representation of the IGR's after the context strings have been separated out, which is to determine whether the original IRRP set on its left is of type LRL or RLR. Provided ${\it n }>1$, it is not immediately obvious which is the case because the pointer positions and the parameter ${\it j}_{\rm 1}$ can be counted going either way, for example compare \eqref{igr1} with \eqref{igr1.2}. The way it works is that a CS in the computer program output is represented as $CS(t,p,l,string)$ where $t$ is the machine state, $p$ is the pointer position counted from the left and is one for the symbol on the left, and is 0 for the position just to the left of this symbol, and is $l+{\rm 1}$ for the position just to the right of the string, where $l={\it n}$ is the length of the string which is spelled out inside quote marks in printed output. After the context strings have been split out of the derived IGR, the pointer position in the origin of the IRRP set on the LHS of the IGR is 1 if the original IRRP set (the LHS of the new IGR) was of type LRL because the pointer starts at 1 and is not affected by the truncation of the symbols from the right. If the the original IRRP set was of type RLR, the pointer position in its origin is initially at ${\it n}$ (i.e. the right hand end) and is reduced as a result of applying splitting out the context symbols. This for ${\it j}_{\rm 1}={\rm 0}$ is position ${\it n}$ minus the length of the string of symbols removed also ${\it n}$ i.e. {\rm 0}, and is ${\it n}$ minus the length of $y_{\it n}\ldots y_{{\it j}_{\rm 1} + 2}$ otherwise, which is ${\it j}_{\rm 1} + {\rm 1}$. This value can never be 1, so the value 1 is characteristic of the original IGR being of type LRL. This implies that the value $p = 1$ in an origin CS on the LHS of an IGR indicates, provided ${\it n}>1$, that the context strings ($T_1$ and $T_2$) are added on the right, and on the left otherwise. For the case ${\it n}=1$ this is obvious from the RHS of the IRRP\_set on the LHS of the IGR. The above argument shows, when combined with Theorem~\ref{irr_ind_thm}, that\\ (1) every IRR of length ${\it n}+{\rm 1}$ of type RL can be derived by $F$ from another IRR of length ${\it n}$ of type RL by an IGR with parameters ${({\it r}_{\rm 1},{\it r}_{\rm 2})}$ of type \eqref{igr_types}.1 satisfying ${\rm 1}\le\it r_{\rm 1}\le{\it n}$ and ${\rm 1}\le{\it r}_{\rm 2}\le{\it n}+{\rm 1}$ as described and\\(2) every IRR of length ${\it n}+{\rm 1}$ of type RR can be derived by $F$ from another IRR of length ${\it n}$ of type RL by an IGR of type \eqref{igr_types}.2 with parameters ${\it r}_{\rm 1}$ and ${\it r}_{\rm 2}$ such that ${\rm 1}\le\it r_{\rm 1}\le{\it n}$ and ${\it r}_{\rm 2}={\it n}+{\rm 1}$. These can be applied recursively to show that \begin{Theorem}any extendable IRR (type RL or LR) of length $\ge {\it 3}$ can be obtained from a member of IRR(2) by a sequence of substitutions of IGR's as described here under case (1). Any non-extendable IRR (type LL or RR) can be obtained from a member of IRR(2) by the above substitutions (0 or more) followed by a single substitution step under case (2). \end{Theorem} This theorem is illustrated by the example at the beginning of this section. \newline This suggests the obvious process for generating the set of all the IGR's could start as follows after finding all the members of IRR(2). Find all the members of IRR(3) and the IGR's used to generate them from the IRR(2). These will be IGR's of lengths $({\rm 1,1})$, $({\rm 1,2})$, $({\rm 1,3}), ({\rm 2,1})$, $({\rm 2,2})$, and $({\rm 2,3})$. Likewise the IRR(4) can be obtained from the IRR(3) and the IGR's summarising this can be added while not duplicating any IGR's already found etc.. This can be repeated to generate up to the IRR(${\it n}$). After a while hopefully to generate the ${\rm IRR}({\it n}+{\rm 1})$ from the ${\rm IRR}({\it n})$ will not require any IGR's that have not already been obtained for ${\it n}$ sufficiently large. This has almost been done by a computer program. It just remains to allow in it the possibility that $T_{\rm 1}$ and $T_{\rm 2}$ can have different lengths. Describe new program and how the IGR's were obtained starting with the ones with contexts present. \newpage \fontsize{10}{10}\selectfont \begin{longtable}{ll} \caption{IGR's generated by the computer program\label{table3}}\\ 1&$1\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 3\_bT_2$\\ 2&$1\un{c}aT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1\to\to 3\_bT_2$\\ 3&$1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{a}baa\\1\un{a}bab\end{array}\right\}T_1\to\to 3\_bT_2$\\ 4&$1\un{c}ababT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccbT_1\to\to 3\_bT_2$\\ 5&$1\un{c}ababcT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccacT_1\to\to 3\_bT_2$\\ 6&$1\un{c}abcT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}ccac\\2\un{a}ccbc\end{array}\right\}T_1\to\to 3\_bT_2$\\ 7&$1\un{c}cT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}bcT_1\to\to 3\_bT_2$\\ 8&$2\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 3\_bT_2$\\ 9&$3\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}2\un{a}T_1\to\to 3\_bT_2$\\ 10&$3\un{T_1}\to\to 1\_aT_2\stackrel{c}{\Rightarrow}3\un{c}T_1\to\to 2bb\un{T_2}$\\ 11&$1\un{c}cT_1\to\to 1\_ababT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3bbbbb\un{T_2}$\\ 12&$1\un{c}aT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3\_bababaT_2$\\ 13&$1\un{c}aaT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}2\un{b}baa\\2\un{b}bab\end{array}\right\}T_1\to\to 3\_bababaT_2$\\ 14&$1\un{c}ababT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccb\to\to 3\_bababaT_2$\\ 15&$1\un{c}ababcT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bbccacT_1\to\to 3\_bababaT_2$\\ 16&$1\un{c}abcT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ccac\\3\un{c}ccbc\end{array}\right\}T_1\to\to 3\_bababaT_2$\\ 17&$1\un{c}cT_1\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3\_bababaT_2$\\ 18&$2\un{T_1}\to\to 1\_ababaT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3\_bababaT_2$\\ 19&$1\un{c}cT_1\to\to 1\_ababcT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3bbbbbc\un{T_2}$\\ 20&$1\un{c}aT_1\to\to 1\_abcT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3\_bbbb\un{T_2}$\\ 21&$2\un{T_1}\to\to 1\_cT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 1bb\un{T_2}$\\ 22&$1\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 1\_aT_2$\\ 23&$1\un{c}aT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}ca\\2\un{a}cb\end{array}\right\}T_1\to\to 1\_aT_2$\\ 24&$1\un{c}aaT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}baa\\2\un{a}bab\end{array}\right\}T_1\to\to 1\_aT_2$\\ 25&$1\un{c}ababT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccbT_1\to\to 1\_aT_2$\\ 26&$1\un{c}ababcT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bbccacT_1\to\to 1\_aT_2$\\ 27&$1\un{c}abcT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}ccac\\2\un{a}ccbc\end{array}\right\}T_1\to\to 1\_aT_2$\\ 28&$1\un{c}cT_1\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}bcT_1\to\to 1\_aT_2$\\ 29&$2\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 1\_aT_2$\\ 30&$3\un{T_1}\to\to 3\_T_2\stackrel{b}{\Rightarrow}1\un{a}T_1\to\to 1\_aT_2$\\ 31&$2\un{T_1}\to\to 3\_baT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3bbb\un{T_2}$\\ 32&$2\un{c}aT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 3\_babaT_2$\\ 33&$1\un{c}aaT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}2\un{b}baa\\2\un{b}bab\end{array}\right\}T_1\to\to 3\_babaT_2$\\ 34&$1\un{c}ababT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bbccbT_1\to\to 3\_babaT_2$\\ 35&$1\un{c}ababcT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bbccacT_1\to\to 3\_babaT_2$\\ 36&$1\un{c}abcT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ccac\\3\un{c}ccbc\end{array}\right\}T_1\to\to 3\_babaT_2$\\ 37&$1\un{c}cT_1\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 3\_babaT_2$\\ 38&$2\un{T_1}\to\to 3\_babT_2\stackrel{c}{\Rightarrow}2\un{b}T_1\to\to 3\_babaT_2$\\ 39&$3\un{T_1}\to\to 3\_babT_2\stackrel{c}{\Rightarrow}3\un{c}T_1\to\to 3\_babaT_2$\\ 40&$1\un{T_1}\to\to 1T_2\_\left\{\begin{array}{l}\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\to\to 2T_2b\_\\\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1T_2b\_\end{array}\right.$\\ 41&$1\un{T_1}\to\to 2T_2\_\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\to\to 3T_2b\_$\\ 42&$3\un{T_1}\to\to 2T_2\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 2T_2c\_$\\ 43&$1\un{T_1}\to\to 3T_2\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 3T_2c\_$\\ 44&$3T_1bb\un{b}\to\to 3T_2\_\stackrel{c}{\Rightarrow}\left.\begin{array}{l}2T_1aab\un{c}\\2T_1abb\un{c}\end{array}\right\}\to\to 3T_2c\_$\\ 45&$1\un{T_1}\to\to 2T_2b\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 3\un{T_2}bc$\\ 46&$1\un{T_1}\to\to 2T_2c\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1T_2bb\_$\\ 47&$3\un{T_1}\to\to 3T_2c\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 2T_2bb\_$\\ 48&$1\un{T_1}\to\to 2T_2bb\_\stackrel{c}{\Rightarrow}2T_1\un{c}\to\to 1\un{T_2}abc$\\ 49&$3\un{T_1}\to\to 3T_2bb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 1\un{T_2}aba$\\ 50&$3\un{T_1}\to\to 3T_2cb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3T_2bbb\_$\\ 51&$3T_1bb\un{b}\to\to 3T_2cb\_\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\right\}\to\to 3T_2bbb\_$\\ 52&$3\un{T_1}\to\to 3T_2bbb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3\un{T_2}baba$\\ 53&$1\un{T_1}\to\to 3T_2bbbbb\_\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1\un{a}\\3T_1\un{b}\end{array}\right\}\to\to 3\un{T_2}bababa$\\ 54&$3\un{T_1}\to\to 3T_2bbbbb\_\stackrel{b}{\Rightarrow}1T_1\un{b}\to\to 3\un{T_2}bababa$\\ 55&$3T_1bb\un{b}\to\to 3T_2bbbbb\_\stackrel{a}{\Rightarrow}\left.\begin{array}{l}3T_1aab\un{a}\\3T_1abb\un{a}\\3T_1aab\un{b}\\3T_1abb\un{b}\end{array}\right\}\to\to 3\un{T_2}bababa$\\ \end{longtable} \fontsize{12}{12}\selectfont In Table~\ref{table4} the numbers refer to IGR's in Table~\ref{table3}. The letters if present refer to the part of the IGR associated with that letter as the symbol above $\Rightarrow$ i.e. the symbol called $\alpha$, otherwise the whole IGR is referred to. The following number refers to the sub-part of the IGR with that numbered origin in the RHS of the IGR. On the RHS of Table~\ref{table3} (to the right of $\to$) all parts and sub-parts of an IGR referenced are included. Every IGR on the left can be followed by any IGR on the right. \fontsize{10}{10}\selectfont \begin{longtable}{ll} \caption{The relation `can be followed by'\label{table4}}\\ $1b1\to$ &$22,23,24,25,26,27,28,32,33,34,35,36,37$\\ $3b1,3b2,4b1,5b1,7b1,8b2\to$ &$22$\\ $\left.\begin{array}{l}2b1,2b2,6b1,6b2,9b1,13c1,13c2,14c1,15c1,\\17c1,18c1,33c1,33c2,34c1,35c1,37c1,38c1\end{array}\right\}\to$ &$29,31,38$\\ $12c1,12c2,16c1,16c2,36c1,36c2,39c1\to$ &$30,39$\\ $22b1\to$ &$1,2,3,4,5,6,7,10,11,12,13,14,15,16,18,19$\\ $23b1,23b2,27b1,27b2,30b1\to$ &$8,18$\\ $24b1,24b2,25,26,28,29\to$ &$1$\\ $32c1,30c2\to$ &$29,38$\\ $40a1,40a2\to$ &$42$\\ $41a1\to$ &$49,50,52,54$\\ $41a2\to$ &$44,49,50,51,52,54,55$\\ $42b1\to$ &$41,46$\\ $47b1\to$ &$41,45,48$\\ $50b1\to$ &$43,53$\\ $51a1,51a2,51a3\to$ &$49,52,54$\\ $51a4\to$ &$44,49,52,54,55$\\ \end{longtable} \fontsize{12}{12}\selectfont By examining these IGR's in Table~\ref{table3} and the compatibility relations in Table~\ref{table4} the following facts become evident: \begin{itemize} \item IGR's can be chained together by substitutions for the arbitrary strings $T_1$ and $T_2$. \item Table~\ref{table4} is the restriction on which single IGR can be followed by another IGR resulting from the structure of the IGR's themselves. \item Other restrictions result from the way in which sequences of substitutions operate. \item By carrying out by hand the process called F to the RHS of an IGR, it is sometimes possible to deduce that no previous IGR's to a sequence of them can affect the analysis of which IGR's can follow the sequence. \item If by carrying out the process F to any sequence of IGR's to find which IGR's can be next in the sequence, there always results an IGR that has already been listed, then it would show that the set of IGR's found is sufficient to generate all the IRR's for the TM. \end{itemize} From Table~\ref{table4} IGR $22$ clearly plays an important role so I thought I would start there regarding the last point above. IGR $22$ on its own obviously has too many possibilities for a following IGR depending on $T_1$ and perhaps $T_2$. By restricting consideration to IGR $1$ followed by IGR $22$ i.e. $1\to 22$ fewer possibilities will result for the following IGR's. \subsubsection{$1\to 22$} $1\to 22$ is $1\un{T_1}\to\to 1\_T_2\stackrel{b}{\Rightarrow}1\un{c}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}1\un{c}cT_1\to\to 1\_abT_2$ obtained by substituting $cT_1$ for $T_1$ and $bT_2$ for $T_2$ in IGR $22$. Applying the process F to the result of this, start by considering what CS's can lead to $1\alpha\un{c}cT_1$ for any symbol $\alpha$. It is easy to see that \begin{equation}\label{eq23}1\alpha\un{c}cT_1\left\{\begin{array}{l}\stackrel{\alpha = b}{\leftarrow}1\un{c}ccT_1\\\leftarrow 2\alpha c\un{c}T_1\leftarrow 2\alpha\un{b}cT_1\left\{\begin{array}{l}\stackrel{\alpha = b}{\leftarrow} 1\un{a}bcT_1\\\stackrel{\alpha = c}{\leftarrow}2\un{b}bcT_1\end{array}\right.\end{array}\right..\end{equation} is the complete search tree for the reverse steps from $1\alpha\un{c}cT_1$. Note that after the first of these reverse steps $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$ is. Expressing the result as an IGR gives the result \begin{equation}\label{res}1\un{c}cT_1\to\to 1\_abT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}cc\\1\un{a}bc\end{array}\right\}T_1\to\to 3\_babT_2\\\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 2bbc\un{T_2}\end{array}\right..\end{equation} Combining this with \begin{equation}\label{eq24}1\un{b}abT_2\to 3\_babT_2\text{ and }1\un{c}abT_2\to 2bbc\un{T_2}\end{equation} and identifying the longest strings of symbols that are not altered in each branch of \eqref{res}, gives three IGR's that can follow, being $1$, $7$, and the new one \begin{equation}\label{new}1\un{c}cT_1\to\to 1\_abT_2\stackrel{c}{\Rightarrow}2\un{b}bcT_1\to\to 2bbc\un{T_2}.\end{equation} The above comment on \eqref{res} implies that there are no special cases regarding regarding what symbols $T_1$ starts with that can generate another branch or extra case in \eqref{res} i.e. \eqref{res} is essentially complete. This special circumstance implies that if the same analysis ($F$) was applied to any sequence of IGR's that end in $1\to 22$, the equivalent results for the set of IGR's that can follow the sequence would be obtained that can also be expressed as $\{1,7,\eqref{new}\}$. \subsubsection{$3\to 22$} This is \begin{equation}1\un{c}aaT_1\to\to 1\_T_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{a}baa\\1\un{a}bab\end{array}\right\}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_abT_2\end{equation} This cannot be repeated because the strings do not match i.e. $3\to 22\to 3\to 22$ is not possible. Applying F gives, after replacing the strings involving $T_1$ and $T_2$ by their shortest forms: IGRs $1$ and $2$ and\begin{equation} 1\un{c}aT_1\to\to 1\_abT_2\stackrel{c}{\Rightarrow}\left.\begin{array}{l}3\un{c}ca\\3\un{c}cb\end{array}\right\}T_1\to\to 2bbc\un{T_2}.\end{equation} In this case the search tree is not necessarily complete in the sense above because the reverse search path can lead to the pointer adjacent to $T_1$ in states $1$ and $3$ indicating that if another symbol of $T_1$ is specified, more consequent IGR's might result that follow on, i.e. if other previous history is specified before IGR 3, more following IGR's might result. Table~\ref{table4} shows that IGR $3$ can only be preceded by IGR $22$. Therefore any IRR's derived ending with $3\to 22$ must take the form $\ldots x\to 22\to 3\to 22$ where $x$ is not IGR $3$. Reasoning from the other end shows that IGR $22$ with context $(b,b)$, $22(b,b)$, is $1\un{b}T_1\to\to 3\_bT_2\stackrel{b}{\Rightarrow}1\un{c}bT_1\to\to 1\_abT_2$ which cannot be followed by IGR $3$ because $1\un{c}bT_1$ does not match $1\un{c}aaT_1$, and $(b,b)$ is the context in which IGR $22$ appears in the set IRR(2) from which all IRR's are derived by IGR's. \subsubsection{$22\to 3 \to 22$} This can be written as \begin{equation}1\un{T_1}\to\to 3\_T_2\stackrel{bbb}{\Rightarrow}\left.\begin{array}{l}1\un{c}abaa\\1\un{c}abab\end{array}\right\}T_1\to\to 1\_abaT_2\end{equation} In $22\to 3$, $T_1$ in $22$ must start with $aa$. This is inconsistent with $T_1$ starting with $c$ in $1$ and $T_1$ starting with $ab$ in $3$ $4$, $5$ and $7$, therefore $22\to 3$ can be preceded only by $8$, the only other option in Table~\ref{table4}. Applying $F$ to $22\to 3b1\to 22$ gives \begin{equation}\label{223b122}1\un{c}abaaT_1\to\to 1\_abaT_2\left\{\begin{array}{l}\stackrel{b}{\Rightarrow}\left.\begin{array}{l}2\un{a}cabaa\\2\un{a}cbbaa\end{array}\right\}T_1\to\to 3\_babaT_2\\\stackrel{c}{\Rightarrow}3\un{c}cbbaaT_1\to\to 3bbcb\un{T_2}\end{array}\right..\end{equation} along with \begin{equation}\label{extra}\left.\begin{array}{l}3\alpha caab\un{a}\\3\alpha caab\un{b}\\3\alpha cabb\un{a}\\3\alpha cabb\un{b}\end{array}\right\}T_1.\end{equation} which are the residual CS's for which the pointer reached the opposite end of the string from $\alpha$. These are not usually included because they do not generate any new IGR's. They were included to show that when $F$ is now applied to $8\to 22\to 3b1\to 22$, an effect of $8$ is to require that $T_1$ in \eqref{223b122} must start with $a$, therefore the CS's in \eqref{extra} followed by $a$ must appear in the larger analysis, from which there no additions to \eqref{223b122} but the following additional CS's playing the same role as in \eqref{extra} \begin{equation}\left.\begin{array}{l}3\alpha caaab\un{a}\\3\alpha caaab\un{b}\\3\alpha caabb\un{a}\\3\alpha caabb\un{b}\end{array}\right\}T_1.\end{equation} $4\to 22\to 3$ is impossible therefore so is $4\to 22\to 3\to 22$ but $4$ seems to be alright followed by $22\to 3\to 22$ when expressed in abbreviated form therefore when doing this each IGR must be treated singly. The starting points of these chains of IGR's to generate all the IRR's must be the IGR's involved in the IRR(2) together with their associated contexts. \begin{longtable}{c|c} \caption{The IGR's and contexts that give on their RHS's all the IRR(2)\label{table5}}\\ IGR&Set of context pairs\\ \hline $41$ &$(a,b)$\\ $22$&$(b,b)$\\ $40$&$(c,b)$\\ $8$&$(c,c)$\\ $9$&$(a,a),(b,a)$\\ $47$&$(c,)$\\ $45$&$(a,)$\\ $21$&$(c,)$\\ $10$&$(b,),(a,)$\\ \end{longtable} \begin{thebibliography}{99} \bibitem{jhn2013}\href{https://www.longdom.org/articles/methods-for-understanding-turing-machine-computations.pdf}{Methods for Understanding Turing Machine Computations} \bibitem{jhn2017} \href{https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf}{John Nixon Reverse engineering Turing Machines and the Collatz Conjecture} \bibitem{tie} \href{http://www.bluesky-home.co.uk/tie_v2_1.txt}{The previous version in D of the computer program for analysis of Turing Machines} \bibitem{Tarjan's_paper}\href{https://doi.org/10.1137/0201010}{SIAM Journal on Computing, 1 (2): 146-160, Depth-First Search and Linear Graph Algorithms doi:10.1137/0201010} \bibitem{Tarjan's_algorithm} \href{http://bluesky-home.co.uk/Tarjan_v1_0.txt}{An implementation of Tarjan's strongly connected components algorithm in D} \bibitem{tie_v3_0}\href{http://www.bluesky-home.co.uk/tie_v3_0.txt}{The new program tie v3.0 for doing the computations in this paper} \end{thebibliography} \end{document}