Re: Normalisation
Date: Tue, 12 Jul 2005 21:11:52 GMT
Message-ID: <smWAe.143397$1f4.7471162_at_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