回文图灵机
Turing machine for palindrome
用一带和二带描述TM，决定语言的回文组成（单词只有'1'和'0'符号）。估算每个 TM 的工作时间。
一盘磁带：
读取第一个符号，如果为 0 则移至状态 A，如果为 1 则移至状态 B。替换为空白。向右移动到磁带的末尾（第一个空白符号）。向左移动一个符号。如果这个符号是 0 而你处于状态 A，或者如果它是 1 而你处于状态 B，则将其设为空白并 return 一直向左直到找到空白符号，然后向右移动一个。否则，这个词不是回文，你会停止拒绝。以这种方式继续，直到您停止拒绝或磁带上的所有符号都被空白替换，在这种情况下您停止接受。这大约需要 (n+1) + n + ... + 1 ~ O(n^2) 次移动。
两盘磁带：
将输入磁带的磁带头移动到末尾，然后向后读取到输入磁带的开头。一边走，一边在第二张纸带上按顺序写下纸带符号，这样你就可以在第二张纸带上得到输入纸带的反面。重置两个磁头，然后将每个磁头移动到磁带的末端，每一步都比较每个磁头指向的符号。如果您发现符号不同的位置，则输入不是回文，您会停止拒绝。如果你走到最后（最后的第一个空白符号）没有发现不匹配，那么它是一个回文，你停止接受。
用一带和二带描述TM，决定语言的回文组成（单词只有'1'和'0'符号）。估算每个 TM 的工作时间。
一盘磁带：
读取第一个符号，如果为 0 则移至状态 A，如果为 1 则移至状态 B。替换为空白。向右移动到磁带的末尾（第一个空白符号）。向左移动一个符号。如果这个符号是 0 而你处于状态 A，或者如果它是 1 而你处于状态 B，则将其设为空白并 return 一直向左直到找到空白符号，然后向右移动一个。否则，这个词不是回文，你会停止拒绝。以这种方式继续，直到您停止拒绝或磁带上的所有符号都被空白替换，在这种情况下您停止接受。这大约需要 (n+1) + n + ... + 1 ~ O(n^2) 次移动。
两盘磁带：
将输入磁带的磁带头移动到末尾，然后向后读取到输入磁带的开头。一边走，一边在第二张纸带上按顺序写下纸带符号，这样你就可以在第二张纸带上得到输入纸带的反面。重置两个磁头，然后将每个磁头移动到磁带的末端，每一步都比较每个磁头指向的符号。如果您发现符号不同的位置，则输入不是回文，您会停止拒绝。如果你走到最后（最后的第一个空白符号）没有发现不匹配，那么它是一个回文，你停止接受。