Understanding Turing Machines & Language Recognition

In summary, a Turing machine recognizes a language if the final state after inputting a string w is in an accept state. A language is recognizable if a Turing machine recognizes it, and it is decidable if the Turing machine halts and either accepts or rejects the input. A decidable language must be both recognizable and co-Turing recognizable, and a decidable language is the intersection of a Turing recognizable and co-Turing recognizable language. Recognizable and Turing recognizable are essentially the same thing in this context.
  • #1
physicsuser
82
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?
 
Physics news on Phys.org
  • #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.
 
  • #3
Corneo said:
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)?
 
  • #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.
 
  • #5
Corneo said:
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?
 
  • #6
No I mean the same thing here.
 

1. What is a Turing Machine?

A Turing Machine is an abstract mathematical model of a computational device that can manipulate symbols on a tape according to a set of rules. It is often used as a theoretical tool to understand the limits of computation.

2. How does a Turing Machine recognize a language?

A Turing Machine recognizes a language by accepting or rejecting strings of symbols on its input tape. It follows a set of rules that determine its behavior when reading and writing symbols, and its transitions between states, to determine if a string is part of the language it is designed to recognize.

3. What is language recognition?

Language recognition is the process of determining whether a given string of symbols belongs to a specific language. In the context of Turing Machines, it refers to the capability of a machine to accept or reject strings of symbols based on a set of predetermined rules.

4. How is a Turing Machine different from a regular computer?

A Turing Machine is an abstract mathematical model, while a regular computer is a physical device. A Turing Machine has an infinite tape that can store an unlimited number of symbols, while a regular computer has a finite amount of memory. Additionally, a Turing Machine is limited to a specific set of rules, while a regular computer can be programmed with a wide variety of algorithms and instructions.

5. What is the significance of the Church-Turing thesis in understanding Turing Machines and language recognition?

The Church-Turing thesis states that any function that can be computed by an algorithm can be computed by a Turing Machine. This means that Turing Machines can theoretically solve any problem that can be solved by an algorithm, making them a powerful tool for understanding the limits of computation and language recognition.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
2
Views
532
  • Programming and Computer Science
Replies
25
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
Replies
2
Views
863
  • Programming and Computer Science
Replies
1
Views
864
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top