Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?

From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 01/12/05 

Date: Wed, 12 Jan 2005 08:22:07 -0500

tchow@lsa.umich.edu wrote:
> Ralph Hartley <hartley@aic.nrl.navy.mil> wrote:
>
>>There are stronger versions of the CT thesis that imply it. For instance if
>>the laws of physics are computable. Then any physical object, including
>>mathematicians, are effectively describable.
>
> By "the laws of physics are computable," I'll take you to mean something
> roughly like the following: The universe is finite and discrete, with
> one time dimension and some number of spatial dimensions; it has an
> initial state, and for all t, the state at time t is determined by a
> deterministic and recursive function of the states at times less than t.

That wasn't close. Perhaps, I should have been more clear about what I
*did* mean.

Physical CT thesis (my definition): The laws of physics do not admit any
computing device more powerful than a TM.

Or: No physical system can compute any non-recursive function.

There should be some fine print about what it means for a physical system
to "compute" a function, but the details of a good definition shouldn't matter.

Assume that, given an input, you can construct an initial state by any
recursive process, let the physical system evolve, and use any recursive
process (with access to the entire history if needed) to decode the result
(This could be stated without reference to time evolution, but it is
trickier). States of the system may be represented in any reasonable way.

The thesis is not a tautology. Many theories include physical constants
that must be measured, not calculated. Those real numbers could be
recursive, or not. It is quite likely that they are essentially random
(which technically makes them non-recursive, but not good for much). In
principle, they could even permit devices that solve the halting problem,
e.g. if the fine structure constant encoded Chaitin's omega.

With that caveat, I don't know of any real physical theory that permits the
computation of non-recursive functions.

Ralph Hartley

Relevant Pages

  • Re: Penrose vs the Robot
    ... then is it true that it is STRONGER than a Turing machine? ... by a universal model computing machine operating by finite means." ... "Quantum mechanical measurements on a physical system are ... "Penrose argues that the nondeterminism of physics ...
    (sci.logic)
  • Re: Symbol Grounding Problem (attn: Vend)
    ... For example, Physical CT covers operations on real-valued quantities, continuous dynamical processes operating on strings (as in certain kinds of connectionist computing and molecular computing), and quantum processes. ... brain over biological time. ... not make the physical system a Turing Machine. ... "e have good reason to believe that the laws of physics are computable, so that we at least ought to be able to simulate human behavior computationally." ...
    (comp.ai.philosophy)
  • Re: A dilemma
    ... Not knowing your math or computing background I'm not sure what to point in your direction though. ... A hypercomputer working with real numbers could theoretically calculate things that a UTM could only ever approximate whilst taking all the time and space in the universe to do so. ... If the brain is an ARNN, and consciousness is an epiphenomenon of that hardware, then you'll never build one out of Lego, no matter how much you have. ... Computers need only classical physics to operate which is a subset of the physics the rest of the universe uses, including our brains. ...
    (rec.arts.sf.composition)
  • Quantum Computer Algorithms
    ... internal state (where these operations behave as in classical physics). ... time differed from computing device to computing device...) ... Our current best quantum mechanical ... which produce the same result as classical algorithms but ...
    (sci.physics.research)
  • Re: BOOK for Learning AND teaching the Foundation Certificate
    ... I studied some physics at college but ended up doing computing. ... or 802.11 - and this got me interested in radio theory. ...
    (uk.radio.amateur)
Quantcast