The Finite Nature of Computability
Sunday, June 22nd, 2008In Introduction to Metamathematics, S.C. Kleene begins his chapter on Turing machines with the following informal characterization [1]:
Suppose that a person is to compute the value of a function for a given set of arguments by following preassigned effective instructions. In performing the computation he will use a finite number of distinct symbols or tokens […]