Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Turing machines

  1. Dec 2, 2005 #1
    Sorry if this is a wrong place to post this.

    What does it mean that a turing machine M recognize language A?
    Does it mean that A={w|M accepts w}? Is so then how does M accept w? Does it accept w if it ends in accept state?
  2. jcsd
  3. Dec 2, 2005 #2
    The language of Turing Machine M is A, as you defined. w is a string in the language M and the final state of M after input w is in an accept state.
  4. Dec 2, 2005 #3
    So language A is recognizable if a TM recognizes it right?

    And a decidable language B if B = {x| TM accepts or rejects x} ? If this is correct then how can a decidable language be Turing-recognizable(unless we know that it always accepts)?
  5. Dec 2, 2005 #4
    A language is B is decidable if B = {x | TM M halts and either accepts or rejects x}. You will probably find out there is a term for a language's whose complement is Turing recognizable. A language as described is call co-Turing recognizable. For a language to be decidable, it must be recognizable and co-Turing recognizable. That is a deciable language is the intersection of a Turing recognizable and co-Turing recognizable language. Thus, a deciable language is recognizable.
  6. Dec 3, 2005 #5
    Are recognizable and Turing recognizable different things?
  7. Dec 3, 2005 #6
    No I mean the same thing here.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook