二进制到一元图灵机

Question

如何实现将输入从二进制转换为一元的图灵机？

示例： 给定输入 - $101 输出应该是-1^5=11111

Answer 1

问题陈述没有特别要求单带图灵机，这大大简化了事情。由于我们知道多磁带图灵机具有与其对应的等效单磁带机，因此我们只需担心多磁带定义并将其转换为单磁带类型作为练习。

我们将使用三带图灵机，其工作原理如下：

1. 第一盘磁带是输入磁带，我们只需从中读取。
2. 第二个胶带是我们的刮胶带。我们将在这里记录我们当前在输入字符串中查看的任何数字的一元等效项（例如 1、11、1111 等）
3. 第三个磁带是我们的输出磁带。我们将在这里记录我们的答案。
4. 我们首先转到输入磁带的最后一个符号。我们还用值 1 初始化暂存磁带。
5. 如果我们正在查看的输入磁带的当前值为1，那么我们将暂存磁带复制到输出磁带；否则，我们什么也不做。
6. 将输入磁带头向左移动一格，并将暂存磁带复制到暂存磁带本身的末尾，有效地将其上的 1 数量加倍。
7. 返回步骤5并重复，直到输入胶带头位于单面胶带正面的空白处。*

其工作原理示例：

Input:
#101#  ######### ######
^      ^         ^

After initialization:
#101#  #1####### ######
   ^    ^        ^

After first iteration of steps 5 & 6
#101#  #11###### #1####
  ^    ^          ^

After second iteration of steps 5 & 6
#101#  #1111#### #1####
 ^     ^          ^

After third iteration of steps 5 & 6
#101#  #11111111 #111111#
^      ^               ^

• 我总是假设我们在单面胶带的前面有一个标记，这样我们就知道不要越过边缘。如果您不想假设这一点，您始终可以通过将输入移动一个空格并在输入磁带前面写一个空白来强制执行它，这是执行所有其他操作之前的第一步。

Answer 2

您可以在输入左侧保留一个输出部分，用分隔符分隔（如

#

）。从输入中取出并删除最高有效数字，然后将左侧部分中的任何数字加倍，如果取出的数字是“1”，则在左侧部分添加一个“1”。重复。

要将左侧部分加倍，请应用图灵机算法典型的锯齿形方法。

下面是应用该算法的转换表（“_”为空）：

状态	阅读	写	摇头	下一个状态
开始	_ 或 0	_	对	停下来
开始	1	#	左	初始化
初始化	_	1	对	阅读
阅读	_		左	最终确定
阅读	#		对	阅读
阅读	0	#	左	双
阅读	1	#	左	携带1
携带1	#		左	携带1
携带1	1		对	延长
延长	#	1	左	双
双	#		左	双
双	1		左	标记
标记	_	1	对	重复
标记	1	3	左	复制
标记	2		左	复制最后
重复	1 或 2	1	对	重复
重复	#		对	阅读
复制	_	2	对	返回
复制	1 或 2		左	复制
返回	1 或 2		对	返回
返回	3	1	左	标记
复制最后	2		左	复制最后
复制最后	_	1	对	清理
清理	1 或 2	1	对	清理
清理	#		对	阅读
最终确定	#	_	左	最终确定
最终确定	1		对	停下来

这是一个可以使用您的输入运行的实现。请注意，生成的“1”的数量与您作为输入提供的位数呈指数关系。

createTuring({
    transitions: [
        { state: "start",    read: "_0", write: "_", move: "R", nextState: "halt" },
        { state: "start",    read: "1",  write: "#", move: "L", nextState: "init" },
        { state: "init",     read: "_",  write: "1", move: "R", nextState: "read" },      
        { state: "read",     read: "_",              move: "L", nextState: "finalise" },
        { state: "read",     read: "#",              move: "R", nextState: "read" },
        { state: "read",     read: "0",  write: "#", move: "L", nextState: "double" },
        { state: "read",     read: "1",  write: "#", move: "L", nextState: "carry1" },
        { state: "carry1",   read: "#",              move: "L", nextState: "carry1" },
        { state: "carry1",   read: "1",              move: "R", nextState: "extend" },
        { state: "extend",   read: "#",  write: "1", move: "L", nextState: "double" },
        { state: "double",   read: "#",              move: "L", nextState: "double" },
        { state: "double",   read: "1",              move: "L", nextState: "mark"   },
        { state: "mark",     read: "_",  write: "1", move: "R", nextState: "repeat" },
        { state: "mark",     read: "1",  write: "3", move: "L", nextState: "copy" },
        { state: "repeat",   read: "12", write: "1", move: "R", nextState: "repeat" },
        { state: "repeat",   read: "#",              move: "R", nextState: "read" },
        { state: "copy",     read: "_",  write: "2", move: "R", nextState: "back" },
        { state: "copy",     read: "12",             move: "L", nextState: "copy" },
        { state: "back",     read: "12",             move: "R", nextState: "back" },
        { state: "back",     read: "3",  write: "1", move: "L", nextState: "mark" },
        { state: "mark",     read: "2",              move: "L", nextState: "copyLast" },
        { state: "copyLast", read: "2",              move: "L", nextState: "copyLast" },
        { state: "copyLast", read: "_",  write: "1", move: "R", nextState: "cleanup" },
        { state: "cleanup",  read: "12", write: "1", move: "R", nextState: "cleanup" },
        { state: "cleanup",  read: "#",              move: "R", nextState: "read" },
        { state: "finalise", read: "#",  write: "_", move: "L", nextState: "finalise" },
        { state: "finalise", read: "1",              move: "R", nextState: "halt" },
    ],
    initState: "start",
    tape: "1011",
});

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