(Notes from Chapter 6, Sections 3 - 5)
Given a Turing machine \({\cal M}\) with alphabet \(A = \{s_1,\ldots,s_n\}\), a word \(u \in A^*\) is said to be accepted by \({\cal M}\) if \({\cal M}\) will eventually halt if it begins with the configuration \[ \begin{array}{llllll} B & u \\ \uparrow \\ q_1 \end{array} \]
The set of all words \(u \in A^*\) accepted by \({\cal M}\) is called the language accepted by \({\cal M}\).
Theorem 3.1. A language is accepted by some Turing machine if and only if the language is r.e.
Theorem 3.2. A set \(U\) of numbers is r.e. if and only if there is a Turing machine \({\cal M}\) with alphabet \(\{1\}\) that accepts \(1^{[x]}\) if and only if \(x \in U\).
Theorem 3.3. Let \(A \subseteq \tilde{A}\) where \(A\) and \(\tilde{A}\) are alphabets and let \(L \subseteq A^*\). Then \(L\) is an r.e. language on the alphabet \(A\) if and only if \(L\) is an r.e. language on \(\tilde{A}\).
Corollary 3.4. Let \(A, \tilde{A}, L\) be as in Theorem 3.3. Then \(L\) is a recursive language on \(A\) if and only if \(L\) is a recursive language on \(\tilde{A}\).
The halting problem for a fixed given Turing machine \({\cal M}\) is the problem of finding an algorithm to determine if \({\cal M}\) will eventually halt starting with a given configuration.
Theorem 4.1. There is a Turing machine \({\cal K}\) with alphabet \(\{1\}\) that has an unsolvable halting problem.
Theorem 4.2. There is a Turing machine \({\cal \tilde{K}}\) with alphabet \(\{1\}\) and a state \(q_m\) such that there is no algorithm that can determine whether \({\cal \tilde{K}}\) will ever arrive at state \(q_m\) when it begins at a given configuration.
Recall that a nondeterministic Turing machine is simply an arbitrary finite set of quadruples. A configuration \[\begin{array}{lll} \cdots & s_j & \cdots \\ & \uparrow & \\ & q_i \end{array}\] is called terminal with respect to a given nondeterministic Turing machine if it contains no quadruple beginning \(q_is_j\).
We use the symbol \(\vdash\) placed between a pair of configurations to indicate that the transition from the configuration on the left to that on the right is permitted by one of the quadruples of the machine under consideration.
Let \(A = \{s_1,\ldots,s_n\}\) be a given alphabet and let \(u \in A^*\). Then the nondeterministic Turing machine \({\cal M}\) is said to accept \(u\) if there is a sequence of configurations \(\gamma_1,\ldots,\gamma_m\) such that \(\gamma_m\) is terminal with respect to \({\cal M}\), \(\gamma_1\) is the configuration \[\begin{array}{lll} s_0 & u \\ \uparrow & \\ q_1 \end{array}\] and \( \gamma_1 \vdash \cdots \vdash \gamma_m\).
The sequence \(\gamma_1,\ldots,\gamma_m\) is called an accepting computation by \({\cal M}\) for \(u\). If \(A\) is the alphabet of \({\cal M}\), then the language accepted by \({\cal M}\) is the set of all \(u \in A^*\) that are accepted by \({\cal M}\).
Theorem 5.1. For every r.e. language \(L\), there is a nondeterministic Turing machine \({\cal M}\) that accepts \(L\).
The converse of Theorem 5.1 also holds. This will be discussed later.