FOM: Central Issues in Foundations 1

[Harvey Friedman]

A main purpose for the founding of the FOM e-mail list was the open
discussion of central issues in foundations of mathematics. Since topics in
foundations of computer science are closely connected, an open discussion
of them would obviously also be very valuable for the FOM list.

As I have stressed many times on the FOM,

**issues in f.o.m. no longer play a significant role in the formulation of
research projects in mathematical logic, or even in the evaluation of
research in mathematical logic by mathematical logicians. Nor does any
concept of general intellectual interest.**

As this situation continues, we will see communities outside mathematical
logic tending to value mathematical logic solely on the basis of what
direct applications it has outside mathematical logic. Although significant
direct applications exist, this is certainly not an enviable position for
mathematical logic to be in. Hence my view that it is crucial for
mathematical logic to return to its roots in the foundations of
mathematics.

In my view, there has not been a sufficient concentration on what (at least
some of) the central issues in foundations are, what progress has been made
on them, formal approaches to them, prospects for addressing them,
etcetera, on the FOM list. This includes my postings. I have made a lot of
numbered postings (#1 - #56) announcing mathematical results. Most of these
postings represent advances in central issues in the foundations of
mathematics. But I haven't written enough about the central issues
themselves. Of course, a limited number of subscribers know what some of
these central issues are and how those numbered postings relate to them.
Even for that limited number of subscribers, it would be incomparably
preferable if there was a systematic discussion of various specific central
issues in foundations in particular, and central issues in foundations in
general.

There have been recent postings that, in various ways, suggest that results
about the lattice of r.e. sets, r.e. degrees, Turing degrees, shed light on
central issues in the foundations of computer science. This suggestion can
be considered to be implicit in the so called name change movement from
"recursion theory" to "computability theory" in which all of the old names
such as "recursive" or "recursively enumerable" or "r.e. degrees" are
changed to "computable" or "computably enumerable" or "c.e. degrees."

I would like to ask: just what central issues in the foundations of
computer science (or mathematics) have light shed on them by results about
the lattice of r.e. sets, r.e. degrees, Turing degrees? NOTE: I'm only
asking this in light of the previous paragraph.

Here is a very well known example of a central issue in the foundations of
computer science. I have stated it in a way that highlights its general
intellectual interest.

Many applications of computers take the following form. We are given some
finite amount of data that arises in some real world situation. We wish to
determine whether some particular property of real world interest holds of
this data. Or we wish to find a real world object that optimizes some
aspect of the data. Examples: given a "network", is there a path from a
given point to another obeying a constraint, or find the cheapest path from
a given point to another. I.e., traveling salesman and related problems.
Also, various code cracking problems, etcetera.

Question: In one direction, can we always find a program to solve the
problem (on a real world computer in a real world amount of time)? In
another direction, Are there completely unbreakable codes, and what exactly
does that mean?

The foundational issues are many. One is to give appropriate mathematical
models of these problems. The most well known models are asymptotic, and
lead immediately to the P = NP problem and related problems. They are still
unsolved. Other models take into account finite bounds on the sizes of
everything involved, where the finite bounds go to infinity. More severe
models inject absolutely finite bounds, based on physical reality. Other
central issues concern the observed fact that real world data is not only
of reasonably small size, but not at all random. A thorny foundational
problem is how one wishes to take the special nature of real world data
into account.

But the intriguing bottom line is that we strongly suspect that all sorts
of things we really want to do in the real world - from optimization under
various constraints, to breaking various coding schemes - cannot be done in
the real world. However we have essentially no such impossibility proofs.

Note that this sets the bar pretty high for a central issue in the
foundations of computer science. Also note that there are a variety of
central issues embedded in this brief description.