Turing machines

Turing Machine Computations

content/turing-machines/machines-computations/machines-computations.tex

% Part: turing-machines% Chapter: machines-computations\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{tur}{mac}{Turing Machine Computations}\olimport{introduction}\olimport{representing-tms}\olimport{turing-machines}\olimport{configuration}\olimport{unary-numbers}\olimport{halting-states}\olimport{disciplined-machines}\olimport{combining-machines}\olimport{variants}\olimport{church-turing-thesis}\OLEndChapterHook\end{document}

content/turing-machines/machines-computations/introduction.tex

% Part: turing-machines % Chapter: machines-computations % Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{int}\olsection{Introduction}What does it mean for a function, say, from $\Nat$ to $\Nat$ to be\emph{computable}? Among the first answers, and the most well knownone, is that a function is computable if it can be computed by aTuring machine. This notion was set out by Alan Turing in 1936.Turing machines are an example of \emph{a model of computation}---theyare a mathematically precise way of defining the idea of a``computational procedure.''  What exactly that means is debated, butit is widely agreed that Turing machines are one way of specifyingcomputational procedures.  Even though the term ``Turing machine''evokes the image of a physical machine with moving parts, strictlyspeaking a Turing machine is a purely mathematical construct, and assuch it idealizes the idea of a computational procedure.  Forinstance, we place no restriction on either the time or memoryrequirements of a Turing machine: Turing machines can computesomething even if the computation would require more storage space ormore steps than there are atoms in the universe.\begin{explain}It is perhaps best to think of a Turingmachine as a program for a special kind of imaginary mechanism. Thismechanism consists of a \emph{tape} and a \emph{read-write head}. Inour version of Turing machines, the tape is infinite in one direction(to the right), and it is divided into \emph{squares}, each of whichmay contain a symbol from a finite \emph{alphabet}. Such alphabets cancontain any number of different symbols, but we will mainly make dowith three: $\TMendtape$, $\TMblank$, and $\TMstroke$. When themechanism is started, the tape is empty (i.e., each square containsthe symbol $\TMblank$) except for the leftmost square, which contains$\TMendtape$, and a finite number of squares which contain the\emph{input}. At any time, the mechanism is in one of a finite numberof \emph{states}. At the outset, the head scans the leftmost squareand in a specified \emph{initial state}. At each step of themechanism's run, the content of the square currently scanned togetherwith the state the mechanism is in and the Turing machine programdetermine what happens next. The Turing machine program is given by apartial function which takes as input a state~$q$ and asymbol~$\sigma$ and outputs a triple~$\tuple{q', \sigma',  D}$. Whenever the mechanism is in state $q$ and reads symbol$\sigma$, it replaces the symbol on the current square with $\sigma'$,the head moves left, right, or stays put according to whether $D$ is$\TMleft$, $\TMright$, or $\TMstay$, and the mechanism goes intostate~$q'$.For instance, consider the situation in \olref{fig:tm}.\begin{figure}  \olasset{\olpath/assets/diagrams/turing-machine.tikz}  \caption{A Turing machine executing its program.}  \ollabel{fig:tm}\end{figure}The visible part of the tape of the Turing machine contains theend-of-tape symbol $\TMendtape$ on the leftmost square, followed bythree $1$'s, a $0$, and four more $1$'s.  Thehead is reading the third square from the left, which containsa~$1$, and is in state~$q_1$---we say ``the machine is readinga $1$ in state~$q_1$.'' If the program of the Turing machinereturns, for input $\tuple{q_1, 1}$, the triple $\tuple{q_2,0, \TMstay}$, the machine would now replace the~$1$ onthe third square with a~$0$, leave the read/write head where itis, and switch to state~$q_2$.  If then the program returns$\tuple{q_3, 0, \TMright}$ for input $\tuple{q_2, 0}$,the machine would now overwrite the~$0$ with another~$0$(effectively, leaving the content of the tape under the read/writehead unchanged), move one square to the right, and enter state~$q_3$.And so on.We say that the machine \emph{halts} when it encounters some state,$q_n$, and symbol, $\sigma$ such that there is no instruction for$\tuple{q_n, \sigma}$, i.e., the transition function for input$\tuple{q_n,\sigma}$ is undefined. In other words, the machine has noinstruction to carry out, and at that point, it ceasesoperation. Halting is sometimes represented by a specific haltstate~$h$.  This will be demonstrated in more detail later on.\end{explain}\begin{digress}The beauty of Turing's paper, ``On computable numbers,'' is that hepresents not only a formal definition, but also an argument that thedefinition captures the intuitive notion of computability.From the definition, it should be clear that any function computableby a Turing machine is computable in the intuitive sense. Turingoffers three types of argument that the converse is true, i.e., thatany function that we would naturally regard as computable iscomputable by such a machine. They are (in Turing's words):\begin{enumerate}\item A direct appeal to intuition.\item A proof of the equivalence of two definitions (in case the new  definition has a greater intuitive appeal).\item Giving examples of large classes of numbers which are  computable.\end{enumerate}Our goal is to try to define the notion of computability ``inprinciple,'' i.e., without taking into account practical limitationsof time and space. Of course, with the broadest definition ofcomputability in place, one can then go on to consider computationwith bounded resources; this forms the heart of the subject known as``computational complexity.''\end{digress}\begin{history}Alan Turing invented Turing machines in 1936. While his interest atthe time was the decidability of first-order logic, the paper has beendescribed as a definitive paper on the foundations of computerdesign. In the paper, Turing focuses on computable real numbers, i.e.,real numbers whose decimal expansions are computable; but he notesthat it is not hard to adapt his notions to computable functions onthe natural numbers, and so on.  Notice that this was a full fiveyears before the first working general purpose computer was built in1941 (by the German Konrad Zuse in his parent's living room), sevenyears before Turing and his colleagues at Bletchley Park built thecode-breaking Colossus (1943), nine years before the American ENIAC(1945), twelve years before the first British general purposecomputer---the Manchester Small-Scale Experimental Machine---was built inManchester (1948), and thirteen years before the Americans firsttested the BINAC (1949). The Manchester SSEM has the distinction ofbeing the first stored-program computer---previous machines had to berewired by hand for each new task.\end{history}\end{document}

content/turing-machines/machines-computations/representing-tms.tex

% Part: turing-machines% Chapter: machines-computations% Section: representing-tms\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{rep}\olsection{Representing Turing Machines}\begin{explain}Turing machines can be represented visually by \emph{state diagrams}. The diagrams are composed ofstate cells connected by arrows. Unsurprisingly, each state cell representsa state of the machine. Each arrow represents an instruction that can becarried out from that state, with the specifics of the instruction written aboveor below the appropriate arrow. Consider the following machine, which has only two internal states, $q_0$ and $q_1$, and one instruction:\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state]   (A)              {$q_0$};  \node[state]   (B) [right of=A] {$q_1$};  \path (A) edge  node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (B);\end{tikzpicture}\]Recall that the Turing machine has a read/write head and a tape withthe input written on it. The instruction can be read as \emph{ifreading a~$\TMblank$ in state $q_0$, write a~$\TMstroke$, move right,and move to state $q_1$}. This is equivalent to the transitionfunction mapping $\tuple{q_0, \TMblank}$ to $\tuple{q_1, \TMstroke,\TMright}$.\end{explain}\begin{ex}\emph{Even Machine}: The following Turing machine halts if, and onlyif, there are an even number of $\TMstroke$'s on the tape (under theassumption that all $\TMstroke$'s come before the first $\TMblank$ onthe tape).\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state]         (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (B)            edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (A);\end{tikzpicture}\]The state diagram corresponds to the following transition function:\begin{align*}\delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\\delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\\delta(q_1, \TMblank)  & = \tuple{q_1, \TMblank, \TMright}\end{align*}\end{ex}\begin{explain}The above machine halts only when the input is an even number of strokes.Otherwise, the machine (theoretically) continues to operate indefinitely. For any machine and input, it is possible to trace through the \emph{configurations} of the machine in order to determine the output. We will give a formal definition of configurations later. For now,we can intuitively think of configurations as a series of diagrams showing the state of the machine at any point in time during operation.Configurations show the content of the tape, the state of the machine and thelocation of the read/write head.Let us trace through the configurations of the even machine if it isstarted with an input of four $\TMstroke$'s. In this case, we expect that themachine will halt.  We will then run the machine on an input of three$\TMstroke$'s, where the machine will run forever.The machine starts in state~$q_0$, scanning the leftmost~$\TMstroke$.We can represent the initial state of the machine as follows:\[\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMstroke \TMblank \ldots\]The above configuration is straightforward. As can be seen, themachine starts in state one, scanning the leftmost~$\TMstroke$. Thisis represented by a subscript of the state name on thefirst~$\TMstroke$. The applicable instruction at this point is$\delta(q_0, \TMstroke) = \tuple{q_1, \TMstroke, \TMright}$, and sothe machine moves right on the tape and changes to state~$q_1$.\[\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMstroke \TMblank \ldots\]Since the machine is now in state~$q_1$ scanning a~$\TMstroke$, we have to``follow'' the instruction $\delta(q_1, \TMstroke) = \tuple{q_0,  \TMstroke, \TMright}$. This results in the configuration\[\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMstroke \TMblank \ldots\]As the machine continues, the rules are applied again in the sameorder, resulting in the following two configurations:\[\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke_1 \TMblank \ldots\]\[\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke \TMblank_0 \ldots\]The machine is now in state~$q_0$ scanning a~$\TMblank$. Based on thetransition diagram, we can easily see that there is no instruction to becarried out, and thus the machine has halted. This means that the inputhas been accepted.Suppose next we start the machine with an input of three$\TMstroke$'s. The first few configurations are similar, as the sameinstructions are carried out, with only a small difference of the tapeinput:\[\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMblank \ldots\]\[\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMblank \ldots\]\[\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMblank \ldots\]\[\TMendtape \TMstroke \TMstroke \TMstroke \TMblank_1 \ldots\]The machine has now traversed past all the $\TMstroke$'s, and isreading a~$\TMblank$ in state~$q_1$. As shown in the diagram, there isan instruction of the form $\delta(q_1, \TMblank) =\tuple{q_1,\TMblank, \TMright}$. Since the tape is filled with $\TMblank$indefinitely to the right, the machine will continue to execute thisinstruction \emph{forever}, staying in state~$q_1$ and moving everfurther to the right. The machine will never halt, and does not acceptthe input.\end{explain}\begin{explain}It is important to note that not all machines will halt. If haltingmeans that the machine runs out of instructions to execute, then wecan create a machine that never halts simply by ensuring that there isan outgoing arrow for each symbol at each state. The even machine canbe modified to run indefinitely by adding an instruction for scanning a$\TMblank$ at~$q_0$.\end{explain}\begin{ex}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \path  (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)      edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (A)  (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (B)      edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (A);\end{tikzpicture}\]\end{ex}\begin{explain}Machine tables are another way of representing Turingmachines. Machine tables have the tape alphabet displayed on the$x$-axis, and the set of machine states across the $y$-axis. Inside thetable, at the intersection of each state and symbol, is written therest of the instruction---the new state, new symbol, and direction ofmovement. Machine tables make it easy to determine in what state, andfor what symbol, the machine halts. Whenever there is a gap in thetable is a possible point for the machine to halt. Unlike statediagrams and instruction sets, where the points at which the machinehalts are not always immediately obvious, any halting points arequickly identified by finding the gaps in the machine table.\end{explain}\begin{ex}The machine table for the even machine is:\[\centering\begin{tabular}{lllll}\cline{2-4}\multicolumn{1}{l|}{}      & \multicolumn{1}{c|}{$\TMblank$}                & \multicolumn{1}{c|}{$\TMstroke$}     & \multicolumn{1}{c|}{$\TMendtape$}   &  \\ \cline{1-4}\multicolumn{1}{|l|}{$q_0$} & \multicolumn{1}{l|}{}                          & \multicolumn{1}{l|}{\TMtrans{\TMstroke}{q_1}{\TMright}} & \multicolumn{1}{l|}{\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}}} &  \\ \cline{1-4}\multicolumn{1}{|l|}{$q_1$} & \multicolumn{1}{l|}{\TMtrans{\TMblank}{q_1}{\TMright}} & \multicolumn{1}{l|}{\TMtrans{\TMstroke}{q_0}{\TMright}} & \multicolumn{1}{l|}{\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}}} &  \\ \cline{1-4}\end{tabular}\]As we can see, the machine halts when scanning a~$\TMblank$ in state~$q_0$.\end{ex}\begin{explain}So far we have only considered machines that read and accept input.However, Turing machines have the capacity to both read and write. Anexample of such a machine (although there are many, many examples) isa \emph{doubler}. A doubler, when started with a block of~$n$$\TMstroke$'s on the tape, outputs a block of~$2n$ $\TMstroke$'s.\end{explain}\begin{ex}  \ollabel{ex:doubler} Before building a doubler machine, it is  important to come up with a \emph{strategy} for solving the problem.  Since the machine (as we have formulated it) cannot remember how  many $\TMstroke$'s it has read, we need to come up with a way to  keep track of all the $\TMstroke$'s on the tape. One such way is to  separate the output from the input with a~$\TMblank$. The machine  can then erase the first $\TMstroke$ from the input, traverse over  the rest of the input, leave a $\TMblank$, and write two new  $\TMstroke$'s.  The machine will then go back and find the second  $\TMstroke$ in the input, and double that one as well. For each one  $\TMstroke$ of input, it will write two $\TMstroke$'s of output.  By  erasing the input as the machine goes, we can guarantee that no  $\TMstroke$ is missed or doubled twice. When the entire input is  erased, there will be $2n$ $\TMstroke$'s left on the tape. The state  diagram of the resulting Turing machine is depicted in  \olref{fig:doubler}.  \begin{figure}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (1)              {$q_0$};  \node[state]         (2) [right of=1] {$q_1$};  \node[state]         (3) [right of=2] {$q_2$};  \node[state]         (4) [below of=3] {$q_3$};  \node[state]         (5) [left of=4]  {$q_4$};  \node[state]         (6) [left of=5]  {$q_5$};  \path (1) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (2)    (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2)      edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (3)    (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (3)        edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (4)    (4) edge [loop below] node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (4)        edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)    (5) edge [loop below]  node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)        edge              node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (6)    (6) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (6)        edge              node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (1);\end{tikzpicture}\]\caption{A doubler machine}\ollabel{fig:doubler}\end{figure}\end{ex}\begin{prob}Choose an arbitrary input and trace through the configurations of thedoubler machine in \olref[tur][mac][rep]{ex:doubler}.\end{prob}\begin{prob}Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$that accepts, i.e., halts on, any string of $A$'s and $B$'s where thenumber of $A$'s is the same as the number of $B$'s \emph{and} all the$A$'s precede all the $B$'s, and rejects, i.e., does not halt on, anystring where the number of $A$'s is not equal to the number of~$B$'s orthe $A$'s do not precede all the~$B$'s. (E.g., the machine should accept$AABB$, and $AAABBB$, but reject both $AAB$ and $AABBAABB$.)\end{prob}\begin{prob}Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$that takes as input any string $\alpha$ of $A$'s and $B$'s andduplicates them to produce an output of the form $\alpha\alpha$. (E.g.input $ABBA$ should result in output $ABBAABBA$).\end{prob}\begin{prob}\emph{Alphabetical?:} Design a Turing-machine with alphabet$\{\TMendtape,\TMblank, A, B\}$ that when given as input a finitesequence of $A$'s and $B$'s checks to see if all the $A$'s appear tothe left of all the $B$'s or not. The machine should leave the inputstring on the tape, and either halt if the string is``alphabetical'', or loop forever if the string is not.\end{prob}\begin{prob}\emph{Alphabetizer:} Design a Turing-machine with alphabet$\{\TMendtape,\TMblank, A, B\}$ that takes as input a finite sequenceof $A$'s and $B$'s rearranges them so that all the $A$'s are to theleft of all the~$B$'s. (e.g., the sequence $BABAA$ should become thesequence $AAABB$, and the sequence $ABBABB$ should become the sequence$AABBBB$).\end{prob}\end{document}

content/turing-machines/machines-computations/turing-machines.tex

% Part: turing-machines% Chapter: machines-computations% Section: turing-machines\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{tur}\olsection{Turing Machines}\begin{explain}The formal definition of what constitutes a Turing machine looksabstract, but is actually simple: it merely packs into onemathematical structure all the information needed to specify theworkings of a Turing machine. This includes (1) which states themachine can be in, (2) which symbols are allowed to be on the tape, (3)which state the machine should start in, and (4) what the instructionset of the machine is.\end{explain}\begin{defn}[Turing machine]A \emph{Turing machine} $M$ is a tuple $\langle Q, \Sigma, q_0,\delta\rangle$ consisting of\begin{enumerate}\item a finite set of \emph{states}~$Q$,\item a finite \emph{alphabet} $\Sigma$ which includes $\TMendtape$ and  $\TMblank$,\item an \emph{initial state}~$q_0 \in Q$,\item a finite \emph{instruction set}~$\delta\colon Q \times \Sigma  \pto Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}$.\end{enumerate}The partial function~$\delta$ is also called the \emph{transition function}of~$M$.\end{defn}\begin{explain}We assume that the tape is infinite in one direction only. For thisreason it is useful to designate a special symbol~$\TMendtape$ as amarker for the left end of the tape. This makes it easier for Turingmachine programs to tell when they're ``in danger'' of running off thetape. We could assume that this symbol is never overwritten, i.e.,that $\delta(q,\TMendtape) = \tuple{q', \TMendtape, x}$ if$\delta(q,\TMendtape)$ is defined. Some textbooks do this, we do not.You can simply be careful when constructing your Turing machine thatit never overwrites~$\TMendtape$.  Moreover, there are cases whereallowing such overwriting provides some convenient flexibility.\end{explain}\begin{ex}\emph{Even Machine:} The even machine is formallythe quadruple $\tuple{Q, \Sigma, q_0, \delta}$ where\begin{align*}Q & = \{ q_0, q_1 \} \\\Sigma & = \{ \TMendtape, \TMblank, \TMstroke \}, \\\delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\\delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\\delta(q_1, \TMblank)  & = \tuple{q_1, \TMblank, \TMright}.\end{align*}\end{ex}\end{document}

content/turing-machines/machines-computations/configuration.tex

% Part: computability% Chapter: machines-computations% Section: configuration\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{tur}{con}\olsection{Configurations and Computations}\begin{explain}Recall tracing through the configurations of the even machine earlier.The imaginary mechanism consisting of tape, read/write head, andTuring machine program is really just an intuitive way of visualizingwhat a Turing machine computation is.  Formally, we can define thecomputation of a Turing machine on a given input as a sequence of\emph{configurations}---and a configuration in turn is a sequence ofsymbols (corresponding to the contents of the tape at a given point inthe computation), a number indicating the position of the read/writehead, and a state. Using these, we can define what the Turingmachine~$M$ computes on a given input.\end{explain}\begin{defn}[Configuration]A \emph{configuration} of Turing machine $M = \tuple{Q, \Sigma, q_0,\delta}$ is a triple $\tuple{C, m, q}$ where\begin{enumerate}\item $C \in \Sigma^*$ is a finite sequence of symbols from $\Sigma$,\item $m \in \Nat$ is a number $< \len{C}$, and\item $q \in Q$\end{enumerate}Intuitively, the sequence~$C$ is the content of the tape (symbols ofall squares from the leftmost square to the last non-blank orpreviously visited square), $m$~is the number of the square theread/write head is scanning (beginning with $0$ being the number ofthe leftmost square), and $q$ is the current state of the machine.\end{defn}\begin{explain}The potential input for a Turing machine is a sequence of symbols,usually a sequence that encodes a number in some form.  The initialconfiguration of the Turing machine is that configuration in which westart the Turing machine to work on that input: the tape contains thetape end marker immediately followed by the input written on thesquares to the right, the read/write head is scanning the leftmostsquare of the input (i.e., the square to the right of the left endmarker), and the mechanism is in the designated start state~$q_0$.\end{explain}\begin{defn}[Initial configuration]The \emph{initial configuration} of $M$ for input $I \in \Sigma^*$ is\[\tuple{\TMendtape \frown I, 1, q_0}.\]\end{defn}\begin{explain}The~$\frown$ symbol is for \emph{concatenation}---the input stringbegins immediately to the left end marker.\end{explain}\begin{defn}We say that a configuration $\tuple{C, m, q}$ \emph{yields theconfiguration $\tuple{C', m', q'}$ in one step} (according to~$M$),iff\begin{enumerate}\item the $m$-th symbol of $C$ is $\sigma$,\item the instruction set of $M$ specifies $\delta(q, \sigma) =  \tuple{q', \sigma', D}$,\item the $m$-th symbol of $C'$ is $\sigma'$, and \item\begin{enumerate}\item $D = L$ and $m' = m - 1$ if $m>0$, otherwise $m'=0$, or\item $D = R$ and $m' = m + 1$, or\item $D = N$ and $m' = m$,\end{enumerate}\item if $m' = \len{C}$, then $\len{C'} = \len{C} + 1$ and the $m'$-th  symbol of $C'$ is~$\TMblank$. Otherwise $\len{C'}=\len{C}$.\item for all $i$ such that $i < \len{C}$ and $i \neq m$, $C'(i) = C(i)$,\end{enumerate}\end{defn}\begin{defn}\ollabel{defn:run-output}A \emph{run of $M$ on input~$I$} is a sequence $C_i$ of configurationsof $M$, where $C_0$ is the initial configuration of $M$ for input~$I$,and each $C_i$ yields $C_{i+1}$ in one step.We say that $M$ \emph{halts on input $I$ after $k$ steps} if $C_k =\tuple{C, m, q}$, the $m$th symbol of~$C$ is~$\sigma$, and $\delta(q,\sigma)$ is undefined.  In that case, the \emph{output} of~$M$ forinput~$I$ is~$O$, where $O$ is a string of symbols not endingin~$\TMblank$ such that $C = \TMendtape \concat O \concat \TMblank^j$for some~$j \in \Nat$. ($\TMblank^j$ is a sequence of $j$ $\TMblank$'s.)\end{defn}\begin{explain}According to this definition, the output~$O$ of~$M$ always ends in a symbol other than~$\TMblank$, or, if at time~$k$ the entiretape is filled with~$\TMblank$ (except for the leftmost~$\TMendtape$),$O$~is the empty string.\end{explain}\end{document}

content/turing-machines/machines-computations/unary-numbers.tex

% Part: turing-machines% Chapter: machines-computations% Section: unary-numbers\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{una}\olsection{Unary Representation of Numbers}\begin{explain}Turing machines work on sequences of symbols written on their tape.Depending on the alphabet a Turing machine uses, these sequences ofsymbols can represent various inputs and outputs.  Of particularinterest, of course, are Turing machines which compute\emph{arithmetical} functions, i.e., functions of natural numbers.  Asimple way to represent positive integers is by coding them assequences of a single symbol~$\TMstroke$.  If $n \in \Nat$, let$\TMstroke^n$ be the empty sequence if $n = 0$, and otherwise thesequence consisting of exactly $n$ $\TMstroke$'s.\end{explain}\begin{defn}[Computation]A Turing machine~$M$ \emph{computes} the function $f\colon \Nat^k \to \Nat$ iff$M$~halts on input\[\TMstroke^{n_1} \TMblank \TMstroke^{n_2} \TMblank \dots \TMblank \TMstroke^{n_k}\]with output $\TMstroke^{f(n_1, \dots, n_k)}$.\end{defn}\begin{prob}  Give a definition for when a Turing machine~$M$ computes the  function $f\colon \Nat^k \to \Nat^m$.\end{prob}\begin{ex}\ollabel{ex:adder}\emph{Addition:}Let's build a machine that computes the function $f(n,m) = n + m$.This requires a machine that starts with two blocks of $\TMstroke$'sof length $n$ and~$m$ on the tape, and halts with one block consistingof $n+m$~$\TMstroke$'s. The two input blocks of~$\TMstroke$'s areseparated by a~$\TMblank$, so one method would be to write a stroke onthe square containing the $\TMblank$, and erase the last~$\TMstroke$.\begin{figure}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state]         (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [right of=B] {$q_2$};  \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B)           edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)            edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C)        (C) edge [loop above] node {\TMtrans{\TMstroke}{\TMblank}{\TMstay}} (C);\end{tikzpicture}\]\caption{A machine computing $f(x,y) = x+y$}\ollabel{fig:adder}\end{figure}\end{ex}\begin{prob}Trace through the configurations of the machine from\olref[tur][mac][una]{ex:adder} for input~$\tuple{3,2}$. What happensif the machine computes $0+0$?\end{prob}\begin{explain}In \olref[rep]{ex:doubler}, we gave an example of a Turing machinethat takes as input a sequence of~$\TMstroke$'s and halts with a sequenceof twice as many~$\TMstroke$'s on the tape---the doubler machine.However, because the output contains $\TMblank$'s to the left of thedoubled block of~$\TMstroke$'s, it does not actually compute thefunction $f(x) = 2x$, as you might have assumed. We'll describe twoways of fixing that.\end{explain}\begin{ex}The machine in \olref{fig:doubler-disc} computes the function $f(x) =2x$. Instead of erasing the input and writing two $\TMstroke$'s at thefar right for every $\TMstroke$ in the input as the machine from\olref[rep]{ex:doubler} does, this machine adds a single~$\TMstroke$to the right for every~$\TMstroke$ in the input. It has to keep trackof where the input ends, so it leaves a~$\TMblank$ between the inputand the added strokes, which it fills with a~$\TMstroke$ at the veryend. And we have to ``remember'' where we are in the input, so wetemporarily replace a~$\TMstroke$ in the input block by a~$\TMblank$.  \begin{figure}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (0)              {$q_0$};  \node[state]         (1) [above of=0] {$q_1$};  \node[state]         (2) [above of=1] {$q_2$};  \node[state]         (3) [right of=2] {$q_3$};  \node[state]         (4) [below of=3] {$q_4$};  \node[state]         (5) [below of=4] {$q_5$};  \node[state]         (6) [above right of=4] {$q_6$};  \node[state]         (7) [below of=6] {$q_7$};  \node[state]         (8) [below of=7] {$q_8$};  \path (0) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (1)%    (0) edge node {\TMtrans{\TMblank}{\TMblank}{\TMstay}} (h)    (1) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (1)      edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (2)    (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2)        edge node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (3)    (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (3)        edge node[left] {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (4)    (4) edge        node[left] {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)    (5) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)        edge              node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (0)    (4) edge      node[sloped] {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (6)    (6) edge              node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (7)    (7) edge [loop right] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (7)        edge              node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (8)    (8) edge [loop right] node {\TMtrans{\TMstroke}{\TMblank}{\TMstay}} (8);    \end{tikzpicture}\]\caption{A machine computing $f(x) = 2x$}\ollabel{fig:doubler-disc}\end{figure}\end{ex}\begin{ex}\ollabel{ex:mover}A second possibility for computing $f(x) = 2x$ is to keep the originaldoubler machine, but add states and instructions at the end which movethe doubled block of strokes to the far left of the tape.  The machinein \olref{fig:mover} does just this last part: started on a tapeconsisting of a block of~$\TMblank$'s followed by a blockof~$\TMstroke$'s (and the head positioned anywhere in the blockof~$\TMblank$'s), it erases the $\TMstroke$'s one at a time and writesthem at the beginning of the tape. In order to be able to tell when itis done, it first marks the end of the block of $\TMstroke$'s witha~$\TMendtape$ symbol, which gets deleted at the end. We've startednumbering the states at~$q_6$, so they can be added to the doublermachine. All you'll need is an additional instruction $\delta(q_0,\TMblank) = \tuple{q_6,\TMblank,\TMstay}$, i.e., an arrow from~$q_0$to~$q_6$ labelled~$\TMtrans{\TMblank}{\TMblank}{\TMstay}$. (There isone subtle problem: the resulting machine does not work forinput~$x=0$. We'll leave this as an exercise.)\begin{figure}  \[  \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                      semithick]    \tikzstyle{every state}=[fill=none,draw=black,text=black]    \node[initial,state] (6)              {$q_6$};    \node[state]         (7) [right of=6] {$q_7$};    \node[state]         (8) [right of=7] {$q_8$};    \node[state]         (9) [below of=8] {$q_9$};    \node[state]         (10) [left of=9] {$q_{10}$};    \node[state]         (11) [left of=10]  {$q_{11}$};    \node[state]         (12) [below of=11]  {$q_{12}$};    \node[state]         (13) [right of=12] {$q_{13}$};    \node[state]         (14) [right of=13] {$q_{14}$};    \path    (6)  edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (7)    (7)  edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (7)         edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (8)    (8)  edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (8)         edge node {\TMtrans{\TMblank}{\TMendtape}{\TMleft}} (9)    (9)  edge [loop right] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (9)         edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (10)    (10) edge node[above] {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (11)    (11) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (11)         edge node[left] {\begin{tabular}{@{}l@{}}          \TMtrans{\TMendtape}{\TMendtape}{\TMright}\\          \TMtrans{\TMstroke}{\TMstroke}{\TMright}         \end{tabular}} (12)    (12) edge node[] {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (13)    (13) edge [loop below] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (13)         edge node[sloped] {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (11)    (13) edge node {\TMtrans{\TMendtape}{\TMblank}{\TMstay}} (14);  \end{tikzpicture}  \]  \caption{Moving a block of $\TMstroke$'s to the left}  \ollabel{fig:mover}\end{figure}\end{ex}\begin{prob}In \olref[tur][mac][una]{ex:mover} we described a machine consistingof a combination of the doubler machine from\olref[tur][mac][una]{fig:doubler-disc} and the mover machine from\olref[tur][mac][una]{fig:mover}. What happens if you start thiscombined machine on input~$x=0$, i.e., on an empty tape?  How wouldyou fix the machine so that in this case the machine halts withoutput~$2x=0$? (You should be able to do this by adding one state andone transition.)\end{prob}\begin{prob}\emph{Subtraction:} Design a Turing machine that when given an inputof two non-empty strings of strokes of length $n$ and~$m$, where $n >m$, computes the function $f(n,m) = n - m$.\end{prob}\begin{prob}\emph{Equality:} Design a Turing machine to compute the following function:\[\fn{equality}(n,m) = \begin{cases}  \text{1} & \text{if~$n = m$} \\  \text{0} & \text{if~$n \neq m$}\end{cases}\]where~$n$ and~$m \in \PosInt$.\end{prob}\begin{prob}Design a Turing machine to compute the function $\min(x,y)$ where $x$and $y$ are positive integers represented on the tape by strings of$\TMstroke$'s separated by a $\TMblank$. You may use additionalsymbols in the alphabet of the machine.The function $\min$ selects the smallest value from its arguments, so$\min(3,5)=3$, $\min(20,16)=16$, and $\min(4,4)=4$, and so on.\end{prob}\begin{defn}  A Turing machine~$M$ computes the partial function $f\colon \Nat^k  \pto \Nat$ iff,   \begin{enumerate}    \item $M$ halts on input $\TMstroke^{n_1}\concat\TMblank\concat    \dots \concat\TMblank\concat\TMstroke^{n_k}$ with output $\TMstroke^{m}$ if $f(n_1, \dots, n_k) = m$.    \item $M$ does not halt at all, or with an output that is not a    single block of~$\TMstroke$'s if $f(n_1, \dots, n_k)$ is undefined.  \end{enumerate}\end{defn}\end{document}

content/turing-machines/machines-computations/halting-states.tex

% Part: turing-machines% Chapter: machines-computations% Section: halting-states\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{hal}\olsection{Halting States}\begin{explain}Although we have defined our machines to halt only when thereis no instruction to carry out, common representations of Turingmachines have a dedicated \emph{halting state}~$h$, such that$h \in Q$.The idea behind a halting state is simple: when the machine hasfinished operation (it is ready to accept input, or has finishedwriting the output), it goes into a state~$h$ where it halts. Somemachines have two halting states, one that accepts input and one thatrejects input.\end{explain}\begin{ex}\emph{Halting States}.To elucidate this concept, let us begin with an alteration of theeven machine. Instead of having the machine halt in state~$q_0$if the input is even, we can add an instruction to send the machineinto a halting state.\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial, state]         (A)                     {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [below of=A] {$h$};  \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (B)  	    edge node {\TMtrans{\TMblank}{\TMblank}{N}} (C)        (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{R}} (B)            edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (A);\end{tikzpicture}\]Let us further expand the example. When the machine determines that the inputis odd, it never halts. We can alter the machine toinclude a \emph{reject} state by replacing the looping instruction with aninstruction to go to a reject state~$r$.\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state]         (A)                     {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [below of=A] {$h$};  \node[state]         (D) [below of=B] {$r$};  \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (B)  	    edge node {\TMtrans{\TMblank}{\TMblank}{N}} (C)        (B) edge node {\TMtrans{\TMblank}{\TMblank}{N}} (D)            edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (A);\end{tikzpicture}\]\end{ex}\begin{explain}Adding a dedicated halting state can be advantageous in cases likethis, where it makes explicit when the machine accepts/rejects certaininputs.  However, it is important to note that no computing power isgained by adding a dedicated halting state. Similarly, a lessformal notion of halting has its own advantages. The definition ofhalting used so far in this chapter makes the proof of the\emph{Halting Problem} intuitive and easy to demonstrate. For thisreason, we continue with our original definition.\end{explain}\end{document}

content/turing-machines/machines-computations/disciplined-machines.tex

% Part: turing-machines% Chapter: machines-computations% Section: well-behaved-machines\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{dis}\olsection{Disciplined Machines}\begin{explain}In section \olref[hal]{sec}, we considered Turing machines that have asingle, designated halting state~$h$---such machines are guaranteed tohalt, if they halt at all, in state~$h$.  In this way, machines with asingle halting state are more ``disciplined'' than we allow Turingmachines in general to be.  There are other restrictions we mightimpose on the behavior of Turing machines.  For instance, we also havenot prohibited Turing machines from ever erasing the tape-end markeron square~$0$, or to attempt to move left from square~$0$. (Ourdefinition states that the head simply stays on square~$0$ in thiscase; other definitions have the machine halt.) It is likewisesometimes desirable to be able to assume that a Turing machine, ifit halts at all, halts on square~$1$.\end{explain}\begin{defn}\ollabel{defn:disciplined}A Turing machine~$M$ is \emph{disciplined} iff\begin{enumerate}    \item it has a designated single halting state~$h$,    \item it halts, if it halts at all, while scanning square~$1$,    \item it never erases the $\TMendtape$ symbol on square~$0$, and    \item it never attempts to move left from square~$0$.\end{enumerate}\end{defn}\begin{explain}We have already discussed that any Turing machine can be changed intoone with the same behavior but with a designated halting state. This isdone simply by adding a new state~$h$, and adding an instruction$\delta(q, \sigma) = \tuple{h, \sigma, N}$ for any pair$\tuple{q,\sigma}$ where the original $\delta$~is undefined.  It istrue, although tedious to prove, that any Turing machine~$M$ can beturned into a disciplined Turing machine~$M'$ which halts on the sameinputs and produces the same output. For instance, if the Turingmachine halts and is not on square~$1$, we can add some instructionsto make the head move left until it finds the tape-end marker, thenmove one square to the right, then halt.  We'll leave you to thinkabout how the other conditions can be dealt with.\end{explain}\begin{ex}    In \olref{fig:adder-disc}, we turn the addition machine    from \olref[una]{ex:adder} into a disciplined machine.    \begin{figure}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state]         (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [below right of=B] {$q_2$};  \node[state]         (D) [below left of=C] {$q_3$};  \node[state]         (H) [left of=D] {$h$};  \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B)           edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)            edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C)        (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D)        (D) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D)        edge node {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (H);\end{tikzpicture}\]\caption{A disciplined addition machine}\ollabel{fig:adder-disc}\end{figure}\end{ex}\begin{prop}\ollabel{prop:disciplined} For every Turing machine~$M$,there is a disciplined Turing machine~$M'$ which halts with output~$O$if $M$~halts with output~$O$, and does not halt if $M$~does not halt.In particular, any function $f\colon\Nat^n \to \Nat$ computable by aTuring machine is also computable by a disciplined Turing machine.\end{prop}\begin{prob}\label{tur:mac:dis:prob:disc-succ}Give a disciplined machine that computes $f(x) = x+1$.\end{prob}\begin{prob}\label{tur:mac:dis:prob:copier}Find a disciplined machine which, when started on input $\TMstroke^n$produces output $\TMstroke^n \concat \TMblank \concat \TMstroke^n$.\end{prob}\end{document}

content/turing-machines/machines-computations/combining-machines.tex

% Part: turing-machines% Chapter: machines-computations% Section: combining-machines\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{cmb}\olsection{Combining Turing Machines}\begin{explain}The examples of Turing machines we have seen so far have been fairlysimple in nature. But in fact, any problem that can be solved with anymodern programming language can also be solved with Turing machines.To build more complex Turing machines, it is important to convinceourselves that we can combine them, so we can build machines to solvemore complex problems by breaking the procedure into simpler parts.If we can find a natural way to break a complex problem down intoconstituent parts, we can tackle the problem in several stages,creating several simple Turing machines and combining them into onemachine that can solve the problem. This point is especially importantwhen tackling the Halting Problem in the next section.How do we combine Turing machines $M = \tuple{Q, \Sigma, q_0, \delta}$and~$M' = \tuple{Q', \Sigma', q_0', \delta'}$?  We now use theconfiguration of the tape after $M$~has halted as the inputconfiguration of a run of machine~$M'$.  To get a single Turingmachine $M \frown M'$ that does this, do the following:\begin{enumerate}    \item Renumber (or relabel) all the states~$Q'$ of~$M'$ so that $M$    and~$M'$ have no states in common ($Q \cap Q' = \emptyset$).    \item The states of $M \frown M'$ are $Q \cup Q'$.    \item The tape alphabet is $\Sigma \cup \Sigma'$.    \item The start state is~$q_0$.    \item The transition function is the function $\delta''$ given by:    \[\delta''(q,\sigma) =    \begin{cases}      \delta(q,\sigma) & \text{if $q \in Q$}\\      \delta'(q,\sigma) & \text{if $q \in Q'$}\\      \tuple{q_0', \sigma, \TMstay} & \text{if $q \in Q$ and      $\delta(q,\sigma)$ is undefined}    \end{cases}\]\end{enumerate}The resulting machine uses the instructions of~$M$ when it is in astate $q \in Q$, the instructions of~$M'$ when it is in a state~$q \inQ'$. When it is in a state $q \in Q$ and is scanning a symbol~$\sigma$for which $M$ has no transition (i.e., $M$ would have halted), itenters the start state of~$M'$ (and leaves the tape contents and headposition as it is).Note that unless the machine~$M$ is disciplined, we don't know wherethe tape head is when $M$~halts, so the halting configuration of~$M$need not have the head scanning square~$1$. When combining machines,it's important to keep this in mind.\end{explain}\begin{ex}\emph{Combining Machines:} We'll design a machine which, when startedon input consisting of two blocks of~$\TMstroke$'s of length $n$and~$m$, halts with a single block of $2(m+n)$ $\TMstroke$'s on thetape. In order to build this machine, we can combine two machines weare already familiar with: the addition machine, and the doubler. Webegin by drawing a state diagram for the addition machine.\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [right of=B] {$q_2$};  \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B)            edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)            edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C)        (C) edge [loop above] node {\TMtrans{\TMstroke}{\TMblank}{\TMstay}} (C);\end{tikzpicture}\]Instead of halting in state~$q_2$, we want to continue operation inorder to double the output. Recall that the doubler machine erases thefirst stroke in the input and writes two strokes in a separate output.Let's add an instruction to make sure the tape head is reading thefirst stroke of the output of the addition machine.\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [right of=B] {$q_2$};  \node[state]         (D) [below left of=C] {$q_3$};  \node[state]         (E) [below left of=D] {$q_4$};  \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B)            edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)            edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C)        (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D)        (D) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D)            edge node[left, xshift=-2mm] {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (E);\end{tikzpicture}\]It is now easy to double the input---all we have to do is connect thedoubler machine onto state~$q_4$. This requires renaming the states ofthe doubler machine so that they start at~$q_4$ insteadof~$q_0$---this way we don't end up with two starting states. Thefinal diagram should look as in \olref{fig:combined}.\begin{figure}\[\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,                    semithick]  \tikzstyle{every state}=[fill=none,draw=black,text=black]  \node[initial,state] (A)              {$q_0$};  \node[state]         (B) [right of=A] {$q_1$};  \node[state]         (C) [right of=B] {$q_2$};  \node[state]         (D) [below left of=C] {$q_3$};  \node[state]         (E) [below left of=D] {$q_4$};  \node[state]         (2) [right of=E] {$q_5$};  \node[state]         (3) [right of=2] {$q_6$};  \node[state]         (4) [below of=3] {$q_7$};  \node[state]         (5) [left of=4]  {$q_8$};  \node[state]         (6) [left of=5]  {$q_9$};  \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B)            edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)        (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B)            edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C)        (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D)        (D) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D)            edge node[left, xshift=-2mm] {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (E)    (E) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (2)    (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2)      edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (3)    (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (3)        edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (4)    (4) edge [loop below] node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (4)        edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)    (5) edge [loop below]  node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5)        edge              node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (6)    (6) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (6)        edge              node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (E);\end{tikzpicture}\]\caption{Combining adder and doubler machines}\ollabel{fig:combined}\end{figure}\end{ex}\begin{prop}    If $M$ and $M'$ are disciplined and compute the functions $f\colon    \Nat^k \to \Nat$ and $f'\colon \Nat \to \Nat$, respectively, then    $M \frown M'$ is disciplined and computes~$\comp{f}{f'}$.\end{prop}\begin{proof}    Since $M$ is disciplined, when it halts with    output~$f(n_1,\dots,n_k) = m$, the head is scanning square~$1$. If    we now enter the start state of~$M'$, the machine will halt with    output $f'(m)$, again scanning square~$1$. The other conditions of    \olref[dis]{defn:disciplined} are also satisfied.\end{proof}\begin{prob}    Give a disciplined Turing machine computing $f(x) = x+2$ by taking    the machine~$M$ from \cref{tur:mac:dis:prob:disc-succ} and    construct $M \frown M$.\end{prob}\end{document}

content/turing-machines/machines-computations/variants.tex

% Part: turing-machines% Chapter: machines-computations% Section: variants\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{var}\olsection{Variants of Turing Machines}There are in fact many possible ways to define Turing machines, ofwhich ours is only one.  In some ways, our definition is more liberalthan others. We allow arbitrary finite alphabets, a more restricteddefinition might allow only two tape symbols, $\TMstroke$and~$\TMblank$.  We allow the machine to write a symbol to the tapeand move at the same time, other definitions allow either writing ormoving.  We allow the possibility of writing without moving the tapehead, other definitions leave out the $\TMstay$ ``instruction.''  Inother ways, our definition is more restrictive. We assumed that thetape is infinite in one direction only, other definitions allow thetape to be infinite both to the left and the right. In fact, one caneven allow any number of separate tapes, or even an infinite grid ofsquares.  We represent the instruction set of the Turing machine by atransition function; other definitions use a transition relation wherethe machine has more than one possible instruction in any givensituation.This last relaxation of the definition is particularly interesting.In our definition, when the machine is in state~$q$ readingsymbol~$\sigma$, $\delta(q, \sigma)$ determines what the new symbol,state, and tape head position is.  But if we allow the instruction setto be a relation between current state-symbol pairs $\tuple{q,  \sigma}$ and new state-symbol-direction triples $\tuple{q', \sigma',  D}$, the action of the Turing machine may not be uniquelydetermined---the instruction relation may contain both $\tuple{q,  \sigma, q', \sigma', D}$ and $\tuple{q, \sigma, q'', \sigma'', D'}$.In this case we have a \emph{non-deterministic} Turing machine.  Theseplay an important role in computational complexity theory.There are also different conventions for when a Turing machine halts:we say it halts when the transition function is undefined, otherdefinitions require the machine to be in a special designated haltingstate. We have explained in \olref[hal]{sec} why requiring adesignated halting state is not a restriction which impacts whatTuring machines can compute.  Since the tapes of our Turing machinesare infinite in one direction only, there are cases where a Turingmachine can't properly carry out an instruction: if it reads theleftmost square and is supposed to move left. According to ourdefinition, it just stays put instead of ``falling off'', but we couldhave defined it so that it halts when that happens. This definition isalso equivalent: we could simulate the behavior of a Turing machinethat halts when it attempts to move left from square~$0$ by deletingevery transition $\delta(q,\TMendtape) =\tuple{q',\sigma,\TMleft}$---then instead of attempting to move lefton~$\TMendtape$ the machine halts.\footnote{This doesn't \emph{quite}work, since nothing prevents us from writing and reading $\TMendtape$on squares other than square~$0$ (see \olref[una]{ex:mover}). We canget around that by adding a second~$\TMendtape'$ symbol to use insteadfor such a purpose.}There are also different ways of representing numbers (and hence theinput-output function computed by a Turing machine): we use unaryrepresentation, but you can also use binary representation. Thisrequires two symbols in addition to $\TMblank$ and~$\TMendtape$.Now here is an interesting fact: none of these variations matters asto which functions are Turing computable. \emph{If a function is Turingcomputable according to one definition, it is Turing computableaccording to all of them.}We won't go into the details of verifying this. Here's just oneexample: we gain no additional computing power by allowing a tape thatis infinite in both directions, or multiple tapes. The reason is,roughly, that a Turing machine with a single one-way infinite tape cansimulate multiple or two-way infinite tapes. E.g., using additionalstates and instructions, we can ``translate'' a program for amachine with multiple tapes or two-way infinite tape into one with asingle one-way infinite tape.  The translated machine can use theeven squares for the squares of tape~$1$ (or the ``positive'' squaresof a two-way infinite tape) and the odd squares for the squares oftape~$2$ (or the ``negative'' squares).\end{document}

content/turing-machines/machines-computations/church-turing-thesis.tex

% Part: computability% Chapter: tm-computations% Section: church-turing-thesis\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{tur}{mac}{ctt}\olsection{The Church--Turing Thesis}Turing machines are supposed to be a precise replacement for theconcept of an effective procedure. Turing thought that anyone whograsped both the concept of an effective procedure and the conceptof a Turing machine would have the intuition that anything that couldbe done via an effective procedure could be done by Turing machine.This claim is given support by the fact that all the other proposedprecise replacements for the concept of an effective procedure turnout to be extensionally equivalent to the concept of a Turing machine---that is, they can compute exactly the same set of functions. Thisclaim is called the \emph{Church--Turing thesis}.\begin{defn}[Church--Turing thesis]The \emph{Church--Turing Thesis} states that anything computable viaan effective procedure is Turing computable.\end{defn}The Church--Turing thesis is appealed to in two ways.  The first kindof use of the Church--Turing thesis is an excuse for laziness.  Supposewe have a description of an effective procedure to compute something,say, in ``pseudo-code.''  Then we can invoke the Church--Turing thesisto justify the claim that the same function is computed by some Turingmachine, even if we have not in fact constructed it.The other use of the Church--Turing thesis is more philosophicallyinteresting.  It can be shown that there are functions which cannot becomputed by Turing machines.  From this, using the Church--Turingthesis, one can conclude that it cannot be effectively computed, usingany procedure whatsoever.  For if there were such a procedure, by theChurch--Turing thesis, it would follow that there would be a Turingmachine for it.  So if we can prove that there is no Turing machinethat computes it, there also can't be an effective procedure.  Inparticular, the Church--Turing thesis is invoked to claim that theso-called halting problem not only cannot be solved by Turingmachines, it cannot be effectively solved at all.\end{document}