X-Message-Number: 8656
From:  (Thomas Donaldson)
Subject: one more comment for John
Date: Thu, 2 Oct 1997 23:18:10 -0700 (PDT)

Hi again!

I forgot to answer another one of your claims, to wit, that working with a
finite Turing machine would be worthless since the sizes and capabilities of
computers are changing very fast.

I really don't understand how that could be a problem. You use these 
algebraic things called VARIABLES. ie. let NT be the number of spaces on
the tape of the Turing machine, and p0 and p1 be the time it takes to
write down a 0 or a 1, and VT be the speed with which it can move over
one space on the tape. Then you can do such things as study whether it can
perform a given algorithm more efficiently with large NT and high VT or 
whether only a high VT is needed. You can even discuss the algorithms it
might perform with sets of the 4 parameters (NT,VT,p0,p1) --- though you
could not prove no algorithm would do better than the one you had chosen,
you could at least make a mapping: Turing machines with parameters 
(NT1,VT1,p01,p11) can do A,B,C but cannot accomplish D. That would be
interesting. ie. such and such a Turing Machine with parameters (NT,VT,
p0,p1) could do all the jobs involved in accounting for a small business,
but not solve partial differential equations in 2 dimensions.

Naturally when you bring finitude into the issue, you also bring the 
possibility that machines designed other than the way a Turing machine is
designed may work better on some jobs... or even most jobs. But by using
variables rather than constants, you've got a way to explore the range of
possible machines, too. You may not have heard of this, but a breath of
it happens in parallel computing, where we have classes of machines:
SIMD machines, MIMD machines, multiprocessors with the same addressing
space, multiprocesors with distributed addressing spaces, and so on. Even
though people have persisted in coming up with machines which did not fit
the previous categories, the categories themselves were still useful ---
if only to get people to think of machines which did not fit in them.
And some results are almost trite, but still worth knowing: if you have
a MIMD machine then just what you can do depends a lot on how fast you
can send messages between the different processors. If it is emulating
a machine with a single memory, then depending on message-passing 
speed you may (or may NOT) have to pay attention to where you or your
compiler puts your variables. No doubt with quantum computers we'll get
even more florid classes.

But fundamentally, the advantage of including such limits is that your
results become much more pertinent to practical computing. 

			Long long life,

				Thomas Donaldson

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8656