Note on Computational Complexity - 1.1 Models of computation-Turing Machines

Chapter 1. Models of computation

1.1 Turing Machines

1.1.1 Definitions

A Turing Machine (we will use TM in short) is a theoretical computational model introduced by Alan Turing in 1936. It is used to define the limits of what can be computed and serves as a foundation for theoretical computer science.

Definition: A TM, $𝑀$, is a tuple $(\mathrm{\Gamma },𝑄,𝛿)$ which is defined as

• A set $\mathrm{\Gamma }$ of the symbols that $𝑀$’s tapes can contain. We assume that $\mathrm{\Gamma }$ contains a designated “blank” symbol, denoted $\square$, a designated “start” symbol, denoted $▹$ and the numbers 0 and 1. We call $\mathrm{\Gamma }$ the alphabet of $𝑀$.
• A set $𝑄$ of possible states $𝑀$’s register can be in. We assume that $𝑄$ contains a designated start state, denoted ${𝑞}_{\text{start}}$ and a designated halting state, denoted ${𝑞}_{\text{halt}}$. Note: the states in this definition refers to the state of the whole machine. Sometimes, we may also use the word configuration to mean the same thing.
• A function $𝛿:𝑄\times {\mathrm{\Gamma }}^{𝑘}\to 𝑄\times {\mathrm{\Gamma }}^{𝑘}\times \{\text{L},\text{S},\text{R}{\}}^{𝑘}$ describing the rule $𝑀$ uses in performing each step. This function is called the transition function of $𝑀$.

All tapes except for the input are initialized in their first location to the start symbol $▹$ and in all other locations to the blank symbol $\square$. The input tape contains initially the start symbol $▹$, a finite non-blank string (``the input’‘), and the rest of its cells are initialized with the blank symbol $\square$. All heads start at the left ends of the tapes and the machine is in the special starting state ${𝑞}_{\text{start}}$. This is called the start configuration of $𝑀$ on input $𝑥$. Each step of the computation is performed by applying the function $𝛿$ as described above. The special halting state ${𝑞}_{\text{halt}}$ has the property that once the machine is in ${𝑞}_{\text{halt}}$, the transition function $𝛿$ does not allow it to further modify the tape or change states. Clearly, if the machine enters ${𝑞}_{\text{halt}}$ then it has halted. In complexity theory we are typically only interested in machines that halt for every input in a finite number of steps.

For calculation part, if $𝑀$ now is in state $𝑞$ with $𝐴=({𝛼}_{𝑖}{)}_{𝑖\in [1,𝑘]}$ are the current letters be read on $𝑘$ tapes and $𝛿(𝑞,𝐴)=𝛿({𝑞}^{\prime },𝐵,𝑡)$ where $𝐵=({𝛽}_{𝑖}{)}_{𝑖\in [1,𝑘]}$ and $𝑡\in \{\text{L},\text{S},\text{R}{\}}^{𝑘}$, then in next step $𝑀$ will enter a new state ${𝑞}^{\prime }$ from $𝑞$ where each word ${𝛼}_{𝑖}$ on the tape is replaced by ${𝛽}_{𝑖}$ and the state of the i-th head is changed to ${𝑧}_{𝑖}$, namely to Left, Stay or to Right.

Some definitions of a Turing machine add additional details to the tuple, like having a limited input alphatable $\mathrm{\Sigma }\supseteq \mathrm{\Gamma }$ or an explicit set of accepting state $𝐴\subseteq 𝑄$. We will include these details as needed.

For the definition of $𝑄$, if we allow the Turing machine to do nothing, we do not necessarily need to include an explicit halting state. Instead, we can define the machine to halt if it reaches a state where it does not move its heads, change states or any symbols on the tape. But, it is often convenient to include an explicit halting state ${𝑞}_{\text{halt}}$ (with the convention that the machine will not do anything once it reaches this state), or, for machines that accept or reject their input, explicit accepting and rejecting states ${𝑞}_{𝑎𝑐𝑐}$ and ${𝑞}_{𝑟𝑒𝑗}$.

1.1.2 Complexity

After having the definition of TM, we now can formalize the notion of running time. As every non-trivial algorithm needs to at leastread its entire input, by “quickly” we mean that the number of basic steps we use is small when considered as a function of the input length.

Definition:

Let $𝑓:\{0,1{\}}^{*}\to \{0,1{\}}^{*}$ and let $𝑇:\mathbb{N}\to \mathbb{N}$ be some functions, and let $𝑀$ be a Turing machine. We say that $𝑀$ computes $𝑓$ in $𝑇(𝑛)$-time if for every $𝑥\in \{0,1{\}}^{*}$, if $𝑀$ is initialized to the start configuration on input $𝑥$, then after at most $𝑇(|𝑥|)$ steps it halts with $𝑓(𝑥)$ written on its output tape.

We say that $𝑀$ computes $𝑓$ if it computes $𝑓$ in $𝑇(𝑛)$ time for some function $𝑇:\mathbb{N}\to \mathbb{N}$.

Remark: As a convention, we require $𝑇(𝑛)⩾𝑛$ for $𝑛$ large enough(since we always need time to read the input) and if that computes the function $𝑥\to ⌞(𝑇(𝑛))⌟$ in time $𝑇(𝑛)$ (As usual, $⌞(𝑇(𝑛))⌟$ denotes the binary representation of the number $𝑇(|𝑥|)$.), we call it time-constructable.

1.1.3 Robustness

Using this Complexity concept, we may prove our TM with $𝑘$ heads and tapes is same as simplest TM(i.e. has only 1 head and a tape) up to polynomial time transformation on time and space complexity(and this blow up is inevitabe and worst case will be $5𝑘{𝑇}^2(𝑛)$).

Proof:

Left to readers

1.1.4 Universal Turing Machine