Finite Model Theory, Spring 1997

Assignment 2. Due approximately Feb.24

1. Exercise 7.1.3 of Ebbinghaus and Flum (page 167).

2. Exercise 7.1.5 of Ebbinghaus and Flum (page 169). Is this trivial or subtle?

3. Show that the collection of formulas ϕ(\overline{x}, S) such that the operator F (S) = \{\overline{a} : ϕ(\overline{a}, S)\} is monotone is not recursive. See the paragraph after 7.1.6 (page 169).

4. Explain Paragraph 7.1.16 page 174, if possible.

5. Consider structures coded in way described in the proof that PTIME = FP. Suppose a class of such structures is decided in nondeterministic log space (NL). That is, the machine may have k tapes, but each has maximum length log n. Suppose |A| = n.

1. Show each configuration of M (i.e. state, tape description, head location) can be coded by a sequence of k numbers less than n.

2. Show that the ternary relation x + y = z is definable in L_{FP}(τ). (Actually it is the transitive closure of a relation defined in ⟨n, S⟩. (Hint: define x + y = w + z.)

3. Continue working in ⟨n, S⟩. Let j, w < n. Show the predicate ‘ON(w,j)’ (which means the jth term in the binary expansion of n is definable in L_{FP}(τ). (Again you can get by with transitive closure but need to fix a constant and use an existential quantifier.)

4. With this information, Next(Conf_{a}, Conf_{b}) (M moves in one step from configuation a to configuration b) is first order definable.

5. Conclude NL is contained in FP.

If necessary consult Immerman SIAM Journal of Control, 16 (1987) 760-777.

6. Prove that inflationary fixed point logic is closed under simulataneous inductions.

7. Consider a formalization of Turing machines with 3 tape symbols: 0, 1, B. Show if a language L is recognized in polynomial time by a machine M, then there is a machine M′ which recognizes L in polynomial time but never writes over a 0 or a 1.