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
Theory of Computation  GO Classroom
Day Date Contents Slides Assignments 1 Sep 27 Regular Language alphabets, language(set of strings), language class or language family All languages uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, ... finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.
posted
Oct 6
in
Theory of Computation
by
Manoja Rajalakshmi A
Active
(
4,135
points)

594
views
theoryofcomputation
goclassroom
preparationschedule
2
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
(
3,063
points)

696
views
theoryofcomputation
3
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,261
points)

217
views
ricetheorem
theoryofcomputation
4
Important Questions in Theory of Computation
posted
Aug 9, 2015
in
Theory of Computation
by
Arjun
Veteran
(
360,967
points)

5,650
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
IIT Madras Phd
Databases GO Classroom
I need help in Preparation for 2020
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent Blog Comments
They are not reviewed by GO. But they will be...
What is the job profile for candidate at AAI and...
GATEBOOK2019 DS1 doesn't have solutions,...
How to prepare for aptitude part?
Belated happy birthday to you, sir :)
42,296
questions
48,419
answers
153,541
comments
62,661
users