Games with 1-backtracking |
| |
Authors: | Stefano Berardi Thierry Coquand |
| |
Institution: | a Department of Computer Science, University of Turin, Turin, Italy b Department of Computer Science, Chalmers University, Goteborg, Sweden c Department of Humanistic Informatics, Kyoto University, Kyoto, Japan |
| |
Abstract: | We associate with any game G another game, which is a variant of it, and which we call . Winning strategies for have a lower recursive degree than winning strategies for G: if a player has a winning strategy of recursive degree 1 over G, then it has a recursive winning strategy over , and vice versa. Through we can express in algorithmic form, as a recursive winning strategy, many (but not all) common proofs of non-constructive Mathematics, namely exactly the theorems of the sub-classical logic Limit Computable Mathematics (Hayashi (2006) 6], Hayashi and Nakata (2001) 7]). |
| |
Keywords: | 03B30 91D35 03D35 |
本文献已被 ScienceDirect 等数据库收录! |
|