图灵机添加两个数字

sza*_*man 1 turing-machines

如何创建图灵机,它将计算用#分隔的两个二进制数字的总和,例如.111#101B,其中B是空白?结果可以写在磁带的末尾.

Ano*_*on. 11

  1. 编写图灵机将两个二进制数转换为一元(保持它们之间的空白).
  2. 写一台图灵机用1替换空白,然后从末端切下一个数字.
  3. 编写图灵机将一元数转换为二进制数.
  4. 把这三台机器连在一起.

  • 我讨厌玩死灵法师,但是当您在Google上搜索“添加图灵机线性时间的二进制数”时,就会出现这种情况。而且,这绝对不是一种有效的解决方案,因为它需要指数级的步数(原始输入大小)。 (2认同)