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