Re: Turing Machines and Physical Computation

From: Eray Ozkural exa (examachine_at_gmail.com)
Date: 11/27/04 

Date: 26 Nov 2004 17:13:01 -0800

JXStern <JXSternChangeX2R@gte.net> wrote in message news:<5ci1q0tqrsrbnut54hbn7kbvt5g8idf1so@4ax.com>...
> On Sun, 21 Nov 2004 03:41:25 +0000 (UTC), "Kent Paul Dolan"
> <xanthian@well.com> wrote:
>
> >Turing Machines are under precisely _no_ obligation
> >to be physically realizable. They teach this point
> >in school, Eray, where were you at the time?
>
> I don't know where Eray was, but from the moment I first heard this
> sort of stuff, I wondered about it. Many false "fact" are taught in
> school, though their falsity may not be overturned until years or
> centuries later. Don't just appeal to authority here. Technically,
> sure, one can study Turing Machine functions that cannot be physically
> realized. But that does not make Turing Machine theory inapplicable
> to machines that can be realized.

Well, our instructors were careful enough to teach us the Cinderella
book which says no such stupid thing. It talks about abstract
machines, but it takes pains to make it awfully clear that this is
indeed the theory of real-world computers. Abstract does not mean
non-physical, and I'm grateful that the authors are clever persons.

I wonder, can these so-called hobbyists of theory like Harris and
Dolan provide for me a reference from a respected theory of computing
textbook that claims Turing machines are inapplicable to machines that
can be realized? I would be quite surprised with that. For a
reasonable computer scientist, the Turing Machine is just another kind
of automata, and its mechanism is firmly rooted in the physical world.
There is no ontological difference between a PDA and a TM. It is no
magic construction. When we see the transition graph of a TM, etc. we
immediately know that this is just another computer. And it is one
among many models of c.e. computation. Only these self-branded
sci.math "philosophers" seem to insist on this naive idealist talk.
And in our textbooks, it is clearly written: the ID of a TM is finite
at all times. This is a physical machine specification.

I wonder. Will these people also say that Lambda calculus depicts
non-physical processes? That the mundane task of substituting and
rewriting is in fact a non-physical thing? I wonder that very much.
Because *if* the TM is equivalent to evaluation of Lambda calculus
expressions, then that should be the case. This is I believe a
sufficient refutation of years of Harris's posts full of
misconceptions about the subject.

You see, all that is happening is that the theory programs on these
people's brains, which seems short of a stack, crashes the moment
they see the word "infinity" somewhere.

There are surely skyhook workers who would imagine "hypercomputation"
and other physically impossible classes of machines, but let's see, we
don't really deal with that in any reasonable curriculum. Computer
Science is first and foremost the science of complex physical events.

Computer Science does not deal with what an angel could have done in
heaven, assuming he could process an infinite amount of information in
a finite time. That *is* theology. And it doesn't work.

We like things that work.

> >I'm pretty sure at this point you have stepped well
> >past the bounds of sane thinking. You are trying to
> >limit "science" to "physical science", and that
> >limitation only exists in your own mind.
>
> Would you like to give an example of non-physical science?

Lester uttered geometry, logic, math as examples.

However, he may be neglecting that these disciplines too are based on
our sensory experience. That is their true foundation. (However, it
may not be precise to call these sciences in their present state.)

On the other hand, these are seen more "analytic" than the purely
empirical branches of inquiry, naturally. That is not to say that they
should be indulging in useless metaphysics, though. There are surely
measures for the utility of their statements.

For mathematics, we can know where to draw the line. For instance,
there is no need to talk about actually infinite fractal objects.
Nobody can observe such a thing in the world. What we can indeed
observe is the unbounded nature of computation, a far more natural
thing than the continuum, which has never existed, and never will.

Of course, if one shows a physical phenomenon that makes it
_necessary_ to invoke these absurd objects to explain them, then they
are useful, and that would actually be a physical proof of the
continuum, that there are indeed such infinite objects that are a part
of our world! No such thing has been done.

To propose a theory which is based on nomologically impossible axioms
is most definitely in the realm of theology or bad metaphysics. Modern
philosophy has no dealing with the non-physical, and it need not
either.
 
I am actually expecting a brilliant reply by some of the least
sophisticated philosophers I have ever had the opportunity to meet,
who are available on sci.math. Let's see these "philosophers" assert
that Turing Machines are nonphysical entities.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Lambda Calculus and Turing Equivalence
    ... Eray> Since the imagined "actually infinite" tape of TM does ... Eray> not exist in this other equivalent model of computation, ... Eray> a "potentially infinite" tape can be part of a TM, ... Eray> symbols on a TM tape, and the Turing Machine has no ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... Eray> Since the imagined "actually infinite" tape of TM does ... Eray> not exist in this other equivalent model of computation, ... Eray> a "potentially infinite" tape can be part of a TM, ... Eray> symbols on a TM tape, and the Turing Machine has no ...
    (sci.math)
  • Re: Turing Machines and Physical Computation
    ... > I don't know where Eray was, but from the moment I first heard this ... But that does not make Turing Machine theory inapplicable ... Science is first and foremost the science of complex physical events. ... there is no need to talk about actually infinite fractal objects. ...
    (comp.theory)
  • Re: Wolframs 2,3 Turing Machine Is Universal!
    ... that 20-year-old Alex Smith of Birmingham, ... Turing Machine Research Prize was ... that Wolfram's Turing machine is universal, ... Has it led to any useful contributions to science? ...
    (sci.math)
  • Re: [EGN] turing completeness
    ... I thought your claim was that NO Turing Machine ... This is because you use the word "infinite" carelessly and in a manner ... >> other TM is the UTM. ... > process is required to prove the impossibility of simulating the UTM. ...
    (comp.programming)
Quantcast