Understanding Turing Machines & Language Recognition

[physicsuser]

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?

 

[Corneo]

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.

 

[physicsuser]

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.

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)?

 

[Corneo]

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.

 

[physicsuser]

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.

Are recognizable and Turing recognizable different things?

 

[Corneo]

No I mean the same thing here.