Login
Register
@
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
Recent questions tagged proof
0
votes
0
answers
1
Kenneth Rosen Edition 7 Exercise 8.2 Question 10 (Page No. 525)
Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ ... $n = 0,1,2,\dots,$ where $\alpha_{1}$ and $\alpha_{2}$ are constants.
Lakshman Bhaiya
asked
in
Combinatory
May 3, 2020
by
Lakshman Bhaiya
220
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
proof
0
votes
0
answers
2
Kenneth Rosen Edition 7 Exercise 6.5 Question 63 (Page No. 434)
Prove the Multinomial Theorem: If $n$ ... $C(n:n_{1},n_{2},\dots,n_{m}) = \dfrac{n!}{n_{1}!n_{2}!\dots n_{m}!}$ is a multinomial coefficient.
Lakshman Bhaiya
asked
in
Combinatory
May 1, 2020
by
Lakshman Bhaiya
515
views
kenneth-rosen
discrete-mathematics
counting
combinatory
proof
0
votes
0
answers
3
Kenneth Rosen Edition 7 Exercise 6.4 Question 32 (Page No. 422)
Prove the binomial theorem using mathematical induction.
Lakshman Bhaiya
asked
in
Combinatory
Apr 30, 2020
by
Lakshman Bhaiya
163
views
kenneth-rosen
discrete-mathematics
counting
binomial-theorem
proof
3
votes
0
answers
4
Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
607
views
michael-sipser
theory-of-computation
context-free-grammar
recursive-and-recursively-enumerable-languages
decidability
proof
1
vote
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
329
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
proof
0
votes
1
answer
6
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
692
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
1
vote
2
answers
7
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
549
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
444
views
michael-sipser
theory-of-computation
context-free-grammar
turing-machine
decidability
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
349
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
1
vote
0
answers
10
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
382
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
427
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
400
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
1
vote
0
answers
13
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
456
views
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
0
votes
0
answers
14
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 Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
383
views
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
0
votes
0
answers
15
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 Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
289
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
199
views
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
17
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 Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
196
views
michael-sipser
theory-of-computation
decidability
reduction
proof
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
161
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
reduction
proof
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
383
views
michael-sipser
theory-of-computation
context-free-grammar
reduction
post-correspondence-problem
decidability
proof
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
280
views
michael-sipser
theory-of-computation
decidability
proof
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 5 Question 19 (Page No. 240)
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
299
views
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 5 Question 18 (Page No. 240)
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
475
views
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 5 Question 17 (Page No. 240)
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
249
views
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 5 Question 16 (Page No. 240)
Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$, consider all $k-$state TMs that halt when ... maximum number of $1s$ that remain on the tape among all of these machines. Show that $BB$ is not a computable function.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
400
views
michael-sipser
theory-of-computation
turing-machine
computability
proof
1
vote
0
answers
25
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 Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
926
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
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.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
259
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 5 Question 13 (Page No. 239)
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
322
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 5 Question 12 (Page No. 239)
Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
384
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 5 Question 11 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
273
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
1
vote
0
answers
30
Michael Sipser Edition 3 Exercise 5 Question 10 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem as a language and show that it is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
232
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
Page:
1
2
3
4
5
6
...
9
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(24)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(682)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
243k
comments
79.7k
users
Recent questions tagged proof
Recent Blog Comments
Hlo I'm Rupesh I got AIR 3485 in gate CS and AIR...
@Ajay Sasank here is the direct link...
Thank you for the post didi My GATE 2023 & 2024...
I Hope it helps 😊
Today's best post I seen thank you for motivation