Godel、Escher、Bach Typographical Number Theory（TNT）パズルとソリューション

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

  •  22-07-2019
  •  | 
  •  

質問

Douglas HofstaderによるGodel、Escher、Bachの第8章では、読者はこれら2つのステートメントをTNTに翻訳するように求められています。

<！> quot; bは2 <！> quot;のべき乗です。

and

<！> quot; bは10 <！> quot;のべき乗です。

次の回答は正しいですか？：

（「<！>＃8707;」が「数字が存在する」ことを意味すると仮定）：

<！>＃8707; x：（x.x = b）

i.e。 <！> quot; xにxを掛けた値がb <！> quot;に等しくなるような数値「x」が存在する

それが正しい場合、次のものも同様に簡単です：

<！>＃8707; x：（x.x.x.x.x.x.x.x.x.x = b）

私は混乱しています。著者は、彼らがトリッキーであり、2番目のものは解決するのに何時間もかかるべきだと示しているからです。ここで明らかな何かを見逃していたはずですが、見えません！

役に立ちましたか？

解決

あなたの式は、ステートメントと同等です<！> quot; b is square number <！> quot; <！> quot; bは、数値の10乗<！> quot;それぞれ。 <！> quot; power of <！> quot;の変換TNTへのステートメントはかなり複雑です。

他のヒント

一般に、私は<！> quot; bは2のべき乗だ<！> quot; <！> quot;と同等です。1を除くbのすべての約数は2 <！> quot;の倍数です。つまり：

<！>＃8704; x（（<！>＃8707; y（y * x = b <！> amp; <！>＃172;（x = S0）））<！>＃8594; < ！>＃8707; z（SS0 * z = x））

EDIT：これは10では機能しません（コメントをありがとう）。しかし、少なくともすべての素数で機能します。ごめんなさい。結局、何らかのエンコードシーケンスを使用する必要があると思います。 <！> quot; G <！>＃246; delの不完全性定理<！> quot;より詳細でより一般的なアプローチが必要な場合は、Raymond Smullyanによって。

または、剰余定理を使用して数値のシーケンスをエンコードし、その後、指数定義を定義できるように、再帰的な定義をエンコードできます。実際、これが基本的に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))))

should state <！> quot; b is Power of 10 <！> quot ;、実際には<！> quot;と言います。yは異なる素数の積であるyとkこれらの素数は1から始まり、aの次の要素cは10 * aであり、b <！> quot;

で終わるという性質を持っています。

<！> quot; bには10のべき乗の解決策があります<！> quot;懐疑的な科学者の投稿こちらのスポイラーボタンの背後にある問題。それは数論からの中国の剰余定理と素数の任意の長さの算術シーケンスの存在に依存します。ホフスタッターが指摘したように、適切な定理を知っていても、思い付くのは簡単ではありません。

方法：

<！>＃8704; x：<！>＃8704; y：（SSx <！>＃8729; y = b <！>＃8594; <！>＃8707; z：z <！>＃8729 ; SS0 = SSx）

（英語：<！>＃8805であるbの任意の要素; 2はそれ自体2で割り切れる必要があります;文字通り：すべての自然数xおよびyに対して、（2 + x）* y = bの場合、これは暗黙的に意味しますz * 2 =（2 + x）のような自然数zがあること。）

TNT の構文でこれが許可されているかどうかは100％確信できません。 命題計算、GEBを熟読してからしばらく経ちました。

（編集：少なくともb = 2 n の問題; 10は素数ではないので10 n の方が難しい理由がわかります。しかし11 < sup> n は、1つの用語<！> quot; SS0 <！> quot;を<！> quot; SSSSSSSSSSS0 <！> quot;に置き換えることを除いて同じことです。）

<！> quot; bは10のべき乗である<！> quot;を表現する際、実際には中国剰余定理や有限シーケンスのコーディングは必要ありません。あるいは、次のように作業することもできます（|、<！> gt;、c-dなどの通常の記号を、明白な意味を持つ数式/用語のショートカットとして使用します）：

  1. 素数pの場合、<！> quot; pは素数であり、aはp <！> quot;であるというTNTの式をEXP（p、a）で表します。構築方法は既に知っています。 （技術的な理由により、S0はpのべき乗とは見なされません。したがって、〜EXP（p、S0）。）

  2. pが素数の場合、EXP p （c、a）<！>＃8790; <！>＃10216; EXP（p、a）<！>＃8743; （c-1）|（a-1）<！>＃10217;。ここで、シンボル| <！> quot; divides <！> quotのショートカットです。 1つの既存の量指定子と乗算を使用して、TNTで簡単に定義できます。同じことがc-1（a-1、それぞれ）にも当てはまります。これは、<！> quot; dがSd = c <！> quotであるということです（Sd = a、それぞれ）。
    EXP（p、c）が成り立つ場合（つまり、cはpのべき乗）、式EXP p （c、a）は、<！> quot; aはc <！> quot; <！>＃8801; 1（mod c-1）その後。

  3. プロパティPの数値（つまり、非負の整数）を使用して、TNTでこのプロパティを使用して最小の数値を参照する方法があります。<！>＃10216; P（a）<！> ＃8743; <！>＃8704; c：<！>＃10216; a <！> gt; c <！>＃8594; 〜P（a）<！>＃10217; <！>＃10217;。

  4. <！> quot; bが10 <！> quotのべき乗を表す式を記述できます。 （読みやすくするために、シンボル<！>＃10216;と<！>＃10217;を省略し、SS0とSSSSS0の代わりに2と5を記述します）：
    <！>＃8707; a：<！>＃8707; c：<！>＃8707; d：（EXP（2、a）<！>＃8743; EXP（5、c）<！>＃8743; EXP （5、d）<！>＃8743; d <！> gt; b <！>＃8743; a <！>＃8901; c = b <！>＃8743; <！>＃8704; e：（e <！> gt; 5 <！>＃8743; e | c <！>＃8743; EXP 5 （e、c）<！>＃8594;〜EXP 5 （e、d））<！>＃8743; <！>＃8704; e：（<！> quot; eはEXP 5 （c、e）<！> ＃8743; EXP 5 （d、e）<！> quot; <！>＃8594;（d-2）|（ea）））。

説明： b = a <！>＃8901; c = 2 x <！>＃8901; 5 y （ x、y <！> gt; 0）そして、zとyが互いに素になるようにd = 5 z <！> gt; bを選択します（たとえば、zは素数になります）。次に、<！> quot;最小のe ... <！> quot; （5 z ） y = d y <！>＃8801; 2 y （mod d-2）、および（d-2）|（ea）はa = 2 x = e mod（d-2）= 2 y （「d-2 <！> gt; 2 y 」と「d-2 <！> gt; a」もあります）、したがってx = yです。

備考：このアプローチは、<！> quot; bはn <！> quotのべき乗を定義するために簡単に適用できます。固定分解a 1 a 2 ... a k を持つ任意の数nに対して、各a i 素数のべき乗p i およびp i = p j <！>＃8594; i = j。

ここに私が思いついたものがあります：

<！>＃8704; c：<！>＃8707; d：<！> lt;（c * d = b）<！>＃8594; <！> lt;（c = SO）v <！ >＃8707; e：（d = e * SSO）<！> gt; <！> gt;

次のように翻訳されます：

すべての数値cについて、数値dが存在します。c×dがbに等しい場合、cは1であるか、dがe×2に等しい数値eが存在します。

または

すべての数値cには、数値dが存在します。bがcの因子であり、dの場合、cは1であるか、dは2の因子です

または

2つの数値の積がbである場合、そのうちの1つは1であるか、1つは2で割り切れます

または

bの約数はすべて1または2で割り切れます

または

bは2のべき乗です

上記のほとんどは、bが4の倍数でなければならないことだけを示していると思います。これについてはどうでしょうか。 lt; <！>＃8704; e：（c <！>＃8729; e）= b <！> amp; 〜<！>＃8707; c '：<！>＃8707; c' ':( ssc' <！>＃8729; ssc ''）= c <！> gt; <！>＃8594; c = 2 <！> gt;

書式設定は完璧だとは思いませんが、次のように表示されます：

bが存在するため、すべてのcについて、cがbの因子でcが素数の場合、cは2に等しくなります。

これは、私が声明のために思いついたものです<！> quot; bは2 <！> quotの累乗です。

<！>＃8707; b：<！>＃8704; a：〜<！>＃8707; c：（（a * ss0）+ sss0）* c = b

これは<！> quot;であると思います;すべての数字aに対して、（a * 2）+ 3（言い換えれば、奇数より大きい数字2）cを掛けると、b。<！> quot;したがって、bが存在し、ゼロにすることはできず、2を超える奇数の除数がない場合、bは必ずしも1、2、または別の2のべき乗ではありませんか？

bが2のべき乗であることを意味するオープンな表現では、∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

これは事実上、すべてのaについて、S（Sa <！>＃8729; SS0）はbの因子ではないことを示しています。しかし、通常の用語では、S（Sa <！>＃8729; SS0）は1 + ((a + 1) * 2)または3 + 2aです。これで、ステートメントを<！> quot;と言い換えることができます。少なくとも3である奇数はb <！> quot;の要因ではありません。これは、bが2のべき乗の場合にのみ当てはまります。

私はまだbの10のべき乗の問題に取り組んでいます。

私のbの解は2のべき乗です： <！>＃8704; x：<！>＃8707; y x.y = b（isprime（x）= <！> gt; x = SS0）

isprime（）を書くのは難しくありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top