First-order approximation of algorithmic theories (Q1095655)

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.