Re: Why NP Problem is Important and Practical Examples

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 01/19/05 

Date: Tue, 18 Jan 2005 23:53:02 GMT

"Eray Ozkural" <examachine@gmail.com> wrote ...
> Google doesn't allow me to quote easily. I don't have the time to edit
> text like that. How do you turn on quoting in google news? Follow the
> references. It's seen what I reply to.

That's just the problem -- unless a reader is using Google, it may
very well be quite difficult to see what you're responding to. For
various reasons, the previous post may not be available, or, if it
is available, it may be a great inconvenience to find it (possibly
buried in a jungle of other postings).

IMO, it's likely that a lot of readers just ignore postings which,
lacking any quoted context, are often effectively meaningless.

> Anyway, Rick is repeating Stephen Harris's flawed argument without
> realizing it.
>
> He says there is no limit on the memory available to a TM, but a real
> world computer has a bounded amount of memory available. So there *is*
> a difference between a TM and a physical computer he says, physical
> computers can only imperfectly realize some perfect forms out there
> because a physical computer always lacks a necessary property of a TM.
> I argue that physical computers are perfectly adequate examples to
> "computers" as described by "models of computation" like TMs, RAM
> machine, LISP machine, etc.

I think it may be useful to comment on something you said in your
previous posting, when you wrote ...

>> Read Turing's paper more carefully, there a potentially infinite
>> tape is talked of, NOT AN ACTUALLY INFINITE TAPE.

In later works, Turing himself clarified and corrected some things
he wrote in his '37 paper (aside from corrections published in '37).
For example, in "The word problem in semi-groups with cancellation",
Annals of Mathematics, Vol. 52, No. 2, Sept. 1950, referring to his
1937 paper, Turing wrote the following ...

     "As in Turing[1], Post[1], we identify the existence
   of a 'general METHOD for determining ...' with that of
   a 'computing MACHINE constructed to determine ...'."

and then

     "A computing machine is IMAGINED as a mechanical
   device capable of a finite number of states or internal
   configurations (I.C.) q_1, q_2, ..., q_r, working on a
   (both ways) INFINITE TAPE divided into squares on which
   symbols are printed."

(The ellipses are in the original; the all-caps are mine.)

Since Turing regards such a machine as an *imagined* device equivalent
to a *method*, it seems likely that when he says the tape is infinite,
he means that that is just how it is to be imagined -- giving no
consideration at all to being only "potentially" infinite, or unbounded.
In any case, his machines are devices of the imagination only.

> I don't want to repeat all the boring argument but the above difference
> which you suggest is analogous to misunderstanding that unbounded does
> not mean infinite.
-snip-
> The problem is first the following: the model of computation does not
> compute.
-specious argument snipped-

Turing's imagined machines are equivalent to *methods* of computation.
So if there is a certain "method for determining", say, the 9^^^^^9th
binary digit of pi, then I doubt it matters whether we say that the
*method* determines it, or that we *imagine* a person determining it
using that method, or that it's computable, or that it's computed by
a TM. (Evidently there are strong elements of psychologism, or
fictionalism, in Turing's view of mathematical objects.)

 
> Second, we can program a physical computer (PC) such that it will fill
> all available space-time in the "reachable" universe with its
> computations. Such a computer is "unbounded" but not-infinite, mainly
> because NOTHING in a finite universe is infinite.
-snip-

Ridiculous! Can you arrange for arbitrarily large portions of the
universe to make itself available upon demand for your unbounded
physical computer? If you were to say only that it can be *imagined*,
then plenty of people, perhaps even Turing, would agree.

--r.e.s.

Relevant Pages