Re: Normalisation

From: Jon Heggland <>
Date: Sun, 10 Jul 2005 19:21:56 +0200
Message-ID: <>

In article <OI5Ae.141460$>, 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. But if you won't bother to explain, no big deal. I still say both operations are trivial to perform. And why draw the line at that particular place?

Received on Sun Jul 10 2005 - 19:21:56 CEST

Original text of this message