X-Message-Number: 8616
Date: Sat, 20 Sep 1997 09:35:52 -0700
From: Peter Merel <>
Subject: Re: CryoNet #8611 - #8614

Thomas Donaldson writes,

>Whether or not anyone has defined one, I believe it would be useful to 
>consider a device which is like a Turing machine but suffers from limits
>of various kinds: length of tape, speed with which it can write or read
>from its tape, and so on. 

As suggested previously, you're describing the foundation of another
well-plumbed branch of computer science, the analysis of algorithms by
their computational complexity. If this study interests you, there's 
work in the field you ought to review before troubling yourself with 
such reinvention, beginning with Knuth's signal "The Art of Computer
Programming". Try

http://www-rocq.inria.fr/algo/AofA/index.html
and http://www.apnet.com/www/catalog/al.htm

for pointers to some recent results in this field.

>I'm playing here with intellectual constructions of various kinds,
>ideas derived from the idea of a Turing machine but by no means the same.

There are no computing devices that have been imagined in fifty years that 
are not mathematically equivalent, in terms of computability, to a 
Turing Machine. Your "Donaldson Machines" are certainly each Turing 
equivalent, so infinite arrays of Donaldson Machines are certainly bound, 
in terms of algorithmic complexity, within the set NP. If you don't 
know what NP describes, you have some enjoyable reading ahead. 

>As for what is practical, you might think of such a machine as 
>a Turinglike machine operating not on a tape but on an N-dimensional
>flat surface, moving from point to point (of course with infinite speed)
>to write both horizontally and vertically. 

Another machine within NP, I think.

>The limits, for a practical machine, would then be the lengths of the
>surface in each dimension and the speed with which the machine could do
>its writing.

If there are finite bounds on each dimension, then what you have is not in
NP but P - so what?

As to floating point, fixed point and real numbers, I deduce from your
pedagogy that you were indeed talking about reals. "Floating Point" is 
commonly used in CS to refer to limited precision reals, which is why 
I drew the distinction. I remain interested in the paper you mentioned.

Peter Merel.

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