Standard alphabets beyond equality atoms

In this post, I try to give a characterization of standard alphabets (i.e. alphabets where Turing machines determinize) which works for many choices of atoms.

Theorem. Assume that the atoms are oligomorphic, have a decidable first-order theory, and for every $n$ one can compute the number of orbits of $n$ -tuples of atoms. The following conditions are equivalent for every orbit finite set $B$ .

Turing machines over input alphabet $B$ determinize
There exists a function $f :B^* \to \set{0,1}^*$ which is computable by a deterministic Turing machine, and such that two words are in the same orbit if and only if they have the same image under $f$ .

Proof. I assume that $B$ is equivariant, and the Turing machines in items 1 and 2 are also equivariant. Let us begin by introducing some notation. For an equivariant orbit-finite set $B$ , define a representation to be any equivariant partial function

$r : atoms^k \to B.$

Every equivariant orbit-finite set has at least one representation. By oligomoprhism, the kernel of $r$ , which is an equivariant parital equivalence relation on $k$ -tuples of atoms, is first-order definable, by a formula with $2k$ variables. For $n$ , let

$r_n : atoms^{nk} \to B^n$

be the lifting of $r$ to tuples of atoms of length $nk$ , obtained by applying $r$ to the first $k$ atoms of the input, then the next $k$ atoms of the input, and so on $n$ times. Again, the kernel of $f_n$ is first-order definable, and the formula can be computed given $n$ .

Definition. Let $r$ be a representation of $B$ . Define a $r$ –deatomization of a word $w \in B^n$ to be a first-order formula defining an orbit of $atoms^{nk}$ which cotnains some word $v$ such that $r_n(v)=w$ .

Under some representation of first-order logic formulas as bit strings, one can see an $r$ -representation as a bit string. Define the canonical $r$ -deatomization to be function

$[r] : B^* \to \set{0,1}^*$

which maps a word to its lexicographically smallest $r$ -deatomization. We claim that conditions 1 and 2 in the theorem are equivalent to

3. for some (equivalently, every) representation $r$ , the canonical $r$ -deatomization $[r] : B^* \to \set{0,1}$ is computed by some deterministic Turing machine.

To prove the equivalence of 1,2 and 3, we use the following lemma, which lifts computation of Turing machines from words with atoms to their deatomized versions.

Lemma. Let $B_1,B_2$ be orbit-finite sets with atoms, with representations $r_1,r_2$ . Then for every relation

$g \subseteq B_1^* \times B_2^*$

computed by a (possibly nondeterministic) Turing machine, there exists a relation

$[g] \subseteq \set{0,1}^* \times \set{0,1}^*$

computed by a (possibly nondeterministic) Turing machine, such that $[g] \circ [r_1] = [r_2] \circ g$ . Diagrammatically

$\xymatrix{ B_1^* \ar[r]^g \ar[d]^{[r_1]} & B_2^* \ar[d]^{[r_2]} \\ \set{0,1}^* \ar[r]^{[g]} & \set{0,1}^* }$

Proof of the lemma. By simulating the logic of the Turing machine. The proof uses the assumptions on decidability of first-order theory and computing the number of orbits. $\Box$

1 implies 2. It is straightforward to see that a nondeterministic Turing machine can compute the canonical deatomization $[r]$ . Assumption 1 says that machines can be determinized, and therefore there is a deterministic Turing machine computing $[r]$ . This proves 3, which immediately implies 2.

2 implies 3. Suppose that $f : B^* \to \set{0,1}^*$ is computed by some deterministic Turing machine. Let

$[f] : \set{0,1}^* \to \set{0,1}^*$

be obtained by applying the lemma to $f$ . To compute $[r](w)$ , we do the following: enumerate all possible strings in $v \in \set{0,1}^*$ until finding a string such that $[f](v)=f(w)$ . This string is $[r](w)$ .

3 implies 1. Using the lemma, the whole computation can be done without atoms.

This completes the proof of the theorem.

Question: Are conditions 1,2 and 3 equivalent to the following condition 4?

4. There is a deterministic Turing machine recognizing

$L^B_{iso} = \{wv \in B^* : \mbox{$w$ and $v$ are in the same orbit}\}$

In general, 2 implies 4, because to test if $w$ and $v$ are in the same orbit, it suffices to check if they have the same image under $f$ . For the converse implication, from 4 to 2, some kind of fresh-elimination procedure would be useful.

Atompress

Standard alphabets beyond equality atoms

Leave a Reply Cancel reply

Computation with atoms