Universality probability of a prefix-free machine
Copyright policy )Universality probability of a prefix-free machine
We study the notion of universality probability of a universal prefix-free machine, as introduced by C. S. Wallace. We show that it is random relative to the third iterate of the halting problem and determine its Turing degree and its place in the arithmetical hierarchy of complexity. Furthermore, we give a computational characterization of the real numbers that are universality probabilities of universal prefix-free machines.
- Chinese Academy of Sciences China (People's Republic of)
- Monash University Australia
- Monash University, Clayton campus Australia
- Institute of Software China (People's Republic of)
- State Key Laboratory of Computer Science China (People's Republic of)
universality probability, algorithmic randomness, Other Turing degree structures, Algorithmic randomness and dimension, Turing machines and related notions, Kolmogorov complexity, prefix-free complexity, Algorithmic information theory (Kolmogorov complexity, etc.)
universality probability, algorithmic randomness, Other Turing degree structures, Algorithmic randomness and dimension, Turing machines and related notions, Kolmogorov complexity, prefix-free complexity, Algorithmic information theory (Kolmogorov complexity, etc.)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!