[FOM] Re: On Physical Church-Turing Thesis
Toby Ord
toby.ord at philosophy.oxford.ac.uk
Thu Feb 12 10:02:00 EST 2004
On 11 Feb 2004, at 17:03, Dmytro Taranovsky wrote:
> I do not have references to the precise formulations of recursiveness
> vs.
> recursiveness with randomness. However, as you (Toby Ord)
> suggested, one can ask whether there are definable in second order
> arithmetic (without parameters) but non-recursive functions that are
> physically computable. A positive answer would mean that the physical
> world is non-recursive, while a negative answer would make it almost
> certain that the physical world is recursive (but possibly with
> randomness).
I agree in spirit, but there are still important complications about
what 'almost certain' means and these are difficult to resolve -- could
there be some physical non-recursive functions definable in something
stronger than second order arithmetic, yet no physical non-recursive
functions definable within second order arithmetic? And if so, how do
we catch these cases within our appropriate thesis?
> Do you have a reference for infinite travel in finite time in Newtonian
> mechanics?
The following article gives overviews of several related cases and many
references:
http://www.ams.org/notices/199505/saari-2.pdf
However, it is certainly outside my expertise.
>> There are also many rather bizarre limitations that recursive physics
>> would place upon the universe. For example, it would mean that no
>> measurable quantity (in some currently under specified sense) could
>> grow faster than the busy beaver function or slower than the inverse
>> of
>> the busy beaver function
>
> A quantity that grows faster than the "busy beaver function" would
> quickly become much larger than the observable universe, while if it
> grows at the rate of an inverse busy beaver function it would become
> essentially constant (for billions of years). I do not view the
> limitations as bizarre.
Whether a quantity could become larger than the observable universe
depends quite intimately on it's dimension. For instance, this could be
a charge or momentum or energy rather than length. However, they do
have considerable problems of their own...
Consider, however, a rather hypothetical case where there is a system
(such as an atom) with infinitely many discrete possible configurations
(such as energy level an electron can be in). Imagine, however, that
unlike in the atom case, they get more and more stable, so that putting
the system into state n+1 has a longer mean time before decay than if
it were in state n. Such a system seems intuitively plausible without
breaking limits on finite energy, space, time etc. or regarding
arbitrarily small differences in such quantities. Some rule of 'only
recursive functions are physically computable' implies that this rate
of increase of the stability of each configuration cannot grow as fast
as the busy beaver function. If it did, then by waiting a really,
really long time, we could solve the halting problem (to whatever
confidence we want). Furthermore, if any single configuration of the
universe allows such a quickly growing function, then we can still
solve the halting problem.
Now I agree that we wouldn't be all that surprised if there were no
such cases of impressively quick or slow growth (or decay), but what I
mean by 'bizarre' is that such a law is quite unlike any other physical
laws or derived results that I am aware of.
> I should note that discovery of a failure of physical Church thesis
> would be a most extraordinary event. It would have trillions of
> dollars in
> applications assuming that it can be used to *effectively* solve the
> halting problem.
Indeed. Of course we may end up with a hypermachine that requires some
other more precious resource, such as exponential time (or busy beaver
time!), or the manufacturing of certain kinds of black holes, or
bringing its observer into such a black hole and so on...
Toby Ord.
More information about the FOM
mailing list