Abstract

Turing computation over a non-linguistic domain presupposes a notation for the domain. Accordingly, computability theory studies notations for various non-linguistic domains. It illuminates how different ways of representing a domain support different finite mechanical procedures over that domain. Formal definitions and theorems yield a principled classification of notations based upon their computational properties. To understand computability theory, we must recognize that representation is a key target of mathematical inquiry. We must also recognize that computability theory is an intensional enterprise: it studies entities as represented in certain ways, rather than entities detached from any means of representing them