patternMinor
What is an "encoding" of a TM?
Viewed 0 times
whatencodingstackoverflow
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#49615, answer score: 7
Revisions (0)
No revisions yet.