paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Subcomputable Schnorr Randomness

次可计算 Schnorr 随机性
LMCS vol.Volume 13, Issue 22017匹配度 0/10 · 该论文属于可计算性理论与算法随机性，讨论次可计算类的 Schnorr 随机性及其刻画，未涉及程序分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等研究方向。引用 2 inbox
Claude Sureson
逻辑与自动机
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：为次可计算类提出 Schnorr 随机性概念，并用 Martin-Löf 检验、鞅与测度可计算机器加以刻画。

论文讨论 Schnorr 随机性概念原本针对可计算实数或可计算函数。作者为次可计算类提出一种 Schnorr 随机性版本，并从多个角度刻画它：用 Martin-Löf 检验、鞅或测度可计算机器给出等价描述。结果说明该随机性概念可在次可计算环境中通过测试、下注/预测和机器模型等形式定义，为 Schnorr 随机性在更一般的可计算性层级上的推广提供了统一框架。

问题
如何将原本针对可计算实数或可计算函数的 Schnorr 随机性推广到次可计算类。
方法
提出面向次可计算类的 Schnorr 随机性定义，并用 Martin-Löf 检验、鞅、测度可计算机器等不同模型进行刻画。
评估
以数学证明给出多种定义之间的等价刻画，而非实验评估。
原文摘要（Abstract）

The notion of Schnorr randomness refers to computable reals or computable functions. We propose a version of Schnorr randomness for subcomputable classes and characterize it in different ways: by Martin L\"of tests, martingales or measure computable machines.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{Sureson16,
  title = {Subcomputable Schnorr Randomness},
  author = {Claude Sureson},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 13, Issue 2},
  year = {2017},
  doi = {10.23638/lmcs-13(2:2)2017}
}