Logical Approaches to Computational Barriers

Complete Determinacy and Subsystems of Second Order Arithmetic

Speaker:
| Takako Nemoto |

Slot: |
Array, 11:40-12:00, col. 1 |

This paper investigates the determinacy and the complete determinacy of infinite games following reverse mathematics program whose purpose is to find the set comprehension axioms which are necessary and sufficient for these statements in the frame of second order arithmetic. In some sense, this research clarifies how complex oracles we need to obtain the algorithms which gives a winning strategy and which determines the winning position for players. It will be shown that, depending on the complexity of the rules of games, the complexity of the oracles changes drastically and that determinacy and complete determinacy statements are not always equivalent.

websites: Arnold Beckmann | 2008-05-18 |