# Computability, Turing machines, (un)decidability

(Based on notes by Dr. J. Gil-Férez)

## Motivating discusion

:::warning
* What is a regular language? Is every language regular?
* What tools do we have to prove that a language is not regular?
* Can we use the Pumping Lemma to prove that a language is regular?
* What is the main idea of the proof of the Pumping Lemma?
:::

### Discuss the following argument
:::warning
The language $L = \{10^n 10^m 10^{m+n} : n,m\in\mathbb N\}$ is not regular (why?). Hence, DFAs are insufficient to do Arithmetic.
:::

### Question
What is missing in DFAs, if we want to do arithmetic computations?

## Turing's idea of computation

:::info
* ''Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares.''
* ''I shall also suppose that the number of symbols which may be printed is finite.''
* ''The behaviour of the computer at any moment is determined by the symbols which he is observing, and his "state of mind" at that moment. [...] We will also suppose that the number of states of mind which need be taken into account is finite.''
* ''Let us imagine the operations performed by the computer to be split up into "simple operations" which are so elementary that it is not easy to imagine them further divided.''
* ''We may suppose that in a simple operation not more than one symbol is altered.''

A. M. Turing, *On computable numbers with an application to the Entscheidungsproblem*, Proc. of the London Mathematical Society, vol s2-42, 1 (1937), pp. 230--265.
:::

## Turing machines

A *Turing machine* is a 7-tuple

$$ M = (Q,\Sigma,\Gamma,\delta,q_0,B,F),$$

* $Q$ is the finite set of *states*,
* $\Sigma$ is the finite set of *input symbols*,
* $\Gamma$ is the finite set of *tape symbols* ($\Sigma\subseteq\Gamma$),
* $\delta$ is the (partial) *transition function*,
* $q_0$ is the *start state*,
* $B$ is the *blank symbol* (it is not an input symbol),
* $F$ is the set of *accepting states*.

The transition function $\delta$ takes a state and a symbol and returns a state, a symbol, and either $R$ or $L$:

$$\delta(q,X) = (p,Y,D)$$

* $q$ is the state current state of the machine,
* $X$ is the symbol that the machine scans in the current square,
* $p$ is the new state (it could be $p=q$) of the machine,
* $Y$ is the symbol that is printed in the current square (it could be $Y=X$),
* $D$ is either $R$ or $L$:
-- if $D = R$ then the head moves to the right of the tape,
-- if $D = L$ then the head moves to the left of the tape.

:::info
**Theorem.** TMs are an extension of DFAs.

**Proof.** DFAs can be considered TMs which scan every square of the input exactly once, from left to right, and do not change the input. Thus, all we have to do is "update" the transition function in a trivial way. If the transition function of the DFA maps $\delta(p,X)=q$, the transition function of the TM would be $\delta(p,X)=(q,X,R)$. When the TM finishes scanning the input, it will find the first blank, for which the transition function is not defined, and therefore the TM would halt. $\square$
:::

:::success
**Example.** Let's design a TM to accept the binary strings with an even number of 0's. (This can be done by a DFA.) We need three states $q_0$ (even number of 0's), $q_1$ (odd number of 0's). The start state is $q_0$ and the accepting state is also $q_0$. The input symbols are 0 and 1, and the tape symbols include also $B$.

The machine should scan the symbols of the input string, one by one. If the machine finds a 0, it should change state (from $q_0$ to $q_1$ and from $q_1$ to $q_0$), write 0, and go to the right. If the machine finds a 1, it should remain in the same state, write 1, and go to the right. If the machine scans $B$, then it should do nothing (halt).

| $\delta$ | $0$ | $1$ | $B$ |
| -------- | --------- | --------- |---- |
| $q_0$ | $q_1,0,R$ | $q_0,1,R$ | |
| $q_1$ | $q_0,0,R$ | $q_1,1,R$ | |

http://turingmachinesimulator.com/shared/rgakbxmacg
:::

:::warning
**Exercise A.**
1. Write a TM to accept the language of binary strings $L = \{10^n : n\in\mathbb N\}$ and for the input $10^n$ it returns the string $10^{n+1}$.
1. Write a TM to accept the language of binary strings $L = \{10^n : n\in\mathbb N\}$ and for the input $10^n$ it returns the string $1$.
1. Write a TM to accept the total language of binary strings and, for every string, it returns the string with 0's and 1's swapped.

**NB:** Note that $10^n = 1 \underbrace{00\ldots0}_{n \; \; \mathrm{times}}$.
:::

:::success
**Example 8.2** What follows is a TM that accepts the language $L = \{0^n1^n : n\in\mathbb N\}$. (Notice that this language is not regular due to the pumping lemma.)

The idea is to change any $0$ to an $X$ and any $1$ to a $Y$ until all $0$'s and $1$'s have been matched. Concretely, reading a $0$ from the left, the head will move over any $0$ and $Y$ until it finds $1$ which then gets rewritten into $X$, prompting the head to move back to the left until it finds an $X$. It then immediately looks for a $0$ on the right. If it finds one, it changes it to $X$, repeating the process, changing a matching $Y$ to $1$.

| $\delta$ | $0$ | $1$ | $X$ | $Y$ | $B$ |
| -------- | --------- | --------- | --------- | --------- |---------- |
| $q_0$ | $q_1,X,R$ | | | $q_3,Y,R$ | |
| $q_1$ | $q_1,0,R$ | $q_2,Y,R$ | | $q_1,Y,R$ | |
| $q_2$ | $q_2,0,L$ | | $q_0,X,R$ | $q_2,Y,L$ | |
| $q_3$ | | | | $q_3,Y,R$ | $q_4,B,R$ |
| $q_4$ | | | | | |

http://turingmachinesimulator.com/shared/htdmgnjsak
:::

:::warning
**Exercise B.**
1. Write a TM to perform unary addition: it should accept the language $L = \{10^n10^m : n,m\in\mathbb N\}$ and for the input $10^n10^m$ it should return $10^n10^m10^{n+m}$.
1. Write a TM to double a binary string: it should accept any binary string, and for the input $w$ it should return $ww$.
:::

## Instantaneous descriptions (IDs)

We can encode a specific step of the computation of a TM by writing the symbols on the tape (except for the infinite blanks on the left and on the right), and writing the state name immediately on the left of the next symbol to be scanned. If the start state is $q_0$ and the input is $X_0X_1\dots X_n$, we represent this by the ID:

$$q_0X_0X_1\dots X_n.$$

And if the transition function is $\delta(q,X_i) = (p,Y,R)$, then we represent the change from the previous step to the new one by

$$X_0\dots X_{i-1}q X_iX_{i+1}\dots X_n \vdash_M X_0\dots X_{i-1}Yp X_{i+1}\dots X_n.$$

We use $\vdash_M^*$ to represent a transition from one ID to another one by several steps of computation. The subscripts of $\vdash_M$ and $\vdash_M^*$ can be omitted if the TM $M$ is understood by context.

:::success
**Example.**
These are the IDs of the first steps of the TM of Example 8.2 with imput $w = 0011$:

$$q_00011 \vdash_M Xq_1011 \vdash_M X0q_111 \vdash_M Xq_20Y1 \vdash_M \dots,$$

because $\delta(q_0,0) = (q_1,X,R)$, $\delta(q_1,0) = (q_1,0,R)$, $\delta(q_1,1) = (q_2,Y,L)$. Then, we can write $q_00011\vdash_M^* Xq_20Y1$.
:::

## Transition diagrams

TMs can be represented by transition diagrams as DFAs. The difference is that we have to label the arcs, not only with the symbol that the machine is scanning, but also with the symbol to be written, and the direction in which the reader/writer moves along the tape.

:::success
**Example.** This is the transition diagram of the TM of Example 8.2.
:::

Transition diagrams of TMs are also an extension of the transition diagrams of DFAs. In particular, given a transition diagram of a DFAs, we can convert it into the transition diagram of the corresponding TM as follows: in every arc, replace the label $X$ with $X/X\to$.

:::warning
**Exercise C.**
Draw transition diagrams for the TMs of the previous exercises.
:::

:::success
**Example 8.4.** This machine computes the *monus* operation (proper subtraction) of natural numbers (see pp. 331--334):
http://turingmachinesimulator.com/shared/ogabrxinrf
:::

## The language of a TM and halting

A string $w$ in the input language of a TM $M$ with start state $q$ is *accepted* by $M$ if $qw\vdash_M^* xpy$ for some accepting state $p$ and whatever strings $x$ and $y$.

The *language* of a TM $M$ is the set $L(M)$ of all the strings that are accepted by $M$.

A language $L$ is *recursively enumerable* (RE) if it is the language of a TM $M$, that is, $L = L(M)$.

A TM *halts* if it enters a state $q$ scanning the symbol $X$ such that $\delta(q,X)$ is not defined. (Some other formalizations of TMs admit a special order to halt the machine.)

:::warning
**Exercise D.** Design a Turing machine that accepts the binary strings with at least one $1$, but doesn't halt for any input.
:::

A language is *recursive* if it is the language of a TM that halts for every input. A problem is *decidable* if can be solved by a TM that always halts.

## Programming techniques

### Storage in the state and multiple tracks
These ideas are usually used in combination. Storing information in the finite control means to create states that "remember" if the machine has read a particular symbol. This is accomplished by "labeling" the states, that is, in the process of designing the machine, we label certain states (possible all), with the symbols of our language. Thus, instead of having states $q$ and $p$, for example, we could have states $[q,A]$, $[q,B]$, $[q,C]$, $[p,A]$, $[p,B]$, $[p,C]$, where $A$, $B$, and $C$ are symbols of our language.

The technique of multiple tracks is useful if we want to mark that we have visited a certain square. This is accomplished by "labeling" the symbols of our language with "marking symbols", in the process of designing the machine. Thus, instead of using the alphabet $\{0,1\}$, we could use the alphabet $\{[B,0]$, $[B,1]$, $[*,0]$, $[*,1]\}$.

:::success
**Example 8.7** This machine accepts the language $L = \{wcw : w \text{ is a nonempty binary string}\}$. (See pp. 339--341.)
http://turingmachinesimulator.com/shared/nduyjifsvy
:::

## Extensions of TMs: multitape TMs

We can add more than one tape to a TM. The transition function will have instructions to write in all the tapes possibly different symbols and move each tape independently. This doesn't enlarge the class of decidable problems:

:::info
**Theorem.** Every language accepted by a multitape TM is also accepted by a TM.

**Idea of the proof.** Every multitape TM can be simulated by a TM.
:::

:::success
**Example.** This multitape TM reverses any binary string. Given an input $w$ it returns $w*w^R$.
http://turingmachinesimulator.com/shared/uwbozvhxjx
:::

:::success
**Example.** This multitape TM computes the division with remainder of natural numbers. Given an input $10^n10^m$ it returns $10^n10^m10^q10^r$, where $n = qm + r$.
http://turingmachinesimulator.com/shared/shghrorpyu
:::

:::warning
**Exercise E.**
1. Design a (multitape) TM that accepts any binary string $w$ and returns another string of the form $0^n1^m$, where $n$ and $m$ are the numbers of $0$'s and $1$'s of $w$, respectively.
1. *Chalenge:* Design a (multitape) TM that computes the multiplication of natural numbers: it accepts any binary string of the form $10^n10^m$ and returns $10^n10^m10^{nm}$.
:::

## Final considerations

* We have seen how every DFA is can be extended in a trivial way to a TM, which always halt, accepting the same language. Therefore, every regular language is recursive.
* TMs constitute a model of computation, but it is not the only one. Church developed (about the same time as Turing) $\lambda$-calculus ("lambda calculus") and Gödel extended Kronecker's work on primitive recursive functions to general recursive functions. Both models, $\lambda$-calculus and general recursive functions, turned out to be equivalent to Turing machines, in that if a problem can be solved by one of them, it can be also solved by the other two. Many other models of computation have been proposed and the more powerful (finitary) ones are always equivalent to Turing machines. A model for computation is calaled *Turing complete* if it can simulate every Turing machine.
* The following questions are equivalent and they are open for discussion and future inquiry:
- Are there languages that are recursively enumerable but not recursive?
- If a language $L$ is accepted by a TM $M$, is there always a TM $M'$ which also accepts $L$ and always halt?
- Are there problems that can be solved (by a TM) but are undecidable?
* Finally, consider the *halting problem:* Is there an algorithm (i.e., a TM) to decide if any given TM $M$ with any given input $w$ will halt? It turns out that the answer is *no*, showing that there are languages that are not even recursively enumerable.