Cover Image

Resource bounded genericity

AbstractResource-bounded genericity concepts have been introduced by Ambos-Spies, Fleischhack and Huwig [AFH84], [AFH88], Lutz [Lu90], and Fenner [Fe91]. Though it was known that some of these concepts are incompatible, the relations among these notions were not fully understood. Here we survey thes...

Full description

Saved in:
Bibliographic Details
Main Author: Ambos-Spies, Klaus (Author)
Format: Chapter/Article
Language:English
Published: 1996
In: Computability, enumerability, unsolvability
Year: 1996, Pages: 1-60
Online Access:Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/books/computability-enumerability-unsolvability/resource-bounded-genericity/D01C9FD0FE33A6AADFA19B240542421C
Get full text
Author Notes:Klaus Ambos-Spies

MARC

LEADER 00000caa a2200000 c 4500
001 1843057689
003 DE-627
005 20230710180509.0
007 cr uuu---uuuuu
008 230418s1996 xx |||||o 00| ||eng c
035 |a (DE-627)1843057689 
035 |a (DE-599)KXP1843057689 
035 |a (OCoLC)1389826291 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 28  |2 sdnb 
100 1 |a Ambos-Spies, Klaus  |d 1951-  |e VerfasserIn  |0 (DE-588)141551607  |0 (DE-627)629951861  |0 (DE-576)16006810X  |4 aut 
245 1 0 |a Resource bounded genericity  |c Klaus Ambos-Spies 
264 1 |c 1996 
300 |a 60 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Elektronische Reproduktion der Druck-Ausgabe 23. Februar 2010 
500 |a Gesehen am 18.04.2023 
520 |a AbstractResource-bounded genericity concepts have been introduced by Ambos-Spies, Fleischhack and Huwig [AFH84], [AFH88], Lutz [Lu90], and Fenner [Fe91]. Though it was known that some of these concepts are incompatible, the relations among these notions were not fully understood. Here we survey these notions and clarify the relations among them by specifying the types of diagonalizations captured by the individual concepts. Moreover, we introduce two new, stronger resource-bounded genericity concepts corresponding to fundamental diagonalization concepts in complexity theory. First we define general genericity, which generalizes all of the previous concepts and captures both, standard finite extension arguments and slow diagonalizations. The second new concept, extended genericity, actually is a hierarchy of genericity concepts for a given complexity class which extends general genericity and in addition captures delayed diagonalizations. Moreover, this hierarchy will show that in general there is no strongest genericity concept for a complexity class. A similar hierarchy of genericity concepts was independently introduced by Fenner [Fe95].Finally we study some properties of the Baire category notions on E induced by the genericity concepts and we point out some relations between resource-bounded genericity and resource-bounded random- ness.IntroductionThe finite extension method is a central diagonalization technique in computability theory (see e.g. [Ro67], [Od89], [Le83], [So87]). In a standard finite extension argument a set A of strings (or equivalently of numbers) is inductively defined by specifying longer and longer initial segments of it. The global property to be ensured for A by the construction is split into countably many subgoals, given as a list {Re: e≥ 0 } of so called requirements. 
773 0 8 |i Enthalten in  |t Computability, enumerability, unsolvability  |d Cambridge : Cambridge University Press, 1996  |g (1996), Seite 1-60  |h 1 Online-Ressource (vii, 347 pages)  |w (DE-627)883351358  |w (DE-576)486903834  |z 9780511629167  |7 nnam  |a Resource bounded genericity 
773 1 8 |g year:1996  |g pages:1-60  |g extent:60  |a Resource bounded genericity 
856 4 0 |u https://www.cambridge.org/core/books/computability-enumerability-unsolvability/resource-bounded-genericity/D01C9FD0FE33A6AADFA19B240542421C  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20230418 
993 |a BookComponentPart 
994 |a 1996 
998 |g 141551607  |a Ambos-Spies, Klaus  |m 141551607:Ambos-Spies, Klaus  |d 110000  |d 110300  |e 110000PA141551607  |e 110300PA141551607  |k 0/110000/  |k 1/110000/110300/  |p 1  |x j  |y j 
999 |a KXP-PPN1843057689  |e 4310890342 
BIB |a Y 
JSO |a {"id":{"eki":["1843057689"]},"origin":[{"dateIssuedDisp":"1996","dateIssuedKey":"1996"}],"name":{"displayForm":["Klaus Ambos-Spies"]},"relHost":[{"title":[{"title_sort":"Computability, enumerability, unsolvability","subtitle":"directions in recursion theory","title":"Computability, enumerability, unsolvability"}],"person":[{"given":"Stuart B.","family":"Cooper","role":"edt","roleDisplay":"HerausgeberIn","display":"Cooper, Stuart B."},{"given":"T.","family":"Slaman","role":"edt","roleDisplay":"HerausgeberIn","display":"Slaman, T."},{"given":"S.","family":"Wainer","role":"edt","roleDisplay":"HerausgeberIn","display":"Wainer, S."}],"part":{"year":"1996","pages":"1-60","text":"(1996), Seite 1-60","extent":"60"},"disp":"Resource bounded genericityComputability, enumerability, unsolvability","note":["Title from publisher's bibliographic system (viewed on 05 Oct 2015)"],"type":{"bibl":"edited-book","media":"Online-Ressource"},"language":["eng"],"recId":"883351358","origin":[{"publisherPlace":"Cambridge","dateIssuedDisp":"1996.","dateIssuedKey":"1996","publisher":"Cambridge University Press"}],"id":{"eki":["883351358"],"doi":["10.1017/CBO9780511629167"],"isbn":["9780511629167"]},"name":{"displayForm":["edited by S.B. Cooper, T.A. Slaman, S.S. Wainer"]},"relMultPart":[{"part":{"number_sort":["224"],"number":["224"]},"pubHistory":["269 [?]-"],"corporate":[{"role":"isb","roleDisplay":"Herausgebendes Organ","display":"London Mathematical Society"}],"language":["eng"],"recId":"89721840X","disp":"London Mathematical Society lecture note series","note":["Gesehen am 6. September 2017"],"type":{"media":"Online-Ressource","bibl":"serial"},"title":[{"title":"London Mathematical Society lecture note series","title_sort":"London Mathematical Society lecture note series"}],"dispAlt":"London Mathematical Society lecture note series","physDesc":[{"extent":"Online-Ressource"}],"id":{"zdb":["2904882-5"],"eki":["89721840X"]},"origin":[{"publisherPlace":"Cambridge ; New York ; Melbourne ; Madrid ; Capetown ; Singapore ; Sao Paulo ; Delhi ; Mexico City","publisher":"Cambridge University Press","dateIssuedDisp":"[2000?]-"}]}],"physDesc":[{"noteIll":"digital, PDF file(s).","extent":"1 Online-Ressource (vii, 347 pages)"}]}],"physDesc":[{"extent":"60 S."}],"title":[{"title_sort":"Resource bounded genericity","title":"Resource bounded genericity"}],"person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","display":"Ambos-Spies, Klaus","roleDisplay":"VerfasserIn"}],"language":["eng"],"recId":"1843057689","note":["Elektronische Reproduktion der Druck-Ausgabe 23. Februar 2010","Gesehen am 18.04.2023"],"type":{"media":"Online-Ressource","bibl":"chapter"}} 
SRT |a AMBOSSPIESRESOURCEBO1996 

Similar Items