Calculus of Cost Functions
From MaRDI portal
Publication:6283906
arXiv1703.01577MaRDI QIDQ6283906FDOQ6283906
Authors: André Nies 
Publication date: 5 March 2017
Abstract: Cost functions provide a framework for constructions of sets Turing below the halting problem that are close to computable. We carry out a systematic study of cost functions. We relate their algebraic properties to their expressive strength. We show that the class of additive cost functions describes the -trivial sets. We prove a cost function basis theorem, and give a general construction for building computably enumerable sets that are close to being Turing complete. This works dates from 2010 and was submitted in 2013 to the long-delayed volume "The Incomputable" arising from the 2012 Cambridge Turing year.
Other degrees and reducibilities in computability and recursion theory (03D30) Constructive and recursive analysis (03F60)
This page was built for publication: Calculus of Cost Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283906)
