# What is the “description” of a Turing machine?

I am currently reading about the Halting Problem in my course on the theory of computation and the following was given in my lecture slides Now my question is that if $$d$$ is the description of a Turing machine, what exactly is $$d$$ from a strictly mathematical point of view? The way that $$d$$ is written above seems to suggest that $$d \in Q$$ (i.e. that $$d$$ is a state of the Turing machine $$T$$), but I can't be entirely sure.

• Think of it as a listing of a program: a complete description of the TM, one which you could use to build the TM. – Rick Decker Oct 25 '18 at 13:37

The description is a string that encodes the formal specification of the machine, comprising:

• the set of states,
• the start state,
• the set of halting states (or, where appropriate, the sets of accepting and rejecting states),
• the tape alphabet,
• the input alphabet,
• the transition function.

Some authors also explicitly include the identity of the blank symbol in the description of the machine; others leave it to convention (e.g., stating that the alphabet will always be $$c_1, \dots, c_k$$ for some $$k$$, and $$c_1$$ is the blank symbol).

• I was unaware that there was a difference between the tape alphabet and the input alphabet. Isn't the input just things written on the tape before the machine starts? Why would you need a separate alphabet for that? – Arthur Oct 25 '18 at 14:18
• An alphabet is a set of symbols. The input alphabet is the set of symbols that can appear in the input. However, these aren't the only symbols that can appear on the tape: at the very least, the blank symbol usually isn't allowed to be a part of the input. The machine might also want to use other symbols as it processes. For example, suppose you want to design a Turing machine whose input is a string of $0$s and $1$s and which decides whether the input contains the same number of $0$s as $1$s. The easiest way to do this is to scan back and forth and, on each pass, replace one $0$ and one $1$ – David Richerby Oct 25 '18 at 14:22
• with, say, an $x$. Repeat until either the (non-blank part of the) tape only has $x$s (accept) or it's just $0$s and $x$s or just $1$s and $x$s (reject). $x$ can't appear in the input but it's written to the tape during the computation. – David Richerby Oct 25 '18 at 14:24
• So what you're then saying is that $d = (Q, \Sigma, \Gamma, \delta, q_0, F)$ where $Q$ is the set of states, $q_0$ the start state, $\Sigma$ the input alphabet, $\Gamma$ the tape alphabet and $\delta$ the transition function. So $d$ actually denotes a Turing machine, my question then is why not just say given a Turing machine $T$ blah blah blah... instead of given a description $d$ of a Turing machine $T$ blah blah blah, I don't see exactly why one should use the latter when $T$ itself is a description of the Turing machine $T$. – Perturbative Oct 25 '18 at 14:29
• No, $d$ is a string of symbols that encodes the mathematical object $(Q,\Sigma,\dots)$. The only real difference between them is that the description can be used as the input to a Turing machine. "Morally speaking", they mean the same thing, but Turing machines can only take strings as input, not general mathematical objects. – David Richerby Oct 25 '18 at 14:32

A formal way to approach this is to note the existence of Universal Turing Machines.

Let U be a universal turing machine. Then, for any other Turning Machine T there exists a tape state T' such that for every tape state S, there exists a tape state S' such that U(T' S') generates the same output at T(S).

Basically, a Universal Turing Machine can take as initial input a "description" of another Turing Machine (T'). From that "description" it can then consume the a transformation of a tape state and simulate everything the source Turing Machine does.