知识卡片
停机问题的边界
停机问题问:能否有一个通用算法,对任意程序与输入都正确判定其最终会停机还是永远运行。答案是否定的,因此“自动识别并修复任意软件问题”不能得到普适保证。这个不可判定性结论针对任意程序的通用判定;不能据此否定受限系统中的异常检测、规则诊断或人工验证后的自动修复。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《OpenTelemetry 可观测性的未来》第3章《自动分析的局限性》(源文件:_epub-src/index_split_025.html)
- 结论依据:原文给出任意程序及输入的停机判定定义,借此批评声称可全自动解决任意运维问题的承诺;卡片同时限定该推论不涵盖受限问题。
- 原始内容:停机问题的定义是,在给定任意计算机程序及其输入的描述的情况下,是否可以编写一个计算机程序来确定任意程序是否会结束运行或永远继续运行。……解决停机问题的一般算法是不存在的。