将两个小数相加的图灵机

Question

我无法概念化如何开始解决这个问题。 我能够创建一个图灵机，将两个一元数和两个二进制数相加。

我对如何解决这个问题有了一个大概的了解：

当第一个数字 > 0 时： 减少第一个数字。 增加第二个数字。

如何实际减少十进制数？

Answer 1

这样，我们就可以将两个数字相加。

Answer 2

假设磁带上的输入有两个数字（以十进制基数表示），并用

+

符号分隔，您可以采用以下方法：

使用“冻结”数字的概念，即以以后可以撤消的方式标记它们。例如，您可以使用此映射：

      0 → a, 1 → b, 2 → c,... 9 → j.  

然后像这样进行：

• 检查第二个操作数的最后一位：

  • 如果为“0”，则将其删除，并找到第一个操作数最右边的非冻结数字：

    • 如果有这样的数字，“冻结”它。
    • 如果没有更多数字，则在输入前面添加冻结的“0”（即“a”）。

  • 如果不是“0”，则将该数字减 1，转到第一个操作数最右边的非冻结数字：

    • 如果没有找到数字，则在前面添加“1”。
    • 如果找到的数字是“9”，则将其变为“0”，并按照相同的步骤将其左边的数字增加。
    • 如果有任何其他数字，则将其增加 1。

• 重复，直到最后一个字符是

  +

  分隔符。

• 删除

  +

  分隔符并将任何冻结的数字转换为原始数字。

这是该方法的转换表，嵌入在可运行的代码片段中，您可以在其中提供您选择的输入：

createTuring ({
    transitions: [
        { state: "start",  read: "0123456789+",     move: "R", nextState: "start"  },
        { state: "start",  read: "_",               move: "L", nextState: "dec"    },
        { state: "dec",    read: "0",   write: "_", move: "L", nextState: "shift"  },
        { state: "dec",    read: "1",   write: "0", move: "L", nextState: "left"   },
        { state: "dec",    read: "2",   write: "1", move: "L", nextState: "left"   },
        { state: "dec",    read: "3",   write: "2", move: "L", nextState: "left"   },
        { state: "dec",    read: "4",   write: "3", move: "L", nextState: "left"   },
        { state: "dec",    read: "5",   write: "4", move: "L", nextState: "left"   },
        { state: "dec",    read: "6",   write: "5", move: "L", nextState: "left"   },
        { state: "dec",    read: "7",   write: "6", move: "L", nextState: "left"   },
        { state: "dec",    read: "8",   write: "7", move: "L", nextState: "left"   },
        { state: "dec",    read: "9",   write: "8", move: "L", nextState: "left"   },
        { state: "dec",    read: "+",   write: "_", move: "L", nextState: "clean"  },
        { state: "left",   read: "0123456789",      move: "L", nextState: "left"   },
        { state: "left",   read: "+abcdefghij",     move: "L", nextState: "inc"    },
        { state: "shift",  read: "0123456789",      move: "L", nextState: "shift"  },
        { state: "shift",  read: "+abcdefghij",     move: "L", nextState: "fix"    },
        { state: "fix",    read: "abcdefghij",      move: "L", nextState: "fix"    },
        { state: "fix",    read: "0",   write: "a", move: "R", nextState: "right"  },
        { state: "fix",    read: "1",   write: "b", move: "R", nextState: "right"  },
        { state: "fix",    read: "2",   write: "c", move: "R", nextState: "right"  },
        { state: "fix",    read: "3",   write: "d", move: "R", nextState: "right"  },
        { state: "fix",    read: "4",   write: "e", move: "R", nextState: "right"  },
        { state: "fix",    read: "5",   write: "f", move: "R", nextState: "right"  },
        { state: "fix",    read: "6",   write: "g", move: "R", nextState: "right"  },
        { state: "fix",    read: "7",   write: "h", move: "R", nextState: "right"  },
        { state: "fix",    read: "8",   write: "i", move: "R", nextState: "right"  },
        { state: "fix",    read: "9",   write: "j", move: "R", nextState: "right"  },
        { state: "fix",    read: "_",   write: "a", move: "R", nextState: "right"  },
        { state: "right",  read: "abcdefghij+0123456789", move: "R", nextState: "right" },
        { state: "right",  read: "_",               move: "L", nextState: "dec"    },
        { state: "inc",    read: "abcdefghij",      move: "L", nextState: "inc"    },
        { state: "inc",    read: "0",   write: "1", move: "R", nextState: "repeat" },
        { state: "inc",    read: "1",   write: "2", move: "R", nextState: "repeat" },
        { state: "inc",    read: "2",   write: "3", move: "R", nextState: "repeat" },
        { state: "inc",    read: "3",   write: "4", move: "R", nextState: "repeat" },
        { state: "inc",    read: "4",   write: "5", move: "R", nextState: "repeat" },
        { state: "inc",    read: "5",   write: "6", move: "R", nextState: "repeat" },
        { state: "inc",    read: "6",   write: "7", move: "R", nextState: "repeat" },
        { state: "inc",    read: "7",   write: "8", move: "R", nextState: "repeat" },
        { state: "inc",    read: "8",   write: "9", move: "R", nextState: "repeat" },
        { state: "inc",    read: "9",   write: "0", move: "L", nextState: "inc"    },
        { state: "inc",    read: "_",   write: "1", move: "R", nextState: "repeat" },
        { state: "repeat", read: "abcdefghij+0123456789", move: "R", nextState: "repeat" },
        { state: "repeat", read: "_",               move: "L", nextState: "dec"    },
        { state: "clean",  read: "a0",  write: "0", move: "L", nextState: "clean"  },
        { state: "clean",  read: "b1",  write: "1", move: "L", nextState: "clean"  },
        { state: "clean",  read: "c2",  write: "2", move: "L", nextState: "clean"  },
        { state: "clean",  read: "d3",  write: "3", move: "L", nextState: "clean"  },
        { state: "clean",  read: "e4",  write: "4", move: "L", nextState: "clean"  },
        { state: "clean",  read: "f5",  write: "5", move: "L", nextState: "clean"  },
        { state: "clean",  read: "g6",  write: "6", move: "L", nextState: "clean"  },
        { state: "clean",  read: "h7",  write: "7", move: "L", nextState: "clean"  },
        { state: "clean",  read: "i8",  write: "8", move: "L", nextState: "clean"  },
        { state: "clean",  read: "j9",  write: "9", move: "L", nextState: "clean"  },
        { state: "clean",  read: "_",               move: "R", nextState: "halt"   },
    ],
    initState: "start",
    tape: "87+967",
});

<script src="https://trincot.github.io/turing.js"></script>