User:IssaRice/Computability and logic/Motivation for encoding

The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answer is only implicit in the theorems which are presented).

I think the three main reasons are:

• Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.
• Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.
• Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we get a bunch of interesting diagonalization theorems, the universal partial recursive function, etc.