The genesis of this paper was my realization that, in a multiprocess system with synchronized clocks, the absence of a message can carry information. I was fascinated by the idea that a process could communicating zillions of bits of information by not sending messages. The…
We present an extension of first-order logic that captures precisely the computational complexity of (the uniform sequences of) constant-depth polynomial-time circuits.
Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous paper [1], was designed and implemented several years ago. We now have had operational experience with…
Remote procedure calls (RPC) appear to be a useful paradigm for providing communication across a network between programs written in a high-level language. This paper describes a package providing a remote procedure call facility, the options that face the designer of such a package, and…
Functional languages supporting lazy evaluation invite novel applications, where conventional languages do not provide appropriate support for the problem. In this paper we present an application of functional languages to arbitrary precision real arithmetic, using an unusual technique based on continued fractions, and depending crucially…
PATHFINDER is a developing expert system to assist pathologists in the interpretation of findings noted on microscopic examination of lymph node tissue. We describe PATHFINDER's hypothesis-directed reasoning approach with an emphasis on intelligent question selection strategies, techniques for managing data inaccuracy, and explanation methods for…
Using a model tokamak equilibrium, the influence of a magnetic separatrix on the stability of the plasma against ideal MHD ballooning modes is investigated. It is found that there is no significant stabilizing effect from the strong global shear near the separatrix, but rather that…
We prove that, under a natural interpretation over finite domains, (i) a function is primitive recursive if and only if it is logspace computable, and (ii)a function is general recursive if and only if it is polynomial time computable.
The problem is proven to be undecidable.
Studying the design and implementation of a number of computer has led to some general hints for system design. They are described here and illustrated by many examples, ranging from hardware such as the Alto and the Dorado to application programs such as Bravo and…
It is well known that for all recursively enumerable sets X1, X2 there are disjoint recursively enumerable sets Y1, Y2 such that Yi is a subset of Xi and (Y1 ∪ Y2) = (X1 ∪ X2). Alistair Lachlan called distributed lattices satisfying this property separated.…
In a series of papers, Büchi proved the decidability of the monadic (second-order) theory of ω0, of all countable ordinals, of ω1, and finally of all ordinals < ω2. Here, assuming the consistency of a weakly compact cardinal, we prove that, in different set-theoretic worlds,…
