不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

J. B. Rosser 与Rosser’s trick

已有 1495 次阅读 2023-4-15 16:19 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

John Barkley Rosser Sr.1907-1989)是一位美国逻辑学家,是丘奇(Alonzo Church)的学生,以在λ计算中参与Church–Rosser 定理而闻名。他还在数论中提出了现在被称为 "Rosser sieve « 的方法。


1936年,他证明了罗瑟的诀窍(Rosser’s trick,这是哥德尔第一个不完全性定理的更强版本,表明对ω-一致性的要求可以弱化为一致性。他没有使用相当于 "I am not provable"的说谎者悖论句子,而是使用了一个句子,即 "For every proof of me, there is a shorter proof of my negation »


参考文献:

https://en.wikipedia.org/wiki/Rosser%27s_trick






https://blog.sciencenet.cn/blog-2322490-1384338.html

上一篇:“停机问题”(3)- 证明溯源
下一篇:“停机问题”(4) - “可计算数”的消失
收藏 IP: 77.201.68.*| 热度|

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-24 05:26

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部