In message <[EMAIL PROTECTED]>, "Bernie Cosell" writes:
: [...] : In particular, CSLs are the same as the set of languages computable by : Turing machines, so that anything a Turing machine can do can be : expressed as a context-senstive language (and vice versa, of course), : [...] You're thinking of the recursively enumerable languages. An LBA (linear-bounded automaton--a Turing machine with a tape of length kn, where n is the length of the input and k is some constant) can be constructed to recognize any CSL. You need a Turing machine with an infinite tape to recognize the r.e. languages, but the kicker is that the membership problem for r.e. languages is undecidable. Greg
