menu
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Login
Register
My account
Edit my Profile
Private messages
My favorites
Register
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
148
views
0
votes
0
votes
Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.
michael-sipser
theory-of-computation
turing-machine
decidability
proof
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
148
views
answer
comment
share this
share
0 Comments
Please
log in
or
register
to add a comment.
Subscribe to GO Classes for GATE CSE 2022
Please
log in
or
register
to answer this question.
0
Answers
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
0
votes
0
answers
1
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
245
views
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Patel RJIT
245
views
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
0
votes
0
votes
0
answers
2
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
166
views
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
166
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
1
vote
1
vote
0
answers
3
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
458
views
Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
458
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
votes
0
answers
4
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
121
views
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
121
views
michael-sipser
theory-of-computation
decidability
reduction
proof
Ask a Question
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
Journey of GO
Honouring the Contributors to GATE Overflow
AIR 1518 to AIR 34
GATE Overflow and GO Classes Test Series - GATE CSE 2023
Kaggle Competition for GATE CSE Topic classification
Categories
All categories
General Aptitude
(2.3k)
Engineering Mathematics
(8.9k)
Digital Logic
(3.1k)
Programming and DS
(5.4k)
Algorithms
(4.7k)
Theory of Computation
(6.4k)
Compiler Design
(2.3k)
Operating System
(4.8k)
Databases
(4.4k)
CO and Architecture
(3.6k)
Computer Networks
(4.4k)
Non GATE
(1.2k)
Others
(2.1k)
Admissions
(636)
Exam Queries
(856)
Tier 1 Placement Questions
(18)
Job Queries
(72)
Projects
(9)
Unknown Category
(1.1k)
Follow @gateoverflow
GATE Overflow
Recent Blog Comments
No new books for 2023:...
@Arjun When Go Book for 2023 will get...
what was the result ?
@ykrishnayOperating System in Computer Science...
If the contribution mean to help people with...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Twitter
WhatsApp
Facebook
Reddit
LinkedIn
Email
Link Copied!
Copy
Search GATE Overflow for GATE CSE