TOC 中图灵机的变体有哪些？

图灵机 (TM)也可以是确定性或非确定性的，但这并不会使它们更强大或更弱。

然而，如果磁带受到限制，你只能看到使用输入部分的磁带，那么图灵机就会变得不那么强大(线性有界自动机)，并且只能识别上下文敏感语言。

许多其他的图灵机变体都等价于原始的图灵机。这包括以下内容：

  • 多轨

  • 多磁带

  • 多磁头

  • 多维磁带

  • 离线图灵机

多磁带图灵机

具有多个磁带的图灵机，我们称之为多磁带图灵机。

每个磁带都有自己的读/写磁头。

对于 N 磁带图灵机

M={( Q,X, ∑,δ,q0,B,F)}

我们定义

δ=QxXN -> Q x XN x {L,R}N

示例

如果 n=2，当前配置 δ(q0,a,e)=(q1,X,Y,L,R)

δ=QxXN -> Q x XN x {L,R}N

非确定性图灵机

它类似于确定性图灵机，除了对于任何输入和当前状态，它都有多个选择。

如果存在一系列移动导致最终状态，则字符串被 NDTM 接受。

转移函数：

=Q x X -> 2QxXx(L,R)

NDTM 允许对于给定的磁带符号具有多个转移。

多磁头图灵机

它有多个磁头而不是一个。

每个磁头独立地读取/写入符号并向左/右移动或保持静止。

离线图灵机

离线图灵机有两个磁带，如下所示：

  • 一个磁带是只读的，包含输入。

  • 另一个是读写的，最初是空白的。

更新于：2023-11-04

33K+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告