From: Gregory Sullivan (sullivan@blaze.cs.jhu.edu)
Date: Sat Oct 11 1997 - 06:54:52 MDT
Regarding "infinitely fast computers": There is more than one concept
that can be defined here.
One precise and mathematically consistent (so far as we know) concept of
an "infinitely fast computer" is called a "machine with an oracle for the
halting problem". This concept is used in the fields of "recursive
function theory" and "computational complexity". Imagine a Turing
machine T in which during execution you can write another Turing machine
description M on a tape and then enter an "oracle query state". The
machine T in the next step then enters either a state indicating that
machine M would halt or a state indicating that machine M would not halt.
Machines with oracles for the halting problem are very powerful. By
definition, they can solve the halting problem for standard Turing
machines. Also, given a collection of axioms A and a proposition P one can
use the machine to determine if P is derivable from A or if (not P) is
derivable from A. Hence you can solve typical open mathematical
conjectures (or show P is independent of A).
See, for example, question seven on the following exam:
http://gulf.uvic.ca/~csunion/exams/CSC320_F95_Final.html
Do not expect to find machines with oracles for the halting problem in
CompUSA stores soon. I believe there is currently no known way to build
such machines. Whether we will discover physical principles that would
allow such machines to be built in the future is unknown in my opinion.
(Deeper issues of testability and Occam's razor would also be raised.)
Note, it is possible to imagine even more powerful machines. For example,
consider a machine with an oracle for "machines with oracles for the
halting problem". This is a provably more powerful machine. Indeed, one
can imagine an entire hierarchy of more powerful machines. This notion and
many others are investigated in recursive function theory. So just saying
"infinitely fast computer" is somewhat ill-defined - there are different
"varieties".
Gregory Sullivan
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:45:01 MST