We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order.


翻译:我们研究了Skolem问题、概率问题和终极概率问题对实际计算模型中真实数字初始值和实际数字系数的线性重现的衰变可能性问题。 我们发现,对于每个问题,都存在一种正确的局部算法,它停止了所有答案本地常态的问题,从而确定了所有这三个问题都接近于衰变的可能性,而人们可以预期它们会在此背景下发生。我们进一步显示,概率问题和超大概率问题的算法几乎都停止了对欧克利底空间通常的Lebesgue测量法的几乎每一种情况。相比之下,准确合理或实际代数系数的类似问题只已知在极低顺序线性重现时才会被衰减。

0
下载
关闭预览

相关内容

可解释强化学习,Explainable Reinforcement Learning: A Survey
专知会员服务
129+阅读 · 2020年5月14日
【Google-CMU】元伪标签的元学习,Meta Pseudo Labels
专知会员服务
31+阅读 · 2020年3月30日
【斯坦福大学】Gradient Surgery for Multi-Task Learning
专知会员服务
46+阅读 · 2020年1月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年10月6日
Arxiv
0+阅读 · 2021年10月6日
VIP会员
相关VIP内容
可解释强化学习,Explainable Reinforcement Learning: A Survey
专知会员服务
129+阅读 · 2020年5月14日
【Google-CMU】元伪标签的元学习,Meta Pseudo Labels
专知会员服务
31+阅读 · 2020年3月30日
【斯坦福大学】Gradient Surgery for Multi-Task Learning
专知会员服务
46+阅读 · 2020年1月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员