A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)
We use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing reducibility.
We advance a model of human probability judgment and apply it to the design of an extrapolation algorithm. Such an algorithm examines a person's judgment about the likelihood of various statements and is then able to predict the same person's judgments about new statements. The algorithm is tested against judgments produced by thirty undergraduates asked to assign probabilities to statements about mammals.
A splitting A1A2 = A of an r.e. set A is called a Friedberg splitting if for any r.e. set W with W — A not r.e., W — Ai≠0 for I = 1,2. In an earlier paper, the authors investigated Friedberg splittings of maximal sets and showed that they formed an orbit with very interesting degree-theoretical properties. In the present paper we continue our investigations, this time analyzing Friedberg splittings and in particular their orbits and degrees for various classes (...) of r.e. sets. (shrink)
A paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.
We examine the prospects for finding “best possible” or “ideal” computing machines for various learning tasks. For this purpose, several precise senses of “ideal machine” are considered within the context of formal learning theory. Generally negative results are provided concerning the existence of ideal learning‐machines in the senses considered.