图灵可判定语言连接封闭性证明的两处疑问咨询

结合经典的构造证明思路，帮你拆解这两个问题：

1. 为什么要从左到右扫描输入纸带直至遇到空白符？ #

这个操作的核心是明确输入的完整范围。咱们要处理的输入是字符串w，而图灵机的纸带里，有效输入是从起始位置到第一个空白符（⊔）之间的所有字符——空白符就是输入的“终止标记”。

扫描到空白符，我们才能确定整个w的长度，进而知道所有可能的分割点：比如x可以是空串（对应分割点在第一个字符前）、x是第一个字符（分割点在第一个和第二个字符之间）……一直到x是整个w（分割点在最后一个字符后，y是空串）。只有明确了输入的边界，才能确保我们遍历所有可能的x和y的组合，不会漏掉任何一种可能让xy属于L1L2的情况。

2. 为什么恰好仅有一个纸带符号被标记？ #

这个设计是为了精准对应一种分割方式。咱们构造的图灵机需要逐个测试所有可能的分割：每一次标记一个符号，就代表“把这个符号左边的所有字符作为x，右边的作为y”——比如标记第k个字符，就测试x=w₁w₂…w_k，y=w_{k+1}…w_n。

如果同时标记多个符号，分割点就模糊了，没法明确区分x和y的范围。而且我们需要按顺序测试每一种分割：先标记第一个位置，测试完就取消标记，再标记第二个位置，以此类推。每次只标记一个，才能清晰、系统地检查每一种可能的xy组合，只要有任意一种组合满足x∈L1且y∈L2，图灵机就可以接受输入w了。

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