%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Theodore Slaman at 2011-01-11 12:31:42 -0800
%% Saved with string encoding Unicode (UTF-8)
@COMMENT{meta_data,
INDEX = {META},
TYPE = {Personal bibliography},
AUTHOR = {Theodore A. Slaman},
AUTHOR_URL = {http://math.berkeley.edu/~slaman/},
AUTHOR_ID_MR = {163530},
TITLE = {Publications of Theodore A. Slaman},
HEADING = {Publications of Theodore A. Slaman},
SOURCE = {Based in part on data drawn from MathSciNet.},
AUTHOR_ID_UCB_MATH= {1},
}
@COMMENT{author_data,
AUTHOR_DATA = {
Ambos-Spies, Klaus id_mr:25415 http://www.math.uni-heidelberg.de/logic/ambos/ambospub.html
Arslanov, Marat M. id_mr:195689 http://www.ksu.ru/persons/5201.ru.html
Ash, C. J. id_mr:27655
Calhoun, William C. id_mr:239276 http://facstaff.bloomu.edu/wcalhoun/
Cholak, Peter id_mr:290865 http://www.nd.edu/~cholak/
Chong, C. T. id_mr:48725 http://www.math.nus.edu.sg/~chongct/
Coles, Richard J. id_mr:636179
Downey, Rod G. id_mr:59535 http://www.mcs.vuw.ac.nz/people/Rod-Downey.shtml
Greenberg, Noam id_mr:757288 http://homepages.mcs.vuw.ac.nz/~greenberg/
Groszek, Marcia id_mr:77515 http://dfd.dartmouth.edu/directory/show/303
Haught, Christine Ann id_mr:234605 http://webpages.math.luc.edu/~cah/
Hinman, Peter G. id_mr:86155 http://www-personal.umich.edu/~pgh/
Jockusch, Carl G. id_mr:94850 http://www.math.uiuc.edu/~jockusch/
Khoussainov, Bakhadyr id_mr:241973 http://www.cs.auckland.ac.nz/~bmk/
Kjos-Hanssen, Bjørn id_mr:710076 http://www.geocities.com/bjoernkjoshanssen/
Knight, J. F. id_mr:103325 http://www.nd.edu/~mathwww/faculty/knight.shtml
LaForte, Geoffrey L. id_mr:603476 http://www.uwf.edu/glaforte/welcome.htm
Lempp, Steffen id_mr:247988 http://www.math.wisc.edu/~lempp/
Maass, Wolfgang id_mr:191753 http://www.igi.tugraz.at/maass/
Manasse, Mark id_mr:118995 http://research.microsoft.com/users/manasse/
Merkle, Wolfgang id_mr:631971 http://www.math.uni-heidelberg.de/logic/merkle/merkle.html
Mihailovi'c, Nenad id_mr:738437 http://math.uni-heidelberg.de/logic/mihailovic/mihailovic.html
Mytilinaios, Michael E. id_mr:128820
Nies, André id_mr:328692 http://www.cs.auckland.ac.nz/~nies/
Qian, Lei id_mr:325816
Sacks, Gerald E. id_mr:152660 http://www.math.harvard.edu/~sacks/
Seetapun, David id_mr:602460
Semukhin, Pavel id_mr:768814
Shinoda, Juichi id_mr:160840
Shore, Richard A. id_mr:161135 http://www.math.cornell.edu/~shore/
Slaman, Theodore A. id_mr:163530 http://math.berkeley.edu/~slaman
Soare, Robert I. id_mr:164330 http://people.cs.uchicago.edu/~soare/
Sorbi, Andrea id_mr:194934 http://www.mat.unisi.it/~sorbi/
Steel, John R. id_mr:166600 http://math.berkeley.edu/~steel
Woodin, W. Hugh id_mr:184480 http://math.berkeley.edu/~woodin
Yang, Yue id_mr:352570 http://www.math.nus.edu.sg/~matyangy/
}}
@unpublished{ConSla11,
Author = {Conidis, Chris J. and Slaman, Theodore A.},
Note = {preprint},
Title = {Random Reals, The Rainbow Ramsey Theorem, and Arithmetic Conservation},
Year = {2011}}
@unpublished{GreMonSla11,
Author = {Greenberg, Noam and Montalb\'an, Antonio and Slaman, Theodore A.},
Note = {preprint},
Title = {Relative to any Non-Hyperarithmetic Set},
Year = {2011}}
@unpublished{ChoSlaYan10,
Author = {Chong, C. T. and Slaman, Theodore A. and Yang, Yue},
Date-Added = {2011-01-08 09:47:50 -0800},
Date-Modified = {2011-01-08 09:51:01 -0800},
Note = {preprint},
Title = {{$\Pi^1_1$}-Conservation of Combinatorial Principles Weaker Than {R}amsey's Theorem for Pairs},
Title_Html = {Π11-Conservation of Combinatorial Principles Weaker Than Ramsey's Theorem for Pairs},
Urls = {http://math.berkeley.edu/~slaman/papers/ChongSlamanYang2010.pdf},
Selected = {yes},
Year = {2010}}
@article{ChoJocSla09,
Author = {Cholak, Peter A. and Jockusch, Jr., Carl G. and Slaman, Theodore A.},
Coden = {JSYLA6},
Date-Added = {2011-01-08 09:23:26 -0800},
Date-Modified = {2011-01-11 12:31:30 -0800},
Fjournal = {Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03F35 (03C62 03D30 03D80)},
Mrnumber = {2583829 (2010k:03055)},
Number = {4},
Pages = {1438--1439},
Title = {Corrigendum to: ``{O}n the strength of {R}amsey's theorem for pairs'' [MR1825173]},
Url = {http://projecteuclid.org/getRecord?id=euclid.jsl/1254748700},
Volume = {74},
Year = {2009},
Bdsk-Url-1 = {http://www.ams.org/mathscinet-getitem?mr=2583829}}
@article{HirShoSla09,
Author = {Hirschfeldt, Denis R. and Shore, Richard A. and Slaman, Theodore A.},
Coden = {TAMTAM},
Date-Added = {2011-01-08 09:23:18 -0800},
Date-Modified = {2011-01-08 09:25:09 -0800},
Doi = {10.1090/S0002-9947-09-04847-8},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03B30 (03C15 03C50 03C57 03D45 03F35)},
Mrnumber = {2529915 (2010m:03019)},
Mrreviewer = {M. Yasuhara},
Number = {11},
Pages = {5805--5837},
Title = {The atomic model theorem and type omitting},
Url = {http://dx.doi.org/10.1090/S0002-9947-09-04847-8},
Volume = {361},
Year = {2009},
Bdsk-Url-1 = {http://www.ams.org/mathscinet-getitem?mr=2529915}}
@article{greenberg.montalban.etal:2010,
Author = {Greenberg, Noam and Montalb\'an, Antonio and Slaman, Theodore A.},
Fjournal = {Proceedings of the American Mathematical Society},
Journal = {Proc. Amer. Math. Soc.},
Title = {The {S}laman-{W}ehner Theorem in Higher Recursion Theory},
Urls = {http://math.berkeley.edu/~slaman/papers/almost_computable.pdf},
Selected = {yes},
Year = 2010}
@unpublished{montalban.slaman:2008,
Arxiv = {http://arxiv.org/abs/0812.1600},
Author = {Barmpalias, George and Greenberg, Noam and Montalb\'an, Antonio and Slaman, Theodore A.},
Note = {preprint},
Title = {${K}$-trivials are Never Continuously Random},
Year = 2010}
@inproceedings{hirschfeldt.jockusch.ea:2008,
Abstract = {We study the reverse mathematics and computability-theoretic strength of (stable)
Ramsey's Theorem for pairs and the related principles COH and DNR. We show that
SRT$^2_2$ implies DNR over RCA$_0$ but COH does not, and answer a question of
Mileti by showing that every computable stable $2$-coloring of pairs has an
incomplete $\Delta^0_2$ infinite homogeneous set. We also give some extensions of
the latter result, and relate it to potential approaches to showing that SRT$^2_2$
does not imply RT$^2_2$.},
Author = {Hirschfeldt, Denis R. and Jockusch, Jr., Carl G. and Bj{\o}rn Kjos-Hanssen and Steffen Lempp and Theodore A. Slaman},
Booktitle = {Computational Prospects of Infinity. Part I: Presented Talks},
Editor = {Chong, Chitat and Feng, Qi and Slaman, Theodore A. and Woodin, W. Hugh and Yang, Yue},
Mrclass = {03B30 (03D80)},
Pages = {143--161},
Publisher = {World Scientific},
Series = {Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore},
Title = {The Strength of Some Combinatorial Principles Related to {R}amsey's Theorem for Pairs},
Urls = {http://math.berkeley.edu/~slaman/papers/khjls.pdf},
Volume = 14,
Year = 2008}
@article{ChoSla10,
Author = {Chong, C. T. and Slaman, T. A.},
Journal = {Israel J. Math.},
Pages = {229--252},
Title = {The theory of the {$\alpha$} degrees is undecidable},
Volume = {178},
Year = {2010},
Urls = {http://math.berkeley.edu/~slaman/papers/chong-slaman.pdf},
Selected= {yes}}
@proceedings{IMS2:2008,
Editor = {Chong, Chitat and Feng, Qi and Slaman, Theodore A. and Woodin, W. Hugh and Yang, Yue},
Publisher = {World Scientific},
Series = {Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore},
Title = {Computational Prospects of Infinity. Part II: Presented Talks},
Volume = 15,
Year = 2008}
@inproceedings{slaman:2008,
Author = {Slaman, Theodore A.},
Booktitle = {Computational Prospects of Infinity. Part I: Tutorials},
Editor = {Chong, Chitat and Feng, Qi and Slaman, Theodore A. and Woodin, W. Hugh and Yang, Yue},
Pages = {83--101},
Publisher = {World Scientific},
Series = {Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore},
Title = {Global Properties of the {T}uring Degrees and the {T}uring Jump},
Urls = {http://math.berkeley.edu/~slaman/papers/IMS_slaman.pdf},
Volume = 14,
Year = 2008}
@proceedings{IMS1:2008,
Editor = {Chong, Chitat and Feng, Qi and Slaman, Theodore A. and Woodin, W. Hugh and Yang, Yue},
Publisher = {World Scientific},
Series = {Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore},
Title = {Computational Prospects of Infinity. Part I: Tutorials},
Volume = 14,
Year = 2008}
@unpublished{reimann.slaman:2008,
Arxiv = {http://arxiv.org/abs/0802.2705},
Author = {Reimann, Jan and Slaman, Theodore A.},
Mrclass = {68Q30},
Note = {preprint},
Selected = {yes},
Title = {Measures and Their Random Reals},
Year = 2008}
@article{kucera.slaman:2007,
Arxiv = {http://arxiv.org/abs/0708.3793v1},
Author = {Ku{\v{c}}era, Anton{\'{\i}}n and Slaman, Theodore A.},
Author_Html = {Kučera, Antonín and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D32 (03D25 03D28 03D80 68Q30)},
Mrnumber = {2518809 (2010h:03064)},
Mrreviewer = {Denis R. Hirschfeldt},
Number = {2},
Pages = {517--534},
Title = {Low upper bounds of ideals},
Urls = {http://math.berkeley.edu/~slaman/papers/low_bounds.pdf},
Volume = {74},
Year = {2009}}
@unpublished{reimann.slaman:2007,
Arxiv = {http://arxiv.org/abs/0707.1390v1},
Author = {Reimann, Jan and Slaman, Theodore A.},
Mrclass = {68Q30},
Note = {preprint},
Selected = {yes},
Title = {Probability Measures and Effective Randomness},
Urls = {http://math.berkeley.edu/~slaman/papers/reimann_slaman.pdf},
Year = 2007}
@incollection{lempp.slaman:2007,
Abstract = {We classify the computability-theoretic complexity of two index sets of classes of
first-order theories: We show that the property of being an $\aleph_0$-categorical
theory is $\Pi^0_3$-complete; and the property of being an Ehrenfeucht theory
$\Pi^1_1$-complete. We also show that the property of having continuum many models
is $\Sigma^1_1$-hard. Finally, as a corollary, we note that the properties of
having only decidable models, and of having only computable models, are both
$\Pi^1_1$-complete.},
Address = {Providence, RI},
Arxiv = {http://arxiv.org/abs/math/0610776},
Author = {Lempp, Steffen and Slaman, Theodore A.},
Booktitle = {Advances in logic},
Mrclass = {03D80 (03C52 03D55)},
Mrnumber = {MR2322362 (2008e:03076)},
Mrreviewer = {Rodney G. Downey},
Pages = {43--47},
Publisher = {Amer. Math. Soc.},
Series = {Contemp. Math.},
Title = {The complexity of the index sets of {$\aleph_0$}-categorical theories and of {E}hrenfeucht theories},
Title_Html = {The Complexity of the Index Sets of א-null-Categorical Theories and Ehrenfeucht Theories},
Urls = {http://math.berkeley.edu/~slaman/papers/LemppSlaman.pdf},
Volume = {425},
Year = {2007}}
@unpublished{marker.slaman:2006,
Abstract = {We consider the fragment $F$ of first order arithmetic in which quantification is
restricted to ``for all but finitely many.'' We show that the integers form an
$F$-elementary substructure of the real numbers. Consequently, the $F$-theory of
arithmetic is decidable.},
Arxiv = {http://arxiv.org/abs/math/0602415},
Author = {Marker, David and Slaman, Theodore A.},
Mrclass = {03F30},
Note = {preprint},
Title = {Decidability of the Natural Numbers with the Almost-All Quantifier},
Urls = {http://math.berkeley.edu/~slaman/papers/marker_slaman.pdf},
Year = 2006}
@article{kucera.slaman:2007*b,
Abstract = {For every Scott set F and every nonrecursive set X in F, there is a Y in F such
that X and Y are Turing incomparable.},
Arxiv = {http://arxiv.org/abs/math/0602439},
Author = {Ku\v{c}era, Anton{\'{\i}}n and Slaman, Theodore A.},
Author_Html = {Kučera, Antonín and Slaman, Theodore A.},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03D28},
Pages = {3723--3731},
Selected = {yes},
Title = {{T}uring Incomparability in {S}cott Sets},
Urls = {http://math.berkeley.edu/~slaman/papers/scott-incomp.pdf},
Volume = 135,
Year = 2007}
@inproceedings{ambos-spies.lempp.ea:2008,
Abstract = {We give an example of a subset of the recursively enumerable Turing degrees which
generates the recursively enumerable degrees using meet and join but does not
generate them using join alone.},
Author = {Ambos-Spies, Klaus and Lempp, Steffen and Slaman, Theodore A.},
Booktitle = {Computational Prospects of Infinity. Part I: Presented Talks},
Editor = {Chong, Chitat and Feng, Qi and Slaman, Theodore A. and Woodin, W. Hugh and Yang, Yue},
Mrclass = {03D25},
Pages = {1-22},
Publisher = {World Scientific},
Series = {Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore},
Title = {Generating Sets for the Recursively Enumerable {T}uring Degrees},
Urls = {http://math.berkeley.edu/~slaman/papers/kst.pdf},
Volume = 14,
Year = 2008}
@article{khoussainov.semukhin.etal:2006,
Abstract = {We give the basic definitions of computable, $\Sigma^0_1$, and $\Pi^0_1$-algebras,
and provide some examples. In the second section, we characterize those
$\Sigma^0_1$-algebras that are non-computable. As a corollary we obtain that the
isomorphism types of finitely generated computable algebras (in particular, the
arithmetic and the term algebras) and computable infinite fields fail to have
non-computable $\Sigma^0_1$-algebras. In the third section, we define the class of
term separable algebras. We prove that many known algebras such as basic
arithmetic, the term algebras, fields and vector spaces are term
separable. Finally, the last section is devoted to showing that all infinite
computable term separable algebras are isomorphic to non-computable
$\Pi^0_1$-algebras.},
Author = {Khoussainov, Bakhadyr and Semukhin, Pavel and Slaman, Theodore A.},
Journal = {Arch. Math. Logic},
Mrclass = {03D45},
Pages = {769--781},
Title = {On ${\Pi^0_1}$-presentations of algebras},
Title_Html = {On Π01-presentations of algebras},
Urls = {http://math.berkeley.edu/~slaman/papers/kss.pdf},
Volume = 45,
Year = 2006}
@article{khoussainov.lempp.ea:2004,
Abstract = {Computably enumerable algebras are the ones whose positive atomic diagrams are
computably enumerable. Computable algebras are the ones whose atomic diagrams are
computable. In this paper we investigate computably enumerable algebras and
provide several algebraic and computable theoretic distinctions of these algebras
from the class of computable algebras. We give a characterization of computably
enumerable but not computable algebras in terms of congruences and effective
conjunctions of $\Pi^0_1$-sentences. Our characterization, for example, shows that
computable conjunctions of negative atomic formulas true in a given c.e. algebra
can be preserved in infinitely many of its homomorphic images. We also study
questions on how expansions of algebras by finitely many new functions affect
computable isomorphism types. In particular, we construct a c.e. algebra with
unique computable isomorphism type but which has no finitely generated
c.e. expansion.},
Author = {Khoussainov, Bakhadyr and Lempp, Steffen and Slaman, Theodore A.},
Journal = {International Journal of Algebra and Computation},
Month = {June},
Mrclass = {03D45},
Number = {3},
Pages = {437--454},
Title = {Computably enumerable algebras, their expansions, and isomorphisms},
Urls = {http://math.berkeley.edu/~slaman/papers/kls.pdf},
Volume = {15},
Year = {2005}}
@incollection{slaman:2005,
Abstract = {We survey the properties of the Turing jump, sketching the proof that the jump is
definable in the Turing degrees and classifying the Borel relations on reals
$R(X,Y)$ which share the basic properties of ``$Y$ is definable from $X$''.},
Address = {Wellesley, Massachusetts},
Author = {Slaman, Theodore A.},
Booktitle = {Logic Colloquium 2000, Proceedings of the Annual Summer Meeting of the Association for Symbolic Logic, held in Paris, France, July 23-31, 2000},
Editor = {Cori, Ren\'e and Razborov, Alexander and Todorčević, Stevo and Wood, Carol},
Mrclass = {03D28 (03D55)},
Mrnumber = {MR2143887 (2006b:03049)},
Pages = {365--382},
Publisher = {A K Peters, Ltd.},
Selected = {yes},
Title = {Aspects of the {T}uring jump},
Urls = {http://math.berkeley.edu/~slaman/papers/lc2000.pdf},
Year = 2005}
@incollection{MerMihSla04,
Abstract = {We investigate the characterizations of effective randomness in terms of
Martin-L\"of covers and martingales.},
Address = {Berlin},
Author = {Merkle, Wolfgang and Mihailovi{\'c}, Nenad and Slaman, Theodore A.},
Booktitle = {Automata, languages and programming},
Date-Modified = {2011-01-11 12:30:16 -0800},
Mrclass = {68Q30 (03D80)},
Mrnumber = {MR2161076 (2006c:03064)},
Pages = {983--995},
Publisher = {Springer},
Series = {Lecture Notes in Comput. Sci.},
Title = {Some results on effective randomness},
Urls = {http://math.berkeley.edu/~slaman/papers/mlreals.pdf},
Volume = {3142},
Year = {2004}}
@article{ambos-spies.kjos-hanssen.ea:2004,
Abstract = {We construct an ideal $I$ in the Turing degrees such that for every $X$ in the
ideal there is a $G$ in the ideal which is diagonally nonrecursive relative to $X$
and such that there is no 1-random degree in $I$.},
Author = {Ambos-Spies, Klaus and Kjos-Hanssen,Bj{\o}rn and Lempp, Steffen and Slaman, Theodore A.},
Fjournal = {The Journal of Symbolic Logic},
Id_Mr = {MR2135656},
Journal = {J. Symbolic Logic},
Mrclass = {03B30 (03D80)},
Number = 4,
Pages = {1089--1104},
Title = {Comparing {DNR} and {WWKL}$_0$},
Title_Html = {Comparing DNR and WWKL0},
Urls = {http://math.berkeley.edu/~slaman/papers/DNR.pdf},
Volume = 69,
Year = 2004}
@article{slaman:2004,
Abstract = {Working in the base theory of $PA^-$ + $I\Sigma_0$ + $EXP$, we show that for all
$n$ in $\omega$, the bounding principle for $\Sigma_n$-formulas ($B\Sigma_n$) is
equivalent to the induction principle for $\Delta_n$-formulas ($I\Delta_n$). This
partially answers a question of Paris.},
Author = {Slaman, Theodore A.},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03F30 (03H15)},
Mrnumber = {MR2052424 (2005b:03140)},
Pages = {2449--2456},
Selected = {yes},
Title = {${\Sigma}_n$-Bounding and ${\Delta}_n$-Induction},
Title_Html = {Σn-Bounding and Δn-Induction},
Urls = {http://math.berkeley.edu/~slaman/papers/induction.pdf},
Volume = 132,
Year = 2004}
@incollection{ShoSla06,
Abstract = {We prove that the two quantifier theory of the Turing degrees with order, join and
jump is undecidable.},
Address = {La Jolla, CA},
Author = {Shore, Richard A. and Slaman, Theodore A.},
Booktitle = {Logic Colloquium '03},
Date-Modified = {2011-01-11 12:30:02 -0800},
Mrclass = {03D28 (03D25 03D35)},
Mrnumber = {MR2207361},
Pages = {326--344},
Publisher = {Assoc. Symbol. Logic},
Series = {Lect. Notes Log.},
Title = {The {$\forall\exists$} theory of {${\scr D}(\leq,\vee,')$} is undecidable},
Title_Html = {The for-all there-exists theory of D(<,V,') is undecidable},
Urls = {http://math.berkeley.edu/~slaman/papers/pi2dj.pdf},
Volume = {24},
Year = {2006}}
@article{lempp.slaman.ea:2003e,
Abstract = {We give an algorithm for deciding for pairs $P$ contained in $Q$ of finite partial
orders whether every embedding of $P$ into the enumeration degrees of the
$\Sigma^0_2$-sets can be extended to an embedding of $Q$.},
Author = {Lempp, Steffen and Slaman, Theodore A. and Sorbi, Andrea},
Journal = {Journal of Mathematical Logic},
Mrclass = {03D30},
Number = 2,
Pages = {247--298},
Title = {On Extensions of Embeddings into the Enumeration Degrees of the ${\Sigma}^0_2$-Sets},
Title_Html = {On Extensions of Embeddings into the Enumeration Degrees of the Σ02-Sets},
Urls = {http://math.berkeley.edu/~slaman/papers/lss.pdf},
Volume = 5,
Year = 2005}
@article{mytilinaios.slaman:2003,
Abstract = {We exhibit an structural difference between the truth-table degrees of the sets
which are truth-table above $0'$ and the PTIME-Turing degrees of all sets. Though
the structures do not have the same isomorphism type, demonstrating this fact
relies on developing their common theory.},
Author = {Mytilinaios, Michael E. and Slaman, Theodore A.},
Journal = {Notre Dame J. Formal Logic},
Mrclass = {03D30 (68Q15)},
Number = 1,
Pages = {1--12},
Title = {Differences between resource bounded degree structures},
Urls = {http://math.berkeley.edu/~slaman/papers/mem_tas.pdf},
Volume = 44,
Year = 2003}
@article{GreShoSla06,
Abstract = {Sacks (1966) asked whether the metarecursively enumerable degrees are elementarily
equivalent to the recursively enumerable degrees. We show that they are not. In
fact, the elementary theory of the metarecursively enumerable degrees is
equivalent to the elementary theory of $L(\omega_1^{CK})$.},
Author = {Greenberg, Noam and Shore, Richard A. and Slaman, Theodore A.},
Date-Modified = {2011-01-11 12:30:02 -0800},
Fjournal = {Journal of Mathematical Logic},
Issn = {0219-0613},
Journal = {J. Math. Log.},
Mrclass = {03D60 (03D25)},
Mrnumber = {MR2250953},
Number = {1},
Pages = {49--68},
Title = {The theory of the metarecursively enumerable degrees},
Urls = {http://math.berkeley.edu/~slaman/papers/metare7.pdf},
Volume = {6},
Year = {2006}}
@article{cholak.groszek.ea:2001,
Abstract = {We show there is a non-recursive recursively enumerable set $A$ such that if $W$
is any low recursively enumerable set, then the join $W + A$ is also low. That is,
$A$ is ``almost deep''. This answers a question of Jockusch. The almost deep
degrees form an definable ideal in the recursively enumerable degrees with jump.},
Author = {Cholak, Peter and Groszek, Marcia and Slaman, Theodore},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {2002d:03070},
Mrreviewer = {Michael Stob},
Number = {2},
Pages = {881--901},
Title = {An almost deep degree},
Urls = {http://math.berkeley.edu/~slaman/papers/cgs.pdf},
Volume = {66},
Year = {2001}}
@article{cholak.jockusch.ea:2001,
Abstract = {We study the proof-theoretic strength and effective content of the infinite form
of Ramsey's theorem for pairs. Let $RT^n_k$ denote Ramsey's theorem for
$k$-colorings of $n$-element sets, and let $RT^n_{<\omega}$ denote [For all $k$,
$RT^n_k$]. Our main result on computability is: For any $n \geq 2$ and any
recursive $k$-coloring of the $n$-element sets of natural numbers, there is an
infinite homogeneous set $X$ with $X'' \leq_T 0^{(n)}$. Let $I\Sigma_n$ and
$B\Sigma_n$ denote the $\Sigma_n$ induction and bounding schemes,
respectively. Adapting the case $n=2$ of the above result (where $X$ is low$_2$)
to models of arithmetic enables us to show that $RCA_0$ + $I\Sigma_2$ + $RT^2_2$
is conservative over $RCA_0$ + $I\Sigma_2$ for $\Pi^1_1$ statements and that
$RCA_0 + I\Sigma_3 + RT^2_{<\omega}$ is conservative over $RCA_0+ I\Sigma_3$ for
arithmetic statements. It follows that $RCA_0 + RT^2_2$ does not imply
$B\Sigma_3$. We show in contrast that $RCA_0 + RT^2_{<\omega}$ does imply
$B\Sigma_3$, and so $RT^{2}_{<\omega}$ is strictly stronger than $RT^{2}_{2}$ over
$RCA_0$. },
Author = {Cholak, Peter A. and Jockusch, Jr., Carl G. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03F35 (03C62 03D30 03D80)},
Mrnumber = {2002c:03094},
Mrreviewer = {Roman Murawski},
Number = {1},
Pages = {1--55},
Selected = {yes},
Title = {On the strength of {R}amsey's theorem for pairs},
Urls = {http://math.berkeley.edu/~slaman/papers/cjs.pdf},
Volume = {66},
Year = {2001}}
@article{chong.qian.ea:2001,
Abstract = {Over the base theory of $PA^-+B\Sigma_2$, there is a minimal pair of recursively
enumerable Turing degrees if and only if $I\Sigma_2$. Even so, there is a proof
within $PA^-+B\Sigma_2$ that Shoenfield's conjecture is false. },
Author = {Chong, C. T. and Qian, Lei and Slaman, Theodore A. and Yang, Yue},
Coden = {ISJMAP},
Fjournal = {Israel Journal of Mathematics},
Issn = {0021-2172},
Journal = {Israel J. Math.},
Mrclass = {03D25 (03C62)},
Mrnumber = {2002c:03067},
Mrreviewer = {Thomas McLaughlin},
Pages = {1--28},
Title = {{$\Sigma_2$} induction and infinite injury priority arguments. {III}. {P}rompt sets, minimal pairs and {S}hoenfield's conjecture},
Title_Html = {Σ2-induction and infinite injury priority arguments. III. Prompt sets, minimal pairs and Shoenfield's conjecture},
Urls = {http://math.berkeley.edu/~slaman/papers/chong-etal.pdf},
Volume = {121},
Year = {2001}}
@article{kucera.slaman:2001,
Abstract = {One recursively enumerable real $\alpha$ dominates another one $\beta$ if there
are nondecreasing recursive sequences of rational numbers $(a[n]:n \in \omega)$
approximating $\alpha$ and $(b[n]:n$ in $\omega)$ approximating $\beta$ and a
positive constant $C$ such that for all $n$, $C(\alpha-a[n])\geq(\beta-b[n])$. We
show every recursively enumerable random real dominates all other recursively
enumerable reals. We conclude that the recursively enumerable random reals are
exactly the Chaitin (1977) $\Omega$-numbers. Secondly, we show that the sets in a
universal Martin-L\"of test for randomness have random measure, and every
recursively enumerable random number is the sum of the measures represented in a
universal Martin-L\"of test. },
Author = {Ku\v{c}era, Anton{\'{\i}}n and Slaman, Theodore A.},
Author_Html = {Kučera, Antonín and Slaman, Theodore A.},
Fjournal = {SIAM Journal on Computing},
Issn = {1095-7111},
Journal = {SIAM J. Comput.},
Mrclass = {68Q30},
Mrnumber = {2002k:68078},
Mrreviewer = {Marius Zimand},
Number = {1},
Pages = {199--211 (electronic)},
Selected = {yes},
Title = {Randomness and recursive enumerability},
Urls = {http://math.berkeley.edu/~slaman/papers/random.pdf},
Volume = {31},
Year = {2001}}
@article{shore.slaman:2001,
Abstract = {We prove that, for any $D$, $A$ and $U$ with $D >_T A + U$ and recursively
enumerable in $A + U$, there are pairs $X_0,X_1$ and $Y_0,Y_1$ such that $D =_T
X_0 + X_1$; $D =_T Y_0 + Y_1$; and, for any $i$ and $j$ from $\lbrace 0,1\rbrace$
and any set $B$, if $X_i + A \geq_T B$ and $Y_j + A \geq_T B$ then $A \geq_T
B$. We then deduce that for any degrees $d$, $a$, and $b$ such that $a$ and $b$
are recursive in $d$, $a$ is not $\geq_T b$, and $d$ is $n-REA$ in $a$, $d$ can be
split over $a$ avoiding $b$.},
Author = {Shore, Richard A. and Slaman, Theodore A.},
Coden = {PAMYAR},
Fjournal = {Proceedings of the American Mathematical Society},
Issn = {0002-9939},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03D25 (03D30)},
Mrnumber = {2002h:03094},
Mrreviewer = {Peter Cholak},
Number = {12},
Pages = {3721--3728 (electronic)},
Title = {A splitting theorem for {$n$-{REA}} degrees},
Title_Html = {A splitting theorem for n-REA degrees},
Urls = {http://math.berkeley.edu/~slaman/papers/splitting.pdf},
Volume = {129},
Year = {2001}}
@article{slaman.soare:2001,
Abstract = {We give a decision procedure to determine for any two finite bounded partially
ordered sets $P$ and $Q$, whether every embedding of $P$ into the recursively
enumerable Turing degrees can be extended to an embedding of $Q$.},
Author = {Slaman, Theodore A. and Soare, Robert I.},
Coden = {ANMAAH},
Fjournal = {Annals of Mathematics. Second Series},
Issn = {0003-486X},
Journal = {Ann. of Math. (2)},
Mrclass = {03D25 (03D30)},
Mrnumber = {2002f:03079},
Mrreviewer = {Peter Cholak},
Number = {1},
Pages = {1--43},
Title = {Extension of embeddings in the computably enumerable degrees},
Urls = {http://math.berkeley.edu/~slaman/papers/44.ps [ps]},
Volume = {154},
Year = {2001}}
@article{coles.downey.ea:2000,
Abstract = {For every subset $A$ of $\omega$, there is a Turing degree which is the least
degree of the jumps of all sets $X$ for which $A$ is $\Sigma^0_1(X).$},
Author = {Coles, Richard J. and Downey, Rod G. and Slaman, Theodore A.},
Coden = {JLMSAK},
Fjournal = {The Journal of the London Mathematical Society. Second Series},
Issn = {0024-6107},
Journal = {J. London Math. Soc. (2)},
Mrclass = {03D25 (03D28)},
Mrnumber = {1 794 274},
Number = {3},
Pages = {641--649},
Title = {Every set has a least jump enumeration},
Urls = {http://math.berkeley.edu/~slaman/papers/coles-downey-slaman.pdf},
Volume = {62},
Year = {2000}}
@article{shinoda.slaman:2000,
Abstract = {There is a comeager set $C$ contained in the set of 1-generic reals and a first
order structure $M$ such that for any real number $X$, there is an element of $C$
which is recursive in $X$ if and only if there is a presentation of $M$ which is
recursive in $X$.},
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03C57},
Mrnumber = {1 782 112},
Number = {1},
Pages = {164--172},
Title = {Recursive in a generic real},
Urls = {http://math.berkeley.edu/~slaman/papers/shinoda-slaman.pdf},
Volume = {65},
Year = {2000}}
@incollection{slaman:2000,
Abstract = { Our goal is to convince the reader that recursion theoretic knowledge and
experience can be successfully applied to questions which are typically viewed as
set theoretic. We cite some recent work by Slaman, Hjorth, and Harrington in which
recursion theoretic thinking was applied to problems in classical descriptive set
theory.},
Address = {Providence, RI},
Author = {Slaman, Theodore A.},
Booktitle = {Computability theory and its applications (Boulder, CO, 1999)},
Mrclass = {03E15 (03D65)},
Mrnumber = {2001e:03087},
Pages = {273--278},
Publisher = {Amer. Math. Soc.},
Title = {Recursion theory in set theory},
Urls = {http://math.berkeley.edu/~slaman/papers/boulder.pdf},
Year = 2000}
@article{shore.slaman:1999,
Abstract = {The Turing jump is first order definable in the partial order of Turing degrees.},
Author = {Shore, Richard A. and Slaman, Theodore A.},
Fjournal = {Mathematical Research Letters},
Issn = {1073-2780},
Journal = {Math. Res. Lett.},
Mrclass = {03D28 (03D25 03D55)},
Mrnumber = {2000m:03104},
Mrreviewer = {Peter Cholak},
Number = {5-6},
Pages = {711--722},
Title = {Defining the {T}uring jump},
Urls = {http://math.berkeley.edu/~slaman/papers/jump.pdf},
Volume = {6},
Year = {1999}}
@article{slaman:1999,
Abstract = {There is a set of reals $U$ such that for every analytic set $A$ there is a
continuous function $f$ which maps $U$~bijectively to $A$.},
Author = {Slaman, Theodore A.},
Fjournal = {Fundamenta Mathematicae},
Issn = {0016-2736},
Journal = {Fund. Math.},
Mrclass = {03E15},
Mrnumber = {2000d:03105},
Mrreviewer = {Miroslav Repick{\'y}},
Number = {2},
Pages = {153--159},
Title = {On a question of {S}ierpi{\'n}ski},
Title_Html = {On a question of Sierpiński},
Urls = {http://math.berkeley.edu/~slaman/papers/sierpinski.pdf},
Volume = {159},
Year = {1999}}
@incollection{slaman:1999*b,
Abstract = {We give a survey of the results concerning the structure of the Turing degrees at
large.},
Address = {Amsterdam},
Author = {Slaman, Theodore A.},
Booktitle = {Handbook of computability theory},
Mrclass = {03D28},
Mrnumber = {2000g:03097},
Pages = {155--168},
Publisher = {North-Holland},
Title = {The global structure of the {T}uring degrees},
Year = {1999}}
@article{arslanov.laforte.ea:1998,
Abstract = {We show that the intersection of the class of $2$-REA degrees with that of the
$\omega$-r.e. degrees consists precisely of the class of d.r.e. degrees. We also
include some applications and show that there is no natural generalization of this
result to higher levels of the REA hierarchy.},
Author = {Arslanov, Marat M. and LaForte, Geoffrey L. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30},
Mrnumber = {99f:03057},
Mrreviewer = {Wen Qi Huang},
Number = {2},
Pages = {411--420},
Title = {Relative enumerability in the difference hierarchy},
Volume = {63},
Year = {1998}}
@article{groszek.slaman:1998,
Abstract = {If there is a nonconstructible real, then every perfect set has a nonconstructible
element, answering a question of Prikry. This is a specific instance of a more
general theorem giving a sufficient condition on a pair $M$ contained in $N$ of
models of set theory implying that every perfect set in $N$ has an element in $N$
which is not in $M$.},
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03E45 (03E15)},
Mrnumber = {99c:03072},
Number = {2},
Pages = {204--209},
Selected = {yes},
Title = {A basis theorem for perfect sets},
Urls = {http://math.berkeley.edu/~slaman/papers/prikry.pdf},
Volume = {4},
Year = {1998}}
@article{lempp.nies.ea:1998,
Abstract = {We show the undecidability of the $\Pi_3$-theory of the partial order of
recursively enumerable Turing degrees.},
Author = {Lempp, Steffen and Nies, Andr{\'e} and Slaman, Theodore A.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D25 (03D35)},
Mrnumber = {98j:03056},
Mrreviewer = {Peter Cholak},
Number = {7},
Pages = {2719--2736},
Title = {The ${\Pi}_3$-theory of the computably enumerable {T}uring degrees is undecidable},
Title_Html = {The Π3-theory of the computably enumerable Turing degrees is undecidable},
Volume = {350},
Year = {1998}}
@article{nies.shore.ea:1998,
Abstract = {We develop the Slaman-Woodin coding scheme in the recursively enumerable
degrees. We apply it to prove the Harrington-Slaman theorem that the theory of the
recursively enumerable degrees is recursively isomorphic to the theory of
first-order arithmetic. We also show that various natural relations, just as the
jump-class other than "low", are definable within the recursively enumerable
degrees.},
Author = {Nies, Andr{\'e} and Shore, Richard A. and Slaman, Theodore A.},
Coden = {PLMTAL},
Fjournal = {Proceedings of the London Mathematical Society. Third Series},
Issn = {0024-6115},
Journal = {Proc. London Math. Soc. (3)},
Mrclass = {03D25 (03D30 03D35)},
Mrnumber = {99m:03083},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {2},
Pages = {241--291},
Title = {Interpretability and definability in the recursively enumerable degrees},
Volume = {77},
Year = {1998}}
@article{slaman.sorbi:1998,
Abstract = {We show that there exists a set $A$ such that $A$ has quasi-minimal enumeration
degree, and there are uncountably many sets $B$ such that $A$ is enumeration
reducible to $B$ and $B$ has minimal Turing degree. Answering a related question
raised by Solon, we also show that there exists a nontotal enumeration degree
which is not $e$-hyperimmune.},
Author = {Slaman, Theodore A. and Sorbi, A.},
Coden = {ANLMAE},
Fjournal = {Annali di Matematica Pura ed Applicata. Serie Quarta},
Issn = {0003-4622},
Journal = {Ann. Mat. Pura Appl. (4)},
Mrclass = {03D30 (03D28)},
Mrnumber = {2001a:03092},
Mrreviewer = {Sh. T. Ishmukhametov},
Pages = {97--120},
Title = {Quasi-minimal enumeration degrees and minimal {T}uring degrees},
Volume = 174,
Year = 1998}
@article{slaman.woodin:1998,
Abstract = {J.~\Los\ raised the following question: Under what conditions can a countable
partially ordered set be extended to a dense linear order merely by adding
instances of comparability (without adding new points)? We show that having such
an extension is a $\Sigma^1_1$-complete property and so there is no Borel answer
to \Los's question. Additionally, we show that there is a natural $\Pi_1^1$-norm
on the partial orders which cannot be so extended and calculate some natural ranks
in that norm.},
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {06A05 (03D80 03E15)},
Mrnumber = {99f:06002},
Note = {Conference on Computability Theory (Oberwolfach, 1996)},
Number = {1-3},
Pages = {253--261},
Title = {Extending partial orders to dense linear orders},
Volume = {94},
Year = {1998}}
@article{slaman:1998,
Abstract = {There is a countable first order structure $\M$ such that for any set of integers
$X$, $X$ is not recursive if and only if there is a presentation of $\M$ which is
recursive in $X$.},
Author = {Slaman, Theodore A.},
Coden = {PAMYAR},
Fjournal = {Proceedings of the American Mathematical Society},
Issn = {0002-9939},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03C57 (03D45)},
Mrnumber = {98h:03047},
Mrreviewer = {Cristian Calude},
Number = {7},
Pages = {2117--2122},
Title = {Relative to any nonrecursive set},
Volume = {126},
Year = {1998}}
@incollection{slaman:1998*b,
Abstract = {We give a short survey of the hierarchies of mathematical definability.},
Address = {New York},
Author = {Slaman, Theodore A.},
Booktitle = {Truth in mathematics (Mussomeli, 1995)},
Mrclass = {03D55},
Mrnumber = {1 688 345},
Pages = {233--251},
Publisher = {Oxford Univ. Press},
Title = {Mathematical definability},
Year = {1998}}
@proceedings{oberwolfach1998,
Abstract = {Collection of papers presented during the Oberwolfach workshop of January, 1996.},
Address = {Amsterdam},
Booktitle = {Proceedings of the conference held in Oberwolfach, January 27-Feb\ ruary 3, 1996},
Coden = {APALD7},
Date-Modified = {2011-01-11 12:31:06 -0800},
Editor = {Ambos-Spies, Klaus and Slaman, Theodore A.},
Issn = {0168-0072},
Mrclass = {03Dxx (68Q05)},
Mrnumber = {99b:03006},
Note = {Ann. Pure Appl. Logic {\bf 94} (1998), no. 1-3},
Pages = {i--vi and 1--296},
Publisher = {North-Holland Publishing Co.},
Title = {Conference on {C}omputability {T}heory},
Year = {1998}}
@article{groszek.slaman:1997,
Abstract = {Theorem: There is a non-empty $\Pi^0_1$ class of reals, each of which computes a
real of minimal (Turing) degree. Corollary: $WKL$ proves ``there is a minimal
Turing degree''. This answers a question of H. Friedman and S. Simpson.},
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D30 (03F35)},
Mrnumber = {99f:03058},
Mrreviewer = {C. G. Jockusch, Jr.},
Note = {Logic Colloquium '95 Haifa},
Number = {2},
Pages = {117--144},
Title = {${\Pi}^0_1$ classes and minimal degrees},
Title_Html = {Π01 classes and minimal degrees},
Volume = {87},
Year = {1997}}
@article{haught.slaman:1997,
Author = {Haught, Christine Ann and Slaman, Theodore A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {68Q15 (03D30)},
Mrnumber = {98h:68087},
Mrreviewer = {Rodney G. Downey},
Note = {Fifth Asian Logic Conference (Singapore, 1993)},
Number = {1},
Pages = {139--152},
Title = {Automorphisms in the {P}{T}{I}{M}{E}-{T}uring degrees of recursive sets},
Volume = {84},
Year = {1997}}
@article{slaman.woodin:1997,
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Coden = {AMLOEH},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D30 (03D35)},
Mrnumber = {98m:03089},
Mrreviewer = {A. Ku{\v{c}}era},
Note = {Sacks Symposium (Cambridge, MA, 1993)},
Number = {4-5},
Pages = {255--267},
Title = {Definability in the enumeration degrees},
Volume = {36},
Year = {1997}}
@article{calhoun.slaman:1996,
Author = {Calhoun, William C. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D20},
Mrnumber = {98g:03100},
Mrreviewer = {Michael Stob},
Number = {4},
Pages = {1364--1379},
Title = {The {$\Pi^0_2$} enumeration degrees are not dense},
Title_Html = {The Π02 enumeration degrees are not dense},
Volume = {61},
Year = {1996}}
@book{cooper.slaman.ea:1996,
Address = {Cambridge},
Editor = {Cooper, S. B. and Slaman, T. A. and Wainer, S. S.},
Isbn = {0-521-55736-4},
Mrclass = {03Dxx)},
Mrnumber = {97a:03003},
Note = {Directions in recursion theory},
Pages = {viii+347},
Publisher = {Cambridge University Press},
Title = {Computability, enumerability, unsolvability},
Year = {1996}}
@article{groszek.mytilinaios.ea:1996,
Author = {Groszek, Marcia J. and Mytilinaios, Michael E. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D25 (03C62)},
Mrnumber = {97k:03054},
Mrreviewer = {Peter G. Hinman},
Number = {2},
Pages = {450--467},
Title = {The {S}acks density theorem and {$\Sigma_2$}-bounding},
Title_Html = {The Sacks density theorem and Σ2-bounding},
Volume = {61},
Year = {1996}}
@incollection{mytilinaios.slaman:1996,
Address = {Cambridge},
Author = {Mytilinaios, Michael E. and Slaman, Theodore A.},
Booktitle = {Computability, enumerability, unsolvability},
Mrclass = {03B30},
Mrnumber = {97i:03036},
Mrreviewer = {Andreas Weiermann},
Pages = {205--218},
Publisher = {Cambridge Univ. Press},
Series = {London Math. Soc. Lecture Note Ser.},
Title = {On a question of {B}rown and {S}impson},
Volume = {224},
Year = {1996}}
@article{nies.shore.ea:1996,
Author = {Nies, Andr{\'e} and Shore, Richard A. and Slaman, Theodore A.},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {98g:03105},
Mrreviewer = {Michael Stob},
Number = {4},
Pages = {392--404},
Title = {Definability in the recursively enumerable degrees},
Volume = {2},
Year = {1996}}
@article{seetapun.slaman:1995,
Abstract = {We show that, for every partition F of the pairs of natural numbers and for
every set C, if C is not recursive in F then there is an
infinite set H, such that H is homogeneous for F and C
is not recursive in H. We conclude that the formal statement of Ramsey's
Theorem for Pairs is not strong enough to prove ACA0, the
comprehension scheme for arithmetical formulas, within the base theory
RCA0, the comprehension scheme for recursive formulas. We also
show that Ramsey's Theorem for Pairs is strong enough to prove some sentences in
first order arithmetic which are not provable within RCA0. In
particular, Ramsey's Theorem for Pairs is not conservative over
RCA0 for Π01-sentences.},
Author = {Seetapun, David and Slaman, Theodore A.},
Coden = {NDJFAM},
Fjournal = {Notre Dame Journal of Formal Logic},
Issn = {0029-4527},
Journal = {Notre Dame J. Formal Logic},
Mrclass = {03F35 (03C62)},
Mrnumber = {96k:03136},
Mrreviewer = {Roman Murawski},
Note = {Special Issue: Models of arithmetic},
Number = {4},
Pages = {570--582},
Title = {On the strength of {R}amsey's theorem},
Volume = {36},
Year = {1995}}
@article{slaman.soare:1995,
Author = {Slaman, Theodore A. and Soare, Robert I.},
Coden = {PNASA6},
Fjournal = {Proceedings of the National Academy of Sciences of the United States of America},
Issn = {0027-8424},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Mrclass = {03D25 (03D30)},
Mrnumber = {99i:03048},
Mrreviewer = {Michael Stob},
Number = {2},
Pages = {617--621},
Title = {Algebraic aspects of the computably enumerable degrees},
Volume = {92},
Year = {1995}}
@article{fortnow.gasarch.ea:1994,
Abstract = {Most theories of learning consider inferring a function f from either (1)
observations about f or, (2) questions about f. We consider a
scenario whereby the learner observes f and asks queries to some set
A. If I is a notion of learning then I[A] is the set
of concept classes I-learnable by an inductive inference machine with
oracle A. A and B are I-equivalent if
I[A] = I[B]. The equivalence classes induced are the
degrees of inferability. We prove several results about when these degrees
are trivial, and when the degrees are omniscient (i.e., the set of recursive
functions is learnable). },
Annote = {Subsumes the COLT paper by Gasarch and Pleszkoch entitled {\it Learning via
Queries to an Oracle}},
Annote_Html = {Subsumes the COLT paper by Gasarch and Pleszkoch entitled Learning via Queries to an Oracle},
Author = {L. Fortnow and W. Gasarch and S. Jain and E. Kinber and M. Kummer and S. Kurtz and M. Pleszkoch and T. Slaman and R. Solovay and F. Stephan},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {68Q32 (03D30)},
Mrnumber = {95f:03062},
Mrreviewer = {Costic{\u{a}} Cazacu},
Number = {3},
Pages = {231--276},
Title = {Extremes in the degrees of inferability},
Volume = {66},
Year = {1994}}
@unpublished{groszek.slaman:1994,
Abstract = {We show that the transitivity of pointwise Turing reducibility on the recursively
enumerable sets of integers cannot be proven in $PA^- + I\Sigma_1$, first order
arithmetic with induction limited to $\Sigma_1$ predicates. We produce a example
of intransitivity in a nonstandard model of $PA^-+I\Sigma_1$ by a finite injury
priority construction.},
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Mrclass = {03F30 (03D25)},
Note = {preprint},
Title = {On {T}uring Reducibility},
Urls = {http://math.berkeley.edu/~slaman/papers/intransitivity.pdf},
Year = 1994}
@article{ash.knight.ea:1993,
Author = {Ash, C. J. and Knight, J. F. and Slaman, T. A.},
Fjournal = {Fundamenta Mathematicae},
Issn = {0016-2736},
Journal = {Fund. Math.},
Mrclass = {03C57 (03D45)},
Mrnumber = {94h:03062},
Mrreviewer = {Yu. G. Ventsov},
Number = {2},
Pages = {147--161},
Title = {Relatively recursive expansions. {II}},
Volume = {142},
Year = {1993}}
@article{jockusch.slaman:1993,
Author = {Jockusch, Jr., Carl G. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30},
Mrnumber = {94d:03084},
Mrreviewer = {Marius Zimand},
Number = {1},
Pages = {193--204},
Title = {On the {$\Sigma_2$}-theory of the upper semilattice of {T}uring degrees},
Title_Html = {On the Σ2-theory of the upper semilattice of Turing degrees},
Volume = {58},
Year = {1993}}
@article{shore.slaman:1993,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {94i:03089},
Mrreviewer = {Steffen Lempp},
Number = {3},
Pages = {824--859},
Title = {Working below a high recursively enumerable degree},
Volume = {58},
Year = {1993}}
@inproceedings{cholak.downey.ea:1992,
Author = {Cholak, P. and Downey, R. and Fortnow, L. and Gasarch, W. and Kinber, E. and Kummer, M. and Kurtz, S. and Slaman, T.},
Booktitle = {Fifth Annual Conference on Computational Learning Theory},
Mrclass = {68Q32 (03D30)},
Pages = {180--192},
Publisher = {ACM},
Title = {Degrees of Inferability},
Year = {1992}}
@article{downey.slaman:1992,
Author = {Downey, Rod and Slaman, Theodore A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D50 (03D25)},
Mrnumber = {93g:03042},
Mrreviewer = {Thomas McLaughlin},
Number = {1-3},
Pages = {221--237},
Title = {On co-simple isols and their intersection types},
Volume = {56},
Year = {1992}}
@incollection{maass.slaman:1992,
Address = {New York},
Author = {Maass, Wolfgang and Slaman, Theodore A.},
Booktitle = {Logic from computer science (Berkeley, CA, 1989)},
Mrclass = {03D15 (68Q15)},
Mrnumber = {94g:03081},
Mrreviewer = {Alexey P. Stolboushkin},
Pages = {359--372},
Publisher = {Springer},
Series = {Math. Sci. Res. Inst. Publ.},
Title = {Splitting and density for the recursive sets of a fixed time complexity},
Volume = {21},
Year = {1992}}
@article{maass.slaman:1992*b,
Author = {Maass, Wolfgang and Slaman, Theodore A.},
Coden = {JCSSBM},
Fjournal = {Journal of Computer and System Sciences},
Issn = {0022-0000},
Journal = {J. Comput. System Sci.},
Mrclass = {68Q15 (03D15)},
Mrnumber = {93h:68049},
Mrreviewer = {Rodney G. Downey},
Number = {2},
Pages = {168--192},
Title = {The complexity types of computable sets},
Volume = {44},
Year = {1992}}
@article{shore.slaman:1992,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Coden = {TCSDI},
Fjournal = {Theoretical Computer Science},
Issn = {0304-3975},
Journal = {Theoret. Comput. Sci.},
Mrclass = {03D30 (03D15 03D20 68Q15)},
Mrnumber = {93e:03061},
Mrreviewer = {Marius Zimand},
Number = {2},
Pages = {263--284},
Title = {The p-{T}-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory},
Volume = {97},
Year = {1992}}
@article{hinman.slaman:1991,
Author = {Hinman, Peter G. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30},
Mrnumber = {93b:03072},
Mrreviewer = {J. C. Owings, Jr.},
Number = {2},
Pages = {563--591},
Title = {Jump embeddings in the {T}uring degrees},
Volume = {56},
Year = {1991}}
@inproceedings{slaman.solovay:1991,
Address = {Los Altos, CA},
Author = {Slaman, Theodore A. and Solovay, Robert M.},
Booktitle = {Fourth Annual Workshop on Computational Learning Theory},
Mrclass = {68Q32},
Pages = {379--383},
Publisher = {Morgan Kaufman},
Title = {When oracles do not help},
Year = {1991}}
@inproceedings{slaman:1991,
Address = {Tokyo},
Author = {Slaman, Theodore A.},
Booktitle = {Proceedings of the International Congress of Mathematicians, Vol.\ I, II (Kyoto, 1990)},
Mrclass = {03D30},
Mrnumber = {93b:03074},
Mrreviewer = {Decheng Ding},
Pages = {303--316},
Publisher = {Math. Soc. Japan},
Title = {Degree structures},
Year = {1991}}
@article{slaman:1991*b,
Author = {Slaman, Theodore A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {92e:03061},
Mrreviewer = {J. C. Owings, Jr.},
Note = {International Symposium on Mathematical Logic and its Applications (Nagoya, 1988)},
Number = {1-2},
Pages = {155--179},
Title = {The density of infima in the recursively enumerable degrees},
Volume = {52},
Year = {1991}}
@incollection{maass.slaman:1990,
Address = {Berlin},
Author = {Maass, Wolfgang and Slaman, Theodore A.},
Booktitle = {Recursion theory week (Oberwolfach, 1989)},
Mrclass = {03D15 (03D20 68Q15)},
Mrnumber = {91k:03103},
Mrreviewer = {R. Verbeek},
Pages = {297--322},
Publisher = {Springer},
Series = {Lecture Notes in Math.},
Title = {On the relationship between the complexity, the degree, and the extension of a computable set},
Volume = {1432},
Year = {1990}}
@article{sacks.slaman:1990,
Author = {Sacks, Gerald E. and Slaman, Theodore A.},
Coden = {PLMTAL},
Fjournal = {Proceedings of the London Mathematical Society. Third Series},
Issn = {0024-6115},
Journal = {Proc. London Math. Soc. (3)},
Mrclass = {03D60 (03E15)},
Mrnumber = {91b:03078},
Mrreviewer = {Dag Normann},
Number = {3},
Pages = {417--443},
Title = {Generalized hyperarithmetic theory},
Volume = {60},
Year = {1990}}
@article{shinoda.slaman:1990,
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Coden = {JCSSBM},
Fjournal = {Journal of Computer and System Sciences},
Issn = {0022-0000},
Journal = {J. Comput. System Sci.},
Mrclass = {03D15 (03D30 68Q15)},
Mrnumber = {92b:03049},
Mrreviewer = {Rodney G. Downey},
Number = {3},
Pages = {321--366},
Title = {On the theory of the {PTIME} degrees of the recursive sets},
Volume = {41},
Year = {1990}}
@article{shore.slaman:1990,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Coden = {AMLOEH},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D25},
Mrnumber = {91a:03091},
Mrreviewer = {Michael Stob},
Number = {3},
Pages = {201--211},
Title = {Working below a low${}_2$ recursively enumerable degree},
Title_Html = {Working below a low2 recursively enumerable degree},
Volume = {29},
Year = {1990}}
@article{ash.knight.ea:1989,
Author = {Ash, Chris and Knight, Julia and Manasse, Mark and Slaman, Theodore},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03C57},
Mrnumber = {90d:03065},
Mrreviewer = {Andrey Morozov},
Number = {3},
Pages = {195--205},
Title = {Generic copies of countable structures},
Volume = {42},
Year = {1989}}
@article{downey.slaman:1989,
Author = {Downey, R. G. and Slaman, T. A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {90f:03075},
Mrreviewer = {Christine Ann Haught},
Number = {2},
Pages = {119--152},
Title = {Completely mitotic r.e.\ degrees},
Volume = {41},
Year = {1989}}
@article{lempp.slaman:1989,
Author = {Lempp, Steffen and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {90f:03077},
Mrreviewer = {Anne Leggett},
Number = {2},
Pages = {376--395},
Title = {A limit on relative genericity in the recursively enumerable sets},
Volume = {54},
Year = {1989}}
@inproceedings{maass.slaman:1989,
Author = {Maass, W. and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Mrclass = {03D15 (68Q15)},
Title = {The Complexity Types of Computable Sets},
Year = {1989}}
@incollection{maass.slaman:1989*b,
Address = {Amsterdam},
Author = {Maass, Wolfgang and Slaman, Theodore A.},
Booktitle = {Logic Colloquium '88 (Padova, 1988)},
Mrclass = {03D15 (68Q15)},
Mrnumber = {1 015 320},
Pages = {79--89},
Publisher = {North-Holland},
Series = {Stud. Logic Found. Math.},
Title = {Some problems and results in the theory of actually computable functions (preliminary abstract)},
Volume = {127},
Year = {1989}}
@incollection{maass.slaman:1989*c,
Address = {New York},
Author = {Maass, Wolfgang and Slaman, Theodore A.},
Booktitle = {Fundamentals of computation theory (Szeged, 1989)},
Mrclass = {03D15 (68Q15)},
Mrnumber = {1 033 560},
Pages = {318--326},
Publisher = {Springer},
Series = {Lecture Notes in Comput. Sci.},
Title = {Extensional properties of sets of time bounded complexity (extended abstract)},
Volume = {380},
Year = {1989}}
@proceedings{shinoda.slaman.ea:1989,
Address = {Berlin},
Booktitle = {Proceedings of the Logic Meeting held at Kyoto University, Kyoto, August 3-6, 1987},
Editor = {Shinoda, J. and Slaman, T. A. and Tugu{\'e}, T.},
Isbn = {3-540-51527-5},
Mrclass = {03-06},
Mrnumber = {90d:03007},
Pages = {vi+222},
Publisher = {Springer-Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Mathematical logic and applications},
Volume = {1388},
Year = {1989}}
@incollection{shinoda.slaman:1989,
Address = {Berlin},
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Booktitle = {Mathematical logic and applications (Kyoto, 1987)},
Mrclass = {03D65 (03D30 03E50)},
Mrnumber = {90k:03044},
Mrreviewer = {Peter G. Hinman},
Pages = {153--177},
Publisher = {Springer},
Title = {The continuum hypothesis and the theory of the {K}leene degrees},
Volume = {1388},
Year = {1989}}
@inproceedings{shore.slaman:1989,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Mrclass = {03D15 (03D30 68Q15)},
Title = {The {P}-{T}-Degrees of the Recursive Sets: Lattice Embeddings, Extensions of Embeddings and the Two Quantifier Theory (Extended Abstract)},
Year = {1989}}
@article{slaman.steel:1989,
Author = {Slaman, Theodore A. and Steel, John R.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30 (03D25)},
Mrnumber = {90c:03034},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {1},
Pages = {160--176},
Title = {Complementation in the {T}uring degrees},
Volume = {54},
Year = {1989}}
@incollection{slaman.woodin:1989,
Address = {Berlin},
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Booktitle = {Mathematical logic and applications (Kyoto, 1987)},
Mrclass = {03F30 (03D25 03D30)},
Mrnumber = {91j:03075},
Mrreviewer = {R. A. Di Paola},
Pages = {178--188},
Publisher = {Springer},
Series = {Lecture Notes in Math.},
Title = {{$\Sigma_1$}-collection and the finite injury priority method},
Title_Html = {Σ1-collection and the finite injury priority method},
Volume = {1388},
Year = {1989}}
@incollection{slaman:1989,
Address = {Amsterdam},
Author = {Slaman, Theodore A.},
Booktitle = {Logic Colloquium '88 (Padova, 1988)},
Mrclass = {03D15},
Mrnumber = {1 015 322},
Pages = {111--112},
Publisher = {North-Holland},
Series = {Stud. Logic Found. Math.},
Title = {On bounded time {T}uring reducibility on the recursive sets},
Volume = {127},
Year = {1989}}
@article{mytilinaios.slaman:1988,
Author = {Mytilinaios, Michael E. and Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30 (03F30)},
Mrnumber = {88m:03066},
Number = {1},
Pages = {212--221},
Title = {{$\Sigma_2$}-collection and the infinite injury priority method},
Title_Html = {Σ2-collection and the infinite injury priority method},
Volume = {53},
Year = {1988}}
@inproceedings{shinoda.slaman:1988,
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Mrclass = {03D15 (03D30 68Q15)},
Title = {On the Theory of the {PTIME} Degrees of the Recursive Sets},
Year = {1988}}
@incollection{slaman.steel:1988,
Address = {Berlin},
Author = {Slaman, Theodore A. and Steel, John R.},
Booktitle = {Cabal Seminar 81-85},
Mrclass = {03D30 (03E60)},
Mrnumber = {89m:03033},
Mrreviewer = {Peter G. Hinman},
Pages = {37--55},
Publisher = {Springer},
Series = {Lecture Notes in Math.},
Title = {Definable functions on degrees},
Volume = {1333},
Year = {1988}}
@article{sacks.slaman:1987,
Author = {Sacks, G. E. and Slaman, T. A.},
Coden = {ADMTA4},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. in Math.},
Mrclass = {03D60 (03E40)},
Mrnumber = {88m:03070},
Mrreviewer = {Andreas Blass},
Number = {1},
Pages = {1--30},
Title = {Inadmissible forcing},
Volume = {66},
Year = {1987}}
@article{slaman.woodin:1986,
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Coden = {IJMTAW},
Fjournal = {Illinois Journal of Mathematics},
Issn = {0019-2082},
Journal = {Illinois J. Math.},
Mrclass = {03D28},
Mrnumber = {87m:03061},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {2},
Pages = {320--334},
Title = {Definability in the {T}uring degrees},
Volume = {30},
Year = {1986}}
@article{slaman:1986,
Author = {Slaman, T. A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03C70},
Mrnumber = {87f:03098},
Number = {2},
Pages = {453--461},
Title = {{$\Sigma_1$}-definitions with parameters},
Title_Html = {Σ1-definitions with parameters},
Volume = {51},
Year = {1986}}
@article{slaman:1986*b,
Author = {Slaman, Theodore A.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30},
Mrnumber = {88a:03101},
Number = {2},
Pages = {352--359},
Title = {On the {K}leene degrees of {$\Pi^1_1$} sets},
Title_Html = {On the Kleene degrees of Π11 sets},
Volume = {51},
Year = {1986}}
@incollection{slaman:1985,
Address = {Berlin},
Author = {Slaman, Theodore A.},
Booktitle = {Recursion theory week (Oberwolfach, 1984)},
Mrclass = {03D65},
Mrnumber = {87f:03133},
Mrreviewer = {Dag Normann},
Pages = {372--404},
Publisher = {Springer},
Series = {Lecture Notes in Math.},
Title = {Reflection and the priority method in {$E$}-recursion theory},
Volume = {1141},
Year = {1985}}
@incollection{slaman:1985*b,
Address = {Providence, RI},
Author = {Slaman, Theodore A.},
Booktitle = {Recursion theory (Ithaca, N.Y., 1982)},
Mrclass = {03D25},
Mrnumber = {87f:03118},
Pages = {195--213},
Publisher = {Amer. Math. Soc.},
Series = {Proc. Sympos. Pure Math.},
Title = {The {$E$}-recursively enumerable degrees are dense},
Volume = {42},
Year = {1985}}
@article{slaman:1985*c,
Author = {Slaman, Theodore A.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D65 (03E40)},
Mrnumber = {86m:03079},
Mrreviewer = {Andreas Blass},
Number = {1},
Pages = {79--106},
Title = {Reflection and forcing in {$E$}-recursion theory},
Volume = {29},
Year = {1985}}
@article{groszek.slaman:1983,
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D30 (03E35)},
Mrnumber = {85b:03069},
Mrreviewer = {Stephen G. Simpson},
Number = {2},
Pages = {579--588},
Title = {Independence results on the global structure of the {T}uring degrees},
Volume = {277},
Year = {1983}}
@article{slaman:1983,
Author = {Slaman, Theodore A.},
Coden = {NGMJA2},
Fjournal = {Nagoya Mathematical Journal},
Issn = {0027-7630},
Journal = {Nagoya Math. J.},
Mrclass = {03D65 (03E35)},
Mrnumber = {85b:03081},
Mrreviewer = {Stephen G. Simpson},
Pages = {107--120},
Title = {The extended plus-one hypothesis--a relative consistency result},
Volume = {92},
Year = {1983}}
@phdthesis{slaman:1981,
Author = {Slaman, Theodore A.},
Mrclass = {03D65},
School = {Harvard University},
Title = {Aspects of E-Recursion Theory},
Year = 1981}
@article{gross.halbert.ea:1975,
Author = {E. E. Gross and M. L. Halbert and D. C. Hensley and D. L. Hillis and C. R. Bingham and Alan Scott and F. Todd Baker and T. Slaman},
Journal = {Bull. Am. Phys. Soc.},
Pages = {1192},
Title = {Elastic Scattering of 70 {M}e{V}12{C} Ions from Even {N}d Isotopes},
Volume = 20,
Year = 1975}
@article{hillis.gross.ea:1975,
Author = {D. L. Hillis and E. E. Gross and D. C. Hensley and C. R. Bingham and Alan Scott and F. Todd Baker and T. A. Slaman},
Journal = {Bull. Am. Phys. Soc.},
Pages = {1192},
Title = {Shape Effects in the Inelastic Scattering of 70 {M}e{V}12{C} Ions from 142, 144, 146, 148, 150 {N}d},
Volume = 20,
Year = 1975}