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

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

Date: Sun, 29 Feb 2004 14:10:57 +0000

Edward G. Nilges wrote:
<snip>
>>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.
>
>
> If the universe goes on indefinitely this is wrong.

Well, it is certainly possible to speculate on what-ifs. However being
practical about this, protons will decay after about 10^33 years
(according the the Standard Model), and then of course the computer
might collapse into a black hole under its own weight if it got too
large. Eventually the universe will die a heat death, and that puts (a
very loose) practical upper limit on the length of time we can compute.

It doesn't matter how large that limit is, the point is it is finite.

>>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.
>
>
> The assertion is that given enough time and memory space, a desktop PC
> can compute anything. This assertion is true and equivalent to
> Church's thesis re the Turing machine.

I could be really pedantic here, and ask how large a desktop is... do
you mean a desk that is arbitrarily large, with storage that is
arbitrarily large?

And of course, I could also be pedantic about "everything".

<snip>

>>>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.
>>
>
> This is true so far as it goes. But the description of the TM needs to
> be rephrased depending on your philosophy of mathematics.

I don't think it needs rephrasing. As a mathematical concept, it is
well-defined. It doesn't need to exist in the real world - and this is
not a problem. It's like saying a "complex number" must exist in the
real world. I'm not even sure natural numbers exist in the real world.

> The TM is an "entity" only to the Platonist who ground the truth of
> mathematics in the existence of Forms. To an Intuitionist or Marxist
> the TM is a text and a set of construction instructions.

But, a TM is surely a mathematical entity, not a physical one.

<snip>

> "…writing is not only an auxiliary means in the service of science-and
> possibly its object-but as Husserl in particular pointed out in The
> Origin of Geometry, the condition of the possibility of ideal objects
> and therefore of scientific objectivity."

So a TM is an "ideal object". Oh good, we agree then.

<snip>

> Now, I concede that a computer simulation of a Turing Machine may fail
> on storage limitations for arbitrary TM. But this (empirical) fact
> fails to prove that "it is not possible to simulate a TM with
> software".

It is not possible to simulate _every_ TM with software. That one word
is what is causing the whole argument is it not?

You can simulate many TMs with software, including many useful ones.
However, since there are an infinite number of possible programs, the
proportion of all possible programs a computer can run is exactly 0.

Sorry, didn't read the rest...

Calum

Relevant Pages

  • Re: Absolute reality -> mind -> Relative Reality
    ... Pure NKS investigates how various types of simple programs typically ... behave - much as traditional mathematics examines various mathematical ... public oAbsoluteMatter ...
    (sci.physics)
  • Re: The annotated annotated annotated C standard
    ... outside the Standard in order to achieve a platform-specific goal. ... mathematics found itself ... it is true that there are some cases where division by zero ...
    (comp.programming)
  • Re: The annotated annotated annotated C standard
    ... outside the Standard in order to achieve a platform-specific goal. ... mathematics found itself ... it is true that there are some cases where division by zero ...
    (comp.programming)
  • Re: Pondering a shift
    ... <SNIP HOOKS> ... <SNIP MATH?> ... Not the "beauty" of the mathematics or its ... Nothing but protecting their funding and protecting their jobs. ...
    (sci.physics)
  • Re: Stray Thoughts & Provocative Questions
    ... Mathematics is merely rigorously ... There are ZERO empirical falsifications of Special Relativity. ... prediction at any scale in all venues works exactly as predicted to ...
    (sci.physics)