Turing Machine Encoding

A Turing Machine encoding is some way to represent an object (a graph, a variable, even an algorithm) as a finite string, that can be processed by a Turing machine.

The assumptions of Turing Machine encodings means TMs are a universal model of computation, able to run any type of program (including other Turing Machines!)

Definition §

TM Encoding

Let $O$ be a discrete object. Then the TM encoding for $O$ is given by $⟨O⟩$, and this encoding exists for every discrete object $O$.

If $O_1,O_2,\dots O_n$ is a finite list of objects, then their encoding can be given by $⟨O_1,O_2,\dots O_n⟩$. Note that we don’t have to provide an explicit encoding, we can just assume that one exists.