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.

    Some of My Other Pages

    FMathL - Formal mathematical language

    my home page (http://www.mat.univie.ac.at/~neum/)

    Arnold Neumaier (Arnold.Neumaier@univie.ac.at)