图灵可识别语言是否可判定？
A Turing recognizable language is decidable or not?
如果可以以非递减长度枚举其字符串，那么图灵可识别语言是否是可判定的？
我认为这不是因为你可以去无穷大，这会使它变得不可判定，对吧？
问题是关于在有序元素的无限流 S 中搜索元素：一个非常自然的算法问题。
这个问题确实是可判定的，尽管是以一种偷偷摸摸的方式。你需要通过案例来推理。如果 S 中的元素有上界，则 S 是有限的，因此它是可判定的，因为每个有限集都是可判定的。另一方面，如果 S 没有边界，则它包含大于任何数字的元素。所以，如果你要找w，枚举到找到一个大于等于w的元素（那一定存在），然后和w比较就可以了。
然而，证明不是建设性的，因为你无法决定是否 r.e。集合是否有限。这意味着你知道（在经典意义上）有 must exist 一些决定 S 的程序，但你无法从代码中推导出它枚举 S。一个非常令人沮丧的情况 :)
如果可以以非递减长度枚举其字符串，那么图灵可识别语言是否是可判定的？
我认为这不是因为你可以去无穷大，这会使它变得不可判定，对吧？
问题是关于在有序元素的无限流 S 中搜索元素：一个非常自然的算法问题。
这个问题确实是可判定的，尽管是以一种偷偷摸摸的方式。你需要通过案例来推理。如果 S 中的元素有上界，则 S 是有限的，因此它是可判定的，因为每个有限集都是可判定的。另一方面，如果 S 没有边界，则它包含大于任何数字的元素。所以，如果你要找w，枚举到找到一个大于等于w的元素（那一定存在），然后和w比较就可以了。
然而，证明不是建设性的，因为你无法决定是否 r.e。集合是否有限。这意味着你知道（在经典意义上）有 must exist 一些决定 S 的程序，但你无法从代码中推导出它枚举 S。一个非常令人沮丧的情况 :)