15 pages matching standard measures in this book
Results 1-3 of 15
What people are saying - Write a review
We haven't found any reviews in the usual places.
MEASURES AND COMPUTATIONS
PROPERTIES OF INDIVIDUAL CLASSES AND SETS
4 other sections not shown
_ g a.e. _ max abstract complexity measures acceptable indexing algorithm arbitrarily large Assume axioms Borodin Chapter Church's Thesis class of functions Cofinite computational complexity constructibility properties converges Corollary decision problem Define f diverges domain effective example exists finite invariance finite variants follows directly formalisms function f g-presentable given halting problem Hence hierarchy hold implies index sets infinite input intersection intuitive Kleene Lemma low complexity mathematical properties measured set modified notation number of steps obtain occur otherwise output parallel computation capability parallel computation property partial classes partial complexity classes partial functions partial recursive functions particular predicate previous theorem primitive recursive function proper properties of measures Proposition r.e. presentation r.e. sequence recursive presentation recursive set satisfying specific speed-up standard measures tape measure Theorem 3.1 tion total functions Turing machine undefined