设计一个图灵机来求二进制数的二进制补码

二进制数的二进制补码可以通过两种方法计算。

• 取反加一

• 从左到右遍历位，找到第一个1位，然后反转该1位之后的所有位。

示例

假设输入为1110010

因此，执行二进制补码后，输出如下：

输出 - 0001110

关于使用图灵机求二进制补码，

如果输入如下：

则输出如下：

解释

步骤1 - 我们需要从最右端开始。

步骤2 - 我们将读写头一直移到最右边，跳过所有的0和1。

步骤3 - 向右移动时，当到达空格B时，向左移动一步。

步骤4 - 然后我们将读写头向左移动，跳过所有的0。

步骤5 - 当它到达一个1时，我们将跳过这个1，然后向左移动一步。

步骤6 - 从现在开始，我们将所有的1变为0，所有的0变为1。

步骤7 - 我们将一直重复这个过程，直到字符串的最左边。

步骤8 - 一直移动到最左边，我们将到达空格B，

步骤9 - 然后向右移动一步，使读写头指向第一个字符，然后停止。

相应的图灵机 (TM) 如下所示。这里Q0是初始状态，Q3是最终状态。

解释

借助状态'q0'，我们可以到达字符串的末尾，当到达空格时，向左移动。

借助状态'q1'，我们可以经过所有0，并在找到第一个1后向左移动。

经过单个'1'然后向左移动。

借助状态'q2'，我们可以对每个数字取反并向左移动，当到达空格时，向右移动并到达最终状态q2。

Bhanu Priya

更新于：2021年6月15日

7K+ 浏览量

开启您的职业生涯

完成课程后获得认证

开始学习