Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Theory of Computation  >  Turing Recognizable & Turing Decidable

Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Introduction

  • When we talk about Turing machines (TM) it could accept the input, reject it or keep computing which is called loop.
  • Now a language is recognizable if and only if a Turing machine accepts the string, when the provided input lies in the language.
  • Also, a language can be recognizable if the TM either terminates and rejects the string or doesn't terminate at all. This means that the TM continues with the computing when the provided input doesn't lie in the language.
  • Whereas, the language is decidable if and only if there is a machine which accepts the string when the provided input lies in that language and rejects the string when provided input doesn't lie in that language.

Example

  • A = {hM, wi | M is a DFA and w ∈ L(M)} is decidable.
  • A = {hM, wi | M is a TM and w ∈ L(M)} is recognizable.

The major differences between a recognizable and a decidable in turning machine are as follows:
Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE)

The document Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
Are you preparing for Computer Science Engineering (CSE) Exam? Then you should check out the best video lectures, notes, free mock test series, crash course and much more provided by EduRev. You also get your detailed analysis and report cards along with 24x7 doubt solving for you to excel in Computer Science Engineering (CSE) exam. So join EduRev now and revolutionise the way you learn!
Sign up for Free Download App for Free
18 videos|70 docs|44 tests

Up next

18 videos|70 docs|44 tests
Download as PDF

Up next

Explore Courses for Computer Science Engineering (CSE) exam
Related Searches

past year papers

,

Free

,

MCQs

,

ppt

,

Viva Questions

,

Exam

,

Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE)

,

Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE)

,

Semester Notes

,

Previous Year Questions with Solutions

,

study material

,

Objective type Questions

,

Important questions

,

Sample Paper

,

practice quizzes

,

Summary

,

Extra Questions

,

pdf

,

video lectures

,

mock tests for examination

,

shortcuts and tricks

,

Turing Recognizable & Turing Decidable | Theory of Computation - Computer Science Engineering (CSE)

;