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:
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)