Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/25920

Polynomial-clone reducibility

File SizeFormat 
MA_2010_Culver.pdf278.91 kBAdobe PDFView/Open

Item Summary

Title: Polynomial-clone reducibility
Authors: Culver, Quinn
Advisor: Kjos-Hanssen, Bjørn
Issue Date: 2010
Publisher: University of Hawaii at Manoa
Abstract: Polynomial-clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone C, a sequence B ∈ X ω is C-reducible to A ∈ X ω if there is an algorithm that computes B from A using only effectively selected functions from C. We show that if A is a Kurtz random sequence and C1 C2 are distinct polynomial clones, then there is a sequence B that is C1 -reducible to A but not C2 -reducible to A. This implies a generalization of a result first proved by Lachlan for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov-Loveland stochastic.
Description: Plan B paper, M.A., Mathematics, University of Hawaii at Manoa, 2010
Pages/Duration: 28 pages
URI/DOI: http://hdl.handle.net/10125/25920
Rights: All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Appears in Collections:M.A. Plan B Theses- Mathematics Department



Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.