These questions look into what you can determine about a transition function for a Turing machine, even if you aren’t given the definition.
There are two components in the domain of the Turing Machine transition function, which determine the next configuration. What are they in general (meaning what are the sets that make up the domain)?
What are the two values that the transition function uses if it is in configuration \(\texttt{011}q_7\texttt{00101}\)?
If I tell you that a TM goes from configuration \(\texttt{011}q_7\texttt{00101}\) to \(\texttt{0110}q_7\texttt{0101}\) in one step, what is the transition function’s value (from the range) that is used for this configuration?
Knowing nothing else about the transition function, what is the next configuration is, after \(\texttt{0110}q_7\texttt{0101}\)? Explain your answer!
We consider a alternative TM that we call a “left-detecting TM”. This TM can detect when it is at the leftmost position on its tape, and do different actions when in that position, while a standard TM has no way of detecting the left end (i.e., the beginning) of the tape. A left-detecting TM has two transition functions. One is a special transition function \(\delta_L:Q\times\Gamma\rightarrow Q\times\Gamma\) that is only used when the TM is at the leftmost position on the tape – the TM must move right, so no direction is given. The second transition function is the standard TM transition function \(\delta:Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}\), and is used whenever the TM is not at the leftmost position. Prove that every left-detecting TM has an equivalent standard single-tape Turing machine. (In other words, give a proof in the style of Theorem 3.13 or Theorem 3.16.)
Consider the language \(SUBSET_{DFA}=\{\langle M_1,M_2\rangle\,|\,L(M_1)\subseteq L(M_2)\}\). Show that \(SUBSET_{DFA}\) is decidable.
Let \(\Sigma=\{\texttt{a},\texttt{b},\texttt{c}\}\), so \(\Sigma^*\) is the set of all strings over this alphabet. Prove that \(\Sigma^*\) is countable.
Consider the language \(CFL_{TM}=\{\langle M\rangle\,|\,L(M)\) is a context-free language\(\}\). Prove that this language is undecidable. (Hint: Note the similarity to the language \(REGULAR_{TM}\) in Section 5.1.)
Given a Turing machine \(M\), an input \(w\), and a tape symbol \(x\in\Gamma\), we would like to know if \(M\) writes symbol \(x\) on its tape at some point while running on input \(w\).
Write this decision problem out as a language, using set notation.
Prove that this language is undecidable.
Prove that the language is recognizable.
Now consider the complement language: \(M\) never writes an \(x\) on its tape. Is this decidable? Recognizable?