Non-finite computation in Malament-Hogarth spacetimes.
Lucian Wischik.
M.Phil. dissertation.
June 1997.
Abstract.
Recent work in the field of relativitistic space-times suggests that it may
be possible for a machine to perform an infinite number of operations in a finite time.
Investigation of these machines has three motivations. First, because the machines may
be physically possible, they have implications for the general question of what problems
are theoretically solvable. Second, the physical laws that govern their operation give
rise to a rich mathematical structure. Third, by investigating general relativistic
computation, we get a clearer picture of properties peculiar to the special case of
Turing computation. A mathematical formalisation of the operation of the machines is
presented, and shown to correspond to their physical operation. It is proved that
there is no satisfactory way to give a finite description for the machines.
Although Gödel sentences exist if attention is restricted to a finite set
of machines, further results about the computational power of the machines
and their equivalence to the Kleene arithmetical hierarchy are shown to
depend upon arbitrary assumptions. This gives rise to a non-finite
version of the Church-Turing thesis. The case of non-finite computation is
used to arrive at an abstract principle of computation that is independent of physics.