图灵机找出磁带上出现次数最多的字符
Turing machine to find most occurring char on tape
所以我需要创建一个 TM 的文字表示，它可以找到磁带上出现次数最多的字符并擦除其他所有字符。
TM 只有一盘磁带，输入如下所示：
#a# => #a#
#aaabbaac# => #a#
字母表是{a,b,c,d}。
我需要一些提示来解决这个问题，因为我发现自己卡住了。我的第一个想法是按顺序删除字符（例如，对于任何 'a'，尝试删除另一个 'b' 然后 'c' 然后 'd' 如果可能的话）所以最后会有只保留最常出现的一个，但这似乎太复杂了。
有什么想法吗？
与任何编程任务一样，我们的想法是将其分解为您知道如何在机器中编码的可管理部分，这些部分将 运行 您的程序。一旦我们有了计划，我们就可以着急如何简化它并写下答案。
你的想法不错：我们可以看到第一个未擦除符号是什么，然后向右扫描并删除每个其他未擦除符号的一个实例，直到我们得到一个空白；然后，重新设置并重复，直到最后一次没有擦除任何符号为止。然后，找到最后剩下的未擦除符号，将其复制到磁带的前面，然后将其余部分空白，直到找到右侧的空白为止。这就是设计。
现在我们可以谈谈实现了。我们需要一种状态和转换的编码，它将具有执行上述操作的效果。我们需要做的第一件事是阅读磁带符号，找出第一个未擦除的符号是什么。我们知道 TM 无论如何都需要一个初始状态，所以这就是可能的状态。我们将调用状态 q0.
如果我们在 q0 并且看到一个空白，我们总是可以认为这意味着磁带是空的并且我们可以停止接受。请注意，问题描述不包括两种边缘情况：空字符串；具有相同数量的多个符号的字符串。如果某些符号出现相同的最大次数，我们是将它们全部显示还是什么都不显示？此推导假设我们可以不显示任何内容。
如果在 q0 中我们在磁带上看到 a，我们需要向右扫描并删除最多一个 b、c 和 d .我们甚至可以调用状态 qbcd 来提醒自己我们正在寻找什么。读到a，我们需要擦除它；我们不一定要用空白覆盖它，所以我们可以用一个特殊的符号B来表示擦除。对于其他磁带可能性，我们得到与 qacd、qabd 和 qabc 类似的过渡。
在状态 qxyz 中，其中 x、y 和 z 代表 a、b 中的三个的某种组合、c 和 d，我们希望删除 x、y 或 z 中的一个，但不会删除剩余的符号。所以，如果我们看到剩下的符号，我们就不要管磁带并向右移动；如果我们看到符号 x、y 或 z，那么我们将转换到对应于剩余要删除的两个符号的状态。会有六个这样的状态：qab、qac、qad、qbc、qbd、qcd、
在状态 qxy 中，其中 x 和 y 代表 a、b、c 中的两个的某种组合和 d，我们希望删除 x 或 y 中的一个，但不会删除其他两个符号。所以，如果我们看到其他符号，我们就不要理会磁带并向右移动；如果我们看到符号 x 或 y 然后我们转换到对应于唯一剩余要删除的符号的状态。会有四种这样的状态：qa, qb, qc, qd.
在状态 qx 中，其中 x 代表 a、b、c 和 d 之一，我们是希望删除其他三个符号的 x 但 none。所以，如果我们看到其他三个符号，我们就不要理会磁带并向右移动；如果我们看到符号 x 然后我们转换到指示每个符号之一已被删除的状态。调用此状态 qR.
如果在状态 qxyz、qxy 或 qx 中您发现一个真正的空白符号 - 表示输入已用完 - 这意味着您没有找到某些符号你想删除。这可以;在这种情况下，我们可以转换到与上一段中提到的相同状态：表示我们已经完成了一次通过并准备重复该过程的状态。
在状态 qR 中，您将磁带倒回到第一个真正空白所在的磁带开头，然后转换到我们称为 qF 的另一个状态。 qF 的唯一工作是向右扫描并找到第一个不是 B 的符号。然后，它的行为与初始状态完全一样，并重复上述过程。请注意，所有状态在读取磁带时应忽略 Bs，并跳过它们。我们甚至可以重复使用 q0，因为输入磁带最初不会有任何 B；使用此额外功能重载 q0 是安全的。
如果你到达磁带的右侧 - 所有原始输入后的空白 - 在其中一种状态 qxyz，这意味着你删除了第四个符号 w 但没有找到在同一遍中要擦除的任何其他符号。这意味着 w 最初是具有最多实例的符号。当我们检测到这种特殊情况时，我们可以转换到新状态 qa'、qb'、qc' 和 qd'，其中 return 到磁带的开头，然后过渡到状态 qa''、qb''、qc'' 和 qd'' 以写下它们的输入，然后过渡到 qE 以最终擦除磁带的其余部分，停止- 当到达输入末尾的空白时接受。
这在 TM 中是什么样子的？
state tape | new state new tape head direction
-------------------------------------------------------------
// find and erase the first symbol /////////////////////////
-------------------------------------------------------------
q0 # | halt_accept # same
q0 B | q0 B right
q0 a | qbcd B right
q0 b | qacd B right
q0 c | qabd B right
q0 d | qabc B right
-------------------------------------------------------------
// look for any of three targets ////////////////////////////
-------------------------------------------------------------
qbcd # | qa' # left
qbcd B,a | qbcd B,a right
qbcd b | qcd B right
qbcd c | qbd B right
qbcd d | qbc B right
-------------------------------------------------------------
qacd # | qb' # left
qacd B,b | qacd B,b right
qacd a | qcd B right
qacd c | qad B right
qacd d | qac B right
-------------------------------------------------------------
qabd # | qc' # left
qabd B,c | qabd B,c right
qabd a | qbd B right
qabd b | qad B right
qabd d | qab B right
-------------------------------------------------------------
qabc # | qd' # left
qabc B,d | qabc B,d right
qabc a | qbc B right
qabc b | qac B right
qabc c | qab B right
-------------------------------------------------------------
// look for any of two targets //////////////////////////////
-------------------------------------------------------------
qab # | qR # left
qab B,c,d | qab B,c,d right
qab a | qb B right
qab b | qa B right
-------------------------------------------------------------
qac # | qR # left
qac B,b,d | qac B,b,d right
qac a | qc B right
qac c | qb B right
-------------------------------------------------------------
qad # | qR # left
qad B,b,c | qad B,b,c right
qad a | qd B right
qad d | qa B right
-------------------------------------------------------------
qbc # | qR # left
qbc B,a,d | qbc B,a,d, right
qbc b | qc B right
qbc c | qb B right
-------------------------------------------------------------
qbd # | qR # left
qbd B,a,c | qbd B,a,c right
qbd b | qd B right
qbd d | qb B right
-------------------------------------------------------------
qcd # | qR # left
qcd B,a,b | qcd B,a,b right
qcd c | qd B right
qcd d | qc B right
-------------------------------------------------------------
// look for single target ///////////////////////////////////
-------------------------------------------------------------
qa #,a | qR #,B left
qa B,b,c,d | qa B,b,c,d right
-------------------------------------------------------------
qb #,b | qR #,B left
qb B,a,c,d | qb B,a,c,d right
-------------------------------------------------------------
qc #,c | qR #,B left
qc B,a,b,d | qc B,a,b,d right
-------------------------------------------------------------
qd #,d | qR #,B left
qd B,a,b,c | qd B,a,b,c right
-------------------------------------------------------------
// scan back to the beginning of the tape ///////////////////
-------------------------------------------------------------
qR # | q0 # right
qR B,a,b,c,d| qR B,a,b,c,d left
-------------------------------------------------------------
qa' # | qa'' # right
qa' B,a,b,c,d| qa' B,a,b,c,d left
-------------------------------------------------------------
qb' # | qb'' # right
qb' B,a,b,c,d| qb' B,a,b,c,d left
-------------------------------------------------------------
qc' # | qc'' # right
qc' B,a,b,c,d| qc' B,a,b,c,d left
-------------------------------------------------------------
qd' # | qd'' # right
qd' B,a,b,c,d| qd' B,a,b,c,d left
-------------------------------------------------------------
// write the output if we found one /////////////////////////
-------------------------------------------------------------
qa'' # | halt_accept # same
qa'' B,a,b,c,d| qE a right
-------------------------------------------------------------
qb'' # | halt_accept # same
qb'' B,a,b,c,d| qE b right
-------------------------------------------------------------
qc'' # | halt_accept # same
qc'' B,a,b,c,d| qE c right
-------------------------------------------------------------
qd'' # | halt_accept # same
qd'' B,a,b,c,d| qE d right
-------------------------------------------------------------
// erase the rest of the input tape /////////////////////////
-------------------------------------------------------------
qE # | halt_accept # same
qE B,a,b,c,d| qE # right
如果您宁愿将磁带头留在磁带的前面，您可以编写特殊的磁带符号，如 A、B、C 和 D 在双素数状态下，扫描到最后，向后擦除，直到找到 # 或上述符号之一。这意味着一些额外的状态，但在概念上很简单。
此 TM 有 24 个状态、96 个转换（如果完全展开）并且在每一遍中至少擦除一个符号；因此，它的 运行 时间在最坏的情况下是二次方的：输入大小 4n，每个符号的 n，算法执行 n 次传递并在每次传递中按 n 步的顺序，加上一些 o(n^2) 的东西擦除磁带的结尾。
也许这就是你的想法，但想得太复杂了。我承认写下来花了很长时间。然而，这在概念上非常简单，并且可能是单个磁带 TM 的最佳选择。
所以我需要创建一个 TM 的文字表示，它可以找到磁带上出现次数最多的字符并擦除其他所有字符。 TM 只有一盘磁带，输入如下所示：
#a# => #a#
#aaabbaac# => #a#
字母表是{a,b,c,d}。
我需要一些提示来解决这个问题，因为我发现自己卡住了。我的第一个想法是按顺序删除字符（例如，对于任何 'a'，尝试删除另一个 'b' 然后 'c' 然后 'd' 如果可能的话）所以最后会有只保留最常出现的一个，但这似乎太复杂了。
有什么想法吗？
与任何编程任务一样，我们的想法是将其分解为您知道如何在机器中编码的可管理部分，这些部分将 运行 您的程序。一旦我们有了计划，我们就可以着急如何简化它并写下答案。
你的想法不错：我们可以看到第一个未擦除符号是什么，然后向右扫描并删除每个其他未擦除符号的一个实例，直到我们得到一个空白；然后，重新设置并重复，直到最后一次没有擦除任何符号为止。然后，找到最后剩下的未擦除符号，将其复制到磁带的前面，然后将其余部分空白，直到找到右侧的空白为止。这就是设计。
现在我们可以谈谈实现了。我们需要一种状态和转换的编码，它将具有执行上述操作的效果。我们需要做的第一件事是阅读磁带符号，找出第一个未擦除的符号是什么。我们知道 TM 无论如何都需要一个初始状态，所以这就是可能的状态。我们将调用状态 q0.
如果我们在 q0 并且看到一个空白，我们总是可以认为这意味着磁带是空的并且我们可以停止接受。请注意，问题描述不包括两种边缘情况：空字符串；具有相同数量的多个符号的字符串。如果某些符号出现相同的最大次数，我们是将它们全部显示还是什么都不显示？此推导假设我们可以不显示任何内容。
如果在 q0 中我们在磁带上看到 a，我们需要向右扫描并删除最多一个 b、c 和 d .我们甚至可以调用状态 qbcd 来提醒自己我们正在寻找什么。读到a，我们需要擦除它；我们不一定要用空白覆盖它，所以我们可以用一个特殊的符号B来表示擦除。对于其他磁带可能性，我们得到与 qacd、qabd 和 qabc 类似的过渡。
在状态 qxyz 中，其中 x、y 和 z 代表 a、b 中的三个的某种组合、c 和 d，我们希望删除 x、y 或 z 中的一个，但不会删除剩余的符号。所以，如果我们看到剩下的符号，我们就不要管磁带并向右移动；如果我们看到符号 x、y 或 z，那么我们将转换到对应于剩余要删除的两个符号的状态。会有六个这样的状态：qab、qac、qad、qbc、qbd、qcd、
在状态 qxy 中，其中 x 和 y 代表 a、b、c 中的两个的某种组合和 d，我们希望删除 x 或 y 中的一个，但不会删除其他两个符号。所以，如果我们看到其他符号，我们就不要理会磁带并向右移动；如果我们看到符号 x 或 y 然后我们转换到对应于唯一剩余要删除的符号的状态。会有四种这样的状态：qa, qb, qc, qd.
在状态 qx 中，其中 x 代表 a、b、c 和 d 之一，我们是希望删除其他三个符号的 x 但 none。所以，如果我们看到其他三个符号，我们就不要理会磁带并向右移动；如果我们看到符号 x 然后我们转换到指示每个符号之一已被删除的状态。调用此状态 qR.
如果在状态 qxyz、qxy 或 qx 中您发现一个真正的空白符号 - 表示输入已用完 - 这意味着您没有找到某些符号你想删除。这可以;在这种情况下，我们可以转换到与上一段中提到的相同状态：表示我们已经完成了一次通过并准备重复该过程的状态。
在状态 qR 中，您将磁带倒回到第一个真正空白所在的磁带开头，然后转换到我们称为 qF 的另一个状态。 qF 的唯一工作是向右扫描并找到第一个不是 B 的符号。然后，它的行为与初始状态完全一样，并重复上述过程。请注意，所有状态在读取磁带时应忽略 Bs，并跳过它们。我们甚至可以重复使用 q0，因为输入磁带最初不会有任何 B；使用此额外功能重载 q0 是安全的。
如果你到达磁带的右侧 - 所有原始输入后的空白 - 在其中一种状态 qxyz，这意味着你删除了第四个符号 w 但没有找到在同一遍中要擦除的任何其他符号。这意味着 w 最初是具有最多实例的符号。当我们检测到这种特殊情况时，我们可以转换到新状态 qa'、qb'、qc' 和 qd'，其中 return 到磁带的开头，然后过渡到状态 qa''、qb''、qc'' 和 qd'' 以写下它们的输入，然后过渡到 qE 以最终擦除磁带的其余部分，停止- 当到达输入末尾的空白时接受。
这在 TM 中是什么样子的？
state tape | new state new tape head direction
-------------------------------------------------------------
// find and erase the first symbol /////////////////////////
-------------------------------------------------------------
q0 # | halt_accept # same
q0 B | q0 B right
q0 a | qbcd B right
q0 b | qacd B right
q0 c | qabd B right
q0 d | qabc B right
-------------------------------------------------------------
// look for any of three targets ////////////////////////////
-------------------------------------------------------------
qbcd # | qa' # left
qbcd B,a | qbcd B,a right
qbcd b | qcd B right
qbcd c | qbd B right
qbcd d | qbc B right
-------------------------------------------------------------
qacd # | qb' # left
qacd B,b | qacd B,b right
qacd a | qcd B right
qacd c | qad B right
qacd d | qac B right
-------------------------------------------------------------
qabd # | qc' # left
qabd B,c | qabd B,c right
qabd a | qbd B right
qabd b | qad B right
qabd d | qab B right
-------------------------------------------------------------
qabc # | qd' # left
qabc B,d | qabc B,d right
qabc a | qbc B right
qabc b | qac B right
qabc c | qab B right
-------------------------------------------------------------
// look for any of two targets //////////////////////////////
-------------------------------------------------------------
qab # | qR # left
qab B,c,d | qab B,c,d right
qab a | qb B right
qab b | qa B right
-------------------------------------------------------------
qac # | qR # left
qac B,b,d | qac B,b,d right
qac a | qc B right
qac c | qb B right
-------------------------------------------------------------
qad # | qR # left
qad B,b,c | qad B,b,c right
qad a | qd B right
qad d | qa B right
-------------------------------------------------------------
qbc # | qR # left
qbc B,a,d | qbc B,a,d, right
qbc b | qc B right
qbc c | qb B right
-------------------------------------------------------------
qbd # | qR # left
qbd B,a,c | qbd B,a,c right
qbd b | qd B right
qbd d | qb B right
-------------------------------------------------------------
qcd # | qR # left
qcd B,a,b | qcd B,a,b right
qcd c | qd B right
qcd d | qc B right
-------------------------------------------------------------
// look for single target ///////////////////////////////////
-------------------------------------------------------------
qa #,a | qR #,B left
qa B,b,c,d | qa B,b,c,d right
-------------------------------------------------------------
qb #,b | qR #,B left
qb B,a,c,d | qb B,a,c,d right
-------------------------------------------------------------
qc #,c | qR #,B left
qc B,a,b,d | qc B,a,b,d right
-------------------------------------------------------------
qd #,d | qR #,B left
qd B,a,b,c | qd B,a,b,c right
-------------------------------------------------------------
// scan back to the beginning of the tape ///////////////////
-------------------------------------------------------------
qR # | q0 # right
qR B,a,b,c,d| qR B,a,b,c,d left
-------------------------------------------------------------
qa' # | qa'' # right
qa' B,a,b,c,d| qa' B,a,b,c,d left
-------------------------------------------------------------
qb' # | qb'' # right
qb' B,a,b,c,d| qb' B,a,b,c,d left
-------------------------------------------------------------
qc' # | qc'' # right
qc' B,a,b,c,d| qc' B,a,b,c,d left
-------------------------------------------------------------
qd' # | qd'' # right
qd' B,a,b,c,d| qd' B,a,b,c,d left
-------------------------------------------------------------
// write the output if we found one /////////////////////////
-------------------------------------------------------------
qa'' # | halt_accept # same
qa'' B,a,b,c,d| qE a right
-------------------------------------------------------------
qb'' # | halt_accept # same
qb'' B,a,b,c,d| qE b right
-------------------------------------------------------------
qc'' # | halt_accept # same
qc'' B,a,b,c,d| qE c right
-------------------------------------------------------------
qd'' # | halt_accept # same
qd'' B,a,b,c,d| qE d right
-------------------------------------------------------------
// erase the rest of the input tape /////////////////////////
-------------------------------------------------------------
qE # | halt_accept # same
qE B,a,b,c,d| qE # right
如果您宁愿将磁带头留在磁带的前面，您可以编写特殊的磁带符号，如 A、B、C 和 D 在双素数状态下，扫描到最后，向后擦除，直到找到 # 或上述符号之一。这意味着一些额外的状态，但在概念上很简单。
此 TM 有 24 个状态、96 个转换（如果完全展开）并且在每一遍中至少擦除一个符号；因此，它的 运行 时间在最坏的情况下是二次方的：输入大小 4n，每个符号的 n，算法执行 n 次传递并在每次传递中按 n 步的顺序，加上一些 o(n^2) 的东西擦除磁带的结尾。
也许这就是你的想法，但想得太复杂了。我承认写下来花了很长时间。然而，这在概念上非常简单，并且可能是单个磁带 TM 的最佳选择。