本文概述
- 图灵机的正式定义
图灵机具有多种功能：
- 它具有一个外部存储器，可以记住任意长输入序列。
- 它具有无限的存储功能。
- 该模型具有可轻松读取磁带左侧或右侧输入的功能。
- 机器可以根据其输入产生一定的输出。有时可能需要使用相同的输入来生成输出。因此，在该机器中，输入和输出之间的区别已消除。因此，图灵机可以使用一组通用的字母。
Q：状态的有限集合∑：输入符号的有限集合T：磁带符号q0：初始状态F：一组最终状态B：用作输入的结束标记的空白符号δ：过渡或映射功能。
映射功能显示了从有限自动机的状态和磁带上的输入符号到下一个状态，外部符号以及磁带头移动方向的映射。这被称为三重奏或图灵机程序。
(q0, a) → (q1, A, R)这意味着在q0状态下，如果我们读取符号’ a’ ，它将进入状态q1，用X代替a并向右移动（R代表右）。
例：
为语言L = {0n1n}构造TM，其中n> = 1。
解：
我们已经通过PDA解决了这个问题。在PDA中，我们有一个堆栈来记住先前的符号。图灵机的主要优点是我们有一个可以向前或向后移动的磁带头，并且可以扫描输入的磁带。
我们将应用的简单逻辑是，读出A标记的每个“ 0”，然后与输入带一起向前移动，找出1将其转换为B。现在，对所有a和b重复此过程。
现在，我们将看到该图灵机在0011上的工作方式。
文章图片
现在，我们将看到此图灵机如何在0011上工作。最初，状态为q0，并且将head指向0的方式是：
文章图片
移动将为δ（q0，0）=δ（q1，A，R），这意味着它将进入状态q1，将0替换为A，并且磁头将向右移动为：
文章图片
移动将为δ（q1，0）=δ（q1，0，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：
文章图片
该移动将为δ（q1，1）=δ（q2，B，L），这意味着它将进入状态q2，由B替换为1，并且头部将向左移动为：
文章图片
现在，移动将为δ（q2，0）=δ（q2，0，L），这意味着它将不会更改任何符号，而是保持相同的状态并向左移动：
文章图片
该移动将为δ（q2，A）=δ（q0，A，R），这意味着将进入状态q0，将A替换为A，并且头部将向右移动为：
文章图片
该移动将为δ（q0，0）=δ（q1，A，R），这意味着它将进入状态q1，将0替换为A，并且磁头将向右移动为：
文章图片
该移动将为δ（q1，B）=δ（q1，B，R），这意味着它将不会更改任何符号，而是保持相同的状态并向右移动，如下所示：
文章图片
该移动将为δ（q1，1）=δ（q2，B，L），这意味着它将进入状态q2，由B替换为1，并且头部将向左移动为：
文章图片
移动δ（q2，B）=（q2，B，L）表示将不更改任何符号，保持相同状态并向左移动，如下所示：
文章图片
现在，紧接在B之前是A，这意味着所有0都由A卖出。因此，我们将向右移动以确保不存在1。移动将为δ（q2，A）=（q0，A，R），这意味着它将进入状态q0，将不更改任何符号，并向右移动为：
文章图片
移动δ（q0，B）=（q3，B，R），这意味着它将进入状态q3，不会更改任何符号，并且向右移动为：
文章图片
移动δ（q3，B）=（q3，B，R）表示它不会更改任何符号，而是保持相同的状态并向右移动，如下所示：
文章图片
移动δ（q3，Δ）=（q4，Δ，R）表示将进入状态q4，这是HALT状态，而HALT状态始终是任何TM的接受状态。
文章图片
【自动机之图灵机】相同的TM可用过渡图表示：
推荐阅读
- 图灵机的基本模型
- 非确定性下推自动机
- 下推自动机
- 自动机CFG到PDA的转换
- 自动机PDA验收
- 自动机Greibach范式（GNF）
- 自动机Chomsky范式（CNF）
- 自动机简化CFG
- 自动机无歧义语法