# dm08

View again

## Documents

9 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
DISCRETE MATHEMATICS W W L CHEN c W W L Chen, 1991, 2008. This chapter is available free to all individuals, on the understanding that it is not to be used for ﬁnancial gain, and may be downloaded and/or photocopied, with or without permission from the author. However, this document may not be kept on any information storage and retrieval system without permission from the author, unless such system is not accessible to any individuals other than its owners. Chapter 8 TURING MACHINES 8.1. Int
Document Share
Documents Related
Document Tags

## Areas Of Computer Science

Document Transcript
DISCRETE MATHEMATICS W W L CHEN c  W W L Chen, 1991, 2008.This chapter is available free to all individuals, on the understanding that it is not to be used for ﬁnancial gain,and may be downloaded and/or photocopied, with or without permission from the author.However, this document may not be kept on any information storage and retrieval system without permissionfrom the author, unless such system is not accessible to any individuals other than its owners. Chapter 8 TURING MACHINES 8.1. Introduction A Turing machine is a machine that exists only in the mind. It can be thought of as an extended andmodiﬁed version of a ﬁnite state machine.Imagine a machine which moves along an inﬁnitely long tape which has been divided into boxes, eachmarked with an element of a ﬁnite alphabet A . Also, at any stage, the machine can be in any of a ﬁnitenumber of states, while at the same time positioned at one of the boxes. Now, depending on the elementof  A in the box and depending on the state of the machine, we have the following: ã The machine either leaves the element of  A in the box unchanged, or replaces it with anotherelement of  A . ã The machine then moves to one of the two neighbouring boxes. ã The machine either remains in the same state, or changes to one of the other states.The behaviour of the machine is usually described by a table. Example 8.1.1. Suppose that A = { 0 , 1 , 2 , 3 } , and that we have the situation below:5 ↓ ... 003211 ... Here the diagram denotes that the Turing machine is positioned at the box with entry 3 and that it is instate 5. We can now study the table which describes the bahaviour of the machine. In the table below,the column on the left represents the possible states of the Turing machine, while the row at the top Chapter 8 : Turing Machines page 1 of 9  Discrete Mathematics c  W W L Chen, 1991, 2008 represents the alphabet ( i.e. the entries in the boxes):0 1 2 3...5 1 L 2...The information “1 L 2” can be interpreted in the following way: The machine replaces the digit 3 by thedigit 1 in the box, moves one position to the left, and changes to state 2. We now have the followingsituation:2 ↓ ... 001211 ... We may now ask when the machine will halt. The simple answer is that the machine may not halt atall. However, we can halt it by sending it to a non-existent state. Example 8.1.2. Suppose that A = { 0 , 1 } , and that we have the situation below:2 ↓ ... 001011 ... Suppose further that the behaviour of the Turing machine is described by the table below:0 10 1 R 0 1 R 41 0 R 3 0 R 02 1 R 3 1 R 13 0 L 1 1 L 2Then the following happens successively:3 ↓ ... 011011 ... 2 ↓ ... 011011 ... 1 ↓ ... 011011 ... 0 ↓ ... 010011 ... Chapter 8 : Turing Machines page 2 of 9  Discrete Mathematics c  W W L Chen, 1991, 2008 0 ↓ ... 010111 ... 4 ↓ ... 010111 ... The Turing machine now halts. On the other hand, suppose that we start from the situation below:3 ↓ ... 001011 ... If the behaviour of the machine is described by the same table above, then the following happenssuccessively:1 ↓ ... 001011 ... 3 ↓ ... 001011 ... The behaviour now repeats, and the machine does not halt. 8.2. Design of Turing Machines We shall adopt the following convention:(1) The states of a k -state Turing machine will be represented by the numbers 0 , 1 ,...,k − 1, while thenon-existent state, denoted by k , will denote the halting state.(2) We shall use the alphabet A = { 0 , 1 } , and represent natural numbers in the unary system. Inother words, a tape consisting entirely of 0’s will represent the integer 0, while a string of  n 1’s willrepresent the integer n . Numbers are also interspaced by single 0’s. For example, the string ... 01111110111111111101001111110101110 ... will represent the sequence ..., 6 , 10 , 1 , 0 , 6 , 1 , 3 ,... . Note that there are two successive zeros in thestring above. They denote the number 0 in between.(3) We also adopt the convention that if the tape does not consist entirely of 0’s, then the Turingmachine starts at the left-most 1.(4) The Turing machine starts at state 0. Example 8.2.1. We wish to design a Turing machine to compute the function f  ( n ) = 1 for every n ∈ N ∪{ 0 } . We therefore wish to turn the situation ↓ 01 ... 1            n 0 Chapter 8 : Turing Machines page 3 of 9  Discrete Mathematics c  W W L Chen, 1991, 2008 to the situation ↓ 010(here the vertical arrow denotes the position of the Turing machine). This can be achieved if the Turingmachine is designed to change 1’s to 0’s as it moves towards the right; stop when it encounters thedigit 0, replacing it with a single digit 1; and then correctly positioning itself and move on to the haltingstate. This can be achieved by the table below:0 10 1 L 1 0 R 01 0 R 2Note that the blank denotes a combination that is never reached. Example 8.2.2. We wish to design a Turing machine to compute the function f  ( n ) = n + 1 for every n ∈ N ∪{ 0 } . We therefore wish to turn the situation ↓ 01 ... 1            n 0to the situation ↓ 01 ... 1            n +1 0( i.e. we wish to add an extra 1). This can be achieved if the Turing machine is designed to move towardsthe right, keeping 1’s as 1’s; stop when it encounters the digit 0, replacing it with a digit 1; move towardsthe left to correctly position itself at the ﬁrst 1; and then move on to the halting state. This can beachieved by the table below:0 10 1 L 1 1 R 01 0 R 2 1 L 1 Example 8.2.3. We wish to design a Turing machine to compute the function f  ( n,m ) = n + m forevery n,m ∈ N . We therefore wish to turn the situation ↓ 01 ... 1      n 01 ... 1      m 0to the situation ↓ 01 ... 1      n 1 ... 1      m 0( i.e. we wish to remove the 0 in the middle). This can be achieved if the Turing machine is designedto move towards the right, keeping 1’s as 1’s; stop when it encounters the digit 0, replacing it with a Chapter 8 : Turing Machines page 4 of 9
Similar documents