Recursion Theory and Complexity (de Gruyter Series in Logic and Its Applications, Vol. 2)
目次
Priority method in generalized computability, I.V. Ashaev; polynomialtime versus computable Boolean algebras, D. Cenzer, J.B. Remmel; theproof-theoretic strength of the Dushnik-Miller theorem, R.G. Downey, S.Lempp; effectively nowhere simple relations on computable models, V.Harizanov; jump traces with large gaps, P.G. Hinman; weak recursive degreesand a problem of Spector, Sh.T. Ishmukhametov; compositions of permutationsand algorithmic reducibilities, K.V. Korovin; some properties ofmajorant-computability, M.V. Korovina, O.V. Kudinov; hyperarithmeticalfunctions and algebraicity, A.C. Morozov; weak presentation of fields, notextendible to recursion presentations, A. Shlapentokh; jumps of Sigma0/2-high e-degrees and properly Sigma0/2 e-degrees, R.A. Shore, A. Sorbi; thee-reducibility and problem of the nontotal property of e-degrees, B.Ja.Solon; algebras of recursive functions, V.D. Solo'vev; Sigma2-induction andcuppable degrees, Yang Yue. Open problems from Kazan '97 workshop. List ofWORCT'97 participants, recursion theory. List of talks.