接受为“ 1”的单词的排字机

Question

我正在尝试找出以下任务，可以帮助您，因为我被困住了。我的目标不是直接回答（但是我不介意有人能够设计整个机器）。我对approving / disproving的想法和正确的方向更感兴趣。

任务：

构造一台接受1^k, where k=n^2 n is integer格式单词的图灵机。基本上，它接受这些单词，您可以在其中将它们排列成正方形。例如，前三个可接受的单词将是：

1Δ; 1111Δ; 111111111Δ;

哪个可以像这样排列成正方形：

1

11
11

111
111
111

我的想法：

如果我只获得“ 1”，则应该接受。

Tape: 1Δ; k=1, n=1 and k=n^2

因此，如果磁带上没有其他字符，我假设在一个“ 1”之后我处于“停止”状态（称为状态[[A）。

下一个可接受的词是下一个正方形，我们可以在公式中这样写：

(n+1)^2 That equals: n^2 + 2*n + 1

两个连续正方形之间的差是(2*n + 1)
所以，如果我的假设是正确的，如果我处于状态[[A

，我需要以某种方式检查磁带上是否获得了(2*n + 1)乘以“ 1”的倍数，并且这是否使我回到状态[[A ，它将被正确接受。其他什么都应该被拒绝。

我面临的问题是，我不知道如何在磁带上计算(2*n + 1)乘以“ 1”。

我也应该只用一根胶带找到解决方案。提示它应该以以下形式结束111#111111111Δ，其中左侧的总和等于“ k”，右侧的总和等于“

n

”。可悲的是，这个提示根本没有帮助我。我会说这对我来说更糟。

Answer 1

将输入复制到磁带的末尾，并用分隔符将其与原始输入分开

在磁带末端的一元数中写一个数字k（从1开始），并用第二个分隔符将其与副本分开

通过从副本中反复减去k并用特殊符号标记副本的k个交叉符号之一来将副本除以计数器k，]
1. 假设步骤3中的除法留下0余，以相同的方式再次除法，但仅考虑特殊标记的符号
2. 如果步骤4中的除法运算得到0余数，则看商是否为1。如果是，则发现输入= k ^ 2并可以暂停。否则，您可以在k>输入时暂停。
3. 输入1111的示例：

   1111
-> 1111A1111       // copy input
-> 1111A1111B1     // add counter
-> 1111A3333B1     // divide by 1 by bouncing back and forth, marking every 1th
-> 1111A5555B1     // repeat
-> 1111A1111B11    // don't have one 5, so copy input and increment counter
-> 1111A3232B11    // divide by 2 by bouncing back and forth, marking every 2nd
-> 1111A5242B11    // divide by 2 again considering only 3s from last step
-> accept          // halt-accept since one 5 remaining means input = k^2

您的方法也可以。您可以跟踪当前的n（或k），并在每个阶段迭代舍去副本中的2n + 1。类似于：

   1111
-> 1111A1111    // copy input
-> 1111A1111B   // begin counter at 0
-> 1111A2111B   // cross off 1 in the copy
-> 1111A2111B1  // increment counter
-> 1111A2222B1  // cross off 3 in the copy
-> accept       // all symbols crossed off

如果得到的是“来回弹跳”以进行划掉，减去，除法等操作的实际机制，则想法是将要划掉的符号更改为可以识别的符号为此标记；更改状态，以便您知道下一步需要做什么；去做标记然后，返回您开始的第一个未标记符号（如果有）。