Introduction to computability logic (Q1408853)

The intuitive notion of interactive computational problems is formalized as a sort of games between the machine and the environment (a user). Computability is understood as the existence of a Turing machine that wins the game against any possible environment. The used formalism is an \(n\)-disjoint union of the formalisms of classical, intuitionistic and linear logics, with logical operators interpreted as operations on problems. Validity of a formula is understood as being ``always computable''. The universal logic is the set of all valid formulas. This logic integrates, on the basis of one semantics, classical, intuitionistic and linear logics, with their seemingly unrelated or even antagonistic philosophies. The paper provides illustrations of potential applications of the universal logic in knowledge-based, resource-based and planning systems, as well as constructive applied theories.