5
$\begingroup$

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,w \rangle | \text{ ...etc} \}$, where obviously this would normally stand for $M$ being a TM and $w$ being a string. However, later in the proofs, we replace the $w$ (a string) with an "encoding of a turing machine". Sometimes it's even "an encoding of the TM, $M$".

I'm rather lost on this idea. How do we pass an "encoding of a TM" into a parameter for a string? How do we run that on a TM? Maybe I'm misunderstanding the definition of an "encoding of a TM", which I assume to be the TM itself somehow converted into a string format.

Would anyone mind explaining this to me? I'm sure truly understanding this concept would immensely help me in writing further reductions.

$\endgroup$
  • 1
    $\begingroup$ I feel your doubt is related to difference in syntax and semantics of a string. When we say encoding of a Turing machine , we mean we can write it form of the string, such that given the method of encoding and the string, you can understand the physical Turing machine it represents. $\endgroup$ – sashas Nov 18 '15 at 0:20
5
$\begingroup$

A Turing machine $M$ can be described as a 7-tuple $(Q,F,q_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc.

The encoding of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $M$. You can think of it as "writing the 7-tuple as a binary string" (but this is a simplification). So the encoding of M, is just a string that describes how the TM works.

The last observation is that if you know the encoding - you know everything about the TM; specifically, if $\langle M \rangle$ is given as an input (to a machine $M'$), the TM $M'$ can "run" or "simulate" what $M$ would have done on any given input -- the machine $M'$ knows the states $Q$ of $M$ and the transition $\delta$ of $M$, so it can imitate its actions, step by step.

$\endgroup$
  • $\begingroup$ Your note that we can think of it as "writing the 7-tuple as a binary string" was very helpful. So In most cases where we have a language, say, 'P' and it is written as P{ <<M>, M'> | ... } where M' is the encoding of M, and we run M on M', what would the result be? We are literally running a TM on another TM (itself). How would that even work? $\endgroup$ – user3472798 Nov 18 '15 at 0:32
  • 1
    $\begingroup$ Yes! when you run $M$ on a string $w$ you don't care what $w$ "means". It is just a string... only in our mind this string has a "meaning" of being the encoding of some machine... $\endgroup$ – Ran G. Nov 18 '15 at 0:42
  • $\begingroup$ Huh, gotcha. Thank you! Just one last question, how would it yield a useful result, running M on M'? If the encoding of a machine is just a binary number, how would running this on it's twin yield something of use? What is an accept/reject telling us in this case? $\endgroup$ – user3472798 Nov 18 '15 at 0:47
  • 1
    $\begingroup$ This depends on the specific $M$ and the context. See this answer for some examples of reductions that get other machine's encodings as input, and the "meaning" it makes. $\endgroup$ – Ran G. Nov 18 '15 at 1:00
  • 1
    $\begingroup$ You should probably add that in the context of computability, we need that $\langle \cdot \rangle$ and its (partial) inverse are effectively computable. This corresponds to the set of all TMs (resp. their encodings) being recursively enumerable, a non-trivial insight. The universal Turing machine is another affected concept. $\endgroup$ – Raphael Nov 18 '15 at 12:09
3
$\begingroup$

Part of your confusion seems to be about the nature of $\langle\,M\,\rangle$. That's just a string like any other, except that it is a complete description of $M$. For example, a managable project for an introductory programming course might be to write a program which, when given an input describing a TM, shows the action of that TM on some input. What would such a program need as a description of a TM? We might decide to do something like this:

  1. A list of the states, [q0, q1, ... , qn].
  2. A description of which states are start, accept, and reject states, s, a, r, where each of these is one of q0 ... qn
  3. A list of move rules, of the form (p, a, r, b, d) corresponding to the move $\delta(p, a) = (r, b, d)$, i.e., in state $p$ with input $a$, change to state $r$, write $b$ on the tape, and move in direction $d$ (left or right).

With that information, the program to simulate the TM wouldn't be too hard to write. The point here is that the string

[q1, q2], q1, q1, q2, [(q1, 0, q1, 1, R), (q1, 1, q2, 1, L), ... ] 

would be a complete description of a TM, suitable for use as the basis of the simulation by our assigned program. This description is what we call $\langle\,M\,\rangle$. Now we might further encode this in a more limited alphabet, but that's immaterial. The point is that it can be done: any TM can be described by a suitable string.

$\endgroup$
  • $\begingroup$ The same comment I posted at Ran G.'s answer applies here: it's very important that this encoding is computable, as is it's inverse. $\endgroup$ – Raphael Nov 18 '15 at 12:10

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.