# 计算机代写 | Computer theory

Problem 1 (TM with Undo, 15 points). A TM with undo is the same as a basic single-tape TM, except in one computational step it is also allowed to perform the following “undo” action: Return the head to where it was before the most recent transition, and replace the symbol under the head with whatever was there previously. The state of the TM’s ﬁnite control should remain the same.

For example, suppose a TM with undo starts in conﬁguration 8675p409. If its transition function speciﬁes(p,4) = (q,3,R), then the next conﬁguration will be 86753q09. If its transition function then speciﬁes(q,0) = U (where U stands for “undo”), then the next conﬁguration will be 8675q409.

Things get more interesting when the TM with undo is asked to do multiple undos in succession, or interleave them with normal transitions. In these cases, the machine must be able to undo all of the normal transitions in the correct order – from most recent to least recent. If there is no instruction left to undo, the machine will stay in the same conﬁguration.

For example, suppose the transition function of a TM with undo speciﬁes(p,0) = (p,1,R), (p,1) = (q,0,R),(q,0) = U,(q,1) = (r,0,R), and(r,0) =(r,1) = U. Then if the TM’s starting conﬁguration is p010, the next few conﬁgurations the TM with undo enters are

p010

1. (read 0, write 1, move right)

1p10

2. (read 1, write 0, move right)

10q0

3. (undo instruction 2) 1q10

4. (read 1, write 0, move right)

10r0

5. (undo instruction 4)

1r10

6. (undo instruction 1)

r010

7. (undo…but there is no instruction left to undo)

r010

Give a simulation argument, using an implementation-level description, to show that every language recognizable by a TM with undo is also Turing-recognizable.

Hint: It may be useful to maintain an explicit record of past actions in a stack. Every time the TM with undo performs a normal read/write/move transition, push a record of this action to the stack. And every time it performs an undo, pop the most recent action from the stack. How would you implement this behavior on, say, a multi-tape TM?

Problem 2 (Countability and Diagonalization, 18 points).

(a) An undirected graph is a ﬁnite set of vertices V ✓ N together with a ﬁnite set of edges

E = {{u,v}|u,v 2 V}. Show that the set G of all undirected graphs is countable. (8 points) (b) Let M be the set of all encodings of Turing machines. A TM property is a function f :

M!{0,1}. Use a diagonalization argument to show that the set of all TM properties,

P = {f | f is a TM property}, is uncountable. (10 points)

Problem 3 (Loopy TM, 17 points). Consider the following computational problem. Given a TM M, doesM loop forever on every input w?

(a) Formulate this problem as a language LTM. (3 points)

(b) Use a reduction to prove that LTM is undecidable. Make sure to explain (brieﬂy) why the TM computing your reduction is correct. (14 points)

Problem 4 (Bonus Problem). A function f : N!N is non-increasing if f(i) f(i + 1) for every

i 2 N. Sof(1) = 8,f(2) = 3,f(3) = 2,f(4) = 2,… are the ﬁrst few values of (what looks like)

a non-increasing function f. But the function g where g(1) = 5,g(2) = 6,g(3) = 4,… is not non-increasing.

Is the set NIof non-increasing functions countable or uncountable? Prove your answer.