I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s more, I (...) argue that these counterpossibles don’t just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models. (shrink)

If S is a finite set, let |S| be the cardinality of S. We show that if $m \in \omega, A \subseteq \omega, B \subseteq \omega$ , and |{i: 1 ≤ i ≤ 2 m & x i ∈ A}| can be computed by an algorithm which, for all x 1 ,...,x 2 m , makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.

Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare (...) and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open. (shrink)

Acceptable programming systems have many nice properties like s-m-n-Theorem, Composition and Kleene Recursion Theorem. Those properties are sometimes called control structures, to emphasize that they yield tools to implement programs in programming systems. It has been studied, among others by Riccardi and Royer, how these control structures influence or even characterize the notion of acceptable programming system. The following is an investigation, how these control structures behave in the more general setting of complete numberings as defined by Mal'cev and Eršov.

Acceptable programming systems have many nice properties like s-m-n-Theorem, Composition and Kleene Recursion Theorem. Those properties are sometimes called control structures, to emphasize that they yield tools to implement programs in programming systems. It has been studied, among others by Riccardi and Royer, how these control structures influence or even characterize the notion of acceptable programming system. The following is an investigation, how these control structures behave in the more general setting of complete numberings as defined by Mal'cev and Eršov.

If one regards an ordinal number as a generalization of a counting number, then it is natural to begin thinking in terms of computations on sets of ordinal numbers. This is precisely what Takeuti [22] had in mind when he initiated the study of recursive functions on ordinals. Kreisel and Sacks [9] too developed an ordinal recursion theory, called metarecursion theory, which specialized to the initial segment of the ordinals bounded by.The notion of admissibility was introduced by Kripke [11] and (...) Platek [14] and served to generalize metarecursion theory. Kripke called ordinal α admissible if it satisfied certain closure properties of infinitary computations. It was shown that admissibility could be equivalently formulated in terms of the replacement schema of ZF set theory and that α =is an admissible ordinal. The study of a recursion theory on an initial segment of the ordinals bounded by some arbitrary admissible α became known as α-recursion theory.Kripke [10] employed a Gödel numbering scheme to perform an arithmetiza-tion of α -recursion theory and created an analogue to Kleene'sT-predicate of ordinary recursion theory. TheT-predicate then served as the basis for showing that analogues of the major results of unrelativized o.r.t. held in α-recursion theory; namely, the α-Enumeration Theorem,T Theorem, α-Recursion Theorem, and α-Universal Function Theorem. (shrink)

We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable. MSC: 03B40, 03D35.

It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible in (...) various senses. (shrink)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

A very simple many-valued predicate calculus is presented; a completeness theorem is proved and the arithmetical complexity of some notions concerning provability is determined.

§1. The mission of axiomatic set theory. What is set theory needed for in the foundations of mathematics? Why cannot we transact whatever foundational business we have to transact in terms of our ordinary logic without resorting to set theory? There are many possible answers, but most of them are likely to be variations of the same theme. The core area of ordinary logic is by a fairly common consent the received first-order logic. Why cannot it take care of itself? (...) What is it that it cannot do? A large part of every answer is probably that first-order logic cannot handle its own model theory and other metatheory. For instance, a first-order language does not allow the codification of the most important semantical concept, viz. the notion of truth, for that language in that language itself, as shown already in Tarski. In view of such negative results it is generally thought that one of the most important missions of set theory is to provide the wherewithal for a model theory of logic. For instance Gregory H. Moore asserts in his encyclopedia article “Logic and set theory” thatSet theory influenced logic, both through its semantics, by expanding the possible models of various theories and by the formal definition of a model; and through its syntax, by allowing for logical languages in which formulas can be infinite in length or in which the number of symbols is uncountable. (shrink)

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (∑ 0 4 , ∑ 0 3 ), i.e. isomorphic to the lattice of ∑ 0 4 sets together with a unary predicate selecting out exactly the ∑ 0 3 sets.

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the (...) theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers. (shrink)

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)