First-order approximation of algorithmic theories

DOI10.1016/0304-3975(86)90097-6MaRDI QIDQ1095655zbMATH OpenOpenAlexFDO

Authors Wiktor Dańko

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90097-6

zbMATH Keywords

algorithmic logicalgorithmic theorycoding diverging computationsfirst-order languagemodel theory

Mathematics Subject Classification ID

Logic in computer science (03B70) Basic properties of first-order languages and structures (03C07) Abstract data types; algebraic specification (68Q65)

Review text

Relations are investigated between an algorithmic theory and its first- order translation in which sorts of variables for natural numbers and objects for the coding of computations are added. In particular it is investigated what properties of the original algorithmic theory are preserved by the translation to a first-order language. It appears that equivalence (of theories), decidability, completeness and \(\aleph_ 0\)- categoricity are not preserved by this translation. It is also studied whether every model of the first-order translation of an algorithmic theory has a submodel with standard natural numbers (thus removing the representations of nonstandard computations). It is shown that, in general, the answer to this question is negative. Finally, a method of coding diverging computations is suggested.

Recommendations

• scientific article; zbMATH DE number 23020
• scientific article; zbMATH DE number 3858395
• Elementary approximation theory
• First order theories for partial models
• scientific article; zbMATH DE number 3892594

Cites work

• First-order dynamic logic
• scientific article; zbMATH DE number 3131480 (Why is no real title available?)
• scientific article; zbMATH DE number 3959378 (Why is no real title available?)
• scientific article; zbMATH DE number 3959379 (Why is no real title available?)
• scientific article; zbMATH DE number 3688681 (Why is no real title available?)
• scientific article; zbMATH DE number 3688691 (Why is no real title available?)
• scientific article; zbMATH DE number 3708360 (Why is no real title available?)
• scientific article; zbMATH DE number 3558938 (Why is no real title available?)
• scientific article; zbMATH DE number 3558940 (Why is no real title available?)
• scientific article; zbMATH DE number 3597842 (Why is no real title available?)
• scientific article; zbMATH DE number 3601100 (Why is no real title available?)
• scientific article; zbMATH DE number 3602669 (Why is no real title available?)
• scientific article; zbMATH DE number 3801514 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3198011 (Why is no real title available?)

Cited in

(6)

• Algorithmic problems and hierarchies of first-order languages
• Elementary approximation theory
• Algorithmic Pirogov-Sinai theory
• Towards an Axiomatization of Simple Analog Algorithms
• The collapse theorem for theories ofI-reducible algebraic systems
• A Characterization of Alternating Log Time by First Order Functional Programs

This page was built for publication: First-order approximation of algorithmic theories

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