logic - 哥德尔、埃舍尔、巴赫打印数论 (TNT) 难题和解决方案

Question

在道格拉斯·霍夫斯塔德 (Douglas Hofstader) 的哥德尔、埃舍尔、巴赫的第 8 章中，读者面临着将这 2 句话翻译成 TNT 的挑战:

“b 是 2 的幂”

和

“b 是 10 的幂”

以下答案是否正确？:

(假设“∃”表示“存在一个数字”):

∃x:(x.x = b)

即“存在一个数字‘x’，使得 x 乘以 x 等于 b”

如果这是正确的，那么下一个同样是微不足道的:

∃x:(x.x.x.x.x.x.x.x.x.x = b)

我很困惑，因为作者表示它们很棘手，第二个需要几个小时才能解决；我一定在这里错过了一些明显的东西，但我看不到它!

Answer 1

一般来说，我会说“b 是 2 的幂”相当于“b 的除 1 之外的每个除数都是 2 的倍数”。那是:

∀x((∃y(y*x=b & ¬(x=S0))) → ∃z(SS0*z=x))

编辑:这不适用于 10(感谢您的评论)。但至少它适用于所有素数。对不起。我认为您毕竟必须使用某种编码序列。如果你想要一个详细和更一般的方法，我建议 Raymond Smullyan 的“哥德尔不完备性定理”。

或者，您可以使用中国剩余定理对数列进行编码，然后对递归定义进行编码，这样您就可以定义取幂。事实上，这基本上就是你如何证明皮亚诺算术是图灵完备的。

尝试这个:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

然后

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

应该说明“b 是 10 的幂”，实际上是说“有一个数 y 和一个数 k 使得 y 是不同素数的乘积，并且通过这些素数由 k 编码的序列以 1 开始，具有以下性质a 的元素 c 是 10*a，以 b"结尾