Turing Machines and Physical Computation

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

Date: 19 Nov 2004 22:03:22 -0800

Hi Stephen,

I would have expected a thoughtful reply.

"Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message news:<4zrnd.46389$QJ3.16198@newssvr21.news.prodigy.com>...
> "Eray Ozkural exa" <examachine@gmail.com> wrote in message
> news:320e992a.0411190852.7ce02e6c@posting.google.com...
> > I have had such a discussion with an extremely intelligent and
> > experienced mathematician. He told me that PCs are not Turing
> > Machines, because they have "an infinite tape". I think he did not
> > know anything about descriptive complexity. This infinite portion of
> > the tape consists entirely of blank symbols, and therefore has
> > descriptive complexity O(1), which is easily realized by a physical
> > system. When I told him about Ullman's indefinite growing argument, he
> > objected "But when the universe is filled up, it cannot grow any more!
> > Then, it is not infinite", to which I responded "Yes, but there is
> > *nothing* that is larger than the universe." To assume the contrary
> > would be theology, which I despise.
> >
>
> Turing Machines are idealized which means they are not physically realized.

What a nice assertion.

A TM is just the specification of a very low level machine code,
that's all there is to it. It's just another model of computation, and
not an extremely telling or useful one. Thinking about Turing
Machines which have not been realized yet does not mean that these
things cannot be implemented. Besides, a bounded size FSA simulator,
too, is a Turing Machine... You people overlook this simple point, I
wonder why.

Also, I suggest you to get the most recent edition of Cinderella book
and have a look at what Ullman thinks about this subject. (That's
another argument!) IIRC, in that edition, the authors argue
persuasively that we should think of PCs as TMs rather than DFAs. I
find that a subtle point.

Now, I recall that you made this strange argument about Turing
Machines being able to do things that real computers cannot, because
they have an infinite tape. What an observation.

> TMs are not meant to have physical constraints applied to them.

Another assertion.

Ignoring physical plausibility directly opposes physicalism. When we
start talking about immaterial things, we are not making scientific
statements, we are making metaphysical ones, and that is not a good
sign if the metaphysical statements depict worlds that are not
physically similar to our own. It is a matter of degree, which we can
observe.

The question is: how far from reality? The further you talk, the less
real your statements are, not just as real!

> That mixes categories.

No.

> Sometimes the question is asked, how many sentences can be
> generated in some natural (say English) language? There are finitely many
> words in the language, but the standard answer is that there are countably
> infinite number of sentences, due to appending etc.

That is potential infinity, a plausible concept, considering time for
instance. Current theory of physics *seems* to suggest that time is
going to continue forever. The idea of potential infinity is then, at
least in the temporal sense, not too far from our world. However...

> These kind of questions ask what is the potential in theory, not what is
> practically possible. Observations like: a person can only articulated
> finitely
> many sentences in a lifetime, or any sentence has to be uttered before
> somebody dies or a machine wears out, or that how many sentences
> potentially exist is related to how many people generate sentences over
> the lifetime of humanity in the universe are not relevant, because that is
> not the question being asked. Every process within the universe is finite
> due to heat death of the universe, so that makes all such questions trivial,
> if one interprets them to mean or apply to a physical reality.

That's a quite amazing thought, because it rejects that some facts
about our universe can be simple. That some answer is "trivial" does
not necessarily mean it is wrong. If we are talking about our
universe, yes, if universe is going to expand, and accelerating in
expansion, then, at some time T no efficient causal interaction will
remain, which will disable large computations. Sad for the universe.
But what else can we say? Then, those never-ending computations aren't
quite possible. If that's so, it's not sensible to talk about things
that cannot ever be constructed in our world. Then, let's talk of
finite quantities only. Let's see how big computations behave, without
pretending that there is no bound to their time/space use.

At this point, I should remind you the famous Levin quote. Levin was
Kolmogorov's student, so he probably has a better idea of this issue
than you have.

> A Turing
> Machine or potential sentence of a language (there is no pre-existing
> specification that the sentence has to be of finite length) is not of this
> world.

Of which world is it then? (^_^) And you are saying this Platonist
talk is not theology! You have just murdered physicalism.

> The set of natural numbers is countably infinite and is has some use
> theoretically. Would you claim infinite sets have no use because they
> have more members that there are particles existing in the finite universe?

It has some use theoretically. An immortal being is nice in theory, as
well, but we don't know if it will work out well for us. But that is a
sorry analogy. We can do better. God has some use theoretically, we
can use it to resolve our ethical problems. But we don't know if it
exists. It's just an idea. As you can see, it's pointless to say that
the set of natural numbers exist except as an idea. And that is what
you are affirming in the first sentence. The second is nonsense. I say
nothing about their theoretical use, they make good mental exercise,
and they help us construct simpler theories in exchange for loss of
physicality. (Again, when it becomes less physical, it does not
automatically gain some positive ontological status, if you are also a
physicalist!)

That something has some use theoretically does not grant attaching the
word "exists" to it, from a philosophical point of view. And giving it
a privilege might betray philosophical consistency.

> And the original description of a Turing Machine. It is common to call
> this tape 'infinite' though some prefer finitely unbounded.

The latter camp has the precise terminology.

> There is no
> physical time constraint applied to when the calculation has to be
> completed.

If you mean *any* computation. But a Turing Machine is a *particular*
computer. Not just *any* computer. Let's pay attention to our
language.

> So there are calculations that a physical PC the size of
> a galaxy could not complete before the universe ran out of power to
> energize the computer. A Turing Machine can of course complete
> such a calculation (because the calculation does not need to be infinite,
> just finitely larger/longer in time that can be accomplished by any
> physical device during the existence of the physical universe) because
> the constraint of physical time is not applied to idealized situations.

Wittgenstein once said Turing's theory was of human computers. Which
was quite true if we take the original paper literally, without
abstracting "computer". (And that is what such people were called at
the time, who made calculations)

You are also making a significant conceptual error. We have a theory
T, only a small portion of which has models in the real world. But no
experiments contradict our theory (such as computers existing,that
cannot be explained by T). I think this is a perfectly legitimate
situation in science. And you are twisting the whole physicalist
argument upside-down by saying that, since the theory predicts (by way
of *generalization*) 'there would be machines which can grow
absolutely with no end, if and only if our universe had an infinite
space'; *then* you conclude that this theory must not be a physical
theory. What a bad use of language!

Instead you should have paid attention to basic rules of grammar and
linguistic analysis. What the theory predicts is a *counterfactual*,
it is not too different from saying that "If my mother had a beard,
she would have a lot of hair on her chin". This is quite possibly
*false* for most of our mothers. And for our world, the theory
*predicts* that there will be no machines which can grow absolutely
with no end, since our universe does not have an infinite space. It is
regrettable to think of the theory as independent from physical
statements, if we accept that it is a theory of *machines*.

Anyway, the point remains that Turing's theory is a theory of actual
machines, if not merely humans. Wittgenstein has a point! And then it
is nonsense to argue that:
> A Turing Machine can of course complete such a calculation .... because the
> constraint of physical time is not applied to idealized situations.

But that is a terrible metaphysics you have there! Idealized
situations do not exist. By situation we mean a complex aggregate of
physical events, nothing more. (Again, if we are to call ourselves
physicalists. And Cartesian Dualists, can leave the hall silently!)

> Keeping those categories seperate, the idealized and the physical,
> is definitional. The answer to theoretical questions is trivial and obvious
> if you mix these categories. Mathematicians invented infinity without
> the requirement that it be physically realized because it was useful.
> Pure mathematics invents formal mathematical systems with no
> requirement that this formal system represent any physical event or
> process.

This is quite a muddled reasoning, especially this bit:

> Pure mathematics invents formal mathematical systems with no
> requirement that this formal system represent any physical event or
> process.

There is no requirement of representation, so you think. There is the
requirement of representation of *ideas* in your head, and if your
ideas are *physical*, then it follows that the *exact opposite* of
your statement holds!

>Eray wrote:
>
> > "Yes, but there is
> > *nothing* that is larger than the universe." To assume the contrary
> > would be theology, which I despise.
>
> When you say *nothing* you mean no physical something.

Platonist semantics. *shudder*

When you utter "nothing", you do not refer to anything that exists.
You do not refer to something that does not exist! (That is generally
seen as a wrong account of designating the reference of expressions
with counter-factuals in philosophy of language.)

That would be a very confused understanding of the word "nothing".
Let's do some ordinary philosophy of language to draw a better
picture.

Here are some easy semantics questions. Formalize the semantics of the
following sentences, excluding questions using common knowledge
representation techniques in First Order Logic: (I am explicitly
asking for truth-referential semantics, of course. Usual Tarski's
World stuff, if you are familiar with formal semantics)

- What do you want?
- I want nothing.

- What are you going to do tomorrow?
- I am going to do nothing.

There is nothing in the box.

* An example of an analytically false statement (for nonempty
interpretation domains)
Everything is nothing. (Hint: the solution is like the liar paradox)

> Mathematical
> objects need not be physical.

A Turing Machine is not just a "mathematical object"! [*]

Let's repeat our basic argument again.

1. Not all Turing Machines require finite bounded space.
2. Therefore some Turing Machines run in finite bounded space.
3. Many PCs do just that.
4. Then, PCs are physical functioning models of Turing Machines. (But
most of them are also simple DFAs, or formal axiomatic systems, or
whatever general theory they fit. The theory which has the most
*explanatory* power will be preferred according to the question we are
trying to answer.)

Could this argument be any simpler?

> When you made this comparison, infinity and theology/God, to the size
> of the physical universe, you crossed over from debating potential vs.
> actual infinities to declaring abstract thinking is just theology in another
> guise.

That is exactly what Poincare implied in his famous remark. I will bet
on Poincare, and not on your championing of one school of mathematics.
(I am not the only person who made the comparison!)

I said that before, and it's come true, thanks to you. Why should one
ever discuss foundational issues with those who cannot question the
assumptions of their favorite school of thought?

What I explained to a slightly confused mathematician who believed
himself to be a constructivist was that a sane analysis in philosophy
of computation suggests that Turing Machines should be thought of
physical devices, if we are to remain physicalists. You do not
challenge any of the arguments. Instead, you assert things, like
saying that Turing Machines are not of this world. Show us that
world, or is it the fairy-land of mathematics?

[snip some "philosophy"]

Amused, 

--
Eray Ozkural
[*] And you might as well say, "our language expressions" do not need
to refer to physically plausible things. Then, you should perhaps
think of defending that we freely talk of God in scientific discourse.
But that is not permissible in scientific talk. Maybe it is good for
mythology, which is not our business.

Relevant Pages

  • Turing Machines and Physical Computation
    ... > Turing Machines are idealized which means they are not physically realized. ... they have an infinite tape. ... Ignoring physical plausibility directly opposes physicalism. ... Every process within the universe is finite ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation & TM S REVISIONISTS
    ... >> Postivism implies some sort of physicalism, I think, or at least it ... I do not condone those idealist re-readings of Turing ... > THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation & TM S REVISIONISTS
    ... >> Postivism implies some sort of physicalism, I think, or at least it ... I do not condone those idealist re-readings of Turing ... > THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (sci.math)
  • Re: Turing Machines and Physical Computation
    ... Turing seems to be a concrete physicalist. ... > Postivism implies some sort of physicalism, I think, or at least it ... THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... Turing seems to be a concrete physicalist. ... > Postivism implies some sort of physicalism, I think, or at least it ... THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (sci.math)
Loading