为什么递归可枚举的语言不是不可判定的

Question

这是维基百科的可判定定义

在可计算性理论中,一个不可判定的问题包括一系列实例,其中需要特定的是/否答案,这样就没有计算机程序在给定任何问题实例作为输入的情况下,在有限数字后终止并输出所需答案.的步骤.更正式地说,一个不可判定的问题是一个语言不是递归集的问题

该递归集是的一个子集递归可枚举之一.在递归集之外有一些递归可枚举的语言.那么为什么递归上不可识别的语言不可判断？

Answer 1

递归可枚举的语言/集也称为半可判定的.它们不是可判定的,因为没有一台机器可以查看输入并说是或否(正确).半可判断意味着你可以编写一个查看输入的机器,如果输入在集合中则表示是,或者如果输入不在集合中则不能停止.半可判的结果相当于递归可枚举,与decidable相当于递归相同:

如果你有一个枚举递归可枚举语言的图灵机R,你可以创建一个新的机器D,它接受可能在语言/集合中的输入.D运行R直到R输出该组的第一个元素,然后D将其与其输入进行比较.如果匹配,则返回"是"结果.如果它们不匹配,它将继续运行R直到它获得下一个元素,依此类推.由于R永远不会停止(因为语言只是递归可枚举,而不是递归),D将回答是或不停止.

相反,如果你有一个回答是或未能停止的图灵机D,你可以制作一台新机器R,它使用通常的技术,一步一步地运行几个D的实例,各种输入:所有的元素,可能会或可能不会在集合中.每次D的并行执行之一以"是"答案停止时,R输出D的输入,并继续对所有剩余输入执行D. R永远不会停止(因为有些输入D不会停止),但最终会输出D回答"是"的每个元素,即集合/语言中的每个元素.

不要混淆思考有三种(不相交的)类型:可判定的,半可判定的和不可判定的.有两种:可判定和不可判定的.所有可判定的套装也都是半可判定的(尽管这样说很不寻常).一些不可判断的套装也是半可判定的.这就像说所有可枚举集都是递归可枚举的,并且一些非可枚举集是递归可枚举的.

Answer 2

一个半可否的问题(或等效的递归可枚举问题)可能是:

1. 可判定:如果问题及其补码都是半可否的(或递归可枚举),则问题是可判定的(递归).

2. 不可判定:如果问题是semidecidable及其补不semidecidable(也就是说,不是递归可枚举).

重要说明:请记住,可判定的(递归)问题也是半可否的(递归可枚举).相反,如果问题不是递归可枚举的(半可除),则不是递归的(可判定的).

维基百科条目所说的是:

部分可判定问题是不可判定被称为不可判定的.

通常,半可解决的问题(递归可枚举)可以是可判定的(递归的)或不可判定的(非递归的可枚举的).

还要注意,问题及其补充可能(或者只是其中一个)甚至不是半可判定的(非递归可枚举).还要注意,如果问题是递归的,那么它的补码也是递归的.