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


\begin{document}

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

%\centerline{\bf {John Nixon}} 

%\centerline{} 

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

%\centerline{Battle, East Sussex} 

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


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

%Date: 2017-01-11
\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}
\end{abstract}
{\bf Mathematics Subject Classification:} 68Q25 \\ 

{\bf Keywords:} Turing Machine (TM).

\section{Introduction}
A development is given here for the analysis techniques for non-terminating Turing Machines (TM's) that I described earlier in \cite{jhn2013} and \cite{jhn2017}. This technique was motivated by my earlier work but can be largely described without it resulting in a very short paper where this prior material has been removed. This consists of a simple procedure I call the development algorithm because it seems to be a very natural and general outworking of the rules of a Turing Machine (TM). The material removed and is available as an old version (\cite{jhn2025},\cite{jhn2025txt}) to show where the ideas came from, and this much shortened version of the paper has taken its place as the latest version under active editing.
Comments are welcome. Please send them to
john.h.nixon1@gmail.com

A (non-terminating) Turing Machine (TM) consists of a read-write head that moves by one square at a time on a one-dimensional tape that is infinite in both directions marked off into squares on each of which which one of a set of symbols is written. Any symbol on the tape remains there until it is overwritten by the TM. The action of the TM is as follows. First the current symbol is read, and depending on this and the machine's  internal state, three actions are performed in a cycle. (1) The new symbol is printed at the current square, (2) the TM enters a new state, and (3) the TM moves right or left by one square. These cycles (steps) are repeated indefinitely.
In order to describe the action of a TM, configuration sets (CS's) were introduced. A CS is a set of complete configurations (all the 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 (if it is just off the end of the symbol string) or an underline and the machine state is on the left. For example with machine states 1,2,3, etc. and symbols as 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. It indicates that one or more TM steps will take any configuration in the CS on the left of $\to$ to a configuration in the CS on the right. In this paper rules will not include symbols on the tape that are not read by the TM. A very convenient way of a specifying a TM is to use a set rules involving CS's of length 1.

\section{A very simple example}
The following example of a Turing Machine (TM) and its analysis illustrate all the ideas of the paper.
The TM is 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}
and the analysis developed from it is as follows.
\begin{equation}\label{res}\begin{array}{@{}l}
1\left\{\begin{array}{@{}l}\stackrel{a}{\to}2b\_\left\{\begin{array}{@{}l}\stackrel{a}{\to}1bb\_(1\un{a}a\to 1bb\_)\\\stackrel{b}{\to}2\_aa,(\alpha^*)\end{array}\right.\\[15pt]

\stackrel{b}{\to}2\_a
\left\{\begin{array}{@{}l}\stackrel{a}{\to}2bb\_(2\un{a}a\to 2bb\_)\\\stackrel{b}{\to}2\_aa(\alpha^*)
\end{array}\right.


\end{array}\right.\\[35pt]
2\left\{\begin{array}{@{}l}\stackrel{a}{\to}1b\_
\left\{\begin{array}{@{}l}\stackrel{a}{\to}2bb\_(2\un{a}a\to 2bb\_)\\\stackrel{b}{\to}2\_aa(\alpha^*)\end{array}\right.

\\\stackrel{b}{\to}2\_a (2\un{b}\to 2\_a ,\alpha)

\end{array}\right.\\[22pt]
3\left\{\begin{array}{@{}l}\stackrel{a}{\to}3a\_(3\un{a}\to 3a\_)\\\stackrel{b}{\to}1\_b
\left\{\begin{array}{@{}l}\stackrel{a}{\to}2\_aa (\alpha^*)\\\stackrel{b}{\to}2\_ab
\left\{\begin{array}{@{}l}\stackrel{a}{\to}2\_aaa
\left\{\begin{array}{@{}l}\stackrel{a}{\to}2bbbb\_\\\stackrel{b}{\to}2\_aaaa\end{array}\right.
\\\stackrel{b}{\to}2\_aab (\alpha^*)\end{array}\right.
\end{array}\right.
\end{array}\right.
\end{array}\end{equation}

This can be continued using the rules in Table~\ref{equiv} showing how the length of the CS's can increase indefinitely and the cycles increase in size without limit.
Here the pseudo-sate D arises separately from A,B and C. 
\begin{longtable}{l|l|l|l}
\caption{Computation rules derived from 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 ($\it n$ even)&$a\to$ C &$a\to$ B &$a\to$ D\\
$a\to$ C ($\it n$ odd)&$b\to$ A &$b\to$ A &$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 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 the rules $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 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. From there 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.


\section{The development algorithm}
The algorithm is very simple and is as follows. Starting from any CS, every possible symbol is added at the pointer position leading to a set of branches and in each case the computation continues as far as possible until a symbol in a new position needs to be read (a final CS). The resulting CS forms the next starting point. Whenever a new final CS is reached, if a repeating condition has occurred with other CS's (*) on the path to it from the root (an initial CS only specifying the machine state), i.e. where the state, pointer position (right or left) and the symbol string match between a CS and another CS that is in the path to it from the root of the tree. Then between these two CS's the pointer moves in a range. A repetition also requires every symbol in the second CS in the range to match the corresponding symbol from the first CS.
If this happens the repeating cycle is identified and written within parentheses and optionally labelled by a greek letter. This terminates this branch of the development because any further development on the branch is a special case of analysis that has already been done.  This assumes all branches from CS * have already been developed. Likewise if a CS is reached that matches a repeating cycle already found elsewhere, the label for that cycle is given and an asterisk indicating where to refer to for its continuation. The algorithm starts from every CS (root) that consists of just the TM state i.e. the string of symbols has length 0.






\section{Formulating the condition for a repetition}
In these trees (i.e. results of the development algorithm e.g \eqref{1_}, \eqref{2_} and \eqref{3_} for TM~\eqref{tm2} or \eqref{res} for TM~\eqref{6}), if on any branch, the final CS matches an earlier CS in such a way that the loop can be repeated (this might only work after some symbols not involved in the loop are ignored in which case the repeating loop needs to be first applied to the simpler case where these extra symbols are absent) then the algorithm terminates the branch because continuing is a special case of what has already been done. If this happens, all the CS's that match the final CS in the loop should be listed in order in parentheses, so that many other results of the TM can be found easily.

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



Suppose \begin{equation}\label{branch}CS_{\rm 0}\stackrel{\alpha_1}{\to}CS_{\rm 1}\stackrel{\alpha_2}{\to}\ldots \end{equation} is such a branch that ends in a repeating loop and the pointer is at the right in each CS where $CS_{\it i}$ has length $\it i $, and in step ${\it i}+1$ from $CS_{\it i}$ to $CS_{{\it i}+{\rm 1}}$ 
the pointer reaches and uses ${\it r}({\it i})$ symbols (this excludes the last symbol arrived at that is not yet read). 
$CS_{\rm 0}$ is just a CS of length 0 which only defines the machine state and is the root of a tree of CS's developed from it by the development algorithm. After ${\it l}_{\rm 2}$ steps in \eqref{branch} giving a CS of length ${\it i}={\it l}_{\rm 2}$ the condition for a repetition of an earlier CS of length ${\it i}={\it l}_{\rm 1}$ is as follows. This involves ${\it l}_{\rm 2}-{\it l}_{\rm 1}$ steps in \eqref{branch}.

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

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

\section{A more substantial example}




The following example was also studied.

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

By applying the development algorithm to TM~\ref{tm2} the results in \eqref{1_}, \eqref{2_} and \eqref{3_} were obtained which seem to adequately describe the TM and lead to Table~\ref{equivTM1} which is summarised by Figure~\ref{fig2} and shows how the TM can be `trapped' in a steady movement to its left.

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

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

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

By taking the longest results of the repeating cycles on the RHS's of \eqref{1_},\eqref{2_} and \eqref{3_} i.e. $1\_aba,3\_baba$ and adding every symbol in turn gives $1\un{a}aba\to 1\_abaa, 1\un{a}abaa\to C,1\un{b}abaa\to E, 1\un{c}abaa\to 3b^{\rm 5}\_, 1\un{b}aba\to 3\_baba, 3\un{a}baba\to A, 3\un{b}baba\to A, 3\un{c}baba\to E,1\un{c}aba\to 2bbbb\_$ where the capital letter notation for pseudo-states in Table~\ref{equivTM1} has been used. Another round of this generates all the results of Table~\ref{equivTM1} because in Table~\ref{equivTM1} all possible new symbols to be read are included.

\begin{longtable}[h]{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}


\begin{figure}[h]
\begin{adjustbox}{width = 14cm,center}
\centering
\xymatrix @R = 0.3cm{
& *+[F-:<3pt>]{\txt{Start}}\ar[d]\\
*+[F-:<3pt>]{\txt{TM~\ref{tm2} progresses by sequences of\\ steps each moving the pointer left by\\ one space and restricts the pointer\\ to positions in a window of length 6.
}} & *+[F-:<3pt>]{\txt{Has the pointer reached one position\\ then another 5 spaces to its left?}}\ar[l]|-{yes}\ar[d]|-{no}\\
& *+[F-:<3pt>]{\txt{Continue the TM by one step}}\ar@<-15pt>[u]
}
\caption{Summary of the results of the analysis of TM(\ref{tm2})}
\label{fig2}
\end{adjustbox}
\end{figure}
Table~\ref{equivTM1} 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. This is because Table~\ref{equivTM1} includes every symbol added at the left in every pseudo-state and the effect in each case is to leave the pointer to the left of the string. Because of this, if a snapshot is taken of its behaviour whenever the TM reaches just beyond the left hand end of the window, whatever symbol it finds there, the result will be at the next snapshot that the symbols of the window have changed depending on the previous symbols there and the new symbol. Therefore if the TM reaches position 6 followed by position 1 then the above argument involving the moving window applies. This condition of course will not necessarily happen  but once started (depending on the initial contents of the tape) must continue indefinitely.

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

The behaviours of the two examples of TM's is completely different though each description does depend somewhat on the configuration the TM starts off in.

\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{https://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{https://www.bluesky-home.co.uk/origins.txt}{Program for just doing the backward search for a single CS}
\bibitem{jhn2025}\href{https://www.bluesky-home.co.uk/2025_Turing_notes.pdf}{Turing machine notes 2025.pdf}
\bibitem{jhn2025txt}\href{https://www.bluesky-home.co.uk/2025_Turing_notes.txt}{Turing machine notes 2025.txt}
\end{thebibliography} 
\end{document}