图灵机的例子

范例1：
为语言L = {0n1n2n}构造一个TM，其中n≥1
解：
L = {0n1n2n | n≥1}表示只使用3个字符（即0、1和2）的语言。在这种情况下，一定数量的0后跟相等数量的1，然后再相等数量的2。属于此类别的任何类型的字符串都将被该语言接受。
001122的仿真如下所示：

文章图片
现在，我们将看到此图灵机如何在001122上工作。最初，状态为q0，并且将head指向0的情况是：

文章图片
移动将为δ（q0，0）=δ（q1，A，R），这意味着它将进入状态q1，将0替换为A，并且磁头将向右移动为：

文章图片
【图灵机的例子】移动将为δ（q1，0）=δ（q1，0，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：

文章图片
该移动将为δ（q1，1）=δ（q2，B，R），这意味着它将进入状态q2，由B代替1，并且头部将向右移动为：

文章图片
移动将为δ（q2，1）=δ（q2，1，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：

文章图片
该移动将为δ（q2，2）=δ（q3，C，R），这意味着它将进入状态q3，将2替换为C，并且head将向右移动为：

文章图片
现在移动δ（q3，2）=δ（q3，2，L）和δ（q3，C）=δ（q3，C，L）和δ（q3，1）=δ（q3，1，L）和δ（q3，B）=δ（q3，B，L）和δ（q3，0）=δ（q3，0，L），然后移动δ（q3，A）=δ（q0，A，R），这意味着将进入状态q0，将A替换为A，并且head将向右移动为：

文章图片
该移动将为δ（q0，0）=δ（q1，A，R），这意味着它将进入状态q1，将0替换为A，并且磁头将向右移动为：

文章图片
该移动将为δ（q1，B）=δ（q1，B，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：

文章图片
该移动将为δ（q1，1）=δ（q2，B，R），这意味着它将进入状态q2，由B代替1，并且头部将向右移动为：

文章图片
该移动将为δ（q2，C）=δ（q2，C，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：

文章图片
该移动将为δ（q2，2）=δ（q3，C，L），这意味着它将进入状态q3，将2替换为C，并且磁头将向左移动，直到我们到达A为止：

文章图片
紧接B是A之前，这意味着所有0都被A卖出。因此，我们将向右移动以确保不存在1或2。移动将为δ（q2，B）=（q4，B，R），这意味着它将进入状态q4，不会更改任何符号，并向右移动为：

文章图片
移动将是（q4，B）=δ（q4，B，R）和（q4，C）=δ（q4，C，R）这意味着它将不更改任何符号，保持相同的状态并移动到正确的是：

文章图片
移动δ（q4，X）=（q5，X，R），这意味着它将进入状态q5，该状态为HALT状态，而HALT状态始终是任何TM的接受状态。

文章图片
相同的TM可用过渡图表示：

文章图片
范例2：
构造一个TM机器，以检查均匀长度的字符串的回文。
解：
首先，我们从左侧读取第一个符号，然后将其与右侧的第一个符号进行比较，以检查其是否相同。
同样，我们将左边的第二个符号与右边的第二个符号进行比较。我们对所有符号重复此过程。如果发现任何不匹配的符号，则无法使机器进入HALT状态。
假设字符串是ababbabaΔ。 ababbabaΔ的仿真如下所示：

文章图片
现在，我们将看到此图灵机如何在ababbabaΔ上工作。最初，状态为q0，头指向a：

文章图片
我们将用*标记它，并在右端搜索a：

文章图片
我们将向上移动到Δ，如下所示：

文章图片
我们将向左移动并检查是否为：

文章图片
它是“ a”，因此将其替换为Δ并向左移动为：

文章图片
现在向左移动到*为：

文章图片
向右移动并阅读

文章图片
现在将b转换为*并向右移动为：

文章图片
右移至Δ以搜寻b为：

文章图片
向左移动，如果符号为b，则将其转换为Δ，如下所示：

文章图片
现在左移直到*为：

文章图片
用*替换a，然后右移至Δ，如下所示：

文章图片
我们将向左移动并检查它是否为a，然后将Δ替换为：

文章图片
它是“ a”，因此用Δ替换为：

文章图片
现在向左移动，直到*

文章图片
现在向右移动为：

文章图片
将b替换为*，然后右移至Δ，如下所示：

文章图片
向左移动，如果左侧符号为b，则将Δ替换为：

文章图片
向左移动直到*

文章图片
向右移动并检查是否为Δ

文章图片
进入暂停状态

文章图片
相同的TM可用过渡图表示：

文章图片
范例3：
构造一个用于检查奇数长度字符串回文的TM机器。
解：
首先，我们从左侧读取第一个符号，然后将其与右侧的第一个符号进行比较，以检查其是否相同。
同样，我们将左边的第二个符号与右边的第二个符号进行比较。我们对所有符号重复此过程。如果发现任何不匹配的符号，则会使计算机进入HALT状态。
假设字符串是00100Δ。 00100Δ的仿真如下所示：
现在，我们将看到此图灵机如何在00100Δ下工作。最初，状态为q0，并且通过以下方式指向0：

文章图片
现在将0替换为*，并向右移动为：

文章图片
向右移动到Δ，如下所示：

文章图片
左移并用Δ替换0并左移：

文章图片
现在左移至*为：

文章图片
向右移动，将0转换为*，然后向右移动为：

文章图片
右移至Δ

文章图片
向左移动并用Δ替换0为：

文章图片
左移直到*为：

文章图片
向右移动并将1转换为*为：

文章图片
向左移动

文章图片
由于它是*，因此进入HALT状态。
相同的TM可用过渡图表示：

文章图片
范例4：
为一元数系统的加法函数构造TM。
解：
一元数仅由一个字符组成，即数字5可以在一元数系统中写为11111。在此TM中，我们将对两个一元数进行加法运算。
例如
2 3即11111 = 11111
如果你观察到这种加法过程，你会发现与字符串串联函数的相似之处。
在这种情况下，我们只需将其替换为1，然后向右移动以搜索字符串的末尾，我们会将后1转换为Δ。
输入：3 2
11111Δ的仿真如下所示：