图灵机算法计算0并写出二进制数量

Question

我碰巧需要一个用于图灵机的算法,该算法读取0的字符串,然后在磁带上写入二进制文件中有多少.

我意识到在实践中,机器实际上并不会计算0,但我很难知道如何做到这一点.

首先,我需要用X或其他东西来标记二进制数开始的位置,然后只为前0写一个1,如果最低有效位为0则为后面的每个0写一个它变为a 1但是如果它是1？也许把它变成0并继续左转将所有的1都变成0直到我找到0或空白变为1？然后再说一次,在这种情况下,无论LSB是什么都是一样的,因为我只做同样的事情,只有0才是第一个位置......

嗯......橡皮鸭......

Answer 1

假设输入磁带是#00000000000#,初始读取位置是第一个0.

1. 向右移动直到到达终点#,保持0遇到的数量的奇偶校验(最初为0,然后为1,然后为0,......).0用a 替换每对中的第一个-.在-读取被忽略,不改变奇偶校验.

2. 将奇偶校验写入输出磁带并向左移动(按顺序写入位)

3. 将输入头返回到左侧#,然后转到1.

在第一遍结束时,输入磁带将被#-0-0-0-0-0-#输出1.

在第二次传球结束时:#---0---0---#和11.

在第三次传球结束时:#-------0---#和011.

在第四轮结束时:#-----------#和1011.

Answer 2

编辑：我承认班维尔。

我昨晚想出了我想做什么，它需要两个独立的图灵机，这可能是作弊。

第一台机器的磁头会在输入磁带上运行，如果第二台机器扫描到 0，则简单地启动第二台机器。

第二台机器只是一个加法机，会将 1 加到当前数字上，这很容易做到，它只是长加法，您可以创建一个状态，表示有余数，然后继续向左移动，直到达到零（并将其替换为 1）或找到一个空白点（并创建一个 1）。

班维尔赢得了我的投票。