Completion of Choice
Completion of Choice
复制标题
完成选择
DOI：
10.1016/j.apal.2020.102914
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Gherardi
中科院分区：
文献类型：
--
作者：
V. Brattka;G. Gherardi
本文系统地研究了Weihrauch格上选择问题的完备化问题。选择问题在Weihrauch复杂性中起着关键作用。首先，它们可以用作Weihrauch格中表征重要等价类的地标。另一方面，选择问题也是可计算问题的一个重要特征，如有限思维变化可计算问题、非确定性可计算问题、拉斯维加斯可计算问题和有效Borel可测函数。完备化的闭包算子产生了全Weihrauch约简的概念，这是Weihrauch约简的一个变体。从逻辑上讲，一个问题的完成是一个独立于其前提的问题的版本。因此，研究完成的选择问题，使我们能够同时研究选择问题的总Weihrauch格，以及问题的选择问题可以独立于他们的前提，在通常的Weihrauch格。结果表明，许多重要的选择问题，涉及到紧空间是完全的，而选择问题的无界空间或正测度闭集通常是不完全的。
We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete.
通过 Lawvere-Tierney 拓扑的可计算性理论和逆向数学
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Takehiro Hasegawa;Takashi Komatsu;Norio Konno;Hayato Saigo;Seiken Saito;Iwao Sato;Shingo Sugiyama;Takayuki Kihara
通讯作者：
Takayuki Kihara