[Solved] MLCS Homework3-Computable, c.e. and not computable Problems

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

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

Exercise 1.1. Write down the sentence F_M associated as in the proof of Trakhtenbrot and Churchs Theorems to the Turing Machine described below, where the alphabet is {0,1}, # is the blank symbol, q₀ the intiial state, q_r the reject state. The machine M has the following transition function:

(q₀,0) 7 (q_r,#,+1)

(q₀,1) 7 (q₀,#,+1)

(q₀,#) 7 (q₀,#,+1)

Describe the canonical model of the sentence F_M.

Exercise 1.2. Show by informal arguments the following points.

• If L₁ L₂ is not computable and L₂ is computable then L₁ is not computable.
• If L₁ L₂ is not computable and L₂ is computable then L₁ is not computable.
• If L₁ L₂ is not computable and L₂ is computable then L₁ is not computable.
• If L₂ L₁ is not computable and L₂ is computable then L₁ is not computable.
• If L₁ and L₂ are computably enumerable then L₁ L₂ and L₁ L₂ 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.

• {(i,j) : given j as input, M_i never moves left}.
• {(i,j) : during the computation on j, M_i moves left three times in a row}.

(Hint: you can assume that the Halting Set {(i,j) : M_i(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. Lets call a formula a formula in Universal Second Order Logic if it has the form R₁ R_nF, 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 R₁,,R_n 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,,n1}. 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,n1}{0,1,,n1}. To use these pairs to count up to n² we identify each pair with its position in the lexicographic ordering induced by S on the set of pairs. Define a formula S²(x₁,x₂,y₁,y₂) that expresses that the number represented by (x₁,x₂) is the immediate predecessor of the number coded by (y₁,y₂).

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].

(Hint: Use some inexpressibility result we proved).