您将如何设计用于检查同义词的单磁带、双头 TM？
How would you design a one-tape, two-head TM for checking tautonyms?
我得弄清楚这门语言是不是
L = { ww | w {0,1}*}
可由图灵机判定。 TM 有 1 个磁带和 2 heads/pointers。输入字符串是有限的。关于如何解决它的任何建议？
依我看，如果知道字符串的长度，就很容易解决了。
作为提示，您可以通过反复将一个带头向前移动两步，将另一个带头向前移动一步，直到更快的带头离开弦来找到弦的中点；在那一点上，较慢的磁头在中间点。这可能会帮助您找到字符串中的断点。
希望对您有所帮助！
我得弄清楚这门语言是不是
L = { ww | w {0,1}*}
可由图灵机判定。 TM 有 1 个磁带和 2 heads/pointers。输入字符串是有限的。关于如何解决它的任何建议？
依我看，如果知道字符串的长度，就很容易解决了。
作为提示，您可以通过反复将一个带头向前移动两步，将另一个带头向前移动一步，直到更快的带头离开弦来找到弦的中点；在那一点上，较慢的磁头在中间点。这可能会帮助您找到字符串中的断点。
希望对您有所帮助！