[32] Show that there exists an immune set I (a set without an infinite computably enumerable subset, for instance the complement of a set B as in Theorem 2.7.1, Item (iii)), such that there is a probabilistic Turing machine that computes the characteristic function of some infinite subset of I.

Comments. Hint: use Theorems 2.5.5, 2.7.1, and the following framework. A probabilistic machine is just like a deterministic machine except that at some steps there are several actions (instead of a single action)

that the machine can perform with given probabilities. For simplicity assume that there are exactly two possible actions, each with probability 1 2 . (That is, at each such choice the machine flips a coin.) That a probabilistic machine computes a function φ with probability p means that the machine with input x halts with output φ(x) with probability p. We usually assume p > 1 2 . It can be shown that a machine with any value p between zero and one can be simulated by a machine with value p close to one. It turns out that φ is computable by a probabilistic machine iff φ is partial computable [K. de Leeuw, et al., pp. 183–212 in:
Automata Studies, C.E. Shannon and J. McCarthy, eds., Princeton Univ.
Press, 1956]. This result is often interpreted as showing that probabilistic machines cannot perform tasks that are impossible for deterministic machines. iHowever, a task may not consist only in finding an unambiguous value, but may consist in finding some value out of a set of possible values. In this form there are obviously tasks that deterministic machines cannot do that probabilistic machines can do, such as the construction of an incomputable sequence or to output the characteristic function of some infinite subset of a fixed immune set. The probabilistic machine computes such a characteristic sequence or set if it outputs the sequence or set with positive probability. Source: [A.K. Zvonkin and L.A. Levin, Russ. Math. Surv., 25:6(1970), 83–124], attributed to J.M. Barzdins.