Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Does every FOL (axiom set expressible in First Order Logic) have a corresponding Turing machine?
The proved FOL statements would be strings the Turing machine accepts.
Does every Turing machine have a FOL?
The strings the Turing machine accepts are proved by a finite set of FOL axioms.
Someone said this:
Meanwhile, FOL (unlike propositional logic) is Turing-complete in an appropriate sense
(See comments on https://math.stackexchange.com/a/3635100/187128)
Yes.
Turing himself showed that you can describe the behavior of any Turing-machine using FOL statements, and with that you can indeed show that any FOL statements a Turing-machine accepts would indeed be provable from a finite set of FOL axioms.
Going the other way around, for every finite set of FOL Axioms, you can construct a Turing machines that accepts all and only those statements provable from it. This is closely related to Godel's Completeness Theorem: it turns out there is an algorithm that cranks out all and only valid FOL statements, and thus also a Turing-machine that can do that.
