0017 Computational Complexity problem sheet 5.
1. Design a deterministic TM whose alphabet includes {0, 1} and adds one (in binary) to its input. If there is not enough room to fit the sum in the space of the input (i.e., the input consists of all ones), the machine should halt in the “reject” state N.
Solution: About four states needed. First scan to right till first blank, then move one left. From here, if you read a 0 write a 1, then rewind and halt. If you read a 1 then write a 0, move left and move to the new state. In this new state keep replacing 1s by 0s and moving left. But when you read a 0 then write a 1, then rewind and halt.
2. Design a TM to add two binary numbers. You may use multiple tapes. The solution to overflow can be as in the previous exercise.
Copyright By PowCoder代写 加微信 powcoder
Solution: We are going to use two tapes. First, we use a TM move which moves the second number on the first tape to the second tape, and terminates. We then move both heads to the end of the input. We proceed to rewrite the contents of the first tape, adding the contents of the second tape bit-by-bit. Note that if we read a one on both tapes, then we have to enter a “carry” state, which carries the one to the next position. If you complete the addition but end up in the carry state, this is signalled by having the TM halt in a rejecting state.
add with carry
(01, 01, LL) (10, 00, LL) (11, 11, LL) (1◃, 0◃, LS)
add w/o carry
(00, 10, LL) (0◃, 1◃, LS)
(11, 01, LL)
(σ1σ2, σ1σ2, RR) q1 (σ1⊔, σ1⊔, RS) (⊔σ2, ⊔σ2, SR)
(⊔⊔, ⊔⊔, LL)
(00, 00, LL) q2 (01, 11, LL) (10, 10, LL) (◃0, ◃0, SL)
(σ1◃, σ1◃, SS) (◃◃, ◃◃, SS)
move right until we reach ends of the tapes
(◃σ2, ◃σ2, SS) (◃◃, ◃◃, SS)
Here, the variables σ1 and σ2 implicitly quantify over the set {0, 1}. 1
Answers Not to be printed
(◃1, ◃1, SS)
3. Design a TM that multiplies two non-zero binary numbers. You may again use multiple tapes. The behaviour in case of overflow is as before.
Solution: We are going to compose a solution that uses three tapes, and makes use of the following Turing machines:
• move, which moves the second part of the input to the second tape (as used in the previous exercise).
• copy, which copies the contents of the second tape to the third.
• add, which adds the numbers on the first two tapes, writing the result on the second tape (also from the previous exercise). Recall that if there is overflow, this TM halts in a rejecting state; otherwise, it halts in an accepting state.
• dec, which decrements the number on the third tape.
• zero, which checks number on the third tape is zero. If so, it
halts in the accepting state; if not, it halts in the rejecting state. These TMs can then be composed as follows.
4. Design a TM that takes two binary numbers and returns the remainder when the first is divided by the second.
Solution: Let greater be a TM that halts and succeeds if the binary number on the first tape is strictly greater than the binary number on the second tape, and halts and fails otherwise. Let subtract be a TM that subtracts the binary number on the second tape from the binary number on the first tape. We now combine the TMs as follows:
Answers Not to be printed
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com