# Exercises: # • Modify the machine to check if n-1 is divisible by 3, where n is the input. That is, accept the binary of 1, 4, 7, 10, 23 %23 Hint: this can be done without modifying the tape (no 'write'). - # • Round the number up to the nearest multiple of 3. Hint: do one pass right to find the remainder, then another pass #3 left
# Exercises: # • Modify the machine to check if n-1 is divisible by 3, where n is the input. That is, accept the binary of 1, 4, 7, 10, 23 %23 Hint: this can be done without modifying the tape (no 'write'). - # • Round the number up to the nearest multiple of 3. Hint: do one pass right to find the remainder, then another pass #3 left
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Turing machine
Transcribed Image Text:1 # Checks if a binary number is divisible by 3.
2 input: '10011' # try '1111' (15), '10100' (20), '111001' (57)
3 blank: .
# How it works:
4
6- # Consider neading a binary number, say 10011 (19),
# from left to right one digit at a time.
8.
7
# Each time a digit is read, the new value equals the new digit
9.
# plus the old value shifted left one place (multiplied by 2).
10
11 - # Digits Value
12
23
13
14
15
#3
# 1
# 10
16
# 100
4
# 1001
18
17
# 10011
19
19
20 - # Now instead of tracking the entire number, just track the remainder.
21
# It works the same way.
22
start state: q0
23 - table:
24-
q0:
0: R
1: {R: q1} # 2*0 + 1 = 1
# 2*0 + 0 -0
25
26
27
: {R: accept}
28 -
29
30
q1:
0: {R: q2} # 2*1 + 0 = 2
1: {R: q0} # 2*1 + 1 - 3
q2:
0: {R: q1} # 2*2 + 0 =4
1: {R: q2} # 2*2 + 1 =5
ассеpt:
31-
32
33
34
35
36
# Exercises:
38
39 - # • Modify the machine to check if n-1 is divisible by 3,
#3
37
40
where n is the input. That is, accept the binary of 1, 4, 7, 10,
...
41
Hint: this can be done without modifying the tape (no 'write').
2#3
42
43 - # • Round the number up to the nearest multiple of 3.
#3
Hint: do one pass right to find the remainder, then another pass
left
44
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY