We first provide a framework to formalise infinite sequences of qubits as states of a suitable C* algebra. Thereafter we introduce an analog of Martin-Löf's notion. We show that for classical bit sequences the two notions coincide. We also discuss quantum Kolmogorov complexity for finite sequences of qubits and its relationship to quantum Martin-Löf randomness. Finally we consider an effective version of the Shannon-McMillan-Breiman theorem in the quantum setting.
This is joint work with Volkher Scholz. Paper available at https://arxiv.org/abs/1709.08422.
In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on punctual equivalence relations, i.e., primitive recursive equivalence relations with domain ω. We show that Peq has much structure, being a dense distributive lattice. This contrasts with all other known degree structures on equivalence relations. Finally, we use our analysis to investigate the online content of computably categorical equivalence structures and prove many elementary differences.
This is joint work with Nikolay Bazhenov, Keng Meng Ng, and Andrea Sorbi.