[FOM] Soare's article in the BSL

[Vladik Kreinovich]

Dear Martin, Dear Colleagues, 

For us, originally from the Russian constructivist school, this article
and the work it describes are of special interest. The reason for this 
interest is that - as Soare's article rightfully mentions -- the
Russian constructivist school started with A. A. Markov Jr. (and later
N. A. Shanin) working on algorithmic problems of algebraic topology and
deciding, crudely speaking, that math foundations needs to be changed
to be more adequate in handling algorithmic issues. 

One of the main results by Nabutovsky and Weinberger cited in Soare's
article is interesting because it is formulated as a pure mathematical 
result, but its only known proof is via Turing machines and theory of
computation. It is Theorem 9.6 (p. 32 of the posted article) which says that 
on any smooth compact manifold, there exist infinitely many metrics
g for which the sectional curvature |K(g)| (crudely speaking,
curvature of the geodesics -- shortest lines) does not exceed one, and for 
which any nearby metric h with the same curvature restriction has a
larger value of diameter: D(h)>D(g). 

This result is based on a detailed description of how the diameter D(g)
depends on metric g. It turns out that this dependence forms a
fractal-type surface with many local minima and maxima, and crudely
speaking, every Turing machines can be represented as a part of this
surface - so that interesting results about Turing machines and
computably enumerable sets can lead to interesting descriptions of the
shape of this surface.

Soare does not mention this, but this result is not only an
interesting mathematically, it is also of potential interest
in foundations of physics, especially in quantization of
space-time. This relation is speculative but it is relevant for the
foundation of math. 

Namely, according to the Feynman's formulation of 
quantum mechanics, quantum mechanics means that instead of a single
trajectory of a particle or a field, we consider all possible
trajectories, and if we were originally in state A, the amplitude of
being in state B is the (normalized) integral (sum) of the values
exp(iS/h) over all such trajectories, where S is the action, and h is
Planck's constant. The probability is then determined as the square of 
the absolute value of the amplitude. 

 From this Feynman integration
viewpoint, it is important to analyze the state of all possible
trajectories. When it comes to how the actual (3D) space section of
the 4D space-time changes with time, we need to consider the set of
all possible spaces. 

Results by Nabutovsky and Weinberger provide an insight on how this set 
looks like and thus, hopefully, will help in describing the
probabilities of different changes in quantum theory of space-time.

Why is this of potential interest to foundations of math? The
experience of quantum computing shows that often, when we uncover a
new complexity in physics, we can turn this around and use the
corresponding complex physical phenomena to speed up computations. So
the fact that the space of all 3D spaces turned out to be more complex 
than geometers originally expected may be an indication that by using
quantum effects in space-time geometry, we can further speed up
computations in comparison with the know quantum computing
algorithms. 

An interesting aspect is how we can defined the distance between two
metric spaces. Within a metric space, there is a known notion of
the Hausdorff distance d(A,B) between two sets A and B: it is the
smallest eps such that:

* for every point a from A, there exists an eps-close point in B, and 

* for every point b from B, there exists an eps-close point in A.

When we have two metric spaces A and B, we can isomorphically 
embed both into a single metric space and then find the Hausdorff
distance between the embedded A and B. Michel Gromov suggested to
define the distance between the two metric spaces A and B as the
smallest possible such Hausdorff distance d(A,B).

> From: Martin Davis <martin at eipye.com>

> In the December issue of the Bulletin of the ASL, Bob Soare's article 
> "Computability Theory and Differential Geometry" discusses some of the work 
> of the topologists Nabutovsky and Weinberger to which he contributed. Has 
> anyone on FOM studied the article? I'd love to post comments on it.

Martin