1
$\begingroup$

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

enter image description here

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.

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Oct 25 '18 at 14:18
  • $\begingroup$ 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$ $\endgroup$ – David Richerby Oct 25 '18 at 14:22
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 25 '18 at 14:24
  • $\begingroup$ 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$. $\endgroup$ – Perturbative Oct 25 '18 at 14:29
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Oct 25 '18 at 14:32
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.