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
.



Relevant Pages

  • OT: Church-Turing thesis (was Re: TCL cant do as much as Perl)
    ... Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine, thus they are equally powerful, and no language can exist that is more powerful. ... the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". ... An effective method is defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. ...
    (comp.lang.tcl)
  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ... is just a garbage string? ...
    (sci.math)
  • Re: Raatikainens Paper on Chaitin
    ... >> just be equal to e, with a corresponding Turing machine M_e. ... it established, instead, that the powers of human reason could not be ... I repeat Penrose and compate it to * immediately above: ... Leibniz dream of universal language formally mathematically expressed. ...
    (sci.logic)
  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... > equivalent to Church's thesis re the Turing machine. ... that Marxists would attempt to get involved in mathematical philosophy. ... Initially writing represents speech, and it is very unusual to know how to ... However written language has its own ...
    (comp.programming)
  • Re: An uncomputability conjecture
    ... > language such as LISP or Prolog. ... > Turing machine that corresponds to R. ... let be the set of input words to ... we consider the possible uncomputability ...
    (comp.theory)