是否存在可以解决 Vim 高尔夫问题的算法
Does there exist an algorithm that can solve Vim Golf problems
是否可以创建一个算法来解决 Vim-golf 问题？对于那些不熟悉那是什么的人，你会得到两个不同的文本块，并且必须使用尽可能少的击键次数将第一个块转换为第二个块（在规范示例中使用 Vim，或任何文本编辑您选择使用的程序）。我最初的怀疑是答案是否定的；我们知道所需文本更改数量的上限 - 手动删除差异并输入正确的文本。然而，降低到最小数量更复杂——文本编辑器可以编写强大的宏来执行任务，你可以有多个宏的组合——我猜可能有某种方法可以显示与暂停问题的对应关系，但我不太清楚细节。
编辑： 正如 WuTheFWasThat 所指出的，VIM 宏是 turing complete，因此问题很可能无法确定，因此您的答案问题是没有。我在下面的回答是错误的，因为它假设我们可以在有限的时间内决定 VIM 中给定的击键序列是否终止，但事实并非如此。
旧答案
嗯，这当然不是不可判定的，因为您可以尝试所有可能的击键序列，直到找到答案。长度有一个上限，因为您可以只删除一个并插入另一个。即使减少了一些 NP-hard 问题，您也可以使用良好的近似值。如果人类可以做到，那么计算机应该能够做得更好。
那么可行吗？可能吧，但这似乎是一个棘手的问题。
为什么？因为很多不平凡的问题，比如编辑距离、字符串分解和无数的压缩算法，似乎都可以归结为 Vim 问题。人类可以采用所有这些问题的解决方案，并将它们创造性地结合起来以得出解决方案。
是否可以创建一个算法来解决 Vim-golf 问题？对于那些不熟悉那是什么的人，你会得到两个不同的文本块，并且必须使用尽可能少的击键次数将第一个块转换为第二个块（在规范示例中使用 Vim，或任何文本编辑您选择使用的程序）。我最初的怀疑是答案是否定的；我们知道所需文本更改数量的上限 - 手动删除差异并输入正确的文本。然而，降低到最小数量更复杂——文本编辑器可以编写强大的宏来执行任务，你可以有多个宏的组合——我猜可能有某种方法可以显示与暂停问题的对应关系，但我不太清楚细节。
编辑： 正如 WuTheFWasThat 所指出的，VIM 宏是 turing complete，因此问题很可能无法确定，因此您的答案问题是没有。我在下面的回答是错误的，因为它假设我们可以在有限的时间内决定 VIM 中给定的击键序列是否终止，但事实并非如此。
旧答案
嗯，这当然不是不可判定的，因为您可以尝试所有可能的击键序列，直到找到答案。长度有一个上限，因为您可以只删除一个并插入另一个。即使减少了一些 NP-hard 问题，您也可以使用良好的近似值。如果人类可以做到，那么计算机应该能够做得更好。
那么可行吗？可能吧，但这似乎是一个棘手的问题。
为什么？因为很多不平凡的问题，比如编辑距离、字符串分解和无数的压缩算法，似乎都可以归结为 Vim 问题。人类可以采用所有这些问题的解决方案，并将它们创造性地结合起来以得出解决方案。