# Re: Rice's theorem

*From*: Chris Smith <cdsmith@xxxxxxxxx>*Date*: 13 Jul 2008 16:16:00 GMT

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

.

**Follow-Ups**:**Re: Rice's theorem***From:*Dillon

**References**:**Rice's theorem***From:*sanchopancho80

**Re: Rice's theorem***From:*tchow

**Re: Rice's theorem***From:*Dillon

- Prev by Date:
**Re: Is this language context free?** - Next by Date:
**Re: TAUTOLOGY and SAT** - Previous by thread:
**Re: Rice's theorem** - Next by thread:
**Re: Rice's theorem** - Index(es):