Godel,Escher,Bach印刷数论(TNT)难题和解决方案

在Godel,Escher,Bach by Douglas Hofstader的第8章中,读者被要求将这两个陈述翻译成TNT:

"b是2的力量"

和

"b是10的力量"

以下答案是否正确？:

(假设'''表示'存在数字'):

∃x:(xx = b)

即"存在一个数字'x',使x乘以x等于b"

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

∃x:(xxxxxxxxxx = b)

我很困惑,因为作者表示他们很棘手,第二个应该花费数小时来解决; 我一定错过了一些明显的东西,但我看不到它!

一般来说,我会说"b是2的幂"相当于"除了1的每个除数是2的倍数".那是:

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

编辑:这不适用于10(感谢评论).但至少它适用于所有素数.抱歉.我认为你必须使用某种编码序列.如果你想要一个详细而更通用的方法,我建议Raymond Smullyan的"哥德尔的不完全性定理".

或者,您可以使用中国剩余定理对数字序列进行编码,然后对递归定义进行编码,以便您可以定义指数.事实上,基本上你可以证明Peano算术是完整的.

试试这个:

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 a=c*10))&
 ?x(D(x,y)&Prime(x)&?z(Prime(z)&z>x?¬D(z,y))?(b

应该说"b是10的幂",实际上说"有一个数字y和一个数字k使得y是不同素数的乘积,并且由这些素数以k开头的序列从1开始,具有以下属性: a的元素c是10*a,以b"结尾

        

2> Adam Rosenfi..：
您的表达式分别等同于"b是平方数"和"b是数字的10次方"的语句.将"权力"陈述转换为TNT是相当棘手的.

        
平方数是x ^ 2,2的幂是2 ^ x.