Reference no: EM132883724
Lab - Turing Machines
Introduction
In this lab, you will be asked to complete a number of exercises that are supposed to give you hands-on experience with how a Turing Machine works. The website containing the Turing Machine simulator is located at: https://morphett.info/turing/turing.html
The first part of the lab involves playing with four different machines, which are already done for you. You must study them in order to understand how they work, and answer the questions that are asked. You do not need to turn this part in, but I strongly encourage you to go through with it; it will help you complete part 2.
The second part of the lab will ask you to create a few Turing Machines to solve a specific problem. That is the only part you need to turn in. The deadline and instructions on how to submit are at the end of this document.
Part I: Exploring Turing Machines
Machine 01: Change01toXY
;Change01toXY
;Initial Input: xz0x1 x100 zz11y 0z$zy001 0x$$$00z $
0 _ _ R 0
0 $ $ R halt
0 0 x R 0
0 1 y R 0
0 x x R 0
0 y y R 0
0 z z R 0
Questions:
a) What does this machine do?
b) When does it halt?
c) What would happen if you were to input the following string to the machine? Look at the code and think it through, before trying to run it.
; FindDoubleX
; Initial Input: y x 11x$ zx yxx$yxxx
0 x x R 1
0 y y R 0
0 z z R 0
0 0 0 R 0
0 1 1 R 0
0 $ $ R 0
0 _ _ R 0
1 x x L halt
1 y y R 0
1 z z R 0
1 0 0 R 0
1 1 1 R 0
1 $ $ R 0
1 _ _ R 0
Questions:
a) What does this machine do?
b) When does it halt?
c) Explain the algorithm used in this machine.
Machine 03: FindDoubleX Simplified
; FindDoubleX Simplified by using wildcards (‘*')
; Initial Input: y x 11x$ zx yxx$yxxx
0 x x R 1
0 * * R 0
1 x x L halt
1 * * R 0
Questions:
a) What does this machine do?
b) How is it different from the previous machine (Machine02)?
Exercise: Can you simplify Machine01 using the same trick? If so, create this simplified machine below.
Machine 04:
; CopyXYZ
; Initial Input: yxyzzyxxy
0 _ _ R halt
0 x $ R 1
0 y $ R 5
0 z $ R 9
1 _ _ R 2
1 * * R 1
2 _ x L 3
2 * * R 2
3 _ _ L 4
3 * * L 3
4 $ x R 0
4 * * L 4
5 _ _ R 6
5 * * R 5
6 _ y L 7
6 * * R 6
7 _ _ L 8
7 * * L 7
8 $ y R 0
8 * * L 8
9 _ _ R 10
9 * * R 9
10 _ z L 11
10 * * R 10
11 _ _ L 12
11 * * L 11
12 $ z R 0
12 * * L 12
Questions:
a) What does this machine do?
b) Explain the algorithm, and try to give a functional interpretation for each state (here, numbered from 0 to 12) - in other words, if you had to explain what each state is doing or what is the purpose of each state in plain English, how would you do it?
Part II: Create your own turing machines now
Machine 01
Create a Turing machine that will move to the right until it finds a $. Then it will erase everything on the tape between that $ and the next $ to the right. It will halt when it gets to the second $. The s themselves should not be erased. You can do this with a fairly simple machine that uses only two states, 0 and 1. (Note that if the machine is started on a tape that does not contain two's to the right of the machine's starting position, then the machine will never halt.)
Initial Input: ignore me$ERASE ME$ignore me too
Machine 02
One of the examples in the lab is a Turing machine called "FindDoubleX." This machine moves to the right until it comes to two x's in a row. Then it halts on the first of the two x's. Create a new machine that will move to the right until it finds three x's in a row. It should halt when it finds a group of three consecutive x's. (Ideally, it should move back to the first of the three x's and halt there.)
Initial Input: y x 11x$ zx yxx$yxxxzz$x
Machine 03
Construct a Turing machine to do the following: Assume that the machine is started on a tape that contains nothing but a string of
s. The machine is started on the left end of this string. The purpose of the machine is to multiply the length of the string by 3. For example, if it is started on a string of seven's, it should halt with twenty-one's on the tape. If it is started on a string that contains just one $, it should halt with three's on the tape. Here is one way that the machine might operate: Change one of the's to an x, then go to the end of the string and write two more x's. Go back and process the next $ in the same way. Continue until all the's have been processed. Then change all the x's to's.
Initial Input: $
Machine 04
Construct a Turing machine to do the following: Assume that the machine is started on a tape that contains nothing but a string of
s. The machine is started on the left end of this string. The purpose of the machine is to divide the length of the string by 3. (Throw away any extra fractional part, so that 17 divided by 3 would be 5). For example, if the machine is started on a string of twenty-one's, it should halt with seven's on the tape. If it is started with ten's on the tape, it should halt with three's on the tape. And if it is started with five's on the tape, then it should halt with one $ on the tape.
Initial Input: $$$
Machine 05
Construct a Turing machine to do the following: Assume the machine is started on a tape that contains only a continuous (ie, not broken by spaces) string of characters. The only allowable characters on the string are A, C, G, T or empty space (_). The machine is started on the left of the string. The purpose of the machine is to reverse the string of characters. For instance, if the input string is CAT, the machine should write TAC and halt.
Initial Input: ACATAG
Attachment:- Turing Machines.rar