哥德尔、埃舍尔、巴赫印刷数论 (TNT) 谜题和解决方案

StackOverflow https://stackoverflow.com/questions/644569

  •  22-07-2019
  •  | 
  •  

题

在道格拉斯·霍夫斯塔德 (Douglas Hofstader) 的《哥德尔、埃舍尔、巴赫》的第 8 章中，读者面临着将这两个陈述翻译成 TNT 的挑战：

“b 是 2 的幂”

和

“b 是 10 的幂”

以下答案是否正确？：

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

∃x:(x.x = b)

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

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

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

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

有帮助吗？

解决方案

您表达式是等效于声明“b是平方数”和“b是一个数的10次方”分别。转换语句转换TNT“的力”是相当棘手。

其他提示

在一般情况下，我会说“b为2的幂”等同于“除了1b的每一个除数为2的倍数”。是：

∀x（（∃y（Y * X = B＆¬（X = S0）））→∃z（SS0 * Z = X））

编辑：这10不工作（感谢注释）。但至少它适用于所有的素数。抱歉。我认为你必须使用某种毕竟编码序列。我建议你“哥德尔不完备性定理”，由雷蒙德·斯马恩，如果你想有一个详细的，更全面的方法来此。

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

尝试这种情况：

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开始时，具有性质下列元件C的一个是10 * a和用b结束“

在持怀疑态度的科学家的帖子中，扰流按钮后面有一个解决“b 是 10 的幂”问题的方法 这里. 。它取决于数论中的中国余数定理，以及任意长素数算术序列的存在性。正如霍夫施塔特指出的那样，即使你知道适当的定理，想出它也不容易。

怎么样：

∀x：∀y：（的SSx∙计算y = b→∃z位：Z∙SS0 = SSX）的

（英文：B的任何因素即≥2本身必须是由2整除;字面上：对于所有的自然数x和y，如果（2 + X）* Y = B，则这意味着有一个自然数ž使得Z * 2 =（2 + x）的。）

我不是100％肯定，这是允许在 TNT 和语法命题演算，它已经有一段时间，因为我已经仔细阅读GEB。

（编辑：对于B = 2 名词问题至少;我可以看到为什么10 名词会比较困难，因为10不是素数，但11 < SUP>名词将是相同的东西，除了用 “SSSSSSSSSSS0” 取代 “SS0” 一个术语。）

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

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

  2. 如果 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)。

  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 ∧ EXP5(e,c) → ~EXP5(e,d)) ∧ ∀e:("e 是最小的，使得 EXP5(c,e) ∧ EXP5(d,e)”→(d-2)|(e-a)))。

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

评论： 这种方法可以很容易地适应定义“b是n的幂”对于任何数字n具有固定的分解a1A2...Ak, ，其中每个我 是素数 p 的幂我 和 p我 = pj → i=j。

这就是我想出了：

∀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的幂

我认为最上面的只是表明B必须是4的倍数这样如何：∃b：∀c：<<∀e：（C∙E）= B＆〜∃c'： ∃c '' :( SSC'∙SSC'）= C>→C = 2>

我不认为格式化完美，但它读取：

有存在B，使得对于所有的C，如果c是B A因子和c为素数，则c等于2。

下面是我想出了语句“b是2的幂”

∃b：∀a：〜∃c：（（A * SS0）+ sss0）* C = B

我认为这表示“存在一个数B，使得对于所有数字的，不存在一个数字c使得（a * 2）+ 3（换言之，奇数大于2）乘以由C，给你b“。所以，如果b存在，并且不能为零，并且它具有大于2无奇除数，然后将非B一定是1，2或2另一电力？

有关的开放表达意思是b为2的幂，我已经∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

这有效地说，对所有A，S（萨∙SS0）不是B的一个因素。但在正常而言，S（SA∙SS0）是1 + ((a + 1) * 2)或3 + 2a。现在，我们可以改写该语句，“没有奇数是至少3是B的一个因素”。这是真实的，当且仅当b为2的幂。

我仍然在B的工作是10问题的功率。

我的B溶液是二的幂是： ∀x：∃yx.y格式= B（isprime（X）=> X = SS0）

isprime（）不应该是很难写。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top