Logic and Foundations Commons^™

Observing, Reporting, And Deciding In Networks Of Sentences, H. Jerome Keisler, Jeffrey M. Keisler

Management Science and Information Systems Faculty Publication Series

In prior work we considered networks of agents who prove facts from their knowledge bases and report them to their neighbors in their common languages in order to help a decider verify a single sentence. In report complete networks, the signatures of the agents and the links between agents are rich enough to verify any decider's sentence that can be proved from the combined knowledge base. This paper introduces a more general setting where new observations may be added to knowledge bases and the decider must choose a sentence from a set of alternatives. We consider the question of when …

Enumerations Of The Kolmogorov Function, Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Computer Science Faculty Publication Series

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A.

We determine exactly how hard it is to enumerate the Kolmogorov function, which assigns to each string x its Kolmogorov complexity:

• For every underlying universal machine U, there is a constant a …