prolog - 逻辑编程 - 只有一个功能符号图灵的子集 - 完整吗？

Question

如果我有一个只包含一个功能符号的逻辑编程子集，我能做所有事情吗？

我认为我不能，但我完全不确定。如果编程语言是图灵完备的语言，它可以做任何用户想做的事情。我被教导这意味着它必须能够执行 if..then..else 命令、递归和应该定义自然数。

任何帮助和意见将不胜感激！

Answer 1

在经典谓词逻辑中，公式级别和术语级别之间存在区别。由于 n 元函数可以表示为 (n+1) 元谓词，因此仅限制函数符号的数量不会降低表达性。

在prolog中，公式和术语级别没有区别。您可能会选择一个 n 元符号 p 并尝试通过 p 的嵌套来编码图灵机或等效概念（例如递归函数）。

根据我的直觉，我认为这是不可能的：您基本上可以将带有变量的 n 元树描述为叶子，但是您始终可以统一这些树。这意味着在递归推导期间每个规则头都将匹配，因此您无法表达任何大小写区别。不过，这只是一个非正式的论点，而不是证明。

PS您可能还对一元逻辑感兴趣，其中只允许一元谓词。一阶逻辑的这个片段是可判定的。