Re: Rice's theorem



Dillon wrote:
But I am not sure whether I understand it correctly. Let's consider a
concrete (or "fixed") language
L1 = {a^n¡ñb^n¡ñc^n | n>=0}
where a^n denotes a string consisting of n consecutive letter "a", and
¡ñ, concatenation.
Is L1 decidable or not?

By a Turing machine? Yes, sure. This has nothing to do with Rice's
Theorem. Rice's Theorem is about the more complicated scenario where the
language you are trying to decide (which I'll call L_1) is a language *of
Turing machine descriptions*, and is defined as the set of descriptions
of Turing machines T such that L(T) has some property. (Or equivalently,
that the function computed by T has some property.)

So if L_1 is itself { a^n b^n c^n | n >= 0 }, then it is clearly
decidable. But if L_1 is { L(T) | T is a Turing machine, L(T) =
{ a^n b^n c^n | n >= 0 } }, then it is not decidable, because you're
trying to decide a non-trivial property of a language from descriptions
of Turing machines that decide the language, so you can invoke Rice's
Theorem.

--
Chris Smith
.