×

Recursively presented games and strategies. (English) Zbl 0786.90103

Summary: The complexity of an infinite game is determined in part by the complexity of the set of winning strategies for the game. In this paper, we consider effectively closed, recursively bounded Gale-Stewart games. We give a coding for the winning strategies of such games so that any two different strategies are winning for different sets of games. We show that under our coding of winning strategies, the set of winning strategies can be effectively isomorphic to an arbitrary recursively bounded \(\Pi^ 0_ 1\)-class. This strengthens the well-known result that recursively presented games need not have recursive winning strategies. We also show that for every recursively presented game, there is a polynomial time presented game which has the same set of winning strategies. Thus even feasibly presented games need not have recursive solutions. Finally we develop some criteria which ensures that a polynomial time presented game has a polynomial time winning strategy.

MSC:

91A20 Multistage and repeated games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cenzer, D.; Remmel, J., Polynomial-time versus recursive models, Ann. Pure Appl. Logic, 54, 17-58 (1991) · Zbl 0756.03021
[2] Cenzer, D.; Remmel, J., Polynomial-time Abelian groups, Ann. Pure Appl. Logic, 56, 313-363 (1992) · Zbl 0764.03015
[3] Cenzer, D.; Remmel, J., Feasible graphs and colorings, Methods of Logic in Computer Science (1992), (to appear)
[4] Cenzer, D.; Remmel, J., \(Π^0_1\) classes in mathematics (1992), (to appear)
[5] Gale, D.; Stewart, F. M., Infinite games with perfect information, Ann. Math. Studies, 28, 245-266 (1953) · Zbl 0050.14305
[6] Garey, M.; Johnson, O., Computers and Intractability (1978), Freeman: Freeman New York
[7] Jockusch, C. G.; Soare, R. I., \(Π^0_1\)-classes and degrees of theories, Trans. Am. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041
[8] Jockusch, C. G.; Soare, R. I., Degrees of members of \(Π^0_1\)-classes, Pacific J. Math., 40, 605-616 (1972) · Zbl 0209.02201
[9] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relations to Automata (1969), Addison Wesley · Zbl 0196.01701
[10] Kucera, A., An alternative, priority free, solution to Post’s problem, Lecture Notes Comput. Sci., 233, 493-500 (1986)
[11] Manaster, A.; Rosenstein, J., Effective matchmaking, Proc. London Math. Soc., 25, 615-644 (1972) · Zbl 0251.05001
[12] Metakides, G.; Nerode, A., Effective content of field theory, Ann. Math. Logic, 17, 289-320 (1979) · Zbl 0469.03028
[13] Moschovakis, Y. N., Descriptive Set Theory, (Studies in Logic, Vol. 100 (1980), North-Holland: North-Holland Amsterdam) · Zbl 1172.03026
[14] Remmel, J. B., Graph coloring and recursively bounded \(Π^0_1\)-classes, Ann. Pure Appl. Logic, 32, 185-194 (1986) · Zbl 0625.03024
[15] Rogers, H. J., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[16] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1947), Princeton University Press · Zbl 1241.91002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.