encoding of machines as strings

A compiler reads a program, but to the compiler that program is just a text file, a string of characters. Source code is data. The same trick is the quiet foundation of all of computability theory: any object you care about, a graph, a grammar, a number, or even another machine, can be written down as a finite string over some alphabet, so that a machine can take it as input. Encoding of machines as strings is the specific, crucial case where the object being written down is itself a Turing machine.

We write <M> for a string that fully describes a machine M: list its states, its tape alphabet, its start and accept states, and its transition function, all spelled out in some fixed, agreed format over a finite alphabet (binary, say). Then <M, w> is a single string encoding both a machine M and an input w together. The exact format does not matter, only that the encoding is finite, that any well-formed machine has one, and that the description can be mechanically parsed back. By convention we also decide that any string that is not a valid encoding simply describes some fixed do-nothing machine, so every string is a legal input.

This idea is small but world-changing. Because a machine can be fed the encoding of another machine, machines can take machines as input and run them, which is exactly what a universal Turing machine does and exactly how the stored-program computer works (a program is data in memory). It is also the gateway to self-reference: a machine can be handed its own encoding, the seed of the recursion theorem and of the diagonalization that proves the halting problem undecidable. The honest caveat: encodings must be 'reasonable', easy to parse, with size polynomially related to the natural size of the object, otherwise you could smuggle in extra computation through a fiendishly clever code, which would distort complexity results.