Bi-immunity over different size alphabets

In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a constant to sequences over the alphabet of all natural numbers, which may or may not be bounded by a recursive function, and relate them to the Turing degrees in which they can occur.

Authors

• Cristian S. Calude
• Karen Frilya Celine National University of Singapore
• Ziyuan Gao
• Sanjay Jain
• Ludwig Staiger
• Frank Stephan

Keywords

• Randomness
• Immune sequence
• Bi-immune sequence
• Immune function
• Bi-immune function
• Martingale