上一页

ⓘ 不可判定问题




                                     

ⓘ 不可判定问题

不可判定问题 是可计算性理论和计算复杂性理论中定义的一类决定性问题,此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表:对于停机问题,没有算法能够正确判定任意程序是否会终止运行。

                                     

1. 背景

决定性问题是一类根据从一个无限集合中选取的输入值,得出是或否的回答的问题。因此,根据传统定义,寻求答案为 是 的输入值之集合的问题,与决定性问题等价。