Taking the Finiteness of Computers into Account


Re-design theoretical computer science in a way that takes the finiteness of computers into account. Moreover, develop a paradigm to turn classical results with respect to computability into decisive analyses and prognoses about what is and what is not possible in a limited world.


Leave Turing machines as they are: the built-in infiniteness assumptions result in an elegant theory indeed, but do not correspond to the fact that in reality computations always take place on finite devices. The limitations of computation on a finite device are an important reason why people use computer networks.


Unfortunately, it is not obvious when the challenge formulated above is actually met. Nevertheless, it is considered a clear challenge to reformulate the basics of the theory of computability in terms of infinite families of truly finite devices rather than in terms of idealized finite devices with built-in infiniteness assumptions.


One of the issues that is encountered when taking the finiteness of computers into account in the theory of computability is the following.

Consider a stylized von Neumann computer with a load/store architecture, and separate data memory and program memory, where

This set-up raises interesting questions like: The classical theory of computability does not provide answers to questions like these.

Relevant literature

The instruction implicitly executed by a Turing machine on a test or write step must be capable of reading or overwriting the contents of any cell from the infinite number of cells on the tape of the Turing machine. In reality, computers do not have such instructions. How to get rid of this kind of infinity by means of multi-threading and thread forking, is shown in: Examples of stylized von Neumann computers are the strict load/store Maurer instruction set architectures introduced in: How the transformations on the states of the main memory of such a load/store instruction set architecture that can be achieved depend on the operating unit size is studied in: The finiteness of computers is also the principal driving factor of the work presented in: All help to make the information on relevant literature more complete is greatly appreciated by me.

Last update: July 9, 2019