具有将二进制转换为十进制的一种状态的图灵机
Turing machine with one state that converts binary to decimal
听说只有一个状态的图灵机应该可以将二进制数转换成十进制数。我想弄清楚这怎么可能。我目前很不成功地暴力破解我的结果。如何以更优雅的方式综合它？
二进制数以相反的顺序给出，例如。 25 是 10011 而不是 11001。我认为这样更容易。不确定这是否也是必需的。该数字由另外两个符号封装在末尾。另外 0 和 1 在开头表示为 T 和 F --> ......TFFTTXXXXX。生成的十进制数应如下所示：.....25-----XXXXX。此外，暂停状态不计入真实状态。据我了解，这是制定这样一个问题的必要条件。
研究单态图灵机我发现 this paper。我看到有一个进位和一个计数器位，但我自己无法解释这将如何帮助将十进制数增加到 10，然后进行进位到下一位。给定一个状态，我正在考虑每个十进制数字至少有 10 个不同的术语，还有一些用于中断、进位、计数器等的符号。因此，我的单一状态的定义变得很长。这里有一个例子来说明我的意思（明显错误）：
state trigger --> (output, state, shift):
s, 1 --> (2,s,>)
s, 2 --> (3,s,>)
..., s,
s, 8 --> (9,s,>)
s, 9 --> (c,s,>)
只有一种状态，您必须以计数位编码信息。诀窍是你在二进制数上倒数，在十进制数上倒数。
假设我们从 ......[T]FFTTXXXXX 开始，根据您的示例，[] 表示写入后我们当前的头部位置。向右移动 T 和 F 以减少二进制数。然后，用 1 覆盖遇到的（和任何未来的）.。您现在应该拥有以下内容：
.....[.]FFFTTXXXXX.....[1]FFFTTXXXXX
往右走。现在，我们 运行 遇到一个问题：我们需要经过 Fs，将它们翻转到 Ts，转到第一个 T，然后返回。为了不翻转我们刚刚传递的数字，我们将它们替换为占位符，如-，结果如下：
.....1[F]FFTTXXXXX.....1-[F]FTTXXXXX.....1--[F]TTXXXXX.....1---[T]TXXXXX.....1--[-]FTXXXXX
现在，返回并替换占位符：
.....1-[-]TFTXXXXX.....1[-]TTFTXXXXX.....[1]TTTFTXXXXX
现在只需将 1 增加到 2：.....2[T]TTFTXXXXX。
再次向右走，重复这个过程：
.....[2]FTTFTXXXXX.....3[F]TTFTXXXXX.....3-[T]TFTXXXXX.....3[-]FTFTXXXXX.....[3]TFTFTXXXXX.....4[T]FTFTXXXXX- 等直到图灵机在第一个
X 遇到 时停止
您将遇到的唯一问题是您需要以某种方式用 10 覆盖小数 9。为此，将 9 替换为占位符，向左移动，运行 将正常状态从 . 转换为 1，向右返回并替换带有 0 的占位符。不要忘记添加从 0 到 1 的过渡。
顺便说一句，这似乎是我也参加的某个讲座的家庭作业;)
听说只有一个状态的图灵机应该可以将二进制数转换成十进制数。我想弄清楚这怎么可能。我目前很不成功地暴力破解我的结果。如何以更优雅的方式综合它？
二进制数以相反的顺序给出，例如。 25 是 10011 而不是 11001。我认为这样更容易。不确定这是否也是必需的。该数字由另外两个符号封装在末尾。另外 0 和 1 在开头表示为 T 和 F --> ......TFFTTXXXXX。生成的十进制数应如下所示：.....25-----XXXXX。此外，暂停状态不计入真实状态。据我了解，这是制定这样一个问题的必要条件。
研究单态图灵机我发现 this paper。我看到有一个进位和一个计数器位，但我自己无法解释这将如何帮助将十进制数增加到 10，然后进行进位到下一位。给定一个状态，我正在考虑每个十进制数字至少有 10 个不同的术语，还有一些用于中断、进位、计数器等的符号。因此，我的单一状态的定义变得很长。这里有一个例子来说明我的意思（明显错误）：
state trigger --> (output, state, shift):
s, 1 --> (2,s,>)
s, 2 --> (3,s,>)
..., s,
s, 8 --> (9,s,>)
s, 9 --> (c,s,>)
只有一种状态，您必须以计数位编码信息。诀窍是你在二进制数上倒数，在十进制数上倒数。
假设我们从 ......[T]FFTTXXXXX 开始，根据您的示例，[] 表示写入后我们当前的头部位置。向右移动 T 和 F 以减少二进制数。然后，用 1 覆盖遇到的（和任何未来的）.。您现在应该拥有以下内容：
.....[.]FFFTTXXXXX.....[1]FFFTTXXXXX
往右走。现在，我们 运行 遇到一个问题：我们需要经过 Fs，将它们翻转到 Ts，转到第一个 T，然后返回。为了不翻转我们刚刚传递的数字，我们将它们替换为占位符，如-，结果如下：
.....1[F]FFTTXXXXX.....1-[F]FTTXXXXX.....1--[F]TTXXXXX.....1---[T]TXXXXX.....1--[-]FTXXXXX
现在，返回并替换占位符：
.....1-[-]TFTXXXXX.....1[-]TTFTXXXXX.....[1]TTTFTXXXXX
现在只需将 1 增加到 2：.....2[T]TTFTXXXXX。
再次向右走，重复这个过程：
.....[2]FTTFTXXXXX.....3[F]TTFTXXXXX.....3-[T]TFTXXXXX.....3[-]FTFTXXXXX.....[3]TFTFTXXXXX.....4[T]FTFTXXXXX- 等直到图灵机在第一个
X遇到 时停止
您将遇到的唯一问题是您需要以某种方式用 10 覆盖小数 9。为此，将 9 替换为占位符，向左移动，运行 将正常状态从 . 转换为 1，向右返回并替换带有 0 的占位符。不要忘记添加从 0 到 1 的过渡。
顺便说一句，这似乎是我也参加的某个讲座的家庭作业;)