设计一个图灵机，用于将二进制数加 1

图灵机比有限自动机和下推自动机都强大。这些机器与我们迄今为止制造的任何计算机一样强大。

图灵机的形式化定义

图灵机可以形式化地描述为七元组

(Q,X, Σ,δ,q0,B,F)

其中，

  • Q 是状态的有限集合。

  • X 是带字母表

  • Σ 是输入字母表

  • δ 是转移函数：δ:QxX→QxXx{左移，右移}

  • q0 是初始状态

  • B 是空白符号

  • F 是最终状态。

图灵机 (TM) 是一种数学模型，它包含一条无限长的带，该带被分成单元格，并在其上给出输入。它包含一个读取输入带的磁头。状态寄存器存储图灵机的状态。

读取输入符号后，将其替换为另一个符号，更改其内部状态，并从一个单元格向右或向左移动。如果 TM 达到最终状态，则接受输入字符串，否则拒绝该字符串。

图灵机有一个读/写头。因此，我们可以在磁带上写入。

算法

  • 将尾随的 1 替换为 0。

  • 将最右边的第一个“0”替换为 1。

示例

二进制增量表示将 1 加到给定的输入中。

输入 - 0111

输出 - 1000

输入- 10000

输出- 10001

用于将二进制数加 1 的图灵机如下所示 -

更新于： 2021 年 6 月 14 日

3K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告