构造用于加法的图灵机

通常在不同的有限自动机中，数字以二进制格式表示。

示例 − 2- 010

     3- 011

     4- 100

但是，在使用图灵机进行加法的情况下，系统遵循一元格式。

示例 − 2- 11 或 00

     3- 111 或 000

     4- 1111 或 0000

在一元格式中，数字表示为

因此，让我们考虑使用零来表示图灵机中用于加法的任何数字。

示例

输入 4 和 5

4=0000

5=00000

那么 4+5= 0000c00000

这两个数字由一个临时变量 c 分隔，用于表示这两个数字

输出：000000000 = 9

图灵机 (TM) 如下所示：

解释

步骤 1 − 将 0 转换为 X，跳转到步骤 3。

步骤 2 − 如果符号是“c”，则将其转换为空格，向右移动并跳转到步骤 6。

步骤 3 − 忽略 0 并向右移动。忽略“c”，然后向右移动。

步骤 4 − 忽略 0 并向右移动。将空格转换为 0，然后向左移动。

步骤 5 − 忽略 0 并向左移动。

步骤 6 − 忽略“c”，向左移动。

步骤 7 − 忽略 0 并向左移动。

步骤 8 − 忽略 X，向左移动并跳转到步骤 1。

更新于：2021年6月15日

9K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告