TOC中的图灵机

图灵机由Alan Turing于1936年发明，用于接受递归可枚举语言（由Type-0语法生成）。

图灵机由无限长的磁带组成，可以在磁带上执行读写操作。磁带由无限个单元组成，每个单元上要么包含输入符号，要么包含一个称为空白的特殊符号。它还包括一个指向当前正在读取的单元格的头指针，它可以向两个方向移动。

图：图灵机

TM表示为7元组（Q，T，B，∑, δ、 q0，F）其中：

• Q 是一组有限的状态
• T 是磁带字母表（可以写在磁带上的符号）
• B 是空白符号（除了最初输入的字母表外，每个单元格都用B填充）
• ∑ 是输入字母表（属于输入字母表的符号）
• δ 是一个映射Q×T的转移函数→ Q×T×{L，R}。根据其当前状态和当前磁带字母表（由磁头指针指向），它将移动到新状态，更改磁带符号（可能更改或可能更改），并将磁头指针向左或向右移动。
• q0 是初始状态吗
• F 是最终状态的集合。如果达到F的任何状态，则接受输入字符串。

让我们为L={0^n1^n |n>=1}构造一个图灵机

• Q={q0，q1，q2，q3}，其中q0是初始状态。
• T={0,1,X，Y，B}，其中B表示空白。
• ∑ = {0,1}
• F={q3}

表1给出了过渡函数δ：

插图

让我们看看这台图灵机是如何为0011工作的。最初，head指向带下划线的0，状态为q0，如下所示：

移动将是δ（q0，0）=（q1，X，R）。这意味着，它将进入状态q1，将0替换为X，头部将向右移动，如下所示：

移动将是δ（q1，0）=（q1，0，R），这意味着它将保持在相同的状态，并且在不改变任何符号的情况下，它将向右移动，如下所示：

移动将是δ（q1，1）=（q2，Y，L），这意味着它将移动到q2状态，并将1更改为Y，它将向左移动，如下所示：

以同样的方式操作，机器将达到状态q3，头部将指向B，如图所示：

使用移动δ（q3，B）=停止，它将停止并接受。

注：

• 在非确定性图灵机中，对于给定的状态和磁带符号，可以有多个可能的移动，但非确定性TM不会增加任何功率。
• 每个非确定性TM都可以转换为确定性TM。
• 在多磁带图灵机中，可以有多个磁带和相应的头部指针，但它不会给图灵机增加任何功能。
• 每个多磁带TM都可以转换为单磁带TM。

问题: 单磁带图灵机M有两种状态q0和q1，其中q0是起始状态。M的磁带字母表是{0,1,B}，其输入字母表是{0,1}。符号B是用于表示输入字符串结束的空白符号。下表描述了M的过渡函数。

该表的解释如下所示。第q0行和第1列中的条目（q1，1，R）表示，如果M处于状态q0，在当前磁带方格上读取1，则它在同一磁带方格上写入1，将其磁带头向右移动一个位置，并转换到状态q1。关于M，以下哪项陈述是正确的？

1. M不会在（0+1）中的任何字符串上停止+
2. M不会停在（00+1）中的任何字符串上*
3. M在以0结尾的所有字符串上暂停
4. M在以1结尾的所有字符串上暂停

解决方案：让我们看看机器是否在字符串“1”上停止。初始状态为q0，头部指向1，表示：

使用δ（q0，1）=（q1，1，R），它将移动到状态q1，头部将向右移动，如下所示：

使用δ（q1，B）=（q0，B，L），它将移动到状态q0，头部将向左移动，如下所示：

它将以同样的方式一次又一次地运行，而不会停止。

选项D表示M会在所有以1结尾的字符串上暂停，但它不会暂停1。因此，选项D是不正确的。

让我们看看机器是否在字符串“0”上停止。初始状态为q0，头部指向1，表示：

使用δ（q0，0）=（q1，1，R），它将移动到状态q1，头部将向右移动，如下所示：

使用δ（q1，B）=（q0，B，L），它将移动到状态q0，头部将向左移动，如下所示：

它将以同样的方式一次又一次地运行，而不会停止。

选项C表示M会在所有以0结尾的字符串上暂停，但不会在0处暂停。所以，选项C是不正确的。

选项B表示TM不会因任何字符串（00+1）*而停止。但是空字符串是（00+1）*的一部分，对于空字符串，TM将停止。对于空字符串，磁带将，

使用δ（q0，B）=halt，TM将停止。由于TM暂停为NULL，此选项也不正确。 因此，选项（A）是正确的。

本文由 奏鸣曲 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论