CS61A Lec28 - Undecidability

总之这节课完全是懵的

The halting problem

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

Biting your tail

Not Just a Trick

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

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

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

它表示存在最小的元素

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

相关推荐

下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务