DOC PREVIEW
GSU CSC 2510 - ch08s3

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Modeling Arithmetic, Computation, and LanguagesTuring MachinesTuring MachineExample: Turning MachineFormal Definition: Turing machineTuring Machine (TM) ExampleTMs as Set RecognizersTMs as Function ComputerTMs as Function ComputersChurch-Turing ThesisSlide 11Decision Problems and UncomputabilityHalting ProblemComputational ComplexityNPModeling Arithmetic, Computation, and LanguagesMathematical Structures for Computer ScienceChapter 8Copyright © 2006 W.H. Freeman & Co. MSCS Slides Turing MachinesSection 8.3 Turing Machines 2Turing MachinesA Turing machine is essentially a finite-state machine with the added ability to reread its input and also to erase and write over its input with unlimited auxiliary memory. Unlimited auxiliary memory makes the Turing machine a hypothetical “machine”  a model  and not a real device. A Turing machine consists of a finite-state machine and an unlimited tape divided into cells, each cell containing at most one symbol from an allowable finite alphabet. At any one instant, only a finite number of cells on the tape are nonblank. The special symbol b is used to denote a blank cell. The finite-state unit, through its readwrite head, reads one cell of the tape at any given moment as shown in the figure below:Section 8.3 Turing Machines 3Turing MachineDepending on the present state of the unit and the symbol read, the unit either does nothing (halts) or completes three actions: Print a symbol from the alphabet on the cell read (it might be the same symbol that’s already there) Go to the next state (it might be the same state as before) Move the readwrite head one cell left or rightThe actions of any particular Turing machine can be described by a set of quintuples of the form (s, i, i , s, d), where s and i indicate the present state and the tape symbol being read, i denotes the symbol printed, s denotes the new state, and d denotes the direction in which the readwrite head moves (R for right, L for left).Section 8.3 Turing Machines 4Example: Turning MachineThus, a machine in the configuration illustrated by Figure (a), if acting according to the instructions contained in the quintuple (2, 1, 0, 1, R), would move to the configuration illustrated in Figure (b). The symbol 1 being read on the tape has been changed to a 0, the state of the unit has been changed from 2 to 1, and the head has moved one cell to the right.Section 8.3 Turing Machines 5Formal Definition: Turing machineDEFINITION: TURING MACHINE Let S be a finite set of states and I a finite set of tape symbols (the tape alphabet) including a special symbol b. A Turing machine is a set of quintuples of the form (s, i, i, s, d) where s, s  S; i, i  I; and d  {R, L} and no two quintuples begin with the same s and i symbols.The restriction that no two quintuples begin with the same s and i symbols ensures that the action of the Turing machine is deterministic and completely specified by its present state and symbol read. A Turing machine halts if it gets into a configuration for which its present state and symbol read are not the first two symbols of any quintuple.Section 8.3 Turing Machines 6Turing Machine (TM) ExampleA Turing machine is defined by the set of quintuples (0, 0, 1, 0, R), (0, 1, 0, 0, R), (0, b, 1, 1, L), (1, 0, 0, 1, R), (1, 1, 0, 1, R) The action of this Turing machine when processing a particular initial tape is shown by the sequence of configurations in figure above, which also shows the quintuple that applies at each step.Section 8.3 Turing Machines 7TMs as Set RecognizersA final state in a Turing machine is one that is not the first symbol in any quintuple. Thus, on entering a final state, whatever the symbol read, the Turing machine halts. DEFINITION: TURING MACHINE RECOGNITION (ACCEPTANCE) A Turing machine T with tape alphabet I recognizes (accepts) a subset S of I* if T, beginning in standard initial configuration on a tape containing a string of tape symbols, halts in a final state if and only if   S. The definition of acceptance leaves open two possible behaviors for T when applied to a string  of tape symbols not in S. T may halt in a non final state, or T may fail to halt at all. One can now build a Turing machine to recognize the set S = {0n1n  n  0}. The machine is based on the second approach to this recognition problem, sweeping back and forth across the input and crossing out 01 pairs.Section 8.3 Turing Machines 8TMs as Function ComputerGiven a particular Turing machine T and a string of  tape symbols, we begin T in standard initial configuration on a tape containing  .If T eventually halts with a string  on the tape, we may consider  as the value of a function evaluated at  . Using function notation, T() = . The domain of the function T consists of all strings for which T eventually halts. We can also think of T as computing number-theoretic functions, functions from a subset of Nk into N for any k  1. There is thus an infinite sequence T 1, T 2 ,... , T k ,... of number-theoretic functions computed by T associated with each Turing machine T. For each k, the function Tk is a partial function on k, meaning that its domain may be a proper subset of Nk. A special case of a partial function on Nk is a total function on Nk, where the function is defined for all k-tuples of nonnegative integers.Section 8.3 Turing Machines 9TMs as Function ComputersDEFINITION: TURING-COMPUTABLE FUNCTION A Turing-computable function is a number-theoretic function computed by some Turing machine. A Turing-computable function f can in fact be computed by an infinite number of Turing machines. Once a machine T is found to compute f, we can always include extraneous quintuples in T, producing other machines that also compute f.Section 8.3 Turing Machines 10Church-Turing ThesisCHURCH-TURING THESIS A number-theoretic function is computable by an algorithm if and only if it is Turing computable. The Church-Turing thesis equates an intuitive idea with a mathematical idea, it can never be formally proved and must remain a thesis, not a theorem. The Church-Turing thesis is now widely accepted as a working tool by researchers dealing with computational procedures. If, in a research paper, a method is set forth for computing a function and the method intuitively seems to be an algorithm, then the


View Full Document

GSU CSC 2510 - ch08s3

Documents in this Course
ch02s2

ch02s2

5 pages

ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch06s3

ch06s3

16 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch03s1

ch03s1

19 pages

ch07s1

ch07s1

11 pages

ch02s1

ch02s1

14 pages

ch08s1

ch08s1

15 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Download ch08s3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch08s3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch08s3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?