論文

査読有り
2012年8月

Closed choice and a Uniform Low Basis Theorem

ANNALS OF PURE AND APPLIED LOGIC
  • Vasco Brattka
  • ,
  • Matthew de Brecht
  • ,
  • Arno Pauly

163
8
開始ページ
986
終了ページ
1008
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.apal.2011.12.020
出版者・発行元
ELSEVIER

We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution, we show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, the natural numbers, Cantor space and Baire space correspond to the class of computable functions, functions computable with finitely many mind changes, weakly computable functions and effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. The class of limit computable functions can be characterized with parallelized choice of natural numbers. On top of these results we provide further insights into algebraic properties of closed choice. In particular, we prove that closed choice on Euclidean space can be considered as "locally compact choice" and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be "divided" by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As a main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology. (C) 2011 Elsevier B.V. All rights reserved.

Web of Science ® 被引用回数 : 49

リンク情報
DOI
https://doi.org/10.1016/j.apal.2011.12.020
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000304576300004&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.apal.2011.12.020
  • ISSN : 0168-0072
  • eISSN : 1873-2461
  • Web of Science ID : WOS:000304576300004

エクスポート
BibTeX RIS