Universality probability of a prefix-free machine | Zendy

George Barmpalias | Zendy; David L. Dowe | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Universality probability of a prefix-free machine

Author(s) -

George Barmpalias,

David L. Dowe

Publication year - 2012

Publication title -

philosophical transactions of the royal society a mathematical physical and engineering sciences

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.074

H-Index - 169

eISSN - 1471-2962

pISSN - 1364-503X

DOI - 10.1098/rsta.2011.0319

Subject(s) - universality (dynamical systems) , prefix , turing machine , universal turing machine , mathematics , kolmogorov complexity , discrete mathematics , computer science , algorithm , philosophy , linguistics , physics , quantum mechanics , computation

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research