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 nontrivial property of a language from descriptions
of Turing machines that decide the language, so you can invoke Rice's
Theorem.

Chris Smith
.
 FollowUps:
 Re: Rice's theorem
 From: Dillon
 Re: Rice's theorem
 References:
 Rice's theorem
 From: sanchopancho80
 Re: Rice's theorem
 From: tchow
 Re: Rice's theorem
 From: Dillon
 Rice's theorem
 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):
Relevant Pages
