Recent questions tagged proof - GATE Overflow

+2 votes

0 answers

1

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 79 views

+1 vote

0 answers

2

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 24 views

0 votes

1 answer

3

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 64 views

0 votes

0 answers

4

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 22 views

0 votes

0 answers

5

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}\}$.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 20 views

0 votes

0 answers

6

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 22 views

+1 vote

0 answers

7

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} \}$.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 25 views

0 votes

0 answers

8

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 12 views

0 votes

0 answers

9

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 21 views

0 votes

0 answers

10

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 19 views

0 votes

0 answers

11

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.

asked Oct 20, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 9 views

0 votes

0 answers

12

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}$.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 16 views

0 votes

0 answers

13

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 4 views

0 votes

0 answers

14

Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 6 views

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 2 views

0 votes

0 answers

16

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.)

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 5 views

0 votes

0 answers

17

Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 7 views

0 votes

0 answers

18

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 5 views

0 votes

0 answers

19

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\}$.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 9 views

0 votes

0 answers

20

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\}$.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 9 views

0 votes

0 answers

21

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 2 views

+1 vote

0 answers

22

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 46 views

0 votes

0 answers

23

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 3 views

0 votes

0 answers

24

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 6 views

0 votes

0 answers

25

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 11 views

0 votes

0 answers

26

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 8 views

0 votes

0 answers

27

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 5 views

0 votes

0 answers

28

Michael Sipser Edition 3 Exercise 5 Question 9 (Page No. 239)
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 7 views

0 votes

0 answers

29

Michael Sipser Edition 3 Exercise 5 Question 8 (Page No. 239)
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 4 views

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.9k points) | 8 views

Page:

1
2
3
4
5
6
...
9
next »

Recent questions tagged proof

50,737 questions

57,300 answers

198,291 comments

104,997 users