TY - JOUR

T1 - Undecidability in some structures related to computation theory

AU - Selivanov, Victor L.

PY - 2009/2/1

Y1 - 2009/2/1

N2 - We show that many of the so called discrete weak semilattices considered earlier in a series of authors publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computation theory, we obtain several new undecidability results. This applies e.g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of k-partitions in the Baire space and ω-algebraic domains. Whenever possible, we try to determine also the exact degrees of undecidability of the theories under discussion.

AB - We show that many of the so called discrete weak semilattices considered earlier in a series of authors publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computation theory, we obtain several new undecidability results. This applies e.g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of k-partitions in the Baire space and ω-algebraic domains. Whenever possible, we try to determine also the exact degrees of undecidability of the theories under discussion.

KW - Discrete weak semilattice

KW - Partition

KW - Reducibility

KW - Semilattice

KW - Theory

KW - Undecidability

UR - http://www.scopus.com/inward/record.url?scp=59549088836&partnerID=8YFLogxK

U2 - 10.1093/logcom/exn023

DO - 10.1093/logcom/exn023

M3 - Article

AN - SCOPUS:59549088836

VL - 19

SP - 177

EP - 197

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

SN - 0955-792X

IS - 1

ER -