A gossip protocolGossip protocol is a procedure for sharing secrets in a network. The basic action in a gossip protocolGossip protocol is a telephone call wherein the caller and the callee exchange all the secrets they know. An agent who knows all secrets is an expert. The usual termination condition is that all agents are experts. Instead, we explore some protocols wherein the termination condition is that all agents know that all agents are experts. We call such agents super experts. (...) Additionally, we model that agents who already know that all agents are experts, do not make and do not answer calls. We also model that such protocols are common knowledgeCommon knowledge among the agents. We investigate conditions under which such gossip protocolsGossip protocol terminate, both in the synchronous case, where there is a global clock, and in the asynchronous case, where there is not. We show that a protocol with missed calls can terminate faster than the same protocol without missed calls. (shrink)

A bounded monotone sequence of reals without a limit is called a Specker sequence. In Russian constructive analysis, Church's Thesis permits the existence of a Specker sequence. In intuitionistic mathematics, Brouwer's Continuity Principle implies it is false that every bounded monotone sequence of real numbers has a limit. We claim that the existence of Specker sequences crucially depends on the properties of intuitionistic decidable sets. We propose a schema about intuitionistic decidability that asserts “there exists an intuitionistic enumerable set that (...) is not intuitionistic decidable” and show that the existence of a Specker sequence is equivalent to ED. We show that ED is consistent with some certain well known axioms of intuitionistic analysis as Weak Continuity Principle, bar induction, and Kripke Schema. Thus, the assumption of the existence of a Specker sequence is conceivable in intuitionistic analysis. We will also introduce the notion of double Specker sequence and study the existence of them. (shrink)

We represent the well-known surprise exam paradox in constructive and computable mathematics and offer solutions. One solution is based on Brouwer’s continuity principle in constructive mathematics, and the other involves type 2 Turing computability in classical mathematics. We also discuss the backward induction paradox for extensive form games in constructive logic.

Let A be a subset of the constructive real line. What are the necessary and sufficient conditions for the set A such that A is continuously separated from other reals, i.e., there exists a continuous function f with f−1(0) = A? In this paper, we study the notions of closed sets and closure maps in constructive reverse mathematics.

In the context of intuitionistic analysis, we consider the set consisting of all continuous functions from [0,1] to such that =0 and =1, and the set consisting of ’s in where there exists x[0,1] such that . It is well-known that there are weak counterexamples to the intermediate value theorem, and with Brouwer’s continuity principle we have . However, there exists no satisfying answer to . We try to answer to this question by reducing it to a schema about intuitionistic (...) decidability that asserts “there exists an intuitionistically enumerable set that is not intuitionistically decidable”. We also introduce the notion of strong Specker double sequence, and prove that the existence of such a double sequence is equivalent to the existence of a function where. (shrink)