Last update:
Tue Mar 30 20:02:06 MDT 2021
Vasco Brattka and
Paola Bonizzoni and
S. Barry Cooper and
Benedikt Löwe and
Elvira Mayordomo Editorial . . . . . . . . . . . . . . . 1--2
Mathieu Hoyrup and
Cristóbal Rojas and
Klaus Weihrauch Computability of the Radon--Nikodym
Derivative . . . . . . . . . . . . . . . 3--13
Samuel Coskey and
Joel David Hamkins and
Russell Miller The Hierarchy of Equivalence Relations
on the Natural Numbers Under Computable
Reducibility . . . . . . . . . . . . . . 15--38
John M. Hitchcock Limitations of Efficient Reducibility to
the Kolmogorov Random Strings . . . . . 39--43
Philipp Schlicht and
Benjamin Seyfferth Tree Representations via Ordinal
Machines . . . . . . . . . . . . . . . . 45--57
Alastair A. Abbott and
Cristian S. Calude Von Neumann Normalisation of a Quantum
Random Number Generator . . . . . . . . 59--83
Denis R. Hirschfeldt and
Rebecca Weber Finite Self-Information . . . . . . . . 85--98
Peter A. Cholak and
Damir D. Dzhafarov and
Noah Schweber and
Richard A. Shore Computably Enumerable Partial Orders . . 99--107
Anthony Morphett Incompleteness, Approximation and
Relative Randomness . . . . . . . . . . 109--130
Takayuki Kihara Incomputability of Simply Connected
Planar Continua . . . . . . . . . . . . 131--152
Wolfgang Merkle and
Jason Teutsch Constant Compression and Random Weights 153--169
Alexander P. Kreuzer On the Strength of Weak Compactness . . 171--179
Anonymous Author Index Volume 1 (2012) . . . . . . 181--181
David Diamondstone and
Noam Greenberg and
Daniel Turetsky Natural Large Degree Spectra . . . . . . 1--8
Hannes Diener Weak König's Lemma Implies the Uniform
Continuity Theorem . . . . . . . . . . . 9--13
Kenshi Miyabe $ L^1 $-Computability, Layerwise
Computability and Solovay Reducibility 15--29
Hartmut Ehrig and
Claudia Ermel and
Falk Hüffner and
Rolf Niedermeier and
Olga Runge Confluence in Data Reduction: Bridging
Graph Transformation and Kernelization 31--49
Russell Miller and
Hans Schoutens Computably Categorical Fields via
Fermat's Last Theorem . . . . . . . . . 51--65
Dimiter Skordev On Some Computability Notions for Real
Functions . . . . . . . . . . . . . . . 67--73
François G. Dorais and
Jeffry Hirst and
Paul Shafer Reverse Mathematics and Algebraic Field
Extensions . . . . . . . . . . . . . . . 75--92
Jacob Carson and
Jesse Johnson and
Julia Knight and
Karen Lange and
Charles McCoy and
John Wallbaum The Arithmetical Hierarchy in the
Setting of $ \omega_1 $ . . . . . . . . 93--105
Shinnosuke Seki and
Yasushi Okuno On the Behavior of Tile Assembly System
at High Temperatures . . . . . . . . . . 107--124
Fernando Soler-Toscano and
Hector Zenil and
Jean-Paul Delahaye and
Nicolas Gauvrit Correspondence and Independence of
Numerical Evaluations of Algorithmic
Information Measures . . . . . . . . . . 125--140
Anonymous Author Index Volume 2 (2013) . . . . . . 141--142
Keng Meng Ng and
André Nies and
Frank Stephan The Complexity of Recursive Splittings
of Random Sets . . . . . . . . . . . . . 1--8
J. V. Tucker and
J. I. Zucker Computability of Operators on Continuous
and Discrete Time Streams . . . . . . . 9--44
Cameron Freer and
Bjò rn Kjos-Hanssen and
André Nies and
Frank Stephan Algorithmic Aspects of Lipschitz
Functions . . . . . . . . . . . . . . . 45--61
Stela Nikolova Shared thoughts on Ivan--Soskov
(1954--2013) . . . . . . . . . . . . . . 63--72
Johanna N. Y. Franklin and
Reed Solomon Degrees that Are Low for Isomorphism . . 73--89
Ryan C. Harkins and
John M. Hitchcock and
A. Pavan Strong Reductions and Isomorphism of
Complete Sets . . . . . . . . . . . . . 91--104
Wesley Calvert and
Valentina Harizanov and
Alexandra Shlapentokh Turing Degrees of Isomorphism Types of
Geometric Objects . . . . . . . . . . . 105--134
Cristina Bazgan and
Morgan Chopin and
André Nichterlein and
Florian Sikora Parameterized Inapproximability of
Target Set Selection and Generalizations 135--145
Anonymous Author Index Volume 3 (2014) . . . . . . 147--147
Matthias Schröder and
Victor Selivanov Hyperprojective hierarchy of
qcb$_0$-spaces . . . . . . . . . . . . . 1--17
Amir M. Ben-Amram Mortality of iterated piecewise affine
functions over the integers:
Decidability and complexity . . . . . . 19--56
Henry Towsner On maximum conservative extensions . . . 57--68
Ludovic Patey The complexity of satisfaction problems
in reverse mathematics . . . . . . . . . 69--84
Jack H. Lutz and
Neil Lutz Lines missing every random point . . . . 85--102
Kirill Gura and
Jeffry L. Hirst and
Carl Mummert On the existence of a connected
component of a graph . . . . . . . . . . 103--117
Charles M. Harris On limitwise monotonicity and maximal
block functions . . . . . . . . . . . . 119--139
Eric P. Astor Asymptotic density, immunity and
randomness . . . . . . . . . . . . . . . 141--158
Stanislav O. Speranski Some new results in monadic second-order
arithmetic . . . . . . . . . . . . . . . 159--174
Vasco Brattka and
Paola Bonizzoni and
Olivier Bournez and
Elvira Mayordomo Editorial . . . . . . . . . . . . . . . 1--1
Benedikt Löwe Barry Cooper (1943--2015): The engine of
\em Computability in Europe . . . . . . 3--11
Denis R. Hirschfeldt and
Carl G. Jockusch Jr. and
Timothy H. McNicholl and
Paul E. Schupp Asymptotic density and the coarse
computability bound . . . . . . . . . . 13--27
Sankha S. Basu and
Stephen G. Simpson Mass problems and intuitionistic
higher-order logic . . . . . . . . . . . 29--47
Albert A. Muchnik Strong and weak reducibility of
algorithmic problems1 . . . . . . . . . 49--59
Dag Normann On the Cantor--Bendixson rank of a set
that is searchable in Gödel's $T$ . . . . 61--74
Matthew de Brecht and
Matthias Schröder and
Victor Selivanov Base-complexity classifications of
qcb$_0$-spaces1 . . . . . . . . . . . . 75--102
Ian Herbert Lowness for integer-valued randomness 103--109
Mingzhong Cai and
Steffen Lempp and
Joseph S. Miller and
Mariya I. Soskova On Kalimullin pairs . . . . . . . . . . 111--126
Eric Faber and
Jaap van Oosten Effective operations of type 2 in PCAs 127--146
Rupert Hölzl and
Frank Stephan and
Liang Yu On Martin's pointed tree theorem . . . . 147--157
Arno Pauly On the topological aspects of the theory
of represented spaces . . . . . . . . . 159--180
Merlin Carl Randomness and degree theory for
infinite time register machines . . . . 181--196
Anonymous Author Index Volume 5 (2016) . . . . . . 197--197
Damir D. Dzhafarov and
Gregory Igusa Notions of robust information coding . . 105--124
Martin Huschenbett and
Alexander Kartzow and
Philipp Schlicht Pumping for ordinal-automatic structures
$^1$ . . . . . . . . . . . . . . . . . . 125--164
Oscar H. Ibarra and
Cewei Cui and
Zhe Dang and
Thomas R. Fischer Lossiness of communication channels
modeled by transducers . . . . . . . . . 165--181
Rica Gonen and
Anat Lerner Characterizing incentive compatible,
Pareto optimal and sufficiently
anonymous constrained combinatorial
mechanisms --- Two players case . . . . 183--208
Anonymous Author Index Volume 6 (2017) . . . . . . 209--209
Ludovic Patey Iterative forcing and hyperimmunity in
reverse mathematics . . . . . . . . . . 209--221
Merlin Carl Infinite time recognizability from
generic oracles and the recognizable
jump operator . . . . . . . . . . . . . 223--247
Lars Kristiansen On subrecursive representability of
irrational numbers . . . . . . . . . . . 249--276
Manindra Agrawal and
Diptarka Chakraborty and
Debarati Das and
Satyadev Nandakumar Dimension, pseudorandomness and
extraction of pseudorandomness . . . . . 277--305
Alexei Miasnikov and
Paul Schupp Computational complexity and the
conjugacy problem . . . . . . . . . . . 307--318
Emanuele Frittaion and
Ludovic Patey Coloring the rationals in reverse
mathematics . . . . . . . . . . . . . . 319--331
Arthur Milchior Undecidability of satisfiability of
expansions of FO[$<$] over words with a
FO[$+$]-definable set . . . . . . . . . 333--363
Francis Adams and
Douglas Cenzer Computability and categoricity of weakly
ultrahomogeneous structures . . . . . . 365--389
Timothy H. McNicholl Computable copies of $^\ell p$ . . . . . 391--408
Johanna N. Y. Franklin and
Dan Turetsky Lowness for isomorphism and degrees of
genericity . . . . . . . . . . . . . . . 1--6
Sam Sanders The Gandy--Hyland functional and a
computational aspect of nonstandard
analysis . . . . . . . . . . . . . . . . 7--43
Shuichi Hirahara and
Akitoshi Kawamura On characterizations of randomized
computation using plain Kolmogorov
complexity . . . . . . . . . . . . . . . 45--56
Zvonko Iljazovi\'c and
Bojan Pazek Computable intersection points . . . . . 57--99
Benedikt Löwe Preface to the special issue in memory
of S. Barry Cooper (1943--2015) . . . . 101--101
Richard Elwes and
Andy Lewis-Pye and
Benedikt Löwe and
Dugald Macpherson and
Dag Normann and
Andrea Sorbi and
Alexandra A. Soskova and
Mariya I. Soskova and
Peter van Emde Boas and
Stan Wainer S. Barry Cooper (1943--2015) . . . . . . 103--131
S. Barry Cooper and
Angsheng Li and
Mingji Xia Splitting and jump inversion in the
Turing degrees . . . . . . . . . . . . . 133--142
S. Barry Cooper and
James Gay and
Charles M. Harris and
Kyung Il Lee and
Anthony Morphett Linearisations and the Ershov hierarchy 143--169
George Barmpalias and
Andrew Lewis-Pye and
Angsheng Li Pointed computations and Martin-Löf
randomness . . . . . . . . . . . . . . . 171--177
Hristo A. Ganchev and
Mariya I. Soskova The jump hierarchy in the enumeration
degrees . . . . . . . . . . . . . . . . 179--188
Andrew E. M. Lewis-Pye The search for natural definability in
the Turing degrees . . . . . . . . . . . 189--235
Klaus Ambos-Spies Automorphism bases for the recursively
enumerable degrees . . . . . . . . . . . 237--258
Cristian S. Calude and
Monica Dumitrescu A probabilistic anytime algorithm for
the halting problem . . . . . . . . . . 259--271
Sanjay Jain and
Bakhadyr Khoussainov and
Frank Stephan Finitely generated semiautomatic groups 273--287
Diogo Poças and
Jeffery Zucker Analog networks on function data streams 301--322
Ludovic Patey Partial orders and immunity in reverse
mathematics . . . . . . . . . . . . . . 323--339
Spencer Backman and
Tony Huynh Transfinite Ford--Fulkerson on a finite
network . . . . . . . . . . . . . . . . 341--347
Matthew Wright Degrees of relations on ordinals . . . . 349--365
Joe Davidson and
Greg Michaelson Expressiveness, meanings and machines 367--394
Mark Armstrong and
Jeffery Zucker Notions of semicomputability in
topological algebras over the reals . . 1--26
Petr A. Golovach and
Matthew Johnson and
Barnaby Martin and
Daniël Paulusma and
Anthony Stewart Surjective $H$-colouring: New hardness
results . . . . . . . . . . . . . . . . 27--42
Lars Kristiansen On subrecursive representability of
irrational numbers, part II . . . . . . 43--65
Arnold Beckmann and
Sam Buss and
Sy-David Friedman and
Moritz Müller and
Neil Thapen Feasible set functions have small
circuits . . . . . . . . . . . . . . . . 67--98
Russell Miller Isomorphism and classification for
countable structures . . . . . . . . . . 99--117
John Longley Bar recursion is not computable via
iteration . . . . . . . . . . . . . . . 119--153
Eric P. Astor and
Denis R. Hirschfeldt and
Carl G. Jockusch Jr. Dense computability, upper cones, and
minimal pairs . . . . . . . . . . . . . 155--177
Timothy H. McNicholl and
Donald M. Stull The isometry degree of a computable copy
of $\ell p$ . . . . . . . . . . . . . . 179--189
Vasco Brattka and
Rod Downey and
Julia F. Knight and
Steffen Lempp Preface of the special issue for the
Oberwolfach Workshop on Computability
Theory 2018 . . . . . . . . . . . . . . 191--191
Uri Andrews and
Andea Sorbi Joins and meets in the structure of
ceers . . . . . . . . . . . . . . . . . 193--241
Ellen Chih and
Rod G. Downey Splitting theorems and low degrees . . . 243--252
Barbara F. Csima and
Damir D. Dzhafarov and
Denis R. Hirschfeldt and
Carl G. Jockusch, Jr. and
Reed Solomon and
Linda Brown Westrick The reverse mathematics of Hindman's
Theorem for sums of exactly two elements 253--263
Ekaterina Fokina and
Dino Rossegger and
Luca San Mauro Measuring the complexity of reductions
between equivalence relations . . . . . 265--280
Guido Gherardi and
Alberto Marcone and
Arno Pauly Projection operators in the Weihrauch
lattice . . . . . . . . . . . . . . . . 281--304
Noam Greenberg and
Rutger Kuyper and
Dan Turetsky Cardinal invariants, non-lowness
classes, and Weihrauch reducibility . . 305--346
Matthew Harrison-Trainor A first-order theory of Ulm type . . . . 347--358
Matthew Harrison-Trainor and
Bakh Khoussainov and
Daniel Turetsky Effective aspects of algorithmically
random structures . . . . . . . . . . . 359--375
Ulrich Kohlenbach On the reverse mathematics and Weihrauch
complexity of moduli of regularity and
uniqueness . . . . . . . . . . . . . . . 377--387
Henning Fernau and
Till Fluschnik and
Danny Hermelin and
Andreas Krebs and
Hendrik Molter and
Rolf Niedermeier Diminishable parameterized problems and
strict polynomial kernelization . . . . 1--24
Paul Shafer The strength of compactness for
countable complete linear orders . . . . 25--36
Peter Gerdes An $ \omega $-REA set forming a minimal
pair with $ 0 \sim '$ . . . . . . . . . 37--50
Pietro Milici A differential extension of Descartes'
foundational approach: a new balance
between symbolic and analog computation 51--83
Damir D. Dzhafarov and
Jun Le Goh and
Denis R. Hirschfeldt and
Ludovic Patey and
Arno Pauly Ramsey's theorem and products in the
Weihrauch degrees . . . . . . . . . . . 85--110
Reese Johnston Cantor--Bendixson ranks of effectively
closed sets in admissible recursion
theory . . . . . . . . . . . . . . . . . 111--125
Barbara F. Csima and
Michael Deveau and
Matthew Harrison-Trainor and
Mohammad Assem Mahmoud Degrees of categoricity above limit
ordinals . . . . . . . . . . . . . . . . 127--137
Lorenzo Carlucci and
Leszek Aleksander Ko\lodziejczyk and
Francesco Lepore and
Konrad Zdanowski New bounds on the strength of some
restrictions of Hindman's Theorem . . . 139--153
Cristian S. Calude and
Monica Dumitrescu A statistical anytime algorithm for the
Halting Problem . . . . . . . . . . . . 155--166
Vasco Brattka and
Damir D. Dzhafarov and
Alberto Marcone and
Arno Pauly Dagstuhl Seminar on Measuring the
Complexity of Computational Content 2018 167--168
Matthew de Brecht and
Arno Pauly and
Matthias Schröder Overt choice . . . . . . . . . . . . . . 169--191
Peter A. Cholak and
Damir D. Dzhafarov and
Denis R. Hirschfeldt and
Ludovic Patey Some results concerning the SRT22 vs.
COH problem . . . . . . . . . . . . . . 193--217
Caleb Davis and
Denis R. Hirschfeldt and
Jeffry Hirst and
Jake Pardo and
Arno Pauly and
Keita Yokoyama Combinatorial principles equivalent to
weak induction . . . . . . . . . . . . . 219--229
Jun Le Goh Compositions of multivalued functions 231--247
Peter Hertling Forests describing Wadge degrees and
topological Weihrauch degrees of certain
classes of functions and relations . . . 249--307
Jeffry L. Hirst Leaf management . . . . . . . . . . . . 309--314
Takako Nemoto A constructive proof of the dense
existence of nowhere-differentiable
functions in $ C[0, 1] $ . . . . . . . . 315--326
Victor Selivanov $Q$-Wadge degrees as free structures . . 327--341
Nikolay Bazhenov and
Ekaterina Fokina and
Dino Rossegger and
Luca San Mauro Degrees of bi-embeddable categoricity 1--16
Makoto Fujiwara Weihrauch and constructive reducibility
between existence statements . . . . . . 17--30
Sam Sanders Nets and reverse mathematics . . . . . . 31--62
Michal Konecný and
Eike Neumann Representations and evaluation
strategies for feasibly approximable
functions . . . . . . . . . . . . . . . 63--89