哥德尔、埃舍尔、巴赫印刷数论 (TNT) 谜题和解决方案
在道格拉斯·霍夫斯塔德 (Douglas Hofstader) 的《哥德尔、埃舍尔、巴赫》第 8 章中，读者面临将这 2 个陈述翻译成 TNT 的挑战：
“b 是 2 的幂”
和
“b 是 10 的幂”
以下答案正确吗？
：（假设'∃' 表示'存在一个数字'）：
∃x:(xx = b)
即“存在一个数字'x'，使得 x 乘以 x 等于 b”
如果这是正确的，那么下一个同样微不足道:
∃x:(xxxxxxxxxx = b)
我很困惑，因为作者指出它们很棘手，第二个应该需要几个小时才能解决； 我一定错过了一些明显的东西，但我看不到它！
In chapter 8 of Godel, Escher, Bach by Douglas Hofstader, the reader is challenged to translate these 2 statements into TNT:
"b is a power of 2"
and
"b is a power of 10"
Are following answers correct?:
(Assuming '∃' to mean 'there exists a number'):
∃x:(x.x = b)
i.e. "there exists a number 'x' such that x multiplied x equals b"
If that is correct, then the next one is equally trivial:
∃x:(x.x.x.x.x.x.x.x.x.x = b)
I'm confused because the author indicates that they are tricky and that the second one should take hours to solve; I must have missed something obvious here, but I can't see it!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
在持怀疑态度的科学家的帖子 这里。 它取决于数论中的中国余数定理，以及任意长素数算术序列的存在性。 正如霍夫施塔特指出的那样，即使你知道适当的定理，想出它也不容易。
There's a solution to the "b is a power of 10" problem behind the spoiler button in skeptical scientist's post here. It depends on the chinese remainder theorem from number theory, and the existence of arbitrarily-long arithmetic sequences of primes. As Hofstadter indicated, it's not easy to come up with, even if you know the appropriate theorems.
在表达“b是10的幂”时，实际上不需要中国剩余定理和/也不需要有限序列的编码。 您也可以按如下方式工作（我们使用常用符号 |、>、cd，作为具有明显含义的公式/术语的快捷方式）：
对于素数 p，让我们表示 EXP(p,a) 一些TNT 中的公式表示“p 是素数，a 是 p 的幂”。 我们已经知道如何构建一个。 （出于技术原因，我们不认为 S0 是 p 的幂，因此 ~EXP(p,S0)。）
如果 p 是素数，我们定义 EXPp(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 的幂），则公式 EXPp(c,a) 表示“a 是 c 的幂”，因为 a == 1 (mod c-1) 那么。
具有数字（即非负整数）的属性 P，有一种方法可以在 TNT 中引用具有此属性的最小数字： ⟨P(a) ∧ ∀c:⟨a>c → ~P (a)⟩⟩。
我们可以表述“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 ∧ EXP5(e,c) → ~EXP5(e,d)) ∧ ∀e:("e 是最小的使得 EXP5(c,e) ∧ EXP5(d,e)" → (d-2)|(ea)))。
解释：我们写 b = a⋅c = 2x⋅5y (x,y>0) 并选择 d=5z>b 使得 z 和 y 互质（例如 z 可以是质数）。 那么“最小的 e...”等于 (5z)y = dy ≡ 2y > (mod d-2)，并且 (d-2)|(ea) 意味着 a = 2x = e mod (d-2) = 2y （我们也有 'd-2 > 2y' 和 'd-2 > a'），因此 x = y。
备注：这种方法可以很容易地适用于定义“b 是 n 的幂”，对于任何具有固定分解 a1a2...ak，其中每个 ai 是素数 pi 和 pi 的幂= pj → i=j。
In expressing "b is a power of 10", you actually do not need the Chinese Remainder Theorem and/nor coding of finite sequences. You can alternatively work as follows (we use the usual symbols as |, >, c-d, as shortcuts for formulas/terms with obvious meaning):
For a prime number p, let us denote EXP(p,a) some formula in TNT saying that "p is a prime and a is a power of p". We already know, how to build one. (For technical reasons, we do not consider S0 to be a power of p, so ~EXP(p,S0).)
If p is a prime, we define EXPp(c,a) ≖ ⟨EXP(p,a) ∧ (c-1)|(a-1)⟩. Here, the symbol | is a shortcut for "divides" which can be easily defined in TNT using one existencial quantifier and multiplication; the same holds for c-1 (a-1, resp.) which means "the d such that Sd=c" (Sd=a, resp.).
If EXP(p,c) holds (i.e. c is a power of p), the formula EXPp(c,a) says that "a is a power of c" since a ≡ 1 (mod c-1) then.
Having a property P of numbers (i.e. nonnegative integers), there is a way how to refer, in TNT, to the smallest number with this property: ⟨P(a) ∧ ∀c:⟨a>c → ~P(a)⟩⟩.
We can state the formula expressing "b is a power of 10" (for better readability, we omit the symbols ⟨ and ⟩, and we write 2 and 5 instead of SS0 and SSSSS0):
∃a:∃c:∃d: (EXP(2,a) ∧ EXP(5,c) ∧ EXP(5,d) ∧ d > b ∧ a⋅c=b ∧ ∀e:(e>5 ∧ e|c ∧ EXP5(e,c) → ~EXP5(e,d)) ∧ ∀e:("e is the smallest such that EXP5(c,e) ∧ EXP5(d,e)" → (d-2)|(e-a))).
Explanation: We write b = a⋅c = 2x⋅5y (x,y>0) and choose d=5z>b in such a way that z and y are coprime (e.g. z may be a prime). Then "the smallest e..." is equal to (5z)y = dy ≡ 2y (mod d-2), and (d-2)|(e-a) implies a = 2x = e mod (d-2) = 2y (we have 'd-2 > 2y' and 'd-2 > a', too), and so x = y.
Remark: This approach can be easily adapted to define "b is a power of n" for any number n with a fixed decomposition a1a2...ak, where each ai is a power of a prime pi and pi = pj → i=j.
怎么样：
∀x: ∀y: (SSx∙y = b → ∃z: z∙SS0 = SSx)
（英语：任何 ≥ 2 的 b 因子本身必须能被 2 整除；字面意思：对于所有自然数x 和 y，如果 (2+x) * y = b 那么这意味着存在一个自然数 z 使得 z * 2 = (2+x) ）
我不能 100% 确定语法中允许这样做。 TNT 和 命题演算，我已经有一段时间没有仔细阅读 GEB 了。
（编辑：至少对于 b = 2n 问题；我可以理解为什么 10n 会更困难，因为 10 不是质数。但是 11n 除了将术语“SS0”替换为“SSSSSSSSSSS0”之外，效果是一样的。）
how about:
∀x: ∀y: (SSx∙y = b → ∃z: z∙SS0 = SSx)
(in English: any factor of b that is ≥ 2 must itself be divisible by 2; literally: for all natural numbers x and y, if (2+x) * y = b then this implies that there's a natural number z such that z * 2 = (2+x). )
I'm not 100% sure that this is allowed in the syntax of TNT and propositional calculus, it's been a while since I've perused GEB.
(edit: for the b = 2n problem at least; I can see why the 10n would be more difficult as 10 is not prime. But 11n would be the same thing except replacing the one term "SS0" with "SSSSSSSSSSS0".)
这是我想到的：
∀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 的幂
Here's what I came up with:
∀c:∃d:<(c*d=b)→<(c=SO)v∃e:(d=e*SSO)>>
Which translates to:
For all numbers c, there exists a number d, such that if c times d equals b then either c is 1 or there exists a number e such that d equals e times 2.
Or
For all numbers c, there exists a number d, such that if b is a factor of c and d then either c is 1 or d is a factor of 2
Or
If the product of two numbers is b then one of them is 1 or one of them is divisible by 2
Or
All divisors of b are either 1 or are divisible by 2
Or
b is a power of 2
对于表示 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 的幂问题。
For the open expression meaning that b is a power of 2, I have
∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = bThis effectively says that for all a, S(Sa ∙ SS0) is not a factor of b. But in normal terms, S(Sa ∙ SS0) is
1 + ((a + 1) * 2)or3 + 2a. We can now reword the statement as "no odd number that is at least 3 is a factor of b". This is true if and only if b is a power of 2.I'm still working on the b is a power of 10 problem.
我认为上面大部分都只是表明 b 必须是 4 的倍数。这样怎么样： ∃b:∀c:<<∀e:(c∙e) = b & ~∃c':∃c'':(ssc'∙ssc'') = c> →c=2>
我不认为格式是完美的，但它是这样写的：
存在 b，这样对于所有 c，如果 c 是 b 的因数且 c 是素数，则 c 等于 2。
I think that most of the above have only shown that b must be a multiple of 4. How about this: ∃b:∀c:<<∀e:(c∙e) = b & ~∃c':∃c'':(ssc'∙ssc'') = c> → c = 2>
I don't think the formatting is perfect, but it reads:
There exists b, such that for all c, if c is a factor of b and c is prime, then c equal 2.
这是我对“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 的幂吗？
Here is what I came up with for the statement "b is a power of 2"
∃b: ∀a: ~∃c: ((a * ss0) + sss0) * c = b
I think this says "There exists a number b, such that for all numbers a, there does not exist a number c such that (a * 2) + 3 (in other words, an odd number greater than 2) multiplied by c, gives you b." So, if b exists, and can't be zero, and it has no odd divisors greater than 2, then wouldn't b necessarily be 1, 2, or another power of 2?
我对 b 的解决方案是 2 的幂：
∀x: ∃y xy=b ( isprime(x) => x = SS0 )
isprime() 应该不难写。
my solution for b is a power of two is :
∀x: ∃y x.y=b ( isprime(x) => x = SS0 )
isprime() should not be hard to write.
一般来说，我会说“b是2的幂”相当于“除了1之外b的每个约数都是2的倍数”。 即：
∀x((∃y(y*x=b & Ø(x=S0))) → ∃z(SS0*z=x))
编辑：这不适用于 10 （感谢您的评论）。 但至少它适用于所有素数。 对不起。 我认为你毕竟必须使用某种编码序列。 如果您想要详细且更通用的方法，我建议您阅读雷蒙德·斯穆里安 (Raymond Smullyan) 所著的《哥德尔不完备定理》。
或者，您可以使用中国余数定理对数字序列进行编码，然后对递归定义进行编码，以便可以定义幂。 事实上，这基本上就是证明皮亚诺算术是图灵完备的方法。
试试这个：
然后
应该陈述“b是10的幂”，实际上是说“有一个数字y和一个数字k，使得y是不同素数的乘积，并且k通过这些素数编码的序列从1开始，有属性a的后续元素c是10*a，并且以b结尾”
In general, I would say "b is a power of 2" is equivalent to "every divisor of b except 1 is a multiple of 2". That is:
∀x((∃y(y*x=b & ¬(x=S0))) → ∃z(SS0*z=x))
EDIT: This doesnt work for 10 (thanks for the comments). But at least it works for all primes. Sorry. I think you have to use some sort of encoding sequences after all. I suggest "Gödel's Incompleteness Theorems" by Raymond Smullyan, if you want a detailed and more general approach to this.
Or you can encode Sequences of Numbers using the Chinese Remainder Theorem, and then encode recursive definitions, such that you can define Exponentiation. In fact, that is basically how you can prove that Peano Arithmetic is turing complete.
Try this:
Then
should state "b is Power of 10", actually saying "there is a number y and a number k such that y is product of distinct primes, and the sequence encoded by k throug these primes begins with 1, has the property that the following element c of a is 10*a, and ends with b"
您的表达式分别相当于语句“b 是一个平方数”和“b 是一个数的 10 次方”。 将“power of”语句转换为 TNT 相当棘手。
Your expressions are equivalent to the statements "b is a square number" and "b is the 10th power of a number" respectively. Converting "power of" statements into TNT is considerably trickier.