@

Dark Mode

Profile
Edit my Profile
Messages
My favorites

Register

Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams

Dark Mode

Turing Machines Theory

Abhipsa asked in Theory of Computation Jan 22, 2019

252 views

1 vote

1 vote

What is the difference between Turing Recognizable and Turing Decidable?

Thanks!

theory-of-computation
turing-machine
decidability

Abhipsa asked in Theory of Computation Jan 22, 2019

252 views

1 comment

by Arjun

commented Jan 22, 2019

You can watch this:

https://gateoverflow.in/blog/6484/decidability-slides

1

1

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

4 votes

4 votes

Best answer

Turing Recognizable recursive enumerable

Turing Decidable recursive language

SUNNY054 answered Jan 23, 2019 selected Jan 23, 2019 by Abhipsa

0 Comments

Please log in or register to add a comment.

← Previous Next →

← Previous in category Next in category →

Related questions

1 vote

1 vote

0 answers

1

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

336 views

Turing Machines Deciadability
L ={ T | e(T) belongs to L(T) } , e(T) is the code for turing machine? The answer given is RE but not REC ,but cant we apply Rice theorem as follow- Tyes={Any machine accepting its code} Tno={Machine accepting code of Tyes + a } //Tno ... be applied to T,then members will say say and for Non members it may or may not halt.But where am i wrong in Rice's theorem proof?

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

by rahul sharma 5

336 views

theory-of-computation
turing-machine
decidability

3 votes

3 votes

2 answers

2

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

689 views

TOC Turing machines Decidability
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? L={⟨M⟩∣ M halts on all palindromes}. How can i use Rice's theorem here? Tyes={All palidroms} Tno={Signma*}.Will that work here? M halts on all palindromes means M halts on only palindromes ?

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

by rahul sharma 5

689 views

theory-of-computation
turing-machine
decidability

2 votes

2 votes

2 answers

3

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

405 views

Turing machines decidability
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? {⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M1)∖L(M2)}.

rahul sharma 5 asked in Theory of Computation Aug 8, 2017

by rahul sharma 5

405 views

theory-of-computation
turing-machine
decidability

2 votes

2 votes

0 answers

4

rahul sharma 5 asked in Theory of Computation Aug 5, 2017

340 views

TOC:- Turing Machines Decidiability
Please help in classifying above languages

rahul sharma 5 asked in Theory of Computation Aug 5, 2017

by rahul sharma 5

340 views

theory-of-computation
turing-machine
decidability

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

Quick search syntax

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent Posts

From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
What are the key things to focus on during the final 10-15 days before the GATE exam to improve performance?
All India GO Classes Mock test
NTA UGC NET JRF December 2022 Apply Online Form 2023
Life happens, just chill and do hardwork

Subjects

All categories
General Aptitude (2.5k)
Engineering Mathematics (9.3k)
Digital Logic (3.3k)
Programming and DS (5.8k)
Algorithms (4.6k)
Theory of Computation (6.7k)
Compiler Design (2.3k)
Operating System (5.0k)
Databases (4.6k)
CO and Architecture (3.8k)
Computer Networks (4.6k)
Non GATE (1.3k)
Others (2.4k)
Admissions (649)
Exam Queries (842)
Tier 1 Placement Questions (17)
Job Queries (74)
Projects (9)
Unknown Category (853)

Recent Blog Comments

@abhi_3_0_12 bro revise now, Gate is on upcoming...
I want to buy the test series today but I want to...
@mahendrapatel The more you give those (some...
@ChatGPT bhai muze vo test bhi dena tha...
AIMT is live now:...

Send feedback
Rank Predictor
College Prediction
Useful Links
FAQ
Corrections
Discuss
Copyright
Request
Testimonials
Chat Logs
Chat
Badges
Search tips
Exam Category
Blog Category
Blog Tags
Privacy
Test Series
Contact Us

Developed by Chun

Twitter WhatsApp Facebook Reddit LinkedIn Email

Link Copied!