Problem Detail: 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.
Asked By : user3472798
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49615
