Search

Your search keyword '"Recursive degree"' showing total 2 results
Start Over Descriptor "Recursive degree"
2 results on '"Recursive degree"'

1. Games with 1-backtracking

Author

Berardi, Stefano, Coquand, Thierry, and Hayashi, Susumu

Subjects
*GAME theory, *TOPOLOGICAL degree, *ALGORITHMS, *NUMERICAL calculations, *RECURSIVE functions, *PROOF theory
Abstract

Abstract: We associate with any game another game, which is a variant of it, and which we call . Winning strategies for have a lower recursive degree than winning strategies for : if a player has a winning strategy of recursive degree over , 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) , Hayashi and Nakata (2001) ). [Copyright &y& Elsevier]

Published
2010
Full Text
View/download PDF

2. Games with 1-backtracking

Author

Thierry Coquand, Stefano Berardi, and Susumu Hayashi

Subjects
Discrete mathematics, Degree (graph theory), Game semantics, Backtracking, Logic, Classical logic, proof theory, Mathematical proof, Learning in the limit, game semantics, Recursive degree, backtracking, Proof theory, Limit (mathematics), Limit computable, Mathematics
Abstract

We associate with any game G another game, which is a variant of it, and which we call bck(G). Winning strategies for bck(G) 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 bck(G), and vice versa. Through bck(G) 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]). (C) 2010 Elsevier B.V. All rights reserved.

Published
2010
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results