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

practice quizzes

,

Sample Paper

,

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

,

pdf

,

Semester Notes

,

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

,

Exam

,

video lectures

,

mock tests for examination

,

ppt

,

Free

,

Summary

,

past year papers

,

MCQs

,

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

,

Important questions

,

Viva Questions

,

shortcuts and tricks

,

study material

,

Previous Year Questions with Solutions

,

Objective type Questions

,

Extra Questions

;