Recent questions tagged turing-machine

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

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

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

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

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

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

Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.

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

Show that $\leq_{m}$ is a transitive relation.

Show that $A_{TM}$ is not mapping reducible to $E_{TM}$. In other words, show that no computable function reduces $A_{TM}$ to $E_{TM}$. (Hint: Use a proof by contradictio...

Find a match in the following instance of the Post Correspondence Problem.$\begin{Bmatrix} \bigg[\dfrac{ab}{abab}\bigg],&\bigg[\dfrac{b}{a}\bigg],&\bigg[\dfrac{aba}{b}\bi...

Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a ...

Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.

Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.

Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.

Let $T = \{(i, j, k)\mid i, j, k \in N \}$. Show that $T$ is countable.

Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.

Let $X$ be the set $\{1, 2, 3, 4, 5\}$ and $Y$ be the set $\{6, 7, 8, 9, 10\}$. We describe the functions $f : X\rightarrow Y$ and $g : X\rightarrow Y$ in the following t...

Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.

Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.

Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.

Let $A$ be the language containing only the single string $s$, where$s = \left\{\begin{matrix} \text{0 if life never will be found on Mars} \\ \:\: \text{1 if life will b...

Let $c_{1}x^{n} + c_{2}x^{n-1} + \dots + c_{n}x + c_{n+1}$ be a polynomial with a root at $x = x_{0}.$ Let $c_{max}$ be the largest absolute value of a $c_{i}.$ Show tha...

Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.

Show that every infinite Turing-recognizable language has an infinite decidable subset.

Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable la...

Show that the collection of Turing-recognizable languages is closed under the operation ofunion.concatenation.star.intersection.homomorphism.

Show that the collection of decidable languages is closed under the operation ofunion.concatenation.star.complementation.intersection.