A hierarchy of idealized computer architectures
It is interesting to consider computability results which
apply not only to traditional idealized computer architectures with
infinite memory but finite execution speed, but also to finite
computers and to hypothetical supercomputers with infinite computing
power. As prototypes we consider the following computers:
Neumann,
a computer with finite memory and finite execution speed,
Turing,
an implementation of a universal Turing machine (with infinite,
primitive memory),
Platon,
a flexible modern computer, able to model the platonic world of
precise concepts, but with countably infinite memory and
unlimited integer addresses,
Achill,
who can execute any elementary statement in a time of
the programmer's choice and thus -- according to
Zeno's paradox
-- can do infinitely many steps in finite time,
Cantor,
who can even execute arbitrary transfinite recursions in finite time;
cf.
Infinite time Turing machines (by Hamkins and Lewis)
Our own results will appear here in due course.
FMathL - Formal mathematical language
my
home page (http://arnold-neumaier.at/)
Arnold Neumaier (Arnold.Neumaier@univie.ac.at)