A Map of England, the Simulator Simulated, and Nonuniversality in Computation
Selim G. Akl
A reductio ad absurdum argument is used to establish that a universal computer cannot exist. The proof uses a recursive process whereby an assumed universal computer attempting to simulate itself descends into an infinite regress. Appealing to a more powerful computer to do the simulation leads to the same unavoidable conclusion.
Keywords: Church-Turing thesis, simulation, universal computer, nonuniversality in computation, map within a map, proof by contradiction, proof by counterexample, recursion, self-reference, infinite regress