Register

Recent questions tagged 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.
Prove the Multinomial Theorem: If $n$ is a positive integer, then $\displaystyle{}(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{n_{1} + n_{2} + \dots + n_{m} = n}\:\: C(n:n...
User Avatar
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.
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 you...
User Avatar
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.
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.
User Avatar
Page: