如果图灵可识别语言可以以非递减的长度枚举其字符串，那么它可以判定吗？
我认为这不是因为你可以去无穷大，这会让它变得不可判定，对吧？
问题是关于在有序元素的无限流 S 中搜索元素：一个非常自然的算法问题。
这个问题确实是可以决定的，尽管有点偷偷摸摸。您需要按案例推理。如果 S 中的元素有上限，则 S 是有限的，因此它是可判定的，因为每个有限集合都是可判定的。另一方面，如果 S 没有边界，则它包含大于任何数字的元素。因此，如果您正在寻找 w，枚举就足够了，直到找到大于或等于 w 的元素(必须存在(，然后将其与 w 进行比较。
然而，证明不是建设性的，因为你无法决定一个 r.e. 集合是否有限。这意味着你知道(在经典意义上(必须存在一些决定 S 的程序，但你无法从枚举 S 的代码中派生它。一个相当令人沮丧的情况:)