1

听说有一个状态的图灵机应该可以把二进制数转换成十进制数。我试图弄清楚这怎么可能。我目前非常不成功地强制我的方式获得结果。如何以更优雅的方式综合它？

二进制数以相反的顺序给出，例如。25 是 10011 而不是 11001。我认为这更容易。不确定它是否也是必需品。该数字由另外两个符号封装在末尾。此外，0 和 1 在开头表示为 T 和 F --> .......TFFTTXXXXX。生成的十进制数应如下所示：.....25-----XXXXX。此外，停止状态不计为真实状态。据我了解，这是制定这样一个问题的必要条件。

研究单态图灵机我发现了这篇论文。我看到有一些进位和一个计数器位，但我无法解释自己如何帮助将十进制数增加到 10，然后进行下一位的进位。给定一个状态，我正在考虑每个十进制数字至少有 10 个不同的术语，以及更多用于中断、进位、计数器等的符号。因此，我的单一状态的定义变得很长。这里有一个例子来说明我的意思（显然是错误的）：

state trigger --> (output, state, shift): 
s, 1 --> (2,s,>) 
s, 2 --> (3,s,>) 
..., s, 
s, 8 --> (9,s,>)
s, 9 --> (c,s,>)
4

1 回答 1

2

只有一种状态，您必须将信息编码为计数位。诀窍是你倒数二进制数并数数十进制数。

假设我们从 开始......[T]FFTTXXXXX，根据您的示例，[]在写入后表示我们当前的头部位置。向右并用 a 翻转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遇到时停止

您将遇到的唯一问题是您需要以某种方式覆盖9小数10。为此，将 替换9为占位符，向左移动，运行从 a.到 a的正常状态转换1，向右返回并将占位符替换为0。不要忘记添加从0到的过渡1。

顺便说一句，这似乎是我参加的某个讲座的家庭作业；）

于 2021-03-18T01:12:51.120 回答