《计算机科学导论》课件Unit 14Theory of Computation教学教材.pptVIP

* 14-1 The Turing Machine 14-2 Halting Problem 14-3 Solvable Problems 14-4 References and Recommended Reading 14-5 Summary 14-6 Practice Set OUTLINE * Understand the architecture of Turing machine. Understand Hopcroft and Ullman formally how to define a Turing machine as a 7-tuple . Understand the Church-Turing thesis. After reading this chapter, you are supposed tobe able to : OBJECTIVES Understand halting problem, polynomial problem, and non-polynomial problem. * Informal description Formal description Examples The Church-Turing thesis 14-1 The Turing Machine * Before Turing Machine The Turing machine is an abstract machine devised by Alan Mathison Turing in 1936 to simulate mathematical operation, and is the foundation of modern computers. Turing shows that a machine with the correct minimal set of operations can calculate anything that is computable, no matter what the complexity is. Today, the common computer usually has a finite memory, but here we suppose that the Turing machine’s memory is infinite. In this section, we present a very simplified version of the machine to show how Turing machine works. Informal description Figure 14.2 The Turing machine in the classic style * (1) Tape The tape contains several cells, one next to the other. Every cell consists of a symbol from the finite alphabet. For the sake of simplicity, we suppose that the machine here may accept only two symbols: a blank (b) and digit 1. The tape used here is freely extendable to the right and to the left , i.e., the Turing machine consist of infinite tape needed for its computation. We also suppose that the tape can deal with only positive integer data made up only of 1s. For instance, the integer 6 is represented as 111111 (six 1s). 0 is represented by the absence of 1s. (2) Read/Write Head The read/write head can read and write symbols on the tape and move to the left or to the right one (and only one) cell at a time. In some models the tape m