Polynomial clone reducibility (Q2436621)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Polynomial clone reducibility
scientific article

    Statements

    Polynomial clone reducibility (English)
    0 references
    0 references
    25 February 2014
    0 references
    In the paper under review, the author investigates randomness under polynomial clone reducibilities. The major result states that if \(x\) is Kurtz random and \(C_1\subseteq C_2\) are polynomial clones, then there is a \(y\) that is \(C_1\)-reducible to \(x\) but not \(C_2\).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    computability
    0 references
    algorithmic randomness
    0 references
    Turing reducibility
    0 references
    polynomial clones
    0 references
    0 references