数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究解释图灵机的基本特性？
图灵机比有限自动机 (FA) 和下推自动机 (PDA) 都更强大。它们与我们构建的任何计算机一样强大。
图灵机相较于 PDA 的主要改进如下所示：
无限“全部”可访问内存（以磁带的形式）——可以选择读取和写入。
读写头可以在输入磁带上向左和向右移动（或不改变位置）。
图灵机的工作原理是：一个无限的磁带被分成单元格（双向无限），每个单元格包含字母表中的一个符号或空白符号。（磁带上只写有限数量的非空白符号。）
图灵机始终处于有限数量的状态之一。
读写头读取“当前单元格”中的符号，并根据符号和当前状态：
更改状态
向任一方向移动磁头或不移动
重写“当前符号”或保持不变
默认情况下，我们讨论的是确定性图灵机。
在磁带上移动
在每个步骤中，磁头有三种可能的移动方式，如下所示：
“从当前单元格向左移动一个单元格”，
“停留在当前单元格”，或
“向右移动一个单元格”，
我们将用字母 L、S 和 R 表示它们。
图灵机指令（转移函数）
每个图灵机 (TM) 指令包含五个部分：
输入 - 当前机器状态。（来自 Q）
输入 - 从当前磁带单元格读取的磁带符号（可能是空白符号）（来自 Γ）
输出 - 要写入当前磁带单元格的磁带符号（可能是空白符号或其他符号）（来自 Γ）
输出 - 下一个机器状态（来自 Q）
输出 - 磁头移动的方向 {L, R, S}。
T : Q × Γ → Γ × Q × {L, R, S}
两个输入，三个输出：T(i, a) = (b, j, R)
Γ 包含 ∑（语言的字母表）、“空磁带符号”–，但也包含其他符号。
指令的图形形式如下所示：
这与之前的意思相同：
如果机器的当前状态为 i，并且如果当前磁带单元格中的符号为 a，
↓
然后，将 b 写入当前磁带单元格，向左移动一个单元格，并转到状态 j。
输入字符串在磁带上表示为将字符串的字母（来自 ∑）放置到相邻的磁带单元格中。
磁带的所有其他单元格都包含空白符号，我们将其表示为 。
磁头通常位于输入字符串的最左侧单元格（最左侧的非空白磁带符号）上。
3K+ 浏览量
