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,…
The negative solution is given.
Under a weak set-theoretic assumption, we interpret full second-order logic in the monadic theory of order.
This paper introduces a weaker version of the Byzantine generals problem described in [41]. The problem is "easier" because there exist approximate solutions with fewer than 3n processes that can tolerate n faults, something shown in [41] to be impossible for the original Byzantine generals…
The System Modeller provides automatic support for several different kinds of program development cycle in the Cedar programming system. It handles the daily evolution of a single module or a small group of modules modified by a single person, the assembly of numerous modules into…
This was an invited paper. It describes the state of my views on specification and verification at the time. It is notable for introducing the idea of invariance under stuttering and explaining why it's a vital attribute of a specification logic. It is also one…
We discuss finite temperature lattice Yang-Mills theory with special attention to the confinement problem. The relationship between the confinement criteria of Wilson, Polyakov, and 't Hooft is clarified by establishing a string of inequalities between the corresponding string tensions. The close connection between finite temperature…
We replace Goedel's sophisticated combinatorial argument with a simple probabilistic one.
