用于两个一元数相乘的图灵机

Question

我正在创建一台图灵机，它使用一元表示在 300 步限制内计算两个数字的乘法。例如 2 * 3 为 110111，输出为 111111。3 * 5 为 111011111，输出为 111111111111111。

from turing_machine import TuringMachine

#create the Turing machine
multiplier = TuringMachine( 
    { 
        #Write your transition rules here as entries to a Python dictionary
        #For example, the key will be a pair (state, character)
        #The value will be the triple (next state, character to write, move head L or R)
        #such as ('q0', '1'): ('q1', '0', 'R'), which says if current state is q0 and 1 encountered
        #then transition to state q1, write a 0 and move head right.
        ('q0', '1'): ('q0', '1', 'R'),
        ('q0', '0'): ('q1', '0', 'R'),

        ('q1', '1'): ('q1', '1', 'R'),
        ('q1', ''): ('q2', '0', 'L'),

        ('q2', '1'): ('q2', '1', 'L'),
        ('q2', '0'): ('q3', '0', 'R'),

        ('q3', ''): ('q3', '', 'R'),
        ('q3', '1'): ('q4', '', 'L'),
        ('q3', '0'): ('qa', '', 'R'),

        ('q4', ''): ('q4', '', 'L'),
        ('q4', '0'): ('q5', '0', 'L'),

        ('q5', 'Y'): ('q5', 'Y', 'L'),
        ('q5', '1'): ('q6', 'Y', 'R'),

        ('q6', 'Y'): ('q6', 'Y', 'R'),
        ('q6', '0'): ('q7', '0', 'R'),

        ('q7', '1'): ('q7', '1', 'R'),
        ('q7', ''): ('q7', '', 'R'),
        ('q7', '0'): ('q8', '0', 'R'),

        ('q8', '1'): ('q8', '1', 'R'),
        ('q8', ''): ('q9', '1', 'L'),

        ('q9', '1'): ('q9', '1', 'L'),
        ('q9', '0'): ('q10', '0', 'L'),

        ('q10', '1'): ('q10', '1', 'L'),
        ('q10', ''): ('q10', '', 'L'),
        ('q10', '0'): ('q5', '0', 'L'),

        ('q5', ''): ('q11', '', 'R'),
        ('q11', 'Y'): ('q11', '1', 'R'),
        ('q11', '0'): ('q3', '0', 'R'),
    }
)

multiplier.debug('111011111', step_limit=300)

这个图灵机是基于图的

但是，我无法在300步内输出3 * 5，并且对于2 * 3，输出是

110[1]11111

，如何删除前导的“110”。有人可以指出我做错了什么吗？预先感谢。

Answer 1

在您的方法中，磁头必须经常穿过磁带的整个书写部分。您可以通过确保必须复制的部分始终位于算法将写入副本的部分旁边来减少这种情况。

您可以将第二个操作数视为输出部分的一部分，并确保它使用与输出部分的其余部分不同的符号，并且它位于输出部分的最右侧。这样您就可以用更少的工作进行复制。

这是该方法的转换表（“_”为空）：

状态	阅读	写	摇头	下一个状态
开始	1	_	R	得到
得到	1	_	R	对
得到	0	_	R	清理
对	1		R	对
对	0		R	阅读
阅读	1	2	R	复制
阅读	2		R	阅读
复制	1	4	R	更多复制
复制	3	1	R	最后一个副本
复制	_	1	L	重新启动
更多复制	1,3		R	更多复制
更多复制	_	3	L	查找下一个
查找下一个	1,3		L	查找下一个
查找下一个	4	2	R	复制
最后一个副本	1,2,3	1	R	最后一个副本
最后一个副本	_	1	L	重新启动
重新启动	0,1,2		L	重新启动
重新启动	_		R	得到
清理	12	1	R	清理
清理	_		L	停下来

还有一个可运行的代码片段，用于查看它如何在您的输入上执行：

createTuring({
    transitions: [
        { state: "start",     read: "1",  write: "_", move: "R", nextState: "get"       },
        { state: "get",       read: "1",  write: "_", move: "R", nextState: "right"     },
        { state: "get",       read: "0",  write: "_", move: "R", nextState: "cleanup"   },
        { state: "right",     read: "1",              move: "R", nextState: "right"     },
        { state: "right",     read: "0",              move: "R", nextState: "read"      },
        { state: "read",      read: "1",  write: "2", move: "R", nextState: "copy"      },
        { state: "read",      read: "2",              move: "R", nextState: "read"      },
        { state: "copy",      read: "1",  write: "4", move: "R", nextState: "moreCopy"  },
        { state: "copy",      read: "3",  write: "1", move: "R", nextState: "lastCopy"  },
        { state: "copy",      read: "_",  write: "1", move: "L", nextState: "restart"   },
        { state: "moreCopy",  read: "13",             move: "R", nextState: "moreCopy"  },
        { state: "moreCopy",  read: "_",  write: "3", move: "L", nextState: "findNext"  },
        { state: "findNext",  read: "13",             move: "L", nextState: "findNext"  },
        { state: "findNext",  read: "4",  write: "2", move: "R", nextState: "copy"      },
        { state: "lastCopy",  read: "123",write: "1", move: "R", nextState: "lastCopy"  },
        { state: "lastCopy",  read: "_",  write: "1", move: "L", nextState: "restart"   },
        { state: "restart",   read: "012",            move: "L", nextState: "restart"   },
        { state: "restart",   read: "_",              move: "R", nextState: "get"       },
        { state: "cleanup",   read: "12", write: "1", move: "R", nextState: "cleanup"   },
        { state: "cleanup",   read: "_",              move: "L", nextState: "halt"      },
    ],
    initState: "start",
    tape: "111011111",
});

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

步数还有很大的改进空间，但这在 140 步中执行 3*5 的乘法，在 158 步中执行 5*3 的乘法，因此远低于 300 的限制。