×

On recursively enumerable subsets of \(\mathbb{N}\) and Rees matrix semigroups over \((\mathbb{Z}_3;+)\). (English) Zbl 1005.03041

Freivalds, Rūsiņš (ed.), Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2138, 408-411 (2001).
Summary: Let \(H_3\simeq({\mathbf Z}_3;+)\) be the three-element group \(\{a, a^2,e\}\) with \(a^3-e\); \({\mathbf N}_0= {\mathbf N}\cup \{0\}\); \(L_{\langle \cdot \rangle}\) the class of all first-order formulas of the signature \(\langle \cdot \rangle\). For any recursively enumerable (r.e.) set \(K\subseteq {\mathbf N}\) we effectively define an \({\mathbf N}_0\times {\mathbf N}_0\)-matrix \(P_K\) over \(H_3\) and consider the Rees matrix semigroup \(C_K=M(H_3, {\mathbf N}_0,{\mathbf N}_0, P_K)\). The following theorem presents the main result of the paper.
Theorem. There exists a recursive mapping \({\mathbf N}\to L_{\langle \cdot\rangle}\), giving for every \(m\in {\mathbf N}\) a corresponding closed formula \(\varphi_m\in L_{ \langle \cdot\rangle}\) in such a way that for every r.e. \(K\subseteq {\mathbf N}\): \(m\in K\) iff \(\varphi_m\) is valid on \(C_K\).
Such an interpretation of the membership problem for \(K\) in the elementary theory \(T(C_K)\) enables us to estimate the complexity of \(T(C_K)\); in particular, if \(K\) is a non-recursive set then \(T(C_K)\) is undecidable.
For the entire collection see [Zbl 0969.00084].

MSC:

03D45 Theory of numerations, effectively presented structures
03D25 Recursively (computably) enumerable sets and degrees
03D35 Undecidability and degrees of sets of sentences
PDFBibTeX XMLCite