# Taking the Finiteness of Computers into Account

## Challenge

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.

## Rationale

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.

## Remark

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.

## Illustration

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

• the word length of both the data memory and the program memory is k bits;
• the size of the data memory is l words;
• the size of the program memory is m words;
• the size of the operating unit is n bits;
• the instruction set covers all transformations on the state of the operating unit.
This set-up raises interesting questions like:
• Which transformations on the state of the data memory are "programmable" on this computer?
• What happens to the programmable transformations on the state of the data memory if m is decreased and/or n is increased?
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