Citations of:
Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers
Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co. (1989)
Add citations
You must login to add citations.


We show that there is a low Tupper bound for the class of Ktrivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ Tdegrees for which there is a low Tupper bound. 

The GrätzerSchmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show thatthe set of indices of computable lattices that are complete is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{69pt} \begin{document}$$\Pi ^1_1$$\end{document}complete;the set of indices of computable lattices that are algebraic is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{69pt} \begin{document}$$\Pi ^1_1$$\end{document}complete;the set of compact elements of a computable (...) 

This paper aims to shed light on the broader significance of Frege’s logicism against the background of discussing and comparing Wittgenstein’s ‘showing/saying’distinction with Brandom’s idiom of logic as the enterprise of making the implicit rules of our linguistic practices explicit. The main thesis of this paper is that the problem of Frege’s logicism lies deeper than in its inconsistency : it lies in the basic idea that in arithmetic one can, and should, express everything that is implicitly presupposed so that (...) 



. We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years. 

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of (...) 

Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations. 

This article defends a modest version of the Physical ChurchTuring thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) 

Nykyaikaisen logiikan keskeisenä tutkimuskohteena ovat erilaiset formalisoidut teoriat. Erityisesti vuosisadan vaihteen aikoihin matematiikan perusteiden tutkimuksessa ilmaantuneiden hämmentävien paradoksien (Russell 1902, 1903) jälkeen (ks. kuitenkin jo Frege 1879, Dedekind 1888, Peano 1889; vrt. Wang 1957) keskeiset matemaattiset teoriat on pyritty tällaisten vaikeuksien välttämiseksi uudelleen muotoilemaan täsmällisesti keinotekoisessa symbolikielessä, jonka lauseenmuodostussäännöt on täsmällisesti ja yksikäsitteisesti määrätty. Edelleen teoriat on pyritty aksiomatisoimaan, ts. on pyritty antamaan joukko peruslauseita, joista kaikki muut  tai ainakin mahdollisimman monet  teorian todet lauseet voidaan loogisesti johtaa tarkoin (...) 

Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a nonrecursive oracle. This paper combines these two types — it considers three basic models of queries to a teacher (QEX[Succ], QEX[ The results for each of these three models of queryinference are the same: If an oracle is omniscient for queryinference then it is already omniscient for EX. There is an oracle of trivial EXdegree, which allows nontrivial queryinference. Furthermore, (...) 

Mathematics is traditionally considered being an apriori discipline consisting of purely analytic propositions. The aim of the present paper is to offer arguments against this entrenched view and to draw attention to the experiential dimension of mathematical knowledge. Following Husserl’s interpretation of physical knowledge as knowledge constituted by the use of instruments, I am trying to interpret mathematical knowledge also as acknowledge based on instrumental experience. This interpretation opens a new view on the role of the logicist program, both in (...) 

The truthtable degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domainrandom strings, and show that the truthtable degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truthtable incomplete versions of these sets, namely retraceability and approximability. We give priorityfree constructions of bounded truthtable chains and bounded truthtable antichains inside the truthtable complete degree (...) 

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) 

The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...) 

We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any nontrivial upper cone of Turing degrees and show that the hypersimplefree c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them as the c.e. (...) 

Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof. 

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low2. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both (...) 

Polynomial clone reducibilities are generalizations of the truthtable reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and ${\fancyscript{C}_{1} (...) 

Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic. However, her factor is unnatural in the sense that it is constructed in an ad hoc manner. We present a more natural example of such a factor. We also show that the theory of every nontrivial factor of the Medvedev lattice is contained in Jankov’s logic, the deductive closure of IPC plus the weak law of the excluded middle ¬p∨¬¬p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) 

We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by MartinLöf, Schnorr, and others. We prove that the class of sets constructible by r.e.constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursiontheoretic reducibilities below K. We note that (...) 

The article deals with Cantor's argument for the nondenumerability of reals somewhat in the spirit of Lakatos' logic of mathematical discovery. At the outset Cantor's proof is compared with some other famous proofs such as Dedekind's recursion theorem, showing that rather than usual proofs they are resolutions to do things differently. Based on this I argue that there are "ontologically" safer ways of developing the diagonal argument into a fullfledged theory of continuum, concluding eventually that famous semantic paradoxes based on (...) 

We consider structures of the form, where Φ and Ψ are nonempty sets and is a relation whose domain is Ψ. In particular, by using a special kind of a diagonal argument, we prove that if Φ is a denumerable recursive set, Ψ is a denumerable r.e. set, and R is an r.e. relation, then there exists an infinite family of infinite recursive subsets of Φ which are not R images of elements of Ψ. The proof is a very elementary (...) 

Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to firstorder logic, using the notion of a firstorder hyperdoctrine from categorical logic, to a structure which we will call the hyperdoctrine (...) 

We give natural examples of factors of the Muchnik lattice which capture intuitionistic propositional logic , arising from the concepts of lowness, 1genericity, hyperimmunefreeness and computable traceability. This provides a purely computational semantics for IPC. 

We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them. 

In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice (...) 

We say that A≤LRB if every Brandom set is Arandom with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions. 

This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His wellknown book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe bestknown journal of the area, which he edited for several decades This (...) 



In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multivalued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semilattice. It turns out that parallelization is a closure operator for this semilattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...) 



The main result of this paper states that the isomorphism problem for ωautomatic trees of finite height is at least has hard as secondorder arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies showing that the isomorphism problem for ωautomatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ωautomatic trees of finite height is recursively equivalent with secondorder arithmetic. On the way to (...) 

The article presents several examples of different mathematical structures and interprets their properties related to the existence of universal functions. In this context, relations between the problem of totality of elements and possible forms of universal functions are analyzed. Furthermore, some global and local aspects of the mentioned functional systems are distinguished and compared. In addition, the paper attempts to link universality and totality with the dynamic and static properties of mathematical objects and to consider the problem of limitations in (...) 

In this paper we discuss the following contributions to recursion theory made by John Myhill: two sets are recursively isomorphic iff they are oneone equivalent; two sets are recursively isomorphic iff they are recursively equivalent and their complements are also recursively equivalent; every two creative sets are recursively isomorphic; the recursive analogue of the Cantor–Bernstein theorem; the notion of a combinatorial function and its use in the theory of recursive equivalence types. 

This paper provides characterisations of the equational theory of the PER model of a typed lambda calculus with inductive types. The characterisation may be cast as a full abstraction result; in other words, we show that the equations between terms valid in this model coincides with a certain syntactically defined equivalence relation. Along the way we give other characterisations of this equivalence; from below, from above, and from a domain model, a version of the KreiselLacombeShoenfield theorem allows us to transfer (...) 

We define and study a new notion called kimmunity that lies between immunity and hyperimmunity in strength. Our interest in kimmunity is justified by the result that θ does not ktt reduce to a kimmune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not bttreduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new (...) 

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and (...) 

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable nonmonotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KLstochastic if there is no computable nonmonotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether MartinLöf randomness is the same as KLrandomness. Our first (...) 

In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤r between subsets of the natural numbers, where ≤r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown (...) 

We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees. 

In 1969, De Jongh proved the “maximality” of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using prooftheoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all trueΠ 2 0 (...) 

We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since AmbosSpies [1] has shown that, in the partial ordering of the c.e. identitybounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1shift a+1a+1 of a where a+1 

Using only propositional connectives and the provability predicate of a Σ1sound theory T containing Peano Arithmetic we define recursively enumerable relations that are complete for specific natural classes of relations, as the class of all r. e. relations, and the class of all strict partial orders. We apply these results to give representations of these classes in T by means of formulas. 





Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1]. 

This paper investigates the ontological presuppositions of quantifier logic. It is seen that the actual infinite, although present in the usual completeness proofs, is not needed for a proper semantic foundation. Additionally, quantifier logic can be given an adequate formulation in which neither the notion of individual nor that of a predicate appears. 

We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into (...) 

Let ℸ be the set of Gödel numbers Gn of function symbols f such that PRA ⊢ and let γ be the function such that equation imageWe prove: The r. e. set ℸ is mcomplete; the function γ is not primitive recursive in any class of functions {f1, f2, ⃛} so long as each fi has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ. 