Re: Arthur O'Dwyer on the feasibility of simulating a Turing Machine

From: Calum (calum.bulk_at_ntlworld.com)
Date: 02/28/04 

Date: Sat, 28 Feb 2004 17:21:39 +0000

Edward G. Nilges wrote:
> Willem <willem@stack.nl> wrote in message news:<slrnc3v69e.9cf.willem@toad.stack.nl>...
>
>>)> This has already shown to be false; there's only a finite amount of matter
>>)> in the universe.
>>
>>Edward wrote:
>>
>>) However, do we know if there is a finite amount of time? For by simply
>>) having the simulator act as a sort of virus we can exchange raum for
>>) zeit, space for time.
>>
>>Each operation of any TM-like machine increases the entropy of the universe
>>by some amount (with a fixed nonzero minimum), therefore an UTM needs to be
>>able to increase the entropy of the universe by an unlimited amount.
>>But a finite universe has a finite maximum entropy.
>
>
> In fact, this is false. For any calculation that halts, the universal
> turing machine will execute necessarily a finite number of operations.

But, you can always devise a computation that requires more
time/energy/space/memory/tape than the universe is capable of. Even one
that halts.

E.g.

bool array[NUM_PARTICLES_IN_UNIVERSE+1];
for(int i=0; i<NUM_PARTICLES_IN_UNIVERSE+1; ++i)
        array[i] = is_prime(i);

Your assertion that any desktop PC can compute anything is of course
ridiculous.

> All you're affirming is that BOTH the simulator and the "ideal" will
> consume the universe if they loop. The UTM and the simulator are in
> fact exactly equivalent in this regard.
>
> The UTM, *qua* UTM, has no special permission to continue looping in
> the formalism merely because it is either a Turing Machine or a
> Universal TM: to think so is to confuse the designation TM or UTM with
> some sort of honorific which (again) somehow raises Turing's mere
> contrivance ABOVE writing and into speech, where the UTM is allowed to
> loop.
>
> In fact, the formalism is silent on a number of issues including how
> the tape is expanded, how long the computation will take as a cardinal
> number and not a function of its input, and here, whether the machine
> in a nonhalting state is permitted to loop.

Of course, it is important to realise that a UTM is a thought
experiment, a mathematical entity. Its purpose is primarily to discuss
the mathematical nature of computation. The point is it DOES NOT MATTER
  how the tape is extended, or whether it is performed by a computer or
by pencil and paper. That's what's nice about mathematics, you always
get the same result.

And as for "how long the computation will take", does the phrase
"Halting Problem" have any meaning to you?

Relevant Pages

  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... > Each operation of any TM-like machine increases the entropy of the universe ... > by some amount, therefore an UTM needs to be ... turing machine will execute necessarily a finite number of operations. ...
    (comp.programming)
  • Re: Whilst falling back this weekend
    ... sunset) without making the other worse by the same amount. ... of the amount of time out universe has existed. ... just moving artificial time zones to be more useful WRT Sol. ...
    (alt.home.repair)
  • Re: God --> Retroactive Teleogical Causation
    ... > Life must eventually engulf the entire universe and control it, ... > the amount of information processed between now and the final ... There is no way an infinite amount of information can be recorded in ... by simple inspection 2 of your 5 postulates are false. ...
    (sci.physics.relativity)
  • Re: Light inside a black hole?
    ... Happy New Year David, ... open into our Universe. ... having the amount of hydrogen>> the amount of iron, ... says something twists, ...
    (sci.astro)
  • Re: Hawking in Dublin
    ... > Not if there's a finite amount of matter around, ... > be the case in an asymptotically Minkowskian universe. ... extend for an infinite time; ... AdS as usually understood has infinitely large spatial sections. ...
    (sci.physics.research)