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:
-
J.A. Bergstra and C.A. Middelburg.
Program algebra with a jump-shift
instruction.
Journal of Applied Logic, 6(4):553--563, 2008.
DOI:
10.1016/j.jal.2008.07.001.
-
J.A. Bergstra and C.A. Middelburg.
Data linkage dynamics with shedding.
Fundamenta Informaticae, 103(1--4):31--52, 2010.
DOI:
10.3233/FI-2010-317.
-
J.A. Bergstra and C.A. Middelburg.
Instruction sequence based non-uniform complexity
classes.
Scientific Annals of Computer Science 24(1):47--89, 2014.
DOI:
10.7561/SACS.2014.1.47.
-
J.A. Bergstra and C.A. Middelburg.
On algorithmic equivalence of instruction
sequences for computing bit string functions.
Fundamenta Informaticae, 138(4):411--434, 2015.
DOI:
10.3233/FI-2015-1219.
-
J.A. Bergstra and C.A. Middelburg.
Instruction sequence size complexity of
parity.
Fundamenta Informaticae, 149(3):297--309, 2016.
DOI:
10.3233/FI-2016-1450.
-
J.A. Bergstra and C.A. Middelburg.
Instruction sequences expressing multiplication
algorithms.
Scientific Annals of Computer Science 28(1):39--66, 2018.
DOI:
10.7561/SACS.2018.1.39.
All help to make the information on relevant literature more complete
is greatly appreciated by
me.
Last update: July 9, 2019