[FOM] On Physical Church-Turing Thesis

[Harvey Friedman]

On 2/8/04 5:55 PM, "Dmytro Taranovsky" <dmytro at mit.edu> wrote:

> ... I discuss the physical Church thesis and its relation to
> physical theories.  The physical Church thesis claims that every
> physically realizable machine is recursive but for the ability to pick
> random numbers.  A related claim is that every mental process is
> recursive (but for random choices).
...
> The scenario in "Non-Turing computations via Malament-Hogarth
> spacetimes" by Etesi and Nemeti involves traveling into a rotating black
> hole through the inner horizon.
> 
> I suspect that the scenario is unphysical because it involves crossing
> Cauchy horizon and what happens after an infinite amount of time has
> elapsed.  In most models, the observer would encounter infinite blue
> shift and a deadly singularity at the inner horizon.  Because as the
> observer approaches the horizon the blue shift approaches infinity,
> there is likely a practical limit on how late a signal can be sent
> without destroying the observer.

Are there any Pi-0-1 sentences that you or I or Nemeti want to know the
truth value of so badly that we would risk this kind of horrible death?
Remember, we have to decide on which sentence or sentences to use before we
could get funding for the trip (smile).

On a less cosmic(!) note, what is known about the following questions.

Suppose we are given a (maybe even fairly small) finite number of rational
points in R^3 representing the initial positions of some Newtonian particles
subject only to the Newtonian inverse square law of gravitation (say, in
geometric units). We are also given initial velocity vectors for these
particles, again by rational numbers.

We now ask:

1. Given an integer N, will there be a collision within N units of time?

2. Given an integer N, will there be a collision at exactly N units of time,
and no earlier or later?

3. Will there ever be a collision?

4. Does the diameter of the system become arbitrarily large?

Now suppose that we are given a second set of data, just like the first. Now
we ask:

5. Which system has a collision first? Or will there be a tie?

We want to know the recursion theoretic status of these algorithmic
questions.

What about polynomial time hardness with respect to log space linear time
reductions?

Harvey Friedman