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

Question

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

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

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

Answer 1

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

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

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

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