A=B
Not enough ratings
Exploring Turing completeness in Chapter 6 第六章中关于图灵完备性的探讨
By ax_pokl
This guide is an exploration of the proof of game-Turing completeness in Chapter 6 without using keywords.
本指南是一个有关第六章中,在不使用关键词的情况下对游戏图灵完备性证明的探讨。
   
Award
Favorite
Favorited
Unfavorite
Background Summary 前情提要
In Chapter 6 of the game, the author mentioned a dream where they realized that the keywords in A=B were unnecessary, and the professor confirmed this. However, based on the submitted report for version 6, the author did not provide a proof of Turing completeness that does not rely on keywords.
在游戏的第六章中,作者提到了自己做了一个梦,意识到A=B中的关键字都是不必要的,并且教授肯定了这个说法。然而从提交的第6版的课题报告文件看来,作者并没有提供一个不依赖于关键字的图灵完备性的证明。

I have been thinking about the possibility of proving Turing completeness without keywords these days, and I believe that it is impossible. I tried to rewrite statements with keywords using some general methods to remove them, and succeeded in some cases, but not in others. Successful cases mainly require the following conditions:
这几天我在思考在没有关键字的情况下证明图灵完备性的可能性,我认为结果是不可能的。我尝试用一些通用的办法将带关键字的语句改写为没有关键字的,有一部分情况下成功了,但一些情况下却不行。成功的情况主要需要满足以下特性:

1. The character set of the output string cannot overlap with the character set of the input string.
1. 输出字符串的字符集不能和输入字符串的字符集重叠

2. The length of the input string must be limited.
2. 输入字符串的长度必须有限制

An Example 一个例子
Consider the following code:
考虑到以下代码:

a=(return)true
=(return)false

The purpose of this code is to output true if the string contains "a", otherwise output false. When the length of the input string is greater than or equal to 1, it cannot be replaced by statements without keywords. This is because, no matter how it is rewritten, the code must contain a statement like this:
这个代码的作用是:当字符串中含有a时输出true,否则输出false。当输入字符串长度>=1时,无法用无关键字的语句替代。这是因为,无论如何改写,代码中必定包含这样的语句:

a=xyz

At this point, when the input string does not contain "a", the code must end up with false. Because of the above statement, the string will be replaced with "fxyzlse", and the program cannot stop in the end.
此时,当输入字符串没有a时,代码运行到最后必须是false。由于上面的这条语句,字符串会被替换成fxyzlse,而程序最终无法停止。

If we do not consider the input string as a single character "a" or "b", it is possible to achieve it through complex methods, such as traversing two characters "aa=xyz". In this case, the code cannot recognize the single characters "a" or "b" and output true and false in the end, so the length of the string must be limited.
如果不考虑输入字符串为单个字符a或者b,那通过复杂的方法是可以实现的,例如遍历两个字符aa=xyz。这种情况下,代码无法识别单个字符a或者b并最终输出true和false,因此必须对字符串的长度加以限制。

However, if there is more overlap in the output string, such as outputting "faalse" instead of "false", this method will fail again. Therefore, the character sets for input and output cannot overlap. However, most of the example problems in the game do not meet these requirements, so they cannot be rewritten.
然而,如果输出字符串有更多重叠时,例如要输出faalse而非false,那这种方法又会失效。因此,输入和输出字符集不能重叠。然而游戏中绝大多数例题都不满足要求,因此无法改写。

Replacement Solution 替换方案
If the input and output character sets do not overlap, then most keywords can be replaced, as summarized below:
如果满足输入和输出字符集不重叠,那么大多数关键字都有改法,总结如下:

Let W be the string to be replaced, U be the replacement string, and @, $, %, etc. be temporary characters that are different from all characters in the original code. Please note that each time a replacement is made, new temporary characters must be selected. Reusing temporary characters in the replacement will interfere with subsequent replacement code.
下面我们假设W为被替换的字符串,U为替换的字符串,@为临时字符并且和原始代码中的所有字符都不相同。请注意,每次替换时,必须重新选取新的临时字符。在替换中重复使用临时字符会造成后续替换代码被之前的替换代码干扰。

0. (keyword)W=(keyword)U
(keyword)W=@
@=(keyword)U

1. (start)W=U
(once)=@
@W=U

2. (end)W=U
(once)=(end)@
W@=U
a@=@a
b@=@b
c@=@c
@=

3. W=(start)U
W=@
a@=@a
b@=@b
c@=@c
@=U

4. W=(end)U
W=@
@a=a@
@b=b@
@c=c@
@=U

5. W=(return)U
W=@
a@=@
b@=@
c@=@
@a=@
@b=@
@c=@
@@=@
@=U

6. =(return)U
(once)=@
a=@
b=@
c=@
@@=@
@=U

7. (once)W=U
(once)=@
@W=U
@a=a@
@b=b@
@c=c@
@=

8. (once)=U
# This function cannot be implemented because the output string includes the input string. If anyone knows how to solve this problem, please let me know.
# 无法实现这个函数,因为输出字符串包含输入字符串.如果大家有办法解决这个问题,请告诉我。

3 Comments
SbF5 17 Mar @ 4:16am 
(once)=U可以换成
(once)W=@W#W仅在输入中出现如A+B中的+
@=(start)U
当然这也必须要有W存在时才行
2536733858 3 Mar @ 11:47pm 
除了once不可替代外 应该都行
₍ᐢ..ᐢ₎ᐝ 10 Jul, 2023 @ 4:54am 
👍