Let's discuss the 1-tape Turing machine, i.e. $k=1$. The general case is then clear.

A Turing machine $M\equiv\langle Q,\Gamma,\Sigma,\delta\rangle$ in $\mathrm{TM}_1$ is interpreted to encode how to walk along a tape of symbols and also write on it. The set $\Gamma=\{\Box,\triangleright,0,1,\dots\}$ is an alphabet of characters, the subset $\Sigma$ of it is the legal input alphabet, $Q$ is called a set of states and and $\delta$ is called the transition function. Here is how it goes: Starting the machine, we imagine an infinite string of characters

$ \triangleright\ \underset{q_\mathrm{start}}{a}\ b\ c\ d\ \cdots\ v\ w\ x\ y\ z\ \Box\ \Box\ \Box\ \Box\ \Box\ \cdots $

The input is the data between $\triangleright$ and the first $\Box$ and can be any word in $\Sigma^*$. The so called writer head starts out at the first input character in the state $q_\mathrm{start}$. Now for each given configuration, the transition function $\delta$ tells us how to get to the next one. Depeding on the state $q_j\in Q$ we are in, the $\delta$-component for “$\Gamma\to\Gamma$” tells us what how to overwrite the character at the writer head. And then the last component “$\to\{\mathrm{L},\mathrm{S},\mathrm{R}\}$” puts out the an left/stay/right-information and hence tells us where which place to move the head next. Let's denote the statement “The machine is currently in the state $q_j$ with the tape reading $\triangleright\ a\ b\ c\ d\ \cdots $ and writer head over $b$” by

$ \triangleright\ a\ \underset{q_j}{b}\ c\ d\ \cdots $

If the transition function on $\langle q_j,b\rangle$ evaluates as $\delta(q_j,b)=\langle q_k,x,\mathrm{R}\rangle$ then we interpret this as the instruction.

$ {\triangleright\ a\ \underset{q_j}{b}\ c\ d\ \cdots}\hspace{.2cm} \mapsto \hspace{.2cm}{\triangleright\ a\ x\ \underset{q_k}{c}\ d\ \cdots} $

The simulation is over when the state reaches $q_\mathrm{halt}$.

As a remark, one can reconstruct all of $\langle Q,\Gamma,\Sigma,\delta\rangle$ from $\delta$ along. Moreover, for any Turing machine, one can find another one with uses the reduced alphabet $\Gamma=\{\Box,\triangleright,0,1\}$. However, the latter compressed version runs longer, as is discussed in the Theorem section.

The following sucker lets you compute if your input is a string of 0's of length $2^n$ for some $n$. The picture encodes $\delta$ and $\triangleright$.

The conventions in the pic (Snipsers book) are slightly different, blanks are denoted by another symbol, $q_\mathrm{start}$ is $q_1$, there are two final states $q_\mathrm{accept},q_\mathrm{reject}$ instead of $q_\mathrm{halt}$ and $\mathrm{x}$ is used for what we would likely use $1$. The simulation is considered over when $\delta$ doesn't tell you anymore what to do.

For example, for the input “$0000$” we get

1. $ \triangleright\ \underset{q_1}{0}\ 0\ 0\ 0\ \Box\ \Box\ \cdots $
2. $ \triangleright\ \Box\ \underset{q_2}{0}\ 0\ 0\ \Box\ \Box\ \cdots $
3. $ \triangleright\ \Box\ \mathrm{x}\ \underset{q_3}{0}\ 0\ \Box\ \Box\ \cdots $
4. $ \triangleright\ \Box\ \mathrm{x}\ 0\ \underset{q_4}{0}\ \Box\ \Box\ \cdots $
5. $ \cdots$

We write $\mathrm{TM}\equiv\mathrm{TM}_1$.

The above definition of a Turing machine does not formalize the concept of the working memory as such. In Turing machine as partial function I come up with a procedure which does just that: For any $M\in\mathrm{TM}$ we get a recursively defined partial function $\mathrm{run}_M$, which exactly behaves like the computation using a tape, and as a side effect I also document the runtime. There are denoted by $Mv$ and $t_{Mv}$, respectively.

Now let $f:\{0,1\}^*\to \{0,1\}^*$. Denote by $\lfloor\ \rfloor$ an encoding to strings.

For a 2-tape Turing machine $M\in\mathrm{TM}_2$, we write $Mxy$…

Let $L\subseteq\{0,1\}^*$ be a set of bit strings and let $\chi_L:\{0,1\}^*\to\{0,1\}$ be the associated characteristic function.

Let $T:\mathbb N\to\mathbb N$ and denote the length of the string $v$ by by $\left|v\right|$. Note that $T(n)$ denotes the body of the function $\lambda n.T(n)$, i.e. $n$ is a placeholder for a function argument.

Switching from a $k$-tape machine to a 1-tape machine modifies the runtime at most as $\mathcal O\left(T(n)\right)\to \mathcal O\left(T(n)^2\right)$. The trick is to partition the tape into a grid of length $k$, e.g. the information from tape $2$ are positioned at $2,2+k,2+2k,2+3k,\dots$. A more precise bound for the time scaling is $5k\cdot T(n)^2$, the $5$ coming from additional necessary left-right-left-right-left-sweepings of the head over the whole tape.

Switching from one machine $M$ with alphabet $\Gamma$ to another $M'$ with the small alphabet $\{\triangleright,\Box,0,1\}$ modifies the runtime at most by a factor logarithmic in $\left|\Gamma\right|$

For any Turing machine one can find an alternative oblivious Turing machine, which principally works the same, but where the heads movements don't depend on the tape content but are predetermined in advance for all inputs. For 2-tape Turing machines, using such an alternative also results in an logarithmic overhead.

Switching to a tape which is infinite in both directions gives a runtime bonus factor of $\frac{1}{4}$. Other variations are two- or three dimensional tapes and random access (larger head movements at a single step), but they don't have a significant effect on runtime neither.

Encode the original Turing machine $M$ into a string itself, i.e. $\triangleright\ \mathrm{Mcode}\ \Box\ \Box\ \dots$, where $\mathrm{Mcode}$ is the so called “machine code” of the machine $M$. Now have another machine $M'$ (designed for taking other Turing machines as additional input and copy what they would do) simulate the machine code together with some normal input for $M$. This changes the runtime only as $\mathcal O\left(T(n)\right)\to \mathcal O\left(\lceil\log T(n)\rceil\cdot T(n)\right)$.

Turing showed that there are so called universal Turing machines ($\mathrm{TM}\mathcal U$), which are capable of running any other Turing machine $M$ when given in machine code format. Such a universal machine $M'$ might then be physically realized via hardware (like a PC, designed for executing $\delta$ with 3 Gigahertz) and a machine code $\mathrm{Mcode}$ might come from a computer program written by a 6 year old fat girl from Ohio. This video is from a nerd who wanted to build himself a hands on realization of a $\mathrm{TM}\mathcal U$.

Without going into detail, the idea is the following. Remember that a general transition function is of the type:

$ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$

Consider a transition function $\delta$ for a Turing machine $M$ we want to simulate:

$ \delta: Q\times\Gamma \to Q \times \Gamma \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}$

The art in designing the universal Turing machine $M'$ (and in particular $\delta'$, which by construction has access to $Q$ and $\delta$) in terms of $M$. One key is to story $Q$ and $\delta$ of $M$ on $M'$'s tapes $\Gamma_Q, \Gamma_\delta$. Roughly

“$ \delta': Q'\times\Gamma \times \Gamma_Q \times \Gamma_\delta \to Q' \times \Gamma \times \Gamma_Q \times \Gamma_\delta \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^3$”

After this 3-tape Turing machine is constructed we can concert is to a 1-tape Turing machine, if necessary.

Function

Characteristic function