The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent posts tagged theoryofcomputation
1
DECIDABILITY
PLEASE CHECK MY UNDERSTANDING: 1. Halting Problem: a) A turing machine halts after running for exactly k steps on any input This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input. b) A ... (same as above). c) A turing machine replaces the characters on the tape atmost n times on any input SEMIDECIDABLE(same as above).
posted
Sep 14
in
Theory of Computation
by
Balaji Jegan
Active
(
1,735
points)

542
views
theoryofcomputation
2
Rice Theorem
Nice papers with examples: http://drona.csa.iisc.ernet.in/~deepakd/atc2011/tmreductionsrice.pdf http://people.cs.aau.dk/~srba/courses/CC08/riceuk.pdf
posted
Jan 22, 2016
in
Theory of Computation
by
bahirNaik
Active
(
3,213
points)

213
views
ricetheorem
theoryofcomputation
3
Important Questions in Theory of Computation
posted
Aug 9, 2015
in
Theory of Computation
by
Arjun
Veteran
(
357,599
points)

5,424
views
theoryofcomputation
importantquestions
gate
gatecse
To see more, click for the
full list of questions
or
popular tags
.
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
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
Digital Logic GO Classroom
Follow @csegate
Gatecse
Recent Blog Comments
@Arjun sir how to remove such post? should i hide...
[email protected]
.Plz do share @Sanjay sharma
Please post it as question
This is blog area post it as question
[email protected]
39,779
questions
46,781
answers
140,752
comments
58,683
users