1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?