The $\Omega$ numbers-the halting probabilities of universal prefix-free machines-are known to be exactly the Martin-L{\"o}f random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-L{\"o}f random left-c.e. real $\alpha$, a universal prefix-free machine U whose halting probability is $\alpha$. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha$, one cannot uniformly produce a left-c.e. real $\beta$ such that $\alpha$ -- $\beta$ is neither left-c.e. nor right-c.e.


翻译:============================================================================================================================================================ =====================================================================================================================================================================================================================

0
下载
关闭预览

相关内容

《机器学习思维导图》,一图掌握机器学习知识要点
专知会员服务
68+阅读 · 2021年1月12日
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
Embedding Logical Queries on Knowledge Graphs
Arxiv
3+阅读 · 2019年2月19日
Arxiv
3+阅读 · 2018年10月18日
Learning to Importance Sample in Primary Sample Space
Arxiv
8+阅读 · 2018年3月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关主题
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
Embedding Logical Queries on Knowledge Graphs
Arxiv
3+阅读 · 2019年2月19日
Arxiv
3+阅读 · 2018年10月18日
Learning to Importance Sample in Primary Sample Space
Arxiv
8+阅读 · 2018年3月17日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员