[FOM] Re: On Physical Church-Turing Thesis

[Toby Ord]

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.