Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/std_unix/volume.31/text0025.txt

Text File | 1993-07-15 | 3.8 KB | 80 lines

Submitted-by: [e-mail] (Jeffrey Kegler)

In article <[e-mail]> [e-mail] (Dave Cline) writes:
>In article <[e-mail]>,
>             [e-mail] (Jeffrey Kegler) writes:
>> First off, let me point out, that since we are
>> discussing standards, not physical machines, so the matters under
>> discussion are all theoretical models.
>
>Standards contain limits making them finite.  For example, input
>and output arguments in POSIX.1 are defined in terms of their
>ANSI C realizations (2.9.1) and are clearly finite (e.g. INT_MAX,
>sizeof(char *), etc.).

The readership of comp.std.unix should be able to spot the above
reading of the standard as wrong with no trouble.  As a reading of ANSI
X3.159-1989, section 2.2.4.2.1 shows, INT_MAX is a *minimum* -- the
standard gives a magnitude they must be at least as large as, but
implementors may define their magnitudes larger.  sizeof(char *) is
implementation defined, pure and simple (3.3.3.4, 3.3.4, F.3.7).

But suppose it were right.  Is a memory which can consist of an
infinite number of finite words, infinite in extent, or finite?
Mathematics and intuition agree here, that an infinite number of 32 bit
words contains an infinite number of bits.

With the standards and the math, Dave knows the vocabulary, but just
randomly jumbles it.  It looks convincing as long as you know nothing
about what's being discussed.  Dave should consider going into
management.

>Proofs of the halting problem and undecidabilty all rely on the
>fundamental assumption that the state space of the computation model
>is infinite.  Changing from "infinite" to "very large" invalidates
>the proofs.  Our current standards and the machines that implement
>them are finite.  One cannot use Theory of Computation conclusions
>about the halting problem or undecidability if the premises are not
>satisfied.  Jeffrey's appeal to Turing complexity is unjustified.

Herbert S. Wilf, _Algorithms and Complexity_:  "We are going to talk
about a Turing machine.  It is an idealized computer, and its purpose
is to standardize ideas of computability and time of computation by
referring all problems to the one standard machine. ... The beauty of
the Turing machine is that it is at once a strong enough concept that
it can in principle perform any calculation that any other finite-state
machine can do, while at the same time it is logically clean and simple
enough to be useful for proving theorems about complexity.  The
microcomputer on your desktop might have been chosen as the standard
against which polynomial-time computability is measured."

Incidentally, for someone desiring a good introduction to Theory of
Computation, which has the virtue of focusing on essentials, avoiding
much of the wearying detail that afflicts most such texts, I recommend
Wilf.

Speaking of wearying detail, the moderator is losing patience with this
thread, and I cannot blame him.  This will be my last post in reply to
Cline.  This will allow him to have the last word, or as many such as
the moderator cares to allow.  I can pretty much guarantee I won't even
reply to new points raised, however outrageous -- I don't plan to read
any more of Dave's posts.

I do plan to follow the rest of the discussion, and where I read
arguments cogent enough to demand explication, extension or revision of
my statements, I hope for the indulgence of the moderator.

--
Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc.
[e-mail]
137 E Fremont AVE #122, Sunnyvale CA 94087

[ Unless further messages have a more direct relevance to "unix standards,"
  I will not post them.  I think the subject of testing is extremely
  important, both to standards and software in general, but this is
  no longer pertaining to the topic at hand.  Please feel free to yell at me if
  you disagree -- mod ]

Volume-Number: Volume 31, Number 28