[FOM] A Model of Hypercomputation
Dmytro Taranovsky
dmytro at MIT.EDU
Tue Dec 20 15:20:59 EST 2005
Models of hypercomputation tend to be of two general types: One uses
oracles or oracles in disguise, and the other uses infinite computation
in finite time. A powerful hypercomputation model (of the disguised
oracle type) rests on a surprisingly mild physical assumption:
There is a type of event that occurs an unlimited number of times, but
with frequency of occurrence decreasing sufficiently fast.
Formally, a language L is recognized by an (oracle) Turing machine iff
there is a total function A such that for every B with B(n)>=A(n), the
machine using B as an oracle halts on input S iff S is in L.
Whether or not such machines are physically constructible--and most
experts believe they are not--studying them improves our understanding
of the recursion theory. It can be proved that a language is recognized
by such a hypercomputer iff it is Pi-1-1. Thus, a language is decidable
in the model iff it is hyperarithmetic. Note that Pi-1-1 rather than
Sigma-1-1 is the correct analogue of recursively enumerable.
For sufficiently fast growing A, a recursive relation has an infinite
descending path through n iff it has an infinite descending path through
n and then through a natural number less than A(max(n, m)) where m is
the length of the given recursive definition of the relation. By
Konig's lemma, if the relation is well-founded, then the tree is finite,
and thus the machine will eventually discover that the relation is
well-founded. Also, I think that an ordinal rank for well-behaved
computations (that end in a decision) can be defined by how 'deeply' the
oracle is used and is independent of A.
The model admits a complexity theory. An oracle is given as a
one-dimensional tape with sequential access, with '1' at a position n
indicating that n is in the range. A problem can be solved in time T(n)
iff there is a Turing machine and a sparse set A such that the machine
using A solves the problem in time T(n) and that whenever nth element of
B >= nth element of A, the machine using B correctly solves the problem.
(There may be an at most polynomial unreasonable speed-up from the
peculiarities of A.) Thus, a language has recursive complexity iff it
is recursive, and arithmetic complexity iff it is arithmetic.
Also, a set is definable in first order arithmetic with a sufficiently
fast growing function A (independent of A) iff it is recursive in a
finite hyperjump of 0. Still higher complexity is reachable by
computers that use a sufficiently fast growing function A and a function
B that grows sufficiently fast relative to A.
Dmytro Taranovsky
More information about the FOM
mailing list