集合规模边界约束下的图灵机集合可识别性判定问题

判定结果 #

• 集合A = {T | T是图灵机，L(T)包含至少1001个字符串}：可识别
• 集合B = {T | T是图灵机，L(T)包含至多1001个字符串}：不可识别

核心直觉 #

图灵可识别语言的核心要求是：对属于集合的输入，总能在有限步内给出肯定接受结果，对不属于集合的输入可以无限运行不返回结果。

• 对集合A：只要图灵机T确实满足条件，我们总能通过暴力枚举+模拟的方式，在有限时间内找到1001个被T接受的字符串，即可终止返回接受。哪怕T对应的语言是无限的，只要它的规模≥1001，我们迟早能收集到足够多的有效接受串，不会卡壳。
• 对集合B：不存在有限时间可以确认T的语言“不会再有更多的串”，哪怕你模拟了足够久只找到了300个接受串，也无法证明未来不会出现第1002个被接受的串，永远拿不到确定的肯定结论，不符合可识别的要求。

形式化证明思路 #

集合A可识别的证明 #

构造识别器M，输入为图灵机T的编码：

1. 按字典序枚举所有可能的字符串s₁, s₂, s₃...
2. 对每一个正整数k，并行模拟T在s₁到sₖ上各运行k步
3. 每完成一轮k的模拟，统计当前已经被T接受的字符串数量，一旦数量≥1001，立即停机接受输入T

若T属于A，则必然存在有限的k，使得运行到第k轮时已经找到1001个被接受的串，M一定会停机接受；若T不属于A，M会无限运行，完全符合可识别语言的定义。

集合B不可识别的证明 #

采用归约法，将已知不可识别的补停机问题Ā = {<T,w> | 图灵机T在输入w上永不停机}归约到B：
构造归约函数f，输入为<T,w>，输出图灵机T'的编码，T'的逻辑如下：

• 输入任意字符串x，先模拟T在w上运行|x|步（|x|为x的长度）
• 若T在|x|步内停机，则接受x；否则拒绝x

对归约结果做分析：

1. 若<T,w> ∈ Ā，即T在w上永不停机：对任意x，模拟|x|步都不会触发停机条件，T'永远不会接受任何串，|L(T')|=0 ≤ 1001，因此T'属于B
2. 若<T,w> ∉ Ā，即T在w上运行n步后停机：所有长度≥n的字符串x都会被T'接受，L(T')是无限集，规模远大于1001，因此T'不属于B

如果B是可识别的，我们就可以通过B的识别器来判定Ā，而补停机问题已被证明不可识别，产生矛盾，因此B不可识别。

内容的提问来源于stack exchange，提问作者DazedAndConfused