识别回文串的图灵机模型

TM 设计思想：

我们可以使用两个读/写头的图灵机来识别语言ωωR。其中一个读/写头用于读取输入串ω的字符，另一个读/写头用于读取输入串ω的逆串ωR的字符。我们可以依次比较两个读/写头读取的字符，如果它们相等，则继续移动读/写头并继续比较下一个字符，直到读/写头都到达输入串的末尾。如果在任何时候两个读/写头读取的字符不相等，则图灵机停机并拒绝输入。

TM 定义：

M = '在输入上，使用两个读/写头的图灵机，它识别语言ωωR，其中ω是由a，b组成的字符串：

• 输入：一个由a，b组成的字符串ω。
• 输出：如果ω是ωωR，则接受输入；否则，拒绝输入。
• 动作：
  1. 初始化：将第一个读/写头放在输入串的开始位置，将第二个读/写头放在输入串的末尾位置。
  2. 比较：比较两个读/写头读取的字符。
     • 如果两个字符相等，则将两个读/写头都向前移动一步。
     • 如果两个字符不相等，则停机并拒绝输入。
  3. 重复：重复步骤2，直到两个读/写头都到达输入串的末尾。
  4. 结束：如果两个读/写头都到达输入串的末尾，则接受输入；否则，拒绝输入。

实例的识别过程：

假设输入串为ω = 'abba'。

1. 初始化：第一个读/写头指向字符'a'，第二个读/写头指向字符'a'。
2. 比较：两个字符相等，将两个读/写头都向前移动一步。
3. 比较：两个字符相等，将两个读/写头都向前移动一步。
4. 比较：两个字符相等，将两个读/写头都向前移动一步。
5. 比较：两个字符相等，将两个读/写头都向前移动一步。
6. 结束：两个读/写头都到达输入串的末尾，接受输入。

因此，输入串'abba'是语言ωωR的一个实例，该图灵机可以接受它。