Re: META: Killthread; (Re: Jaron Lanier)

From: James Rogers (
Date: Sat Nov 29 2003 - 11:47:02 MST

On 11/29/03 8:31 AM, "Perry E.Metzger" <> wrote:
> Also, largely, something I can't agree with. I'm a strong AI
> proponent, but merely because all hardware is Turing Equivalent
> doesn't make it equally convenient from an engineering perspective --
> and it is also hardly clear that our solution will look like software
> in a conventional sense, either!

Very much so. Turing equivalence is something that is useful in
mathematics, but something which most engineers should consider to be
poisonously na´ve for the purposes of implementing an arbitrary machine on
some finite substrate.

As a very simple example of this, consider the number of sorting algorithms
currently described. They may be mathematically equivalent, but for many
time, space, concurrency, and pattern bounded hypothetical applications many
of these "equivalent" algorithms can border on intractability or

One can come up with many examples in computer science where the
implementation of some abstract machine can very substantially modify the
complexity exponent. There are many, many spaces where the "obvious"
implementations are intractable such that no amount of hardware will address
the issue, yet novel "less obvious" implementations scale reasonably well on
real hardware. Implementation matters.

I think there is not insubstantial evidence in mathematics that common
conceptions of computational models are incomplete at best. They may all be
Turing equivalent, but there are a number of comparative properties of these
various models that suggest to me that we have quite a bit of useful work
left to do in this area. People are still discovering new and interesting
things in this field, and it looks like they still have a lot more left to

-James Rogers

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:43 MDT