-
16Dependence relations in computably rigid computable vector spacesAnnals of Pure and Applied Logic 132 (1): 97-108. 2005.We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 570–583 ; 379–387 ]
-
16Turing degrees of hypersimple relations on computable structuresAnnals of Pure and Applied Logic 121 (2-3): 209-226. 2003.Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose d…Read more
-
15Regular relations and the quantifier “there exist uncountably many”Mathematical Logic Quarterly 29 (3): 151-161. 1983.
-
15Some effects of Ash–Nerode and other decidability conditions on degree spectraAnnals of Pure and Applied Logic 55 (1): 51-65. 1991.With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is intrinsically r.e. if and only if a natural recursive-syntacti…Read more
-
13Review: C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (review)Bulletin of Symbolic Logic 7 (3): 383-385. 2001.
-
12On the isomorphism problem for some classes of computable algebraic structuresArchive for Mathematical Logic 61 (5): 813-825. 2022.We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.
-
11Cohesive powers of structuresArchive for Mathematical Logic 1-24. forthcoming.A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the cohesive s…Read more
-
11Interpreting a Field in its Heisenberg GroupJournal of Symbolic Logic 87 (3): 1215-1230. 2022.We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Mo…Read more
-
11On Cohesive Powers of Linear OrdersJournal of Symbolic Logic 88 (3): 947-1004. 2023.Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual pre…Read more
-
8Ash C. J. and Knight J.. Computable structures and the hyperarithmetical hierarchy. Studies in logic and the foundations of mathematics, vol. 144. Elsevier, Amsterdam etc. 2000, xv + 346 pp (review)Bulletin of Symbolic Logic 7 (3): 383-385. 2001.
-
7Computable Structures and the Hyperarithmetical HierarchyBulletin of Symbolic Logic 7 (3): 383-385. 2001.
-
4Review: Sergei S. Goncharov, Countable Boolean Algebras and Decidability (review)Journal of Symbolic Logic 63 (3): 1188-1190. 1998.
-
2Logic and Algebraic Structures in Quantum Computing (edited book)Cambridge University Press. 2014.Experts in the field explore the connections across physics, quantum logic, and quantum computing.
-
George Washington UniversityRegular Faculty
Areas of Interest
Logic and Philosophy of Logic |
General Philosophy of Science |