首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 View the MathML source. Winning strategies for View the MathML source 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 View the MathML source, and vice versa. Through View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号