Is Cantor's Theorem Automatic?

摘要

A regular language L together with a binary relation ≤_L on L is an automatic presentation of the rationals iff (L,≤_L) is isomorphic to (Q,≤) and ≤_L can be accepted by a synchronous two-tape automaton. An automorphism of (L,≤_L) is automatic iff it can be computed by a synchronous two-tape automaton. We show (1) that the canonical presentation from [5] is automatic-homogeneous (any tuple can be mapped to any other tuple by an automatic automorphism), (2) that there are presentations which are not automatic-homogeneous, and (3) that there are automatic linear orders that are not isomorphic to any regular subset of the canonical presentation. This last result disproves a conjecture from [5].