第六章中关于图灵完备性的探讨

本指南是对第六章中不使用关键词的游戏图灵完备性证明的探讨。 前情提要 在游戏的第六章中，作者提到自己做了一个梦，意识到A=B中的关键字都是不必要的，并且教授肯定了这个说法。然而，根据提交的6版本报告，作者并未提供不依赖关键字的图灵完备性证明。然而从提交的第6版的课题报告文件看来，作者并没有提供一个不依赖于关键字的图灵完备性的证明。 这几天我在思考在没有关键字的情况下证明图灵完备性的可能性，我认为结果是不可能的。我尝试用一些通用的办法将带关键字的语句改写为没有关键字的，有一部分情况下成功了，但一些情况下却不行。成功的情况主要需要满足以下特性： 1.输出字符串的字符集不能和输入字符串的字符集重叠 输入字符串的长度必须有限制 一个例子 考虑到以下代码： a=(return)true =(return)false 这个代码的作用是：当字符串中含有a时输出true，否则输出false。当输入字符串的长度大于或等于1时，不能用没有关键字的语句替换。这是因为，无论如何重写，代码都必须包含这样的语句：当输入字符串长度>=1时，无法用无关键字的语句替代。这是因为，无论如何改写，代码中必定包含这样的语句：a=xyz。此时，当输入字符串没有a时，代码运行到最后必须是false。由于上面的这条语句，字符串会被替换成fxyzlse，而程序最终无法停止。如果我们不将输入字符串视为单个字符“a”或“b”，则可以通过复杂方法实现，例如遍历两个字符“aa=xyz”。在这种情况下，代码无法识别单个字符“a”或“b”并最终输出true和false，因此必须限制字符串的长度。 如果不考虑输入字符串为单个字符a或者b，那通过复杂的方法是可以实现的，例如遍历两个字符aa=xyz。这种情况下，代码无法识别单个字符a或者b并最终输出true和false，因此必须对字符串的长度加以限制。 但是，如果输出字符串存在更多重叠，例如输出“faalse”而非“false”，这种方法将再次失效。因此，输入和输出的字符集不能重叠。然而，游戏中的大多数示例题目都不符合这些要求，所以无法重写。然而，如果输出字符串有更多重叠时，例如要输出faalse而非false，那这种方法又会失效。因此，输入和输出字符集不能重叠。然而游戏中绝大多数例题都不满足要求，因此无法改写。 替换方案 如果满足输入和输出字符集不重叠，那么大多数关键字都有改法，总结如下： 设W为待替换字符串，U为替换字符串，@、$、%等为与原代码中所有字符均不同的临时字符。请注意，每次进行替换时，都必须选用新的临时字符。在替换中重复使用临时字符会干扰后续的替换代码。 下面我们假设W为被替换的字符串，U为替换的字符串，@为临时字符并且和原始代码中的所有字符都不相同。请注意，每次替换时，必须重新选取新的临时字符。在替换中重复使用临时字符会造成后续替换代码被之前的替换代码干扰。 0. (关键字)W=(关键字)U (关键字)W=@ @=(关键字)U 1. (开始)W=U (单次)=@ @W=U 2. (结束)W=U (单次)=(结束)@ W@=U a@=@a b@=@b c@=@c @= 3. W=(开始)U W=@ a@=@a b@=@b c@=@c @=U 4. W=(结束)U W=@ @a=a@ @b=b@ @c=c@ @=U 5. W=(返回)U W=@ a@=@ b@=@ c@=@ @a=@ @b=@ @c=@ @@=@ @=U 6. =(返回)U (单次)=@ a=@ b=@ c=@ @@=@ @=U 7. (单次)W=U (单次)=@ @W=U @a=a@ @b=b@ @c=c@ @= 8.无法实现这个函数，因为输出字符串包含输入字符串。如果大家有办法解决这个问题，请告诉我。