Game semantics
From Wikipedia, the free encyclopedia
Game semantics (German: dialogische Logik) is an approach to the semantics of logic that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player. Paul Lorenzen was the first to introduce a game semantics for logic, doing so in the late 1950s. Since then, a number of different game semantics have been studied in logic. Game semantics has also been applied to the formal semantics of programming languages.
Contents |
[edit] Classical logic
The simplest application of game semantics is to propositional logic. Each formula of this language is interpreted as a game between two players, known as the "Verifier" and the "Falsifier". The Verifier is given "ownership" of all the disjunctions in the formula, and the Falsifier is likewise given ownership of all the conjunctions. Each move of the game consists of allowing the owner of the dominant connective to pick one of its branches; play will then continue in that subformula, with whichever player controls its dominant connective making the next move. Play ends when a primitive proposition has been so chosen by the two players; at this point the Verifier is deemed the winner if the resulting proposition is true, and the Falsifier is deemed the winner if it is false. The original formula will be considered true precisely when the Verifier has a winning strategy, while it will be false whenever the Falsifier has the winning strategy.
If the formula contains negations or implications, other, more complicated, techniques may be used. For example, a negation should be true if the thing negated is false, so it must have the effect of interchanging the roles of the two players.
More generally, game semantics may be applied to predicate logic; the new rules allow a dominant quantifier to be removed by its "owner" (the Verifier for existential quantifiers and the Falsifier for universal quantifiers) and its bound variable replaced at all occurrences by an object of the owner's choosing, drawn from the domain of quantification. Note that a single counterexample falsifies a universally quantified statement, and a single example suffices to verify an existentially quantified one.
All of these games are of perfect information; the two players always know the truth values of each primitive, and are aware of all preceding moves in the game.
[edit] Intuitionistic logic, denotational semantics, linear logic
The primary motivation for Lorenzen and Kuno Lorenz was to find a game-theoretic (their term was "dialogical" Dialogische Logik) semantics for intuitionistic logic. Blass was the first to point out connections between game semantics and linear logic. This line was further developed by Samson Abramsky, Radhakrishnan Jagadeesan, Pasquale Malacaria and independently Martin Hyland and Luke Ong, who placed special emphasis on compositionality, i.e. the definition of strategies inductively on the syntax. Using game semantics, the authors mentioned above have solved the long-standing problem of defining a fully abstract model for the programming language PCF. Consequently, game semantics has led to fully abstract semantic models for a variety of programming languages and, to new semantic-directed methods of software verification by software model checking.
[edit] Quantifiers
Foundational considerations of game semantics have been more emphasised by Jaakko Hintikka and Gabriel Sandu, especially for Independence-friendly logic (IF logic, more recently Information-friendly logic), a logic with branching quantifiers. It was thought that the principle of compositionality fails for these logics, so that a Tarskian truth definition could not provide a suitable semantics. To get around this problem, the quantifiers were given a game-theoretic meaning. Specifically, the approach is the same as in classical propositional logic, except that the players do not always have perfect information about previous moves by the other player. Wilfrid Hodges has proposed a compositional semantics and proved it equivalent to game semantics for IF-logics. Foundational considerations have motivated the works of others, such as Japaridze's computability logic.
[edit] See also
- Independence-friendly logic
- Intuitionistic logic
- Linear logic
- Computability logic
- Interactive computation
[edit] References
[edit] Articles
- S.Abramsky and R.Jagadeesan, Games and full completeness for multiplicative linear logic. Journal of Symbolic Logic 59 (1994): 543-574.
- A.Blass, A game semantics for linear logic. Annals of Pure and Applied Logic 56 (1992): 151-166.
- G.Japaridze, Introduction to computability logic. Annals of Pure and Applied Logic 123 (2003): 1-99.
- Krabbe, E. C. W., 2001. "Dialogue Foundations: Dialogue Logic Revisited," Supplement to the Proceedings of The Aristotelian Society 75: 33-49.
[edit] Books
- K. Lorenz, P. Lorenzen: Dialogische Logik, Darmstadt 1978
- P. Lorenzen: Lehrbuch der konstruktiven Wissenschaftstheorie, Stuttgart 2000 ISBN 3-476-01784-2
- R. Inhetveen: Logik. Eine dialog-orientierte Einführung., Leipzig 2003 ISBN 3-937219-02-1
