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)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

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

,

shortcuts and tricks

,

Objective type Questions

,

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

,

practice quizzes

,

video lectures

,

Viva Questions

,

Sample Paper

,

Semester Notes

,

MCQs

,

ppt

,

Important questions

,

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

,

Extra Questions

,

study material

,

pdf

,

Summary

,

Exam

,

Free

,

mock tests for examination

,

past year papers

,

Previous Year Questions with Solutions

;