Polynomial-clone reducibility
Polynomial-clone reducibility
dc.contributor.advisor | Kjos-Hanssen, Bjørn | |
dc.contributor.author | Culver, Quinn | |
dc.date.accessioned | 2013-02-06T20:13:31Z | |
dc.date.available | 2013-02-06T20:13:31Z | |
dc.date.issued | 2010 | |
dc.description | Plan B paper, M.A., Mathematics, University of Hawaii at Manoa, 2010 | |
dc.description.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. | |
dc.format.extent | 28 pages | |
dc.identifier.uri | http://hdl.handle.net/10125/25920 | |
dc.language | en-US | |
dc.publisher | University of Hawaii at Manoa | |
dc.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. | |
dc.title | Polynomial-clone reducibility | |
dc.type | Master's project | |
dc.type.dcmi | Text | |
local.thesis.degreelevel | Masters | |
local.thesis.department | Mathematics | |
local.thesis.mastertype | Plan B |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- MA_2010_Culver.pdf
- Size:
- 278.91 KB
- Format:
- Adobe Portable Document Format
- Description: