13

在 Douglas Hofstader 的 Godel, Escher, Bach 的第 8 章中，读者面临着将这两个陈述翻译成 TNT 的挑战：

“b 是 2 的幂”

和

“b 是 10 的幂”

以下答案是否正确？：

（假设 '∃' 表示'存在一个数字'）：

∃x:(xx = b)

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

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

∃x:(xxxxxxxxxx = b)

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

4

10 回答 10

13

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

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

编辑：这对 10 不起作用（感谢您的评论）。但至少它适用于所有素数。对不起。我认为你毕竟必须使用某种编码序列。我建议 Raymond Smullyan 的“Gödel's Incompleteness Theorems”，如果你想要一个详细和更一般的方法来解决这个问题。

或者您可以使用中国剩余定理对数字序列进行编码，然后对递归定义进行编码，这样您就可以定义指数。事实上，这基本上就是证明 Peano Arithmetic 是图灵完备的方法。

试试这个：

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结尾"

于 2009-03-13T22:55:40.297 回答
11

您的表达式分别相当于“b 是平方数”和“b 是数字的 10 次方”的陈述。将“power of”语句转换为 TNT 相当棘手。

于 2009-03-13T20:45:53.807 回答
4

在怀疑科学家的帖子中，扰流板按钮后面的“b 是 10 的幂”问题有一个解决方案。它依赖于数论中的中国余数定理，以及任意长的素数等差数列的存在。正如 Hofstadter 所指出的，即使您知道适当的定理，也不容易提出。

于 2009-05-02T05:06:35.890 回答
3

在表达“b 是 10 的幂”时，您实际上不需要中国剩余定理和/或有限序列的编码。您也可以按如下方式工作（我们使用常用符号 |、>、cd 作为具有明显含义的公式/术语的快捷方式）：

  1. 对于素数 p，让我们用 EXP(p,a) 表示 TNT 中的某个公式，即“p 是素数，a 是 p 的幂”。我们已经知道，如何构建一个。（出于技术原因，我们不认为 S0 是 p 的幂，所以 ~EXP(p,S0)。）

  2. 如果 p 是素数，我们定义 EXP p (c,a) ≖ ⟨EXP(p,a) ∧ (c-1)|(a-1)⟩。在这里，符号 | 是“除数”的一种快捷方式，可以在 TNT 中使用一个存在量词和乘法轻松定义；c-1 (a-1, resp.) 也是如此，这意味着“d 使得 Sd=c”（Sd=a, resp.）。
    如果 EXP(p,c) 成立（即 c 是 p 的幂），则公式 EXP p (c,a) 说“a 是 c 的幂”，因为 a ≡ 1 (mod c-1) 然后。

  3. 具有数字的属性 P（即非负整数），有一种方法可以在 TNT 中引用具有此属性的最小数字：⟨P(a) ∧ ∀c:⟨a>c → ~P(a) ⟩⟩。

  4. 我们可以陈述表达“b 是 10 的幂”的公式（为了更好的可读性，我们省略了符号 ⟨ 和 ⟩，我们用 2 和 5 代替 SS0 和 SSSSS0）：
    ∃a:∃c:∃d: ( EXP(2,a) ∧ EXP(5,c) ∧ EXP(5,d) ∧ d > b ∧ a⋅c=b ∧ ∀e:(e>5 ∧ e|c ∧ EXP 5 (e,c) → ~EXP 5 (e,d)) ∧ ∀e:("e 是最小的，使得 EXP 5 (c,e) ∧ EXP 5 (d,e)" → (d-2)|(ea))) .

解释：我们写 b = a⋅c = 2 x ⋅5 y (x,y>0) 并选择 d=5 z >b 使得 z 和 y 互质（例如 z 可能是素数）。那么“最小的 e...”等于 (5 z ) y = d y ≡ 2 y (mod d-2)，并且 (d-2)|(ea) 意味着 a = 2 x = e mod (d -2) = 2 y（我们也有 'd-2 > 2 y ' 和 'd-2 > a'），所以 x = y。

备注：这种方法可以很容易地适用于定义“b 是 n 的幂”对于具有固定分解 a 1 a 2 ...a k的任何数字 n ，其中每个 a i是素数 p i和 p的幂i = p j → i = j。

于 2013-01-07T19:02:47.250 回答
2

怎么样：

∀x: ∀y: (SSx∙y = b → ∃z: z∙SS0 = SSx)

（英文：b 的任何因子 ≥ 2 本身必须能被 2 整除；字面意思是：对于所有自然数 x 和 y，如果 (2+x) * y = b 那么这意味着存在一个自然数 z 使得z * 2 = (2+x)。)

我不是 100% 确定这在TNT和命题演算的语法中是允许的，自从我仔细阅读 GEB 已经有一段时间了。

（编辑：至少对于 b = 2 n问题；我可以看到为什么 10 n会更困难，因为 10 不是素数。但是 11 n将是同一件事，除了用“SSSSSSSSSS0”替换一个术语“SS0” .)

于 2009-03-13T21:57:46.193 回答
1

这是我想出的：

∀c:∃d:<(c*d=b)→<(c=SO)v∃e:(d=e*SSO)>>

翻译为：

对于所有数 c，存在一个数 d，如果 c 乘 d 等于 b，则 c 为 1，或者存在一个数 e，使得 d 等于 e 乘以 2。

或者

对于所有数 c，存在一个数 d，这样如果 b 是 c 的因数且 d 则 c 是 1 或 d 是 2 的因数

或者

如果两个数的乘积是 b 则其中一个为 1 或其中一个可被 2 整除

或者

b 的所有除数要么是 1，要么能被 2 整除

或者

b 是 2 的幂

于 2011-07-03T04:33:53.213 回答
1

对于表示 b 是 2 的幂的开放表达式，我有∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

这有效地说明对于所有 a，S(Sa ∙ SS0) 不是 b 的因数。但在正常情况下，S(Sa ∙ SS0) 是1 + ((a + 1) * 2)或3 + 2a。我们现在可以将语句改写为“没有至少为 3 的奇数是 b 的因数”。当且仅当 b 是 2 的幂时，这是正确的。

我仍在研究 b 是 10 的幂的问题。

于 2012-07-27T05:59:07.233 回答
0

我认为上面的大部分内容只表明 b 必须是 4 的倍数。这个怎么样：∃b:∀c:<<∀e:(c∙e) = b & ~∃c':∃c' ':(ssc'∙ssc'') = c> → c = 2>

我不认为格式是完美的，但它写道：

存在 b，使得对于所有 c，如果 c 是 b 的因数且 c 是素数，则 c 等于 2。

于 2009-04-15T18:25:22.647 回答
0

以下是我对“b 是 2 的幂”这一说法的看法

∃b: ∀a: ~∃c: ((a * ss0) + sss0) * c = b

我认为这表示“存在一个数字 b，因此对于所有数字 a，不存在一个数字 c 使得 (a * 2) + 3（换句话说，大于 2 的奇数）乘以 c，给你b。” 因此，如果 b 存在，并且不能为零，并且它没有大于 2 的奇数除数，那么 b 不一定是 1、2 或 2 的另一个幂吗？

于 2011-03-04T04:06:26.837 回答
0

我对 b 的解决方案是 2 的幂是：∀x: ∃y xy=b (isprime(x) => x = SS0)

isprime() 应该不难写。

于 2016-04-28T21:23:08.097 回答