[FOM] A Newtonian computing design
Harvey Friedman
friedman at math.ohio-state.edu
Wed Feb 11 15:24:39 EST 2004
This simple design is based on Newtonian inverse square law gravitation. The
ideas can be adapted to other deterministic contexts. We also comment on how
this could be adapted to probabilistic theories.
The idea I am putting forth is at least the plausible possibility that with
sufficiently spectacular purely mathematical developments, that could be a
design of an analog computer, which is not absurd physically, and which
would allows us to get "answers" to questions we want to know that we seem
to have no way of handling otherwise.
Of course, the mathematics involved, if it can be done at all, is going to
be awesomely difficult, and obviously one is going to have to carry this
program out for less naïve physical theories. But it appears that if we take
this program seriously, then there are some manageably difficult purely
mathematical subproblems.
**Perhaps readers can spot fundamental flaws in this approach, either
mathematically or physically.**
##############################
1. The goal is to determine whether any given Turing machine with at most
100 quadruples eventually halts at the empty tape input.
2. Above and beyond all, prove that lots of very interesting problems we
don't know the answer to are demonstrably equivalent to a problem of form 1,
by explicit conversion.
3. Give a practical algorithm that converts any Turing machine with at most
100 quadruples to an "approximating initial configuration" for Newtonian
inverse square law gravitation with at most 100 particles.
4. This "approximating initial configuration", aic, is of the following
form. Particles are numbered 1 through 100. Each particle is assigned three
closed intervals [a,b],[c,d],[e,f] for its initial position, and three
closed intervals [g,h],[i,j],[k,l] for its initial velocity. It is required
that each endpoint is a base 2 decimal with exactly 100 digits to the right
of the decimal point, and there are at most 100 digits to the left of the
decimal point. Also, it is required that the length of each interval be
2^-100.
5. Prove, as a purely mathematical fact, that if any given Turing machine
with at most 100 quadruples eventually halts, then if we start with ANY
initial configuration compatible with the corresponding aic (given by 3),
there will be a collision in less than 1 unit of time.
6. Prove, as a purely mathematical fact, that if any given Turing machine
with at most 100 quadruples never halts, then if we start with ANY initial
configuration compatible with the corresponding aic (given by 3), there will
be no collision in less than 2 units of time.
###################################
Simple modifications of this design can be made to accommodate probabilistic
theories. If we assume absolute control of the setting up of the initial
configuration - of course subject to inevitable error as in the design above
- then we can relax 5,6 as follows.
5'. Prove the following, as a purely mathematical fact. Let TM be a Turing
machine with at most 100 quadruples that eventually halts. Let V be the
space of initial configurations compatible with the corresponding aic (given
by 3). V is a higher dimensional closed rectangle with the usual probability
measure. Then the set of initial configurations in V that lead to a
collision in less than 1 unit of time has probability measure at least 2/3.
6'. Prove the following, as a purely mathematical fact. Let TM be a Turing
machine with at most 100 quadruples that eventually halts. Let V be the
space of initial configurations compatible with the corresponding aic (given
by 3). V is a higher dimensional closed rectangle with the usual probability
measure. Then the set of initial configurations in V that lead to NO
collision in less than 2 units of time has probability measure at least 2/3.
An obvious additional modification will accommodate only probabilistic
control of the initial configuration.
Harvey Friedman
More information about the FOM
mailing list