Category Advanced

On Rogozhin's Universal Turing Machines

Every now and then, we see some headline about Turing Completeness of something. For example, Minecraft or Dwarf Fortress, or even Minesweeper are famous examples of accidentally Turing complete systems.

If you know what a Turing machine is (and you should) you will have an intuitive idea of the claim: you know that X can compute any computable function. Sure; but if you stop thinking about that for a bit, it is not so intuitive how we can prove that. If we think long enough, we can start understanding how X can simulate a Turing machine, but how can we be sure that we can encode a Universal Turing Machine and what is the program of a UTM and how we can prove that it is, in fact, universal?