Selected Papers of
Geoff LaForte

The isolated d.r.e. degrees are dense in the r.e. degrees
Mathematical Logic Quarterly, vol. 42, No.2
A properly d.c.e. degree represents a class of information that can be computably approximated, but only by an algorithm which is explicitly allowed to change its mind at most once on certain values which appeared to already be fixed at an earlier point in the computation. Here I present an algorithm for constructing properly d.c.e. degrees with maximal computably enumerable degrees below them and use this method to show that such degrees occur in every nondegenerate interval of the c.e. degrees.
TeX DVI | Adobe PostScript

2-REA degrees in the difference hierarchy
(with M. Arslanov and T. Slaman)
Journal of Symbolic Logic, Vol 63, No.2, June 1998
A 2-CEA degree represents a class of information that can itself be computably enumerated by a program using a subroutine that calls the values of a computably enumerable set. An omega-c.e. degree represents a class of information which can be computably approximated with a computable bound on the number of changes the approximating algorithm can go through on each argument. We show that the intersection of the class of 2-CEA degrees with that of the omega-c.e. degrees consists precisely of the class of d.c.e. degrees. Hence the possibly-very-large computable bound in an omega-c.e. approximation can be replaced by a bound of 2 in a large and important class of cases. We also include some applications and show that there is no natural generalization of this result to higher levels of the CEA hierarchy.
TeX DVI | Adobe PostScript

Computably enumerable sets and quasi-reducibility
(with R. Downey and A. Nies)
Annals of Pure and Applied Logic, Vol. 95, No. 1-3, Sept. 1998
We consider the computably enumerable sets under the relation of Q-reducibility. This reducibility is an abstraction of the computation procedure of blind search using algebraic rules for a counterexample to an questionable, but possibly-true equation. We first give several results comparing the upper semilattice of c.e. Q-degrees under this reducibility with the more familiar structure of the c.e. Turing degrees (where any computation procedure with a finite use is allowed). In our final section, we use coding methods to show that the elementary theory of this structure is undecidable --- that is, there is no algorithm to determine what relationships can hold between classes of information distinguished in this way.
TeX DVI | Adobe PostScript

Why Goedel's theorem cannot refute computationalism
(with P.J. Hayes and K.M. Ford)
Artificial Intelligence, 104, Sept. 1998
Roger Penrose claims to prove that Gödel's theorem implies that human thought cannot be mechanized. We review his arguments and show how they are flawed. We show that Penrose¹s arguments depend crucially on ambiguities between precise and imprecise senses of key terms which cause the Gödel/Turing diagonalization argument to lead from apparently intuitive claims about human abilities to paradoxical or highly idiosyncratic conclusions. We conclude that any similar argument must also fail in the same ways.
Adobe PostScript

A D₂ set with barely S₂ degree
(with R. Downey and S. Lempp)
Journal of Symbolic Logic, Vol. 64, No. 4, 1999
We construct a D₂ degree which fails to be computably enumerable in any computably enumerable set with degree strictly below that of the halting problem. This is a set which, viewed from the "outside" doesn't have too much information in it, but, when we try to specify it with an ordinary computable enumeration procedure, we find that we need to use all the information in every computably enumerable set for the algorithm to work correctly. A really surprising fact!
TeX DVI | Adobe PostScript

Presentations of computably enumerable reals
(with R. Downey)
Theoretical Computer Science, Vol. 284, No. 2 (2002), pp.539-555
We study the relationship between computably enumerable reals and their approximations by means of sequences of prefix-free binary strings.
TeX DVI | Adobe PostScript

Completing pseudojump operators
(with R. Coles, R. Downey, and C. Jockusch)
preliminary version submitted to Annals of Pure and Applied Logic
We investigate algorithms which use the information in a set X to produce a set with information content that includes that of X and is relatively computably enumerable in X. These procedures, called pseudojumps, are the most natural ways (from a computational standpoint) to increase the information in a given set. In particular, given such a pseudojump procedure, we study which sets X can be used by it to produce sets with exactly the same information as that of the halting problem. We introduce notions of nontriviality for such procedures, and use these to discover which additional properties can be required of sets which can be completed to the halting problem by pseudojumps.
TeX DVI | Adobe PostScript

Decomposition and infima in the computably enumerable degrees
(with R. Downey and R. Shore)
to appear in the Journal of Symbolic Logic
We show that given any two incomparable computably enumerable sets A and B there exists a c.e. set C computable from their join such that C is the infimum of its joins with A and B respectively. In essence, this means we can find a way to distill the information two sets have in common by slightly increasing the information in each of them by the same amount. This complements and extends various theorems of Sacks, Lachlan, and Slaman concerning the structure of the usl of c.e. Turing degrees. The result has an added technical interest because the proof involves a nontrivial extension of the transfinitely-branching-tree computational architecture introduced originally by Shore to prove his noninversion theorem for the jump operator.
TeX DVI | Adobe PostScript

Isolation in higher degree types
preliminary version
Isolation arises when there is some pair of degrees a<b such that there do not exist any degrees of some specified class C between the two. These represent natural discontinuities in the computational power of various kinds of approximation algorithms. I give some results about the situation at higher levels in the difference hierarchy. I also examine the more general situation of isolation in the CEA-hierarchy, where things are more complex because the sets involved are not in general limits of computable functions.
TeX DVI | Adobe PostScript

Conference Lectures

Phenomena in the n-r.e.and n-REA hierarchies
Association for Symbolic Logic, Winter Meeting
San Francisco, CA, Jan. 8, 1995

Quasi-reducibility and algebraically closed groups
VIC '96
Wellington, New Zealand, Dec. 14, 1996

Enumerable sets and quasi-reducibility
Recursion Theory Special Session
Association for Symbolic Logic, European Meeting
Leeds, UK, July 11, 1997

Completion theorems for REA operators
Kazan Workshop in Recursion Theory and Complexity Theory
Kazan, Russia, July 14, 1997

Diagrammatic reasoning:analysis of an example (with P.J. Hayes)
FRVDR:AAAI Fall Symposium
Orlando, FL, Oct. 23, 1998

A barely S₂ degree
Invited ASL address, Joint Mathematics Meetings
San Antonio, TX, Jan. 15, 1999

Isolation in higher degree types
Computability Theory Special Session,
Association for Symbolic Logic, Annual Meeting
San Diego, CA, March 22, 1999

Geoff has also been invited to give talks on computability theory at departmental seminars and colloquia at the Universities of Michigan, Notre Dame, Wisconsin, and Florida, as well as at Cornell University, and at Victoria University of Wellington in New Zealand. He was the co-organizer of VIC '96, a conference on computational complexity and computability held in Wellington, New Zealand in December 1996, and the special session in computability theory at the regional AMS conference in Gainesville, Florida in March of 1999. He has also served as a referee for the Journal of Symbolic Logic, Proceedings of the American Mathematical Society, Theoretical Computer Science, Annals of Pure and Applied Logic and Archive for Mathematical Logic.