Gödel, Escher, Bach typographische Zahlentheorie (TNT) Rätsel und Lösungen

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

  •  22-07-2019
  •  | 
  •  

Frage

In Kapitel 8 von Gödel, Escher, Bach von Douglas Hofstader wird der Leser herausgefordert, diese zwei Aussagen in TNT zu übersetzen:

"b ist eine Potenz von 2"

und

"b ist eine Leistung von 10"

Sind folgende Antworten richtig:

(Unter der Annahme, '∃' bedeutet 'gibt es eine Zahl'):

∃x: (x.x = b)

d. „Es gibt eine Reihe‚x‘, so daß x multiplizierte x gleich b“

Wenn das richtig ist, dann ist der nächste ist ebenso trivial:

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

Ich bin verwirrt, weil der Autor gibt an, dass sie sind schwierig, und dass die zweite Stunden dauern sollte zu lösen; Ich muss etwas offensichtlich hier verpasst haben, aber ich kann es nicht sehen!

War es hilfreich?

Lösung

Ihre Ausdrücke auf die Aussagen äquivalent sind „b ist eine Quadratzahl“ und „b die 10. Potenz einer Zahl ist“ bezeichnet. Konvertieren von „Macht“ Aussagen in TNT ist erheblich schwieriger.

Andere Tipps

Generell würde ich sagen, „b eine Potenz von 2 ist“ ist äquivalent zu „jeder Teiler von b außer 1 ist ein Vielfaches von 2“. Das heißt:

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

EDIT: Dies funktioniert nicht für 10 (Danke für die Kommentare). Aber zumindest funktioniert es für alle Primzahlen. Es tut uns leid. Ich glaube, Sie müssen eine Art verwenden Sequenzen schließlich kodieren. Ich schlage vor, „Gödels Unvollständigkeitssätze“ von Raymond Smullyan, wenn Sie einen detaillierten und allgemeineren Ansatz dazu wollen.

Sie können auch Zahlenfolgen mit dem chinesischen Restsatz kodieren und dann rekursive Definitionen kodieren, so dass Sie Potenzierung definieren können. In der Tat ist, dass im Grunde, wie Sie nachweisen können, dass Peano Arithmetik ist Turing abgeschlossen.

Versuchen Sie folgendes: 

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

Dann 

∃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))))

sollte „b ist Energie von 10“ -Zustand befindet, tatsächlich sagt „gibt es eine Zahl y und eine Zahl k, so dass y Produkt von verschiedenen Primzahlen ist, und die durch k throug diese Primzahlen beginnt codierte Sequenz mit 1, hat die Eigenschaft, c ein dass das folgende Element 10 * a, b und endet mit "

Es gibt eine Lösung für die „b eine Leistung von 10“ Problem hinter der Spoiler Taste in der Post skeptische Wissenschaftler hier . Es hängt von dem chinesischen Restsatz aus der Zahlentheorie, und die Existenz von beliebig langen Sequenzen von arithmetischen Primzahlen. Wie Hofstadter angegeben, es ist nicht leicht, mit zu kommen, auch wenn Sie die entsprechenden Sätze kennen.

, wie etwa:

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

(auf Englisch: jeder Faktor b, das ist ≥ 2 muss sich durch 2 teilbar sein, wörtlich: für alle natürlichen Zahlen x und y, wenn (2 + x) * y = b, dann bedeutet dies, dass es eine natürliche Zahl z, so dass z * 2 = (2 + x)).

Ich bin nicht 100% sicher, dass dies in der Syntax von TNT und Aussagenlogik , es ist schon eine Weile her, seit ich GEB perused haben.

(edit:. Für b = 2 n Problem zumindest, ich kann sehen, warum die 10 n wäre schwieriger als 10 nicht prim ist aber 11 < sup> n die gleiche Sache sein würde, die ein Begriff "SS0" mit "SSSSSSSSSSS0" außer ersetzen.)

In ausdrückt „b eine Leistung von 10 ist“, brauchen Sie eigentlich nicht den chinesischen Restsatz und / oder Codierung von endlichen Folgen. Alternativ können Sie arbeiten wie folgt (wir die üblichen Symbole wie verwenden |,>, c-d, als Shortcuts für Formeln / Begriffe mit offensichtlicher Bedeutung):

  1. Für eine Primzahl p, lassen Sie uns EXP bezeichnen (p, a) einige Formel in TNT sagen, dass "p eine Primzahl ist und a eine Potenz von p". Wir wissen bereits, wie man zu bauen. (Aus technischen Gründen haben wir nicht S0 betrachten eine Potenz von p zu sein, also ~ EXP (p, S0).)

  2. Wenn p eine Primzahl ist, definieren wir EXP p (c, a) ≖ ⟨EXP (p, a) ∧ (c-1) | (a-1)⟩. Hier wird das Symbol | ist eine Abkürzung für „Gräben“, die leicht in TNT über einen existencial Quantifizierer und Multiplikation definiert werden können; das gleiche gilt für die C-1 (a-1, resp.), die "die D, so daß Sd = C" (SD = a, resp.) bedeutet.
    Wenn EXP (p, c) gilt (dh c eine Potenz von p), die Formel EXP p (c, a) sagt, dass "a eine Leistung von c ist", da a ≡ 1 (mod c-1) dann.

  3. eine Eigenschaft P von Zahlen (dh nicht-negative ganzen Zahlen), gibt es eine Art und Weise, wie zu beziehen, in TNT, auf die kleinste Zahl mit dieser Eigenschaft: ⟨P (a) ∧ ∀c: ⟨a> c → ~ P (a) ⟩⟩.

  4. Wir können die Formel Staat ausdrücken „b ist eine Potenz von 10“ (zur besseren Lesbarkeit, lassen wir die Symbole ⟨und⟩, und wir schreiben 2 und 5 statt SS0 und 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 ist die kleinste, so dass EXP 5 (c, e) ∧ EXP 5 (d, e)“→ (d-2) |. (ea)))

Erklärung: Wir schreiben b = a⋅c = 2 x ⋅5 y (x, y> 0) und wählen d = 5 z > b in der Weise, dass z und y coprime (zB z kann eine prime). Dann "die kleinste e ..." ist gleich (5 z ) y = d y ≡ 2 y (mod d-2) und (d-2) | (ea) implizieren a = 2 x = e mod (d-2) = 2 y (wir habe 'd-2> 2 y ' und 'd-2> a', zu), und so x = y.

Bemerkung: kann dieser Ansatz leicht "eine Potenz von n b" zu definieren, angepasst werden, für eine beliebige Zahl n mit einer festen Zersetzung eines 1 a 2 ... a k , wobei jeweils ein i ist eine Potenz einer Primzahl p i und p i = p j → i = j.

Hier ist, was ich kam mit:

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

Welche übersetzt:

Für alle Zahlen c, gibt es eine Zahl d, so dass, wenn c mal d gleich b dann entweder c 1 oder gibt es eine Zahl e derart, daß d gleich e mal 2.

oder

für alle Zahlen c, gibt es eine Zahl d ist, so dass, wenn b ein Faktor ist, c und d, dann entweder C 1 oder D ist ein Faktor von 2

oder

Wenn das Produkt zweier Zahlen ist b dann einer von ihnen ist 1 oder einer von ihnen ist durch 2 teilbar

oder

Alle Teiler von b sind entweder 1 oder teilbar sind durch 2

oder

b ist eine Potenz von 2

Ich denke, dass die meisten der oben nur, daß b ein Vielfaches von 4 sein gezeigt haben müssen wie diesen: ∃b: ∀c: << ∀e: (c ∙ e) b & ~ ∃c = ': ∃c '' :( ssc '∙ ssc' ') = c> → c = 2>

Das glaube ich nicht die Formatierung ist perfekt, aber es liest:

Es gibt b, so dass für alle c, wenn c ist ein Faktor von b und c ist eine Primzahl, dann c gleich 2.

Hier ist, was ich mit der Aussage kam „b ist eine Potenz von 2“

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

Ich denke, das sagt: „Es gibt eine Reihe b existiert, so dass für alle Zahlen a, ist es nicht eine Reihe c solche bestehen, dass (a * 2) + 3 (in anderen Worten, eine ungerade Zahl größer als 2) multipliziert von c, gibt Ihnen b.“ Also, wenn b vorhanden ist, und nicht Null sein kann, und es hat keine ungerade Teiler größer als 2, dann wäre nicht notwendigerweise b sein 1, 2, oder eine andere Potenz von 2?

Für den offenen Ausdruck bedeutet, dass b eine Potenz von 2 ist, ich habe ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Das sagt effektiv, dass für alle a, S (Sa ∙ SS0) kein Faktor b ist. Aber in normalen Bedingungen, S (Sa ∙ SS0) ist 1 + ((a + 1) * 2) oder 3 + 2a. Wir können nun die Aussage als „keine ungerade Zahl, die mindestens 3 ist ein Faktor von b“ umformulieren. Dies gilt, wenn und nur wenn b eine Potenz von 2 ist.

Ich bin auf der b noch arbeiten, ist eine Leistung von 10 Problem.

meine Lösung für b ist eine Zweierpotenz ist: ∀x: ∃y x.y = b (isPrime (x) => x = SS0)

isPrime () sollte nicht schwer zu schreiben.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top