Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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)$.
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.
