<p>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.</p>
<p>The recursive sets, however, aren't closed under projection. Suppose you had a correspondence between logical formulas in some language with <span class="math-container">$n$</span> free variables and Turing machines that always halted that take in <span class="math-container">$n$</span> inputs.</p>
<p>Consider the always-halting Turing machine <span class="math-container">$T$</span> that takes in two inputs <span class="math-container">$m,n$</span> and determines if the <span class="math-container">$n$</span>th Turing machine halts in <span class="math-container">$m$</span> steps. By our supposed correspondence, this corresponds to a formula <span class="math-container">$\phi(m,n)$</span> in our logic. Then there also must be an always-halting Turing machine corresponding to <span class="math-container">$\exists m: \phi(m,n)$</span>. That is, an always-halting Turing machine that takes in an <span class="math-container">$n$</span> and determines if the <span class="math-container">$n$</span>th Turing machine ever halts. This contradicts the halting problem.</p>
<p>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 <span class="math-container">$\mathbb{N}^m$</span> are exactly those that satisfy formulas of the form <span class="math-container">$\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)$</span> where <span class="math-container">$\phi$</span> is a quantifer-free formula in the first-order logic of <span class="math-container">$(\mathbb{N},+,\cdot,0,1)$</span>.</p>

CC BY-SA 4.0
2023-03-18T10:44:07.140Z
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.
Reijo Jaakkola
CC BY-SA 4.0
2023-03-18T12:18:00.013Z
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.
TomKern
CC BY-SA 4.0
2023-03-11T18:29:56.003Z
2023-03-18T12:10:41.040Z
2023-03-18T12:10:41.040Z
TomKern
<p>The paper <a href="https://arxiv.org/abs/1405.1715" rel="noreferrer">Some Turing-Complete Extensions of First-Order Logic</a> by Antti Kuusisto also provides some examples, where you enrich first-order logic with the ability to modify the input structure, and with recursion.</p>

CC BY-SA 4.0
2023-03-13T18:29:36.117Z
2023-03-13T18:29:36.117Z
Denis
<p>There is a rich field known as <a href="https://people.cs.umass.edu/%7Eimmerman/book/descriptiveComplexity.html" rel="nofollow noreferrer">descriptive complexity</a> which studies the connection between computability/complexity and logic; I highly recommend checking out Immerman's book or the <a href="https://people.cs.umass.edu/%7Eimmerman/descriptive_complexity.html" rel="nofollow noreferrer">summary page on his website</a>, 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 :) )</p>
<p>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
<span class="math-container">$$
\mathsf{FO}(\exists \mathbb{N})
$$</span>
which contains all formulas that start with existential quantifiers followed by some arithmetic formula, for example
<span class="math-container">$$
\exists x \exists y \exists z (x = y + z \land x = y \cdot z)
$$</span>
This is the same thing as Hilbert's 10th problem mentioned in TomKern's answer.
It is also closely related to the <a href="https://en.wikipedia.org/wiki/Arithmetical_hierarchy" rel="nofollow noreferrer">arithmetic hierarchy</a>; it's the logic <span class="math-container">$\Sigma_1$</span> near the bottom of the hierarchy.</p>

CC BY-SA 4.0
2023-03-20T00:41:04.120Z
2023-03-20T00:55:09.823Z
2023-03-20T00:55:09.823Z
Caleb Stanford
<p>It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages.</p>
<p>Is there a logic over words (perhaps a nth order logic) such that it and turing machines can express the same set of languages?</p>
<p>I'm aware of other turing machine equivalents (in some sense) such as lambda calculus.</p>

CC BY-SA 4.0
2023-03-11T15:55:49.110Z
Maybe computable functions? https://en.wikipedia.org/wiki/Computable_function
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-03-11T16:33:32.337Z
@a3nm Is that something we could call a "logic" like first order logic?
whoisit
<lo.logic><turing-machines><equivalence>
Turing Machines and Logic
whoisit
# Turing Machines and Logic

(Asked by: username_0 on 2023-03-11)

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.

**Tags:** lo.logic, turing-machines, equivalence
> **Comments:**
> **username_1**: Maybe computable functions? https://en.wikipedia.org/wiki/Computable_function  
> **username_0**: @a3nm Is that something we could call a "logic" like first order logic?  

---

## 3 answers

### Answer by username_2 on 2023-03-11. Score: 6

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)$.

> **Comments:**
> **username_3**: 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.  
> **username_2**: 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.  

---

### Answer by username_4 on 2023-03-13. Score: 5

The paper [Some Turing-Complete Extensions of First-Order Logic](https://arxiv.org/abs/1405.1715) by Antti Kuusisto also provides some examples, where you enrich first-order logic with the ability to modify the input structure, and with recursion.


---

### Answer by username_5 on 2023-03-20. Score: 2

There is a rich field known as [descriptive complexity](https://people.cs.umass.edu/%7Eimmerman/book/descriptiveComplexity.html) which studies the connection between computability/complexity and logic; I highly recommend checking out Immerman's book or the [summary page on his website](https://people.cs.umass.edu/%7Eimmerman/descriptive_complexity.html), 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](https://en.wikipedia.org/wiki/Arithmetical_hierarchy); it's the logic $\Sigma\_1$ near the bottom of the hierarchy.


---

