8 Connections and Open Questions

Alternative Encodings.

While we use right-to-left binary encoding, other choices (left-to-right, different bases, position-aware encodings) would yield different sequences and characterizations. Understanding the relationships between these encodings may reveal invariant properties of the underlying computation.

Complexity of Generation.

Among all TMs that can generate a given finite binary step sequence, what is the minimum number of states required? This question connects the descriptive complexity of the sequence to the state complexity of the generating machine.