CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Games with 1-backtracking

S. Berardi ; Thierry Coquand (Institutionen för data- och informationsteknik, Datavetenskap, Programmeringslogik (Chalmers)) ; S. Hayashi
Annals of Pure and Applied Logic (0168-0072). Vol. 161 (2010), 10, p. 1254-1269.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Classical logic, Game semantics, Backtracking, Learning in the limit, Limit computable, Recursive degree, mathematics



Denna post skapades 2010-07-16. Senast ändrad 2015-01-09.
CPL Pubid: 123891

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)