# Turing Machines and Logic

It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages.

Is there a logic over words (perhaps a nth order logic) such that it and turing machines can express the same set of languages?

I'm aware of other turing machine equivalents (in some sense) such as lambda calculus.

• Maybe computable functions? en.wikipedia.org/wiki/Computable_function
– a3nm
Mar 11 at 15:55
• @a3nm Is that something we could call a "logic" like first order logic? Mar 11 at 16:33

Since Turing machines have three options (accept, reject, not halt), you have a few options as to what class of languages correspond to Turing machines. The recursively enumerable sets aren't closed under complement, so your best bet is to look at recursive sets.

The recursive sets, however, aren't closed under projection. Suppose you had a correspondence between logical formulas in some language with $$n$$ free variables and Turing machines that always halted that take in $$n$$ inputs.

Consider the always-halting Turing machine $$T$$ that takes in two inputs $$m,n$$ and determines if the $$n$$th Turing machine halts in $$m$$ steps. By our supposed correspondence, this corresponds to a formula $$\phi(m,n)$$ in our logic. Then there also must be an always-halting Turing machine corresponding to $$\exists m: \phi(m,n)$$. That is, an always-halting Turing machine that takes in an $$n$$ and determines if the $$n$$th Turing machine ever halts. This contradicts the halting problem.

I consider this to rule out any proper logic equivalent to the Turing Machines. On the other hand, there are nice subsets of logics that are equivalent to the Turing Machines. For instance, by the negative result to Hilbert's Tenth Problem, the recursively enumerable sets are expressively equivalent to the existence of solutions to Diophantine equations. That is, the recursively enumerable subsets of $$\mathbb{N}^m$$ are exactly those that satisfy formulas of the form $$\phi(y_1,\ldots,y_m) \equiv \exists x_1: \cdots \exists x_n: \phi(x_1,\ldots,x_n, y_1, \ldots, y_m)$$ where $$\phi$$ is a quantifer-free formula in the first-order logic of $$(\mathbb{N},+,\cdot,0,1)$$.

• Going from "recursively enumerable sets aren't closed under complement" to "your best bet is to look at recursive sets" does not seem to be well-justified. NP is (probably) not closed under complement and yet there is a logical characterization for it, namely existential second-order logic. Mar 18 at 10:44
• Good point! I should clarify that I only mean this in the sense of ruling out full logics expressively equivalent to the recursively enumerable sets, and that the Diophantine sets are equivalent to the recursively enumerable sets. Mar 18 at 12:18

The paper Some Turing-Complete Extensions of First-Order Logic by Antti Kuusisto also provides some examples, where you enrich first-order logic with the ability to modify the input structure, and with recursion.

There is a rich field known as descriptive complexity which studies the connection between computability/complexity and logic; I highly recommend checking out Immerman's book or the summary page on his website, which gives the correspondence between computation and logic for probably all the computational classes you might be interested in (and probably others you've never heard of :) )

To answer your question, Turing-recognizable functions are equivalent in descriptive complexity terms to first order logic with existential quantification over natural numbers, that is $$\mathsf{FO}(\exists \mathbb{N})$$ which contains all formulas that start with existential quantifiers followed by some arithmetic formula, for example $$\exists x \exists y \exists z (x = y + z \land x = y \cdot z)$$ This is the same thing as Hilbert's 10th problem mentioned in TomKern's answer. It is also closely related to the arithmetic hierarchy; it's the logic $$\Sigma_1$$ near the bottom of the hierarchy.