CSC 341 (Fall 2021)

Reading: Variants and the Church-Turing Thesis

Properties and Variants and the Church-Turing Thesis

Now that we’ve gotten accustomed to the variety of operations we can emulate with Turing machines, we’ll now take a look at the properties of Turing machines. In particular, we’ll look at closure properties and equivalent models of computation and see how robust the Turing machine model is even though it is minimal. In addition, we’ll also examine the Church-Turing Thesis which states something profound about the computational power of Turing machines.

A Note On Descriptions

The book discusses this concept in chapter 3.3, but it is worthwhile to talk about the different levels of descriptions we can give for Turing machines now that their behavior is rapidly getting more and more complex.

When should we choose one description over the other? Through last class (and for Demonstration Set #3), you should be giving formal descriptions of Turing machine behavior since we’re concerned with capturing the low-level behavior of the model. However, from this point forward, our low-level descriptions will be too unwieldy to provide for every machine we must consider. So we will have to choose between implementation and high-level descriptions depending on what the machine’s underlying language is about.

In essence, we have to ask ourselves what is the “hard part” about the computation described in the language. If the hard part is about getting a Turing machine to perform a certain kind of computation, then an implementation description is appropriate. Otherwise, a high-level description gets to the point without introducing unnecessary detail.


Reading Problem (Stack ’Em Up)

(Adapted from Sipser 3.9).

(Consider an array data structure that allows for arbitrary (index-based) read-write access of its elements. Describe a procedure whereby two stack data structures (that only allow pushing and popping of the top of the stack) can simulate an array. (Hint: place the stacks top-to-top.)