Some Turing-complete extensions of first-order logic

MaRDI QIDQ4995355zbMATH OpenFDO

Authors Antti Kuusisto

Publication date 24 June 2021

Full work available at URL https://arxiv.org/abs/1405.1715, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2014.4

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Classical first-order logic (03B10) Turing machines and related notions (03D10)

Abstract: We introduce a natural Turing-complete extension of first-order logic FO. The extension adds two novel features to FO. The first one of these is the capacity to add new points to models and new tuples to relations. The second one is the possibility of recursive looping when a formula is evaluated using a semantic game. We first define a game-theoretic semantics for the logic and then prove that the expressive power of the logic corresponds in a canonical way to the recognition capacity of Turing machines. Finally, we show how to incorporate generalized quantifiers into the logic and argue for a highly natural connection between oracles and generalized quantifiers.

Recommendations

• The logic of Turing progressions
• Fixed-point extensions of first-order logic
• The expressive power of fixed-point logic with counting
• Computing with first-order logic
• scientific article; zbMATH DE number 4008383

Cited in

(9)

• A PSPACE-complete first-order fragment of computability logic
• Bounded game-theoretic semantics for modal mu-calculus
• scientific article; zbMATH DE number 7655660 (Why is no real title available?)
• scientific article; zbMATH DE number 824731 (Why is no real title available?)
• The logic of Turing progressions
• scientific article; zbMATH DE number 5238362 (Why is no real title available?)
• Uniform proofs of standard completeness for extensions of first-order MTL
• scientific article; zbMATH DE number 7455742 (Why is no real title available?)
• An expansion of first-order Belnap-Dunn logic

This page was built for publication: Some Turing-complete extensions of first-order logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4995355)