Copy-cat strategies in physics, geometry, logic and computation
Samson Abramsky ( OUCL )
- 16:30 29th January 2008 ( week 3, Hilary Term 2008 )Lecture Theatre A
Copy-cat strategies belong to `sub-rational game theory'; basic elements of interaction from which logic and structure arise as `emergent behaviour'. We see them as game-theoretic manifestations of ideas which arise in many contexts. We find them in (Linear) Logic, as the basic dynamical explanation of computational content in a classical format; in knot theory, in Temperley-Lieb algebras, the central ingredient of the Jones polynomial; in quantum mechanics, as the basic structures underlying teleportation and other quantum information protocols; and in information security and web computation (man-in-the-middle attacks, CAPTCHA, etc.)
By contrast, non-linear copying (cloning) gives classical (macroscopic) behaviour in the physical context; computational universality in classical computation; and classical deduction in the logical setting.
The existence of common structure in all these different contexts suggests the possibility of a unified calculus for information flow and interaction in a wide variety of settings.