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