First-order approximation of algorithmic theories
type: Item
instance of: scholarly article
title: First-order approximation of algorithmic theories
zbMATH Open document ID: 0632.68036
DOI: 10.1016/0304-3975(86)90097-6
author: Wiktor Dańko
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03C07
zbMATH DE Number: 4028892
zbMATH Keywords: algorithmic logic
zbMATH Keywords: model theory
zbMATH Keywords: algorithmic theory
zbMATH Keywords: first-order language
zbMATH Keywords: coding diverging computations
reviewed by: John-Jules Meyer
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90097-6
OpenAlex ID: W2038113785
cites work: Q4130978
cites work: Q4130976
cites work: Q4167572
cites work: Q3900030
cites work: Q4745808
cites work: Q3727957
cites work: Q3727958
cites work: First-order dynamic logic
cites work: Q4164784
cites work: Q3247504
cites work: Q5734410
cites work: Q5573961
cites work: Q3883461
cites work: Q4168060
cites work: Q3883471
description: scientific article; zbMATH DE number 4028892