MLCS-Homework 3 Solved

1. Computable, c.e. and not computable Problems

N.B. In the following we use (ϕi)i∈N to refer to a fixed programming system (model of computation). You can reason in terms of the one you prefer, be it Turing Machines (Mi)i∈N, the class C, Σ1-definable functions, or in terms of pseudo-code.

Exercise 1.1. Write down the sentence FM associated as in the proof of Trakhtenbrot and Church’s Theorems to the Turing Machine described below, where the alphabet is {0,1}, # is the blank symbol, q0 the intiial state, qr the reject state. The machine M has the following transition function:

                                                                               (q0,0) →7   (qr,#,+1)

(q0,1) 7→ (q0,#,+1)

(q0,#) 7→ (q0,#,+1)

Describe the canonical model of the sentence FM.

Exercise 1.2. Show by informal arguments the following points.

(1)   If L1 ∩ L2 is not computable and L2 is computable then L1 is not computable.

(2)   If L1 ∪ L2 is not computable and L2 is computable then L1 is not computable.

(3)   If L1 \ L2 is not computable and L2 is computable then L1 is not computable.

(4)   If L2 \ L1 is not computable and L2 is computable then L1 is not computable.

(5)   If L1 and L2 are computably enumerable then L1 ∪ L2 and L1 ∩ L2 are computably enumerable.

Exercise 1.3. Assume that the set {i : ϕi is a total function } is not computable. Show (by an informal argument) that the set {(i,j) : ∀n(ϕi(n) ↑ iff ϕj(n) ↑} is not computable. (The notation ↑ indicates that the function is not defined on the given input).

Exercise 1.4. Let C be a set of c.e. sets. If C is not closed under supersets, then {i : dom(ϕi) ∈ C} is not c.e. (Hint: you can assume that the set {i : ϕi(i) ↑} is not c.e.).

Exercise 1.5. Argue informally whether the following sets are computable, c.e., or not computable.

(1)   {(i,j) : given j as input, Mi never moves left}.

(2)   {(i,j) : during the computation on j, Mi moves left three times in a row}.

(Hint: you can assume that the Halting Set {(i,j) : Mi(j) accepts} is not computable).

Exercise 1.6. Show that if we define the minimalization operator by dropping the requirement that the function is defined on all values smaller than the first value on which the output is 0 then we can define some non-computable function.

More precisely, consider the class C∗ defined as the smallest calss of functions containing the initial functions and closed under composition and under the following operator of minimalization: if ψ(~x,y) is in C∗ then the function ϕ(~x) = the minimum y such that ψ(~x,y) = 0, if any; is also in C∗. Show that the class C∗ contains a non-computable function.

1

2. NP problems

Exercise 2.1. Show, by writing a formula, that the following properties are definable in Existential SecondOrder Logic over the class of finite graphs:

•    Even: the graph has an even number of elements.

•    Hamiltonian: the graph contains a cycle which visits each vertex exactly once.

•    Bipartite: the graph is bipartite.

•    Perfect Matching: the graph has a perfect matching.

Exercise 2.2. Express the transitive closure query in Existential Second-Order Logic: write a formula T(x,y) that holds of two elements of a finite structure if and only if they are in the transitive closure of a given binary relation R.

Express the Unreachability query in Existential Second-Order Logic: the Unreachability query, relative to a relation symbol R singles out the pairs (a,b) such that there is not R-path from a to b. Does the negation of your sentence express Reachability?

Exercise 2.3. Let’s call a formula a formula in Universal Second Order Logic if it has the form ∀R1 ...∀RnF, where F is a first-order formula. Show that the property of being a connected graph is expressible by a

Universal Second Order formula using only quantification on relations R1,...,Rn of arity 1. (Hint: start by defining the negation of connectivity).

Exercise 2.4. Let S be a binary relation symbol. Assume that S is interpreted as the standard linear order on the set {0,1,...,n−1}. Define two formulas F(x) and L(x) expressing, respectively, that x is the first and that x is the last element of the ordering. Consider the set of pairs (i,j) ∈ {0,1...,n−1}×{0,1,...,n−1}. To use these pairs to count up to n2 we identify each pair with its position in the lexicographic ordering induced by S on the set of pairs. Define a formula S2(x1,x2,y1,y2) that expresses that the number represented by (x1,x2) is the immediate predecessor of the number coded by (y1,y2).

Discuss how to generalize your answer to the lexicographic ordering on k tuples, for k ≥ 2.

Exercise 2.5. Show that there is no formula F(x,y,z) in first-order logic in the language of orders such that for all n, if a,b,c < n then a + b = c if and only if ({0,1,...,n − 1},<) |= F[a,b,c].