Toggling operators in computability logic

Abstract: Computability logic (CoL) is a recently introduced semantical platform and research program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in CoL stand for interactive computational problems, seen as games between a machine and its environment; logical operators represent operations on such entities; and “truth” is understood as existence of an effective solution, i.e., of an algorithmic winning strategy. The formalism of CoL is open-ended, and may undergo series of extensions as the studies of the subject advance. Propositional connectives and quantifiers in it come in a variety of indispensable versions. So far three sorts of conjunction and disjunction–parallel, sequential and choice–have been studied, with the first and the third sorts being reminiscent of the multiplicative and additive operators of linear logic, respectively. The present paper adds one more natural kind to this collection, termed toggling. The toggling operations can be characterized as lenient versions of choice operations where choices are retractable, being allowed to be reconsidered any finite number of times. This way, they model trial-and-error style decision steps in interactive computation. The main technical result of this paper is constructing a sound and complete axiomatization for the propositional fragment of computability logic whose vocabulary includes all four kinds of conjunction and disjunction: parallel, toggling, sequential and choice, together with negation. Along with toggling conjunction and disjunction, the paper also introduces the toggling versions of quantifiers and recurrence (“exponential”) operations. [Copyright &y& Elsevier]