Turing machine computations in finitely axiomatizable theories
type: Item
instance of: scholarly article
title: Turing machine computations in finitely axiomatizable theories
zbMATH Open document ID: 0567.03014
DOI: 10.1007/BF01980636
published in: Algebra and Logic
publication date: 1983-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/187188
review text: In this paper we describe a general method for interpreting how Turing machines perform computations in finitely axiomatizable theories. The method can be used to construct finitely axiomatizable theories whose properties are determined by Turing machine computations. This method is used to prove that the Lindenbaum Boolean algebra for any recursively enumerable theory \({\mathcal T}\) is recursively isomorphic to the Lindenbaum algebra of a suitable finitely axiomatizable theory \({\mathcal F}\). In addition, the axiom system of the theory \({\mathcal F}\) and the recursive isomorphism of the Boolean algebras \({\mathcal T}\) and \({\mathcal F}\) can be found uniformly with respect to a recursively enumerable index for the axiom system of \({\mathcal T}\). This solves a problem due to \textit{W. Hanf} [Theory of models, Proc. 1963 Int. Symp. Berkeley, 132-145 (1965; Zbl 0166.258)], given as No.22 in H. Friedman's list. \textit{W. Hanf} announced the solution of this problem in Bull. Am. Math. Soc. 81, 587-589 (1975; Zbl 0324.02044) but no proof was ever published. We then use the above method of interpretation to study the properties of simple models. We construct a finitely axiomatizable complete theory possessing a nonconstructivizable simple model, thereby solving a problem posed by \textit{L. Harrington} [J. Symb. Logic 39, 305-309 (1974; Zbl 0332.02055)]. In Section 7 we estimate the complexity of some classes of formulas. The interpretations are based on the author's construction of a complete finitely axiomatizable superstable theory. The models for this theory can be represented as planes on which Turing machines can operate.
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 3904570
zbMATH Keywords: complexity of classes of formulas
zbMATH Keywords: recursively enumerable theory
zbMATH Keywords: Lindenbaum algebra
zbMATH Keywords: properties of simple models
zbMATH Keywords: superstable theory
author: Mikhaĭl G. Peretyat'kin
MaRDI profile type: Publication
cites work: Some aspects of generalized computability
cites work: Q3271835
cites work: An application of games to the completeness problem for formalized theories
cites work: Hierarchies of Boolean algebras
cites work: One hundred and two problems in mathematical logic
cites work: Q5551141
cites work: The Boolean algebra of logic
cites work: Recursively presentable prime models
cites work: On some conjectures connected with complete sentences
OpenAlex ID: W2331179602
description: scientific article; zbMATH DE number 3904570