# 辅导案例-S 516

Cpt S 516 Homework # 2
Electronic Hand-in (to me) before the deadline
1. (standard) Show that L = {〈M〉 : L(M) contains word abba } is not
recursive.
2. (standard) In class, we have shown that the emptiness problem is unde-
cidable for LBAs. A LBA is simply a TM that never moves out of the first
|x| (the input portion) cells for any input word x. Now, I define a restricted
form of LBA, called jump-LBA. A jump-LBA M is a LBA such that, once it
writes on a cell, it must jump back to the beginning of the tape. Show that
the emptiness problem for jump-LBAs is undecidable.
3. (standard) Let L be a recursive language. Define L′ = {x : there is y such
that yxy ∈ L}. Show that L′ is r.e.
4. (standard) Show that if L is a recursive language, then so is Lr. (Lr is
the result of reversing each word in L)
5. (hard) In our standard model of Turing machines, the Turing tape is
one dimension and goes to infinity. Now we consider a 2-Turing machine
M that works on a two dimension tape (it is, in a 2-dimension (x, y)-plane,
x ≥ 0 ∧ y ≥ 0). M works exactly as a normal Turing machine except that
the tape head can move to the Up, to the Down, in addition to moving to
the Left and to the Right. In particular, when the head is on a boundary
cell, a move that falls off the 2-dimension tape will cause the machine to
crash. Initially, the head is at the origin and there are only finitely many
cells containing non-blank symbols. At this moment, you take a picture of
the tape, which is called an input of M . M accepts the input if M enters
a final state. The emptiness problem of M is to decide whether there is an
input accepted by M . We say that a 2-Turing machine M is read-only if
the tape is read-only (you can not change the content of any cell, even when
the cell is blank). Show that the emptiness problem of read-only 2-Turing
machines is undecidable. (yes, Undecidable!)
5. (Research. 20pt) ”Infinitely often” has been an important notion in
addressing some system properties that runs forever. Let k ≥ 0 and consider
1
an infinite sequence of vectors
V0, · · · , Vi, · · ·
Each vector Vi is a tuple of k nonnegative integers. This sequence can be un-
derstood as the observed values of a backbox systems observable nonnegative
integer variables. Consider a matrix inequality P in the form of
AX#B
where A is k by k square integer matrix, X is k-ary nonnegative integer
variables vector, and B is k-ary integers. In particular, # is a vector of
symbols in {≥,=}. We say a vector V of nonnegative intergers is P -positive
if
AV #0.
We say that the infinite sequence is P -i.o (infinitely often) if there are in-
finitely many i such that P (Vi) holds. The infinite sequence is P -positive i.o
if there are infinitely many numbers i1 < ... < ij < ...... such that P (Vij)
holds and Vij+1 − Vij is P -positive, for every j. Prove that the sequence is
P -i.o iff it is P -positive i.o.
Now, you can use the result to prove the following. Consider a graph
with an initial node and every edge is labeled is with a symbol (two edges
can share a symbol). Suppose that there are k kinds of symbols. For any
path, we can get a count vector of nonnegative integers, to count the number
of a particular symbols’s appearance on the path. For a P given in above, we
say that the path satisfies P if the count vector satisfies P . For an infinite
path on the graph, we say that it is P -i.o if there are infinitely many prefixes
each of which satisfies P . Show that it is decidable, whether a given graph
has an P -i.o infinite path.
2 Email:51zuoyejun

@gmail.com