Proof
Immerman 1999 provides a detailed proof of the theorem. Essentially, we use second-order existential quantifiers to arbitrarily choose a computation tableau. For every timestep, we arbitrarily choose the finite state control's state, the contents of every tape cell, and which nondeterministic choice we must make. Verifying that each timestep follows from each previous timestep can then be done with a first-order formula.
A key idea from the proof is that we can encode a linear order of length nk as a 2k-ary relation R on a universe A of size n. To achieve this, we choose a linear ordering L of A and then define R to be the lexicographical ordering of k-tuples from A with respect to L.
Read more about this topic: Fagin's Theorem
Famous quotes containing the word proof:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Right and proof are two crutches for everything bent and crooked that limps along.”
—Franz Grillparzer (1791–1872)
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)