CS61A Lec28 - Undecidability

总之这节课完全是懵的

The halting problem

你不知道是否有程序可以检查一个输入使得程序无限循环

Biting your tail

Not Just a Trick

uncomputable:假设halt?能够返回一个正确的值，那么就说明它有无穷多的输入导致失败的，因为如果这个输入能够让halt?正确工作，那么就可以再构造一个halt?函数使它可以正确工作，这就反而证明了halt?不是不可计算的

举例: 我们不能判断两个程序是否在计算相同的东西，意味着我们不能写出完美的杀毒程序，因为你不能判断程序正在执行的东西

给出符号可能的Assertions来进行限制符号的语义

它表示存在最小的元素

全部评论
经典图灵机
点赞 回复 分享
发布于 2023-05-14 21:48 上海

相关推荐

今天 11:51
北京邮电大学 Hadoop
点赞 评论 收藏
分享
05-15 18:10
北京师范大学 Java
数字年轮里的敲键人生
18 岁，你在志愿表上勾选了 “计算机科学与技术”。老师说这行是未来风口，父亲刷着招聘网站上的高薪岗位频频点头。录取通知书到的那天，母亲在电脑城门口拍了张照片发朋友圈：“咱家要出个敲代码的科技新贵了。”20 岁，你考下计算机二级证书。机房里，后排男生的 C 语言程序总是报错，你把调试好的代码发过去，屏幕蓝光映着他崇拜的眼神。教授夸你算法思路清晰，却没人看见你笔记本上密密麻麻的循环嵌套，像被困在永无止境的迷宫里寻找出口。25 岁，你在互联网公司熬夜改 Bug。黑色的代码编辑器里跳动着红色警告，产品经理突然改需求的消息不断弹出，组长的催促混着机械键盘的敲击声。凌晨两点，你发现少写了个分号导致程序崩...
Elastic90：夺少？55岁就退休？不是已经改成60了吗
投递字节跳动等公司10个岗位 >
点赞 评论 收藏
分享
04-05 17:19
杭州师范大学 管理培训生
双非一本要死在春招了
好难，可以帮忙看看吗
SHC2：关键问题是你这三段实习是三个不同的岗位…你这样子秋招就是只有一段实习的本科生..
点赞 评论 收藏
分享
头像 会员标识
05-12 17:12
河南科技大学 Java
点赞 评论 收藏
分享
05-19 18:39
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的求职总结 #
19620次浏览 379人参与
# 我的工作日记 #
95080次浏览 1252人参与
# 毕业季，给职场新人一些建议 #
16733次浏览 302人参与
# 辞职之后最想做的一件事 #
9314次浏览 148人参与
# 我的实习日记 #
2427478次浏览 25337人参与
# 晒一晒你收到的礼盒 #
61015次浏览 367人参与
# 你想吐槽公司的哪些规定 #
16312次浏览 65人参与
# Offer比较，求稳定还是求发展 #
48371次浏览 235人参与
# 选offer应该考虑哪些因素 #
14767次浏览 246人参与
# 第一份工作应该只看薪资吗 #
137970次浏览 1454人参与
# 你怀疑过自己的专业选择吗？ #
17069次浏览 201人参与
# 薪资一样，你会选择去大厂还是小公司 #
15524次浏览 99人参与
# 牛客十周岁生日快乐 #
129090次浏览 1515人参与
# 秋招想进国企该如何准备 #
57298次浏览 372人参与
# 为了秋招你都做了哪些准备？ #
10323次浏览 156人参与
# 在国企工作的人，躺平了吗？ #
327102次浏览 3840人参与
# 你想留在一线还是回老家？ #
37155次浏览 445人参与
# 你小时候最想从事什么职业 #
90864次浏览 1699人参与
# 工作后会跟朋友渐行渐远吗 #
21122次浏览 167人参与
# 你们公司哪个部门最累？ #
15301次浏览 130人参与
牛客网
牛客企业服务