Affiliations: Sobolev Institute of Mathematics, Novosibirsk, Russia and Novosibirsk State University, Novosibirsk, Russia. [email protected]
Correspondence:
[*]
Address for correspondence: Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090, Novosibirsk, Russia.
Note: [*] The author was partially supported by the grant of the President of the Russian Federation (No. MK-1214.2019.1). The author is grateful to Sergey Goncharov and Stanislav Speranski for helpful discussions.
Abstract: We investigate computability-theoretic properties of contact algebras. These structures were introduced by Dimov and Vakarelov in [Fundam. Inform. 74 (2006), 209–249] as an axiomatization for the region-based theory of space. We prove that the class of countable contact algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. This means that the class of contact algebras is very rich from the computability-theoretic point of view. As an application of our result, we show that the ∏3-theory of contact algebras is hereditarily undecidable. This is a refinement of the result of Koppelberg, Düntsch, and Winter [Algebra Univers., 68 (2012), 353–366].
