Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/std_unix/volume.31/text0021.txt

Text File | 1993-07-15 | 7.9 KB | 154 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:
>
>>The mathematical argument that the base standard implied by the test
>>method standard must be less rigorous than the original is
>>straightforward.  Most POSIX standards will specify a sufficiently
>>complex system to implement a Turing machine.  Testing that all
>>programs for a Turing machine correctly execute on a given black box
>>is impossible, even in theory -- it implies the solution of whole sets
>>of undecidable problems.
>
>I think that the reference to Turing might have been intended to refer
>to Goedel, but anyway, the reference is misplaced.   A Turing machine
>requires infinite storage.  If only finite storage is present, then
>one can, in theory, enumerate all the possible programs and their
>results.  With finite storage there is no halting problem.  One may
>well choose not to wait for the answers, though.  :-)

An outsider comparing these two paragraphs will come away with the
impression that at most one of the writers really knows Theory of
Computation.  One or more knows the terms, some of the names, and even
some of the definitions, but does not understand how the field works.
This impression is correct.

Hackers despise people who drop names, fall back on credentials, etc.,
realizing that good credentials often back poor arguments, and good
arguments often come without strong credentials.  This trait is one of
the joys of working in the community of hackers.  Nonetheless, what we
have here is two people claiming understanding of a difficult field,
where the full explanations would take too much space.  I hope then
the following will be seen as appropriate and helpful.  I have
published a referreed article in Theory ("Technical Correspondence",
Communications of the ACM, June 1986, V29N6).  It went to press with
the change of one typo in my submitted draft.  (It would seem from
this test that it is considerably less hassle to publish new results
in CACM than trivial ones in comp.std.unix!)  I don't claim to be more
than an extremely minor figure in the Theory world.  I do claim to
know what I am talking about when I am careful to stick to the
mathematically trivial and obvious, as I did above.

More in the way of justification follows.  Those who know Theory of
Computation well with find nothing new here.  Those who never cared
about Theory will find nothing that should make them reconsider that
opinion.  To the extent they wish to give me further attention at all
they may jump to the conclusion at the end.  Those who do care some,
and would like to know more, may find their time rewarded.

1.  My reference to the Turing machine is boilerplate.  In order to
establish the relevance of the usual theorems, a result usually starts
by demonstrating equivalence to one of the usual theoretical models,
the Turing machine being the most common.  In theory, this
demonstration consists of a proof that the new computation model can
implement a Turing machine, and vice versa.  In practice, these facts
are usually so obvious that the technique I employed above, known as
"hand-waving", is all that is done.

The applicability of Goedel's undecidability results, and of a host of
others, is established via the Turing machine.

2.  Dave Cline is right when he says the Turing machine allows for
infinite space, in its quaint old model, using an infinite tape.  He
then attempts a demonstration of the irrelevance of any such model to
finite computation.  First off, let me point out, that since we are
discussing standards, not physical machines, so the matters under
discussion are all theoretical models.  Unless they specifically point
out that "no implementation shall be capable of simulating a Turing
machine with a tape containing more than 711 gigabits.", or
mathematically equivalent language, the standards are, in many cases,
Turing machine equivalent in the strict sense.

3.  But even taking the infinite/finite point as seriously as I just
did in the previous paragraph is very misleading.  If we accept that
Dave Cline's point was even potentially valid, it means that no
infinite model is relevant in application to actual, physical, finite
machines.  Big O notation is irrelevant for example.  Saying an
algorithm requires O(log n) time, as opposed to O(n), is meaningless
in real life.  The halting problem, as Dave points out, now can be
considered quite solvable.

Even stupid little finite state automata handle infinite inputs, so
they too must get the heave-ho.  So the math underlying regular
expressions is irrelevant as well.

Dave Cline takes issue, not with my use of Theory of Computation, but
with the basics of most of the field.

4.  Almost all mathematics of computation uses infinite models at some
point.  For that matter, accountants use the integers, of which there
is an infinite number, to represent dollars and cents, even though
none of their clients (except possibly the Federal Reserve) has access
to infinite funds.  This point is more than verbal trickery.  The fact
is that models implying infinity are used routinely in even low level
math, for extremely mundane and practical uses.

This did not come about without a good deal of debate.  The Greeks had
great trouble with the theoretical difficulties the use of infinity
implies.  The more practically minded Indian mathematicians just went
ahead and did it.  They resolved none of the theoretical difficulties,
but made great strides in practice, and our modern daily use of
arithmetic comes from India.  A solid theoretical underpinning to the use of
infinity did not come about until around 1900.

In short, Theory of Computation is based on models of computation
embodying potential infinities, just as engineering or accounting.

5.  Perhaps paradoxically, infinite models are almost always *more*
relevant to practice than finite ones.  Take Dave Cline's example of
the halting problem.  On a finite machine it's solvable by
enumeration, he correctly states.  On the real machine, however, which
does have potentially infinite time available, we must take into
account in counting space all the tapes we could mount, all the new
disks we could buy, all the storage we could access over a net and all
the technological improvements that might come along.  The infinite
tape winds up modeling the complexities of the real world as well or
better than any finite model -- and the math is easier, no small
consideration.

Take the argument that on your finite-sized machine the halting
problem is solvable (by enumeration, based on its finitude), and the
argument that the problem is undecidable -- which is the more
practical?  Anyone wishing to say the former is the more relevant
logic, could prove his case by contributing to the FSF a utility to
solve the halting problem [ or perhaps it could be a lint hack :-) ].

Conclusion: My brief essay into math was intended to make strongly the
point that many essential assertions contained in base standards are
not testable.  This point is one that one does not need Theory of
Computation to decide.  It's fairly obvious to anyone with a hackerly
bent.

In the rare cases where Theory can make an argument stronger, I like
to employ it.  It makes me feel my youthful studies were not entirely
in vain.  Those who don't care for Theory can safely skip the details,
leaping ahead to the result, and seeing it was pretty obvious without
all the BS.

Whether the argument is from Theory or Hackery, test method standards
*must* be watered down versions of the base standard.  No one has
argued this, not even those who appear to be willing to tilt their
lance at whole subfields of Comp. Sci.
--
Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc.
[e-mail]
137 E Fremont AVE #122, Sunnyvale CA 94087
"Chairman Warren, if you felt your life was in danger at the moment,

[ I'm not sure this thread belongs in comp.std.unix anylonger -- mod ]

Volume-Number: Volume 31, Number 22