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
