Definition
Encoding of a Turing Machine
An encoding maps a Turing machine
to a finite code (a string over a fixed alphabet, e.g. , or a natural number) such that:
- the map
is computable and (typically) injective, - there is a computable decoding that recovers
from , - 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.