haskell - 我的程序图灵完备吗？

Question

我花了一两周的时间编写一个简单的逻辑解算器。构建它之后，我发现自己想知道它解决的语言是否是图灵完备的。因此，我编写了一小组方程，它们接受 SKI 组合器微积分中的任何有效表达式，并生成包含该表达式的范式的结果集。由于 SKI 图灵完备，证明我的语言可以执行 SKI 将证明其图灵完备。

但是，有一个故障。求解器不会按正常顺序减少表达式。实际上它所做的是尝试每一种可能的缩减顺序。这意味着解决方案集通常巨大。如果存在范式，它就会在某个地方，但很难说在哪里。

这让我想到两个问题:

• 我的语言图灵完备吗？还是我需要找到更好的证明？

• 解决方案的数量是输入的可计算函数吗？

(起初，我假设解集的大小是输入大小的指数或阶乘。但仔细检查后，情况并非如此。您可以编写已经处于正常形式的巨大表达式，也可以编写已经处于正常形式的微小表达式不要终止。我有一种感觉，确定解决方案集的大小可能相当于解决停止问题，但我不完全确定......)

Answer 1

A)正如 augustss 所说，你的系统显然是图灵完备的。

B)你是对的，确定解决方案大小与停止问题相同。如果序列没有终止，那么您将获得无限的解决方案集。因此，要确定集合是否无限，您需要确定归约序列是否终止。但这正是停机问题!

C)据我记得，一个系统向图灵机发出一组指令，仅说明它们需要多少步才能终止(我想这就是解决方案集的基数)或无法终止如果指令本身未能终止，则本身就完成了。所以这应该有助于这里的直觉。