Re: Normalisation

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Tue, 12 Jul 2005 21:11:52 GMT
Message-ID: <smWAe.143397$1f4.7471162@phobos.telenet-ops.be>

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.

> But if you won't bother to explain, no big deal.

I'll give you hint. For unnesting the string you need a counter. How much space will that counter take on the Turing tape. How much work, on average, will it take to increment that counter?

> I
> 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

Received on Tue Jul 12 2005 - 16:11:52 CDT