X-Message-Number: 8554 Date: Sun, 07 Sep 1997 10:07:59 -0400 From: "John P. Pietrzak" <> Subject: Reality Bites References: <> Hi Thomas, > 1. On Turing Machines: > > [...] That is where parallel computers come into the > picture. Sure, you will have an "equivalent" machine if you have > a sequential Turing machine, but the weight falls on that notion > of "equivalence". The answers would be the same, but they would > not some as fast. To many people that's damned important. So for > PRACTICAL purposes, it's useful to think about more restrictive > definitions. Ack! You want me to deal with the Real World(tm)? :) :) Well, it's true, the Turing Machine (and associated automata) are useful for showing what can and cannot be done in absolute terms, but they give little help in determining which among those algorithms which are possible are in fact "feasable". There's a field of computer science known as Analysis of Algorithms which can provide proofs involving the time constraints of some algorithms, but it's generally not easy to do. At least, you _can_ show that using a parallel processor doesn't get you around the Halting Problem, etc. John Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8554