Complexity of winning strategies
โ
Andreas Blass
๐
Article
๐
1972
๐
Elsevier Science
๐
English
โ 606 KB
Rabin has given an example of a game with recursive rules but no recursive winning strategy. We show that such a game always has a hyperarithmetical winning strategy, but arbitrarily high levels of the hyperarithmetical hierarchy may be needed. We also exhibit a recursively enumerable game which has