CSC 341: March 16, 2007

From CSWiki

Previous Lecture Next Lecture

Instructor's notes for the class session

Sipser just assumes that encoding an automaton, a regular expression, or a context-free grammar as input to a Turing machine is trivial. What might such an encoding actually look like? Could we use Sipser's prose descriptions for this purpose? What about the Scheme data structures that I developed?

In proving that every regular language is Turing-decidable, I argued that any deterministic finite automaton can be simulated by a Turing machine -- we just take the states of the deterministic finite automaton and add q_accept and q_reject, copy the transition table, adding the no-change tape-write operation and the tape motion R to each transition, and adding a transition on the blank character to q_accept from each of the DFA's accept states and to q_reject from each of its non-accept states. Thus there will be a different Turing machine for each DFA that we want to simulate.

The simulator that Sipser posits in his proof of Theorem 4.1 is different -- it's a universal DFA simulator, capable of simulating any DFA by consulting its encoded description whenever it needs to simulate a transition. It's more like a Scheme procedure that takes a Scheme datum representing a DFA as one of its inputs and does a lookup to find out how to simulate each transition. As an adherent of the Church-Turing thesis, Sipser just takes it as obvious that, since we can figure out how to write a program in a high-level language to do this, the Turing machine to do it also exists. (It's not all that difficult to construct the actual Turing machine, but it's tedious.)

Sipser's proof of Theorem 4.2 illustrates two other proof-design patterns to which I wanted to call your attention. One is the idea of using a Turing machine as a component of a larger Turing machine. Once Sipser has proved or posited the existence of a Turing machine, he treats it as a black-box component or library procedure that can be embedded. At a low level, embedding a Turing machine may involve relabelling its states or the symbols in its tape alphabet to avoid name conflicts, changing its accept and reject states into normal states with out-transitions to states in the enclosing environment, adding out-transitions to its states to accommodate tape symbols that are generated and used only in the enclosing environment, and so on. Sipser simply brushes past all of these details.

The second pattern is the idea of pre- and post-processing: preparing string input for an embedded Turing machine by applying some computable string-to-string function to it, or taking the Boolean output of an embedded Turing machine and inverting it, or performing some further computation with it, before delivering the result as the output of the enclosing machine. These are legitimate design techniques provided that the pre- and post-processing functions are computable and specified by algorithms. We'll need to take some case when they are partial functions, that is, when the Turing-machine components that implement them don't halt on some inputs.

The proofs of the theorems in section 4.1 are all constructions, each presenting an algorithm for deciding any instance of a general problem. Because we care only about the existence, correctness, and termination of the algorithm, it's often a ridiculously inefficient, brute-force approach. Turing machines run at the speed of thought, without physical limitations, so brute force is almost always the method of choice.

Theorem 4.7 states that the acceptance problem for context-free grammars, , is a decidable language. One might think that it would be possible to use a similar argument to show that the word problem for semi-Thue processes, , is decidable: Just generate all the possible computations that start from w, and see whether any of them produces w'. Unfortunately, the number of possible computations that start from w is usually infinite, and there is no way to set un upper bound on the number of steps in such a computation, because there is no analogue of Chomsky normal form for semi-Thue processes generally.

Study questions

1. A deterministic finite automaton is indiscriminate if it accepts either all of the strings over its alphabet or none of them. Show that the set of encodings of indiscriminate deterministic finite automata -- that is, the set -- is decidable.
2. A deterministic finite automaton is parity-bound if the strings that it accepts are all of even length or all of odd length. Show that the set of encodings of parity-bound deterministic finite automata is decidable.
3. Let F be the set of given names of (future) sons and daughters of students currently enrolled for this course. Is F decidable?

Proposed Solutions

1. The TM to decide the set of indiscriminate DFAs contains two subroutines. The first, E is a decider for E_DFA, shown to exist in Theorem 4.4, p. 168. If E accepts, then the entire TM accepts, otherwise, it goes to the second subroutine, A. In addition to its original input, our TM gives A the encoding for a DFA which accepts all strings on its alphabet. This DFA can be built by constructing a DFA that accepts no strings, and changing all reject states to accept states. The subroutine A checks the two DFAs for equality (decidable by Theorem 4.5, p. 169). If A accepts, the whole TM accepts, otherwise, the whole TM rejects. As our TM now decides the set of indiscriminate DFAs, that set is decidable.
2. 
   
3. As Prof. Stone mentioned in class, F is decidable because it is finite, and all finite languages are regular.

---

Previous Lecture Next Lecture

Front Door