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$.

In Turing machine as partial function I show how use the transition function $\delta$ of a Turing machine $M$ to realize it as partial function $\mathrm{run}_M$, which even documents its own runtime. Different realizations have different runtimes. Denote by $[M](v)$ the output of a Turing machine $M$ on $v$ for some realization and denote it's runtime by $t_{[M](v)}$.

Let $f:\{0,1\}^*\to \{0,1\}^*$, let $L\subseteq\{0,1\}^*$ 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 run time at most as $\mathcal O\left(T(n)\right)\to \mathcal O\left(T(n)^2\right)$. A more precise bound is $5k\cdot T(n)^2$, the $5$ comes 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 run time 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 run time 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 run time 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 run time 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'$, which stores $M$'s $Q$ and $\delta$ in on tapes $\Gamma_Q, \Gamma_\delta$ is to specify $\delta'$ (which by construction has access to $Q$ and $\delta$), roughtly

“$ \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$”

Function

Characteristic function