CS1005 Logic & Computation
Lab sheet 1: Turing Machines
(Solutions in bold red font)
1. Print off and read (or read on-line) the lecture slides and notes on Turing Machines.
Please make sure that you clarify any questions you have from them with the GTAs.
2. Write down the binary numbers corresponding to decimal 1 to 20 inclusive.
1=1, 2=10, 3=11, 4=100, 5=101, 6=110, 7=111, 8=1000, 9=1001, 10=1010
11=1011, 12=1100, 13=1101, 14=1110, 15=1111, 16=10000, 17=10001, 18=10010,
19=10011, 20=10100
3. Do the following additions in binary notation without translating into decimal.
Show your working [i.e. the ‘carries’]:
0+1 = 1
1+1 = 10
11+1 = 100
101+1 = 110
111+1 = 1000
11+10 = 101
100+101 = 1001
4. Using the Turing machine table below (the same one as we used in the lecture slides),
state the rows of the table that would be used for the following two inputs on the tape
and what the output would be. Remember, we start at the “*” on the right-hand side
of the binary string in the ‘start’ state. Use the example in your slides to help if you
need to.
Row Current State Current Value Direction to New state to
cell to write move enter
content
1 START * * Left ADD
2 ADD 0 1 Right RETURN
3 ADD 1 0 Left CARRY
4 ADD * * Right HALT
5 CARRY 0 1 Right RETURN
6 CARRY 1 0 Left CARRY
7 CARRY * 1 Left OVERFLOW
8 OVERFLOW Ignored * Right RETURN
9 RETURN 0 0 Right RETURN
10 RETURN 1 1 Right RETURN
11 RETURN * * No Move HALT
,In both cases, the rows of the table used would be 1, 2 and 11. The output of the left
side figure would be 011 and 101 for the right side.
5. Do the same thing with a ‘1’ in every cell, i.e., *111*
In the case where every cell is a’1’, an overflow occurs and so the rows of the table
used would be: 1, 3, 6, 6, 7, 8, 10, 9, 9, 9, 11 and output 1000.
6. Do the same thing with configurations (bit patterns) ‘101’ and ‘001’
For 101, the rows used would be: 1, 3, 5, 9, 11
For 001, the rows used would be the same, i.e., : 1, 3, 5, 9, 11
7. What would be the effect on all the examples above if row 2 instead read as below,
i.e., the value to write has changed from a ‘1’ to a ‘0’
Row Current State Current Value Direction to New state to
cell to write move enter
content
2 ADD 0 0 Right RETURN
The numbers on the tape would stay as they are! There would be no change in
the tape at all.
8. If you have time, in your own words, think of one good reason why state analysis is
so important in computing today.
Testing programs often requires analysis of states – and failure to understand a
system in minute detail can be catastrophic with loss of human life. Using
analysis of states can help understand how a system works in detail – but more
importantly help to uncover ‘error’ states that would cause failure.
, CS1005 – Logic and Computation
Worksheet with Solutions: Lab 2: State Transition and Turing Machine
1. Draw a State Transition Table for the following state machine.
Solution:
2. Given the state diagram of a Turing Machine is:
Answer the following:
a) What is the Tape input language Σ
, CS1005 – Logic and Computation
b) What is the result of the computation of the machine?
Solution:
a) Σ={a,b,c}
b) The result of a computation is to replace the a’s in the input string with c’s and the c’s with
b’s.
3. Given the following Turing Machine
0/0, R 0/0, L
Y/Y, R Y/Y, L
0/X, R 1/Y, L
A B C
Y/Y, R X/X,R
D Y/Y, R
Δ/ Δ,L
Δ/ Δ,L
ACCEPT
and the following tape input:
a) Is this input legal?
b) Given this input, in which state will the machine terminate?
Solution:
a) It is not legal because the machine recognizes L=0n 1n .
b) The machine will terminate in the Reject state. Notice that the Reject State is seldom drawn,
and any transition not drawn on the machine is a Reject State.
4. Define A Turing Machine using a state diagram that recognizes the language anbn cn
Solution:
‣ Starting at left-hand of input, if current cell is empty, accept.
‣ Otherwise, if cell contains an a, change this to an X and move right looking for a corresponding b.
‣ If b is found, change it to a Y and move right looking for a corresponding c.
Lab sheet 1: Turing Machines
(Solutions in bold red font)
1. Print off and read (or read on-line) the lecture slides and notes on Turing Machines.
Please make sure that you clarify any questions you have from them with the GTAs.
2. Write down the binary numbers corresponding to decimal 1 to 20 inclusive.
1=1, 2=10, 3=11, 4=100, 5=101, 6=110, 7=111, 8=1000, 9=1001, 10=1010
11=1011, 12=1100, 13=1101, 14=1110, 15=1111, 16=10000, 17=10001, 18=10010,
19=10011, 20=10100
3. Do the following additions in binary notation without translating into decimal.
Show your working [i.e. the ‘carries’]:
0+1 = 1
1+1 = 10
11+1 = 100
101+1 = 110
111+1 = 1000
11+10 = 101
100+101 = 1001
4. Using the Turing machine table below (the same one as we used in the lecture slides),
state the rows of the table that would be used for the following two inputs on the tape
and what the output would be. Remember, we start at the “*” on the right-hand side
of the binary string in the ‘start’ state. Use the example in your slides to help if you
need to.
Row Current State Current Value Direction to New state to
cell to write move enter
content
1 START * * Left ADD
2 ADD 0 1 Right RETURN
3 ADD 1 0 Left CARRY
4 ADD * * Right HALT
5 CARRY 0 1 Right RETURN
6 CARRY 1 0 Left CARRY
7 CARRY * 1 Left OVERFLOW
8 OVERFLOW Ignored * Right RETURN
9 RETURN 0 0 Right RETURN
10 RETURN 1 1 Right RETURN
11 RETURN * * No Move HALT
,In both cases, the rows of the table used would be 1, 2 and 11. The output of the left
side figure would be 011 and 101 for the right side.
5. Do the same thing with a ‘1’ in every cell, i.e., *111*
In the case where every cell is a’1’, an overflow occurs and so the rows of the table
used would be: 1, 3, 6, 6, 7, 8, 10, 9, 9, 9, 11 and output 1000.
6. Do the same thing with configurations (bit patterns) ‘101’ and ‘001’
For 101, the rows used would be: 1, 3, 5, 9, 11
For 001, the rows used would be the same, i.e., : 1, 3, 5, 9, 11
7. What would be the effect on all the examples above if row 2 instead read as below,
i.e., the value to write has changed from a ‘1’ to a ‘0’
Row Current State Current Value Direction to New state to
cell to write move enter
content
2 ADD 0 0 Right RETURN
The numbers on the tape would stay as they are! There would be no change in
the tape at all.
8. If you have time, in your own words, think of one good reason why state analysis is
so important in computing today.
Testing programs often requires analysis of states – and failure to understand a
system in minute detail can be catastrophic with loss of human life. Using
analysis of states can help understand how a system works in detail – but more
importantly help to uncover ‘error’ states that would cause failure.
, CS1005 – Logic and Computation
Worksheet with Solutions: Lab 2: State Transition and Turing Machine
1. Draw a State Transition Table for the following state machine.
Solution:
2. Given the state diagram of a Turing Machine is:
Answer the following:
a) What is the Tape input language Σ
, CS1005 – Logic and Computation
b) What is the result of the computation of the machine?
Solution:
a) Σ={a,b,c}
b) The result of a computation is to replace the a’s in the input string with c’s and the c’s with
b’s.
3. Given the following Turing Machine
0/0, R 0/0, L
Y/Y, R Y/Y, L
0/X, R 1/Y, L
A B C
Y/Y, R X/X,R
D Y/Y, R
Δ/ Δ,L
Δ/ Δ,L
ACCEPT
and the following tape input:
a) Is this input legal?
b) Given this input, in which state will the machine terminate?
Solution:
a) It is not legal because the machine recognizes L=0n 1n .
b) The machine will terminate in the Reject state. Notice that the Reject State is seldom drawn,
and any transition not drawn on the machine is a Reject State.
4. Define A Turing Machine using a state diagram that recognizes the language anbn cn
Solution:
‣ Starting at left-hand of input, if current cell is empty, accept.
‣ Otherwise, if cell contains an a, change this to an X and move right looking for a corresponding b.
‣ If b is found, change it to a Y and move right looking for a corresponding c.
