Date: Tue, 12 Jul 2005 21:11:52 GMT
Jon Heggland wrote:
> In article <OI5Ae.141460$zX6.7309433_at_phobos.telenet-ops.be>,
> jan.hidders_at_REMOVETHIS.pandora.be says...
>>Come on, Jon. How much tape does the Turing machine need that computes >>this transformation if n is the size of the input?
> Apparently, there are holes in my education---I'm more an engineer than
> a scientist. The complexity I'm used to computing on algorithms deals
> with time or number of operations; both the set and string algorithms
> seem linear to me.
And engineers don't have to know about space complexity of algorithms? :-) But time complexity is also different. The unary relation can be transformed in linear time, but the string transformation requires O(n.log(n)) steps.
> still say both operations are trivial to perform. And why draw the line
> at that particular place?
The linear-time constant-space transformation are traditionally seen as the class of computations that just do some reformatting but don't really compute anything new. Of course, this is to some extent a matter of taste and may under certain circumstances not be an appropriate definition, but if you look at what computations are in that class then it usually makes sense.
- Jan Hidders