Bi-immunity over Different Size Alphabets

Abstract

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.