构建一个图灵机来将二进制自然数加2？

图灵机(TM)可以形式化地描述为七元组：

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

其中：

  • Q 是有限状态集。

  • X 是带字母表。

  • ∑ 是输入字母表。

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

  • q0 是初始状态。

  • B 是空白符号。

  • F 是最终状态。

输入 - n 一个自然数

输出 - n + 2

让我们用一元形式表示自然数（例如，3 = 111，5 = 11111），0用空符号表示。

算法

将磁带头移动到第一个1的左侧（如果存在）。

将该空单元格更改为1。

左移并重复。

停止

我们只需要3个状态：0（初始）、1和停止；以及三个指令：

(1): (0, 1, 1, L, 0) 向左移动到空白单元格。

(2): (0, , 1, L, 1) 在单元格中写入1并向左移动。

(3): (1, ❑, 1, S, 停止) 在单元格中写入1并停止。

图形化表示如下

瞬时描述

状态 0：❑ 1 1 1 ❑ 从状态 0 开始

状态 0：❑ 1 1 1 ❑ (1)

状态 1：❑ 1 1 1 1 ❑ (2)

停止：❑ 1 1 1 1 1 ❑ (3)

更新于：2021年6月16日

702 次浏览

启动你的职业生涯

通过完成课程获得认证

开始
广告