Encoding of a Turing Machine

computation

Definition

Encoding of a Turing Machine

An encoding maps a Turing machine $M$ to a finite code $⟨M⟩$ (a string over a fixed alphabet, e.g. $\{0,1\}$, or a natural number) such that:

• the map $M\mapsto ⟨M⟩$ is computable and (typically) injective,
• there is a computable decoding that recovers $M$ from $⟨M⟩$,
• the set of well-formed codes is decidable or at least recursively enumerable.

Different reasonable encodings are equivalent up to computable translation; results like Rice’s Theorem do not depend on the particular choice.