论文标题
单词问题和首席执行官
Word problems and ceers
论文作者
论文摘要
本说明解决了有关哪些船员可以通过可计算的单词问题（或简单地说是C.E.）结构（例如C.E. Semigroup，组和环）实现的问题，其中实现的含义意味着在相同的降低度中降低相同的降低度（在相同的相等关系的降低性下，通常称为“计算可降低性”的概述，或者是相同的ISOM，或者是相同的iSOMORMORMORSOMERS，或者是相同的iSOMORMORSOMORSOMOR，或者是iSOMORSORMORSORMORSORMORSOMORSOMOR，或函数），或在相同的强同构类型中（具有自然数的可计算置换引起的同构）。例如，我们观察到，每个ceer都与某些c.e的问题同构相同。 Semigroup，但是（回答Gao和Gerdes的问题）并非每个CEER都具有某些有限的半群的词句，也不是某些非周期性半群的相同降低度。我们还表明，通过Peano算术可证明的等效性提供的CEER与某些非共同和非树立和非树立的C.E.一词相同的同构类型类型相同。戒指。
This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called "computable reducibility"), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation of the natural numbers). We observe for instance that every ceer is isomorphic to the word problem of some c.e. semigroup, but (answering a question of Gao and Gerdes) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is it in the same reducibility degree of some non-periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphism type as the word problem of some non-commutative and non-Boolean c.e. ring.
