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