Process and truth-table characterisations of randomness

AbstractThis paper uses quick process machines to provide characterisations of computable randomness, Schnorr randomness and weak randomness. The quick process machine is a type of process machine first considered in work of Levin and Zvonkin. A new technique for building process machines and quick process machines is presented. This technique is similar to the KC theorem for prefix-free machines. Using this technique, a method of translating computable martingales to quick process machines is given. This translation forms the basis for these new randomness characterisations. Quick process machines are also used to provide characterisations of computable randomness, Schnorr randomness, and weak randomness in terms of truth-table reducibility