[FOM] Re: On Physical Church-Turing Thesis

[Dmytro Taranovsky]

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).

Do you have a reference for infinite travel in finite time in Newtonian
mechanics?

Notice that in classical mechanics, the n-body problem in gravitation is
decidable (so as to the approximate location of the bodies at a given
time) up to (but probably not including) the moment of a collision or
ejection to infinity, when the theory breaks down because of faulty
assumptions (point particles, classical mechanics, etc.)


>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.

>As has been pointed out in another current post, this problem (as put) 
> is no different from knowing whether or not a given computer (with 
> unbounded memory) is computing multiplication.

I think that the results (should they come in) will be accepted as long
as they are reasonable.  However, I would be skeptical if the results
tell as that Peano Arithmetic is inconsistent without providing a human
verifiable proof of inconsistency.


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.


Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm