problem of turing Machine

CSCI2115Assignment 10
Instructor: Alex Brodsky
Due: 11:59, Wednesday, November 30, 2022
1. Consider the problem of conputing the XOR of two binary and determining if the result is
equal to a third binary number. Suppose the input tape contains three binary numbers,
separated by $ symbols. Each binary number consists of one or more bits with one bit per
cell. E.g.,
#
0
1
1
0
$
0
1
0
1
$
0
0
1
1
#
#
(a) [5 marks] Describe a Turing Machine that accepts if the XOR of the first two binary
numbers is equal to the third binary number and rejects otherwise. Note: You just need
to describe how the TM would function as we have done in lectures. You do not need
to specify the TM in full. Feel free to describe a multi-tape Turing Machine if that is
easier.
(b) [5 marks] Describe a Random Access Machine that accepts if the XOR of the first two
binary numbers is equal to the third binary number and rejects otherwise. Note: You
just need to describe how the RAM would function as we have done in lectures.
2. Consider the problem of checking if an XOR of n binary numbers is equal to 0. The input
tape contains n binary numbers, separated by $ symbols.
(a) [5 marks] Describe a Turing Machine that accepts if the XOR of the binary numbers
is 0. Note: You just need to describe how the TM would function as we have done in
lectures. You do not need to specify the TM in full. Feel free to describe a multi-tape
Turing Machine if that is easier.
(b) [5 marks] Describe a Random Access Machine that accepts if the XOR of the binary
numbers is 0 and rejects otherwise. Note: You just need to describe how the RAM would
function as we have done in lectures.
Marking Scheme
Marking scheme for Question 1a, 1b, 2a, and 2b.
3 points
2 points
Correctness
Machine would work as
described
Description
1 points
Machine may not work
on some inputs
Reasonable
made
Description is
ciently detailed
Some key steps are missing
suffi-
attempt
0 points
No answer provided
Very poor description or
no answer provided
Submission
Assignment is due at 11:59pm of the due date. The Assignment must be submitted electronically
via Crowdmark. See the tutorial on Brightspace for how to submit assignments.
1
CSCI2115
Fall 2022
Assignment 10
Academic Integrity
Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the student named above declares that its content is their original work and that they did
not use any sources for its preparation other than the class notes, the textbook, and ones explicitly
acknowledged in the answers. Any suspected act of plagiarism will be reported to the Facultys
Academic Integrity Officer. The penalty for academic dishonesty may range from grade deduction
to expulsion from the university, in accordance with Dalhousie Universitys regulations regarding
academic integrity.
2
CSCI2115
Assignment 10
Instructor: Alex Brodsky
Due: 9:00am, Tuesday, November 30, 2021
1. Consider the problem of comparing two integers. Suppose the input tape contains two integers, separated by a $ symbol. Each integer consists of one or more digits with one digit per
cell. E.g.,
#
3
1
4
$
2
1
8
7
#
#
(a) [5 marks] Describe a Turing Machine that accepts if the first integer is less than
the second and rejects otherwise. Note: You just need to describe how the TM would
function as we have done in lectures. You do not need to specify the TM in full. Feel
free to describe a multi-tape Turing Machine if that is easier.
Answer: The Turing Machine would need to compare the two numbers,
one digit at a time. It wold also need to deal with the case of the integers
having a different number of 0’s. We will use a 2-tape TM.
Phase 0: Sweep to the right until the second number is found and copy it
to the second tape. Move both heads back to the start of both tapes.
Phase 1: Read the leftmost digit of each of the numbers and replace them
with #. If the digits are the same, repeat. If there are no more digits or if
the digits are different store whether the the digit from the first number was
less than the digit from the second number (or not) and proceed to Phase
2.
Phase 2: Sweep left both heads until one of them runs out of digits. If
the head on the first number runs out of digits first, or both heads run out
of digits at the same time and the last digit read from the first number in
Phase 1 is less than the last digit read from the second number in Phase 1,
then accept. Otherwise, reject.
(b) [5 marks] Describe a Random Access Machine that accepts if the first integer is less
than the second and rejects otherwise. Note: You just need to describe how the RAM
would function as we have done in lectures.
Answer: Our RAM will load the integers into registers and then compare
them.
Phase 1: Use a register, say r0, initialized to 0, to store the current integer
being read. Use a loop to read one digit at a time. In each iteration (i)
multiply r0 by 10, (ii) read in the next digit, (iii) add the digit read to r0.
Once we read a $ proceed to Phase 2.
Phase 2: Same as Phase but for the second number being stored in register
r1. Once we have read the number proceed to Phase 3.
Phase 3: Compare r0 and r1. If r1 is greater than r0, write a 1 to the
output tape, else write a 0.
2. Consider the problem of checking if n integers are in sorted order. The input tape contains n
integers, separated by $ symbols. Each integer consists of one or more digits with one digit
per cell.
1
CSCI2115
Fall 2021
Assignment 10
(a) [5 marks] Describe a Turing Machine that accepts if the integers are in sorted order,
i.e., for each pair of adjacent integers the first integer is less than the second, and rejects
otherwise. Note: You just need to describe how the TM would function as we have done
in lectures. You do not need to specify the TM in full. Feel free to describe a multi-tape
Turing Machine if that is easier.
Answer: We will use a 3-tape TM and the TM from Question 1a to solve
this. Tape 1 will be the input and tapes 2 and 3 will be the work tapes.
The TM will copy the first two numbers to tapes 2 and 3. It will then
compare the numbers using the algorithm described in Question 1a. If the
second number is greater than the first, the TM will move one number
forward on the input tape and repeat. If the first number is not less than
the second, the TM rejects. If the TM is out of numbers, it accepts.
(b) [5 marks] Describe a Random Access Machine that accepts if the integers are in sorted
order and rejects otherwise. Note: You just need to describe how the RAM would
function as we have done in lectures. full.
Answer: We will use the RAM from Question 1b to solve this.
The RAM will read the first two numbers into registers just like the RAM
in Question 1b. It will then compare the numbers. If the second number
not greater than the first, the RAM will write a 0 to the output tape and
halt. Otherwise, it will enter a loop where: (i) the RAM copies the register
r1 into register r0; (ii) reads in the next number from the input tape into
register r1 using the same algorithm as the RAM in Question 1b; (iii) if
register r1 is not greater than r0, the RAM writes a 0 and halts. Otherwise,
it loops to step (1). If there are no more numbers, the RAM writes a 1 and
halts.
Marking Scheme
Marking scheme for Question 1a, 1b, 2a, and 2b.
3 points
2 points
Correctness
Machine would work as
described
Description
1 points
Machine may not work
on some inputs
Reasonable
made
Description is
ciently detailed
Some key steps are missing
suffi-
attempt
0 points
No answer provided
Very poor description or
no answer provided
Submission
Assignments are due by 9:00am on the due date before class. Assignment must be submitted
electronically via Brightspace. Please submit a PDF. You can do most of your work on paper and
then scan in and submit the assignment.
Please use an appropriate app to scan in your assignment instead of just taking a
photograph of it. Photos of assignments tend to be hard to read and are much more
error-prone for the marker.
2
CSCI2115
Fall 2021
Assignment 10
Academic Integrity
Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the student named above declares that its content is their original work and that they did
not use any sources for its preparation other than the class notes, the textbook, and ones explicitly
acknowledged in the answers. Any suspected act of plagiarism will be reported to the Facultys
Academic Integrity Officer. The penalty for academic dishonesty may range from grade deduction
to expulsion from the university, in accordance with Dalhousie Universitys regulations regarding
academic integrity.
3
CSCI2115
Assignment 10
Instructor: Alex Brodsky
Due: 9:00am, Tuesday, November 30, 2021
1. Consider the problem of comparing two integers. Suppose the input tape contains two integers, separated by a $ symbol. Each integer consists of one or more digits with one digit per
cell. E.g.,
#
3
1
4
$
2
1
8
7
#
#
(a) [5 marks] Describe a Turing Machine that accepts if the first integer is less than
the second and rejects otherwise. Note: You just need to describe how the TM would
function as we have done in lectures. You do not need to specify the TM in full. Feel
free to describe a multi-tape Turing Machine if that is easier.
Answer: The Turing Machine would need to compare the two numbers,
one digit at a time. It wold also need to deal with the case of the integers
having a different number of 0’s. We will use a 2-tape TM.
Phase 0: Sweep to the right until the second number is found and copy it
to the second tape. Move both heads back to the start of both tapes.
Phase 1: Read the leftmost digit of each of the numbers and replace them
with #. If the digits are the same, repeat. If there are no more digits or if
the digits are different store whether the the digit from the first number was
less than the digit from the second number (or not) and proceed to Phase
2.
Phase 2: Sweep left both heads until one of them runs out of digits. If
the head on the first number runs out of digits first, or both heads run out
of digits at the same time and the last digit read from the first number in
Phase 1 is less than the last digit read from the second number in Phase 1,
then accept. Otherwise, reject.
(b) [5 marks] Describe a Random Access Machine that accepts if the first integer is less
than the second and rejects otherwise. Note: You just need to describe how the RAM
would function as we have done in lectures.
Answer: Our RAM will load the integers into registers and then compare
them.
Phase 1: Use a register, say r0, initialized to 0, to store the current integer
being read. Use a loop to read one digit at a time. In each iteration (i)
multiply r0 by 10, (ii) read in the next digit, (iii) add the digit read to r0.
Once we read a $ proceed to Phase 2.
Phase 2: Same as Phase but for the second number being stored in register
r1. Once we have read the number proceed to Phase 3.
Phase 3: Compare r0 and r1. If r1 is greater than r0, write a 1 to the
output tape, else write a 0.
2. Consider the problem of checking if n integers are in sorted order. The input tape contains n
integers, separated by $ symbols. Each integer consists of one or more digits with one digit
per cell.
1
CSCI2115
Fall 2021
Assignment 10
(a) [5 marks] Describe a Turing Machine that accepts if the integers are in sorted order,
i.e., for each pair of adjacent integers the first integer is less than the second, and rejects
otherwise. Note: You just need to describe how the TM would function as we have done
in lectures. You do not need to specify the TM in full. Feel free to describe a multi-tape
Turing Machine if that is easier.
Answer: We will use a 3-tape TM and the TM from Question 1a to solve
this. Tape 1 will be the input and tapes 2 and 3 will be the work tapes.
The TM will copy the first two numbers to tapes 2 and 3. It will then
compare the numbers using the algorithm described in Question 1a. If the
second number is greater than the first, the TM will move one number
forward on the input tape and repeat. If the first number is not less than
the second, the TM rejects. If the TM is out of numbers, it accepts.
(b) [5 marks] Describe a Random Access Machine that accepts if the integers are in sorted
order and rejects otherwise. Note: You just need to describe how the RAM would
function as we have done in lectures. full.
Answer: We will use the RAM from Question 1b to solve this.
The RAM will read the first two numbers into registers just like the RAM
in Question 1b. It will then compare the numbers. If the second number
not greater than the first, the RAM will write a 0 to the output tape and
halt. Otherwise, it will enter a loop where: (i) the RAM copies the register
r1 into register r0; (ii) reads in the next number from the input tape into
register r1 using the same algorithm as the RAM in Question 1b; (iii) if
register r1 is not greater than r0, the RAM writes a 0 and halts. Otherwise,
it loops to step (1). If there are no more numbers, the RAM writes a 1 and
halts.
Marking Scheme
Marking scheme for Question 1a, 1b, 2a, and 2b.
3 points
2 points
Correctness
Machine would work as
described
Description
1 points
Machine may not work
on some inputs
Reasonable
made
Description is
ciently detailed
Some key steps are missing
suffi-
attempt
0 points
No answer provided
Very poor description or
no answer provided
Submission
Assignments are due by 9:00am on the due date before class. Assignment must be submitted
electronically via Brightspace. Please submit a PDF. You can do most of your work on paper and
then scan in and submit the assignment.
Please use an appropriate app to scan in your assignment instead of just taking a
photograph of it. Photos of assignments tend to be hard to read and are much more
error-prone for the marker.
2
CSCI2115
Fall 2021
Assignment 10
Academic Integrity
Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the student named above declares that its content is their original work and that they did
not use any sources for its preparation other than the class notes, the textbook, and ones explicitly
acknowledged in the answers. Any suspected act of plagiarism will be reported to the Facultys
Academic Integrity Officer. The penalty for academic dishonesty may range from grade deduction
to expulsion from the university, in accordance with Dalhousie Universitys regulations regarding
academic integrity.
3