[FOM] A Model of Hypercomputation

[Dmytro Taranovsky]

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