Foundations B-Exam Spring 1995

1. Let I_{1} and I_{2} be propositional interpretations (i.e., truth assignments) on the same set AP of atomic propositions (i.e., sentence symbols). We say that I_{1} ≤ I_{2} if I_{1}(P) = true implies I_{2}(P) = true for every P ∈ AP (i.e., I_{2} is “more true than or equal to” I_{1}).

A Horn formula is a propositional formula in conjunctive normal form such that each conjunct contains at most one positive literal (a literal is an atomic proposition or a negated atomic proposition). Show that a Horn formula φ has a ≤-minimal satisfying interpretation. (Hint: Let φ be a Horn formula and let I_{1} and I_{2} be two interpretations that satisfy φ, i.e., I_{1} ⊧ φ and I_{2} ⊧ φ. Let I be an interpretation such that I(P) = true iff both I_{1}(P) = true and I_{2}(P) = true, for every atomic proposition P. Prove that I ⊧ φ.)

2. Fix a vocabulary L that consists of a single binary predicate symbol E. A sentence φ is finitely valid if it holds in all finite structures. The finite-validity problem is to determine whether a given a sentence φ is finitely valid.

Trakhtenbrot’s Theorem says that the validity problem for sentences is undecidable. Show that Trakhtenbrot’s Theorem implies that finite validity is not recursively enumerable. What can you deduce from this about the possibility of finding a sound and complete formal system for finite validity?

3. Let Σ_{1} and Σ_{2} be sets of sentence such that there is no structure A that is a model of both Σ_{1} and Σ_{2}. Use the Compactness Theorem to show that there is sentence α such that Σ_{1} ⊧ α and Σ_{2} ⊧ ¬α.

4. Let R be a regular language and let w_{1}, w_{2}, ⋯, w_{i}, ⋯ be an enumeration of all elements of R such that |w_{i}| ≤ |w_{i+1}| for all i ≥ 1. Prove that there exists a constant c such that |w_{i+1}| − |w_{i}| ≤ c for all i ≥ 1.

5. Let L = \{w ∈ \{0, 1\}^{∗} | w = xx′, |x| = |x′|, and x′ ≠ \overline{x}\}, where \overline{x} is the string obtained from x be reversing all bits. For instance, if x = 01000 then \overline{x} = 10111. Prove that L is a context-free language.

6. Which of the following problems about Turing machines are decidable, and which are undecidable? Justify your answers carefully.

(a) To determine, given a Turing machine M, whether there exists a string w such that M halts on input w.

(b) To determine, given a Turing machine M and an alphabet symbol a, whether M ever writes a on its tape when started on an empty tape.

Solutions

1. Let φ be a Horn formula and let I_{1} and I_{2} be two interpretations that satisfy φ, i.e., I_{1} ⊧ φ and I_{2} ⊧ φ. Let I be an interpretation, denoted I_{1} ⊓ I_{2}, such that I(P) = true iff both I_{1}(P) = true and I_{2}(P) = true, for every atomic proposition P. Note that I ≤ I_{1} and I ≤ I_{2}.

Claim: I ⊧ φ.

Proof: Consider a conjunct α of φ. There are 3 cases to consider:

(a) α is a positive literal P. In this case, we have that I_{1}(P) = I_{2}(P) = true, so I(P) = true, and I ⊧ α.

(b) α is a disjunction ¬P_{1} ∨ ⋯ ∨ ¬P_{k} of negative literals, k ≥ 1. Since I_{1} ⊧ α, we must have I_{1}(P_{j}) = false for some 1 ≤ j ≤ k. Thus, I(P_{j}) = false, and I ⊧ α.

(c) α is a disjunction ¬P_{1} ∨ ⋯ ∨ ¬P_{k} ∨ Q with precisely one positive literal, k ≥ 1. Since I_{1} ⊧ α and I_{2} ⊧ α, we either have that I_{1}(Q) = I_{2}(Q) = true or I_{1}(P_{j}) = false for some 1 ≤ j ≤ k. In the former case we have that I(Q) = true and in the latter case we have that I(P_{j}) = false. In either case I ⊧ α.

Take M = {I : I ⊧ φ} to be the set of interpretations of φ and let J = ⊓M. By the claim above we have that J ⊧ φ and by the observation above J is ≤-minimal.

2. Let us say that a sentence φ is finitely satisfiable if it holds in some finite structures. The finite-satisfiability problem is to determine whether a given sentence φ is finitely satisfiable.

The finite-satisfiability problem is recursively enumerable. To find if a given sentence is finitely satisfiable enumerate all finite structures and check whether they satisfy the given sentence.

A sentence φ is finitely valid iff ¬φ is not finitely satisfiable. If finite validity were recursively enumerable, then it would be decidable, contradicting Trakhtenbrot’s Theorem. To check whether φ is finitely valid or not, we will enumerate in parallel all finitely valid sentences and all finitely satisfiable sentence. Ultimately either φ will show up in the enumeration of finitely valid sentences or ¬φ will show up in the enumeration of finitely satisfiable sentences.

If there is a sound and complete formal system for finite validity, then a sentence φ is finitely valid precisely when it is provable in the system. But then finite validity is recursively enumerable, since one can simply enumerate all proofs and see whether any of them constitute a proof of φ.

3. By assumption Σ_{1} ∪ Σ_{2} is unsatisfiable. By the Compactness Theorem, there are finite subsets Σ′_{1} ⊆ Σ_{1} and Σ′_{2} ⊆ Σ_{2}, such Σ′_{1} ∪ Σ′_{2} is unsatisfiable. Clearly, Σ′_{1} ∪ Σ_{2} is also unsatisfiable. Let α be ⋀ Σ′_{1}. Since Σ′_{1} ⊆ Σ_{1}, clearly Σ_{1} ⊧ α. Also, since Σ′_{1} ∪ Σ_{2} is unsatisfiable, Σ_{2} ∪ {α} is also unsatisfiable, and consequently Σ_{2} ⊧ ¬α.

4. We will use the Pumping Lemma. Let F be a finite automaton that accepts R and let n be the number of states of F. If no string in L has length greater than n, then we can choose c = n. Otherwise let x be any string in R of length greater than n. According to the Pumping Lemma there exist strings u, v, and w such that x = uvw, 1 ≤ |v| ≤ n and uv^{k}w is in R for any k ≥ 0. Thus we can choose in this case c = |v| (or c = n since |v| ≤ n).

5. We will construct a non-deterministic pushdown automaton P that accepts L. Note that L consists of all strings of even length that are not of the form x | x.

Let w be any string of length 2n. To check whether w ∈ L P will, essentially, try to ”guess” a pair of symbols α and β from w such that (i) if k and l are the positions of α and β in w then l = n + k, and (ii) α = β . This will imply that w is not of the form xx′.

On input w, P reads the symbols of w and pushes them onto the stack for some (non-deterministically chosen) number of steps. Then P stores the next, say k-th, symbol of w in its finite memory. Next P reads k more symbols of w popping at each step an element from its stack until the stack is emptied. Once again, P pushes a number of symbols of w (say l − 1) onto its stack and compares the l-th symbol with the one stored in its finite memory. If the two symbols are different then P has no next move and dies. If the symbols are the same, then P checks if there are exactly l more symbols left in w by popping off symbols from its stack. If there are more or less than l symbols left, then P has no next move. If the remaining symbols are exactly l, then P accepts w.

It is straightforward to check that, if P accepts w, then w has 2(k + l) symbols and that the two symbols that P has compared are on positions k and 2k + l = n + k.

6. (a) Undecidable. We will show this by a reduction from the halting problem. Assume that the problem were decidable and let A be an algorithm that determines whether a given arbitrary TM halts on any input. Let M be an arbitrary TM and w be any string over the alphabet of M. Then we can check if M halts on input w by the following algorithm. We construct a TM M′ that ignores its own input and simulates M on w. By definition, M′ halts on any input, iff M halts on w, and M′ halts on no input iff M does not halt on w. Then we can use A to determine whether M′ halts on any input: if yes, then M halts on w, if not, then M does not halt on w. This is a contradiction since the halting problem is undecidable.

(b) Undecidable. We will prove this by a reduction from the membership problem. (We can use the halting problem as well.)

Assume that the problem were decidable and let B be an algorithm that determines whether a given arbitrary TM ever writes a specified alphabet symbol on its tape. Then, given any string w, we can check whether M accepts w as follows. Define a new TM M′ by extending M’s alphabet by a new symbol z and changing M’s moves so that each time M accepts and halts, M′ first writes z and then accepts and halts. Then we can determine if M accepts w by checking (using B) if M′ writes z on its tape.