ألغاز وحلول غودل، إيشر، باخ، نظرية الأعداد المطبعية (TNT).

Question

في الفصل الثامن من كتاب غودل، إيشر، باخ بقلم دوجلاس هوفستادر، يواجه القارئ تحديًا لترجمة هاتين العبارتين إلى مادة تي إن تي:

"ب هي قوة 2"

و

"ب هي قوة 10"

هل الإجابات التالية صحيحة؟:

(بافتراض أن "∃" تعني "يوجد رقم"):

∃س :(x.x = ب)

أي."يوجد رقم 'x' حيث x مضروبة في x يساوي b"

إذا كان هذا صحيحًا، فالأمر التالي تافه أيضًا:

∃x:(x.x.x.x.x.x.x.x.x.x = ب)

أنا في حيرة من أمري لأن المؤلف يشير إلى أنها صعبة وأن الحل الثاني يستغرق ساعات؛لا بد أنني فاتني شيئًا واضحًا هنا، لكني لا أستطيع رؤيته!

Answer 1

والتعبيرات الخاصة بك هي ما يعادل البيانات "ب هو عدد مربع" و "ب هي القوة 10th من عدد" على التوالي. تحويل "قوة" البيانات إلى TNT هي اصعب بكثير.

Answer 2

في عام، أود أن أقول "ب هي قوة 2" ما يعادل "كل المقسوم ب باستثناء 1 من مضاعفات 2". وهذا هو:

و∀x ((∃y (ص * س = ب & ¬ (س = S0))) → ∃z (SS0 * ض = خ))

وتحرير: هذا لا يعمل لمدة 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))))

ويجب القول "ب هي قوة 10"، وقال في الواقع "هناك ص عدد وك عدد بحيث y غير المنتج يعبي متميزة، وتسلسل المشفرة بواسطة ك مارا هذه يعبي يبدأ ب 1، لديه ممتلكات أن العنصر التالي ج من هو 10 * لذلك، وينتهي ب "

Answer 3

وهناك حل لل"ب هو قوة 10" المشكلة راء زر المفسد في آخر عالم متشكك في <لأ href = "http://echochamber.me/viewtopic.php؟f=17&t=13203#p312945" يختلط = "نوفولو noreferrer"> هنا . ان ذلك يعتمد على نظرية الباقي الصينية من نظرية الأعداد، ووجود تسلسل الحسابية بشكل تعسفي طويلة من الأعداد الأولية. كما هو مبين هوفستادتر، فإنه ليس من السهل الخروج، حتى لو كنت تعرف النظريات المناسبة.

Answer 4

وماذا عن:

و∀x: ∀y: (SSX ∙ ص = ب → ∃z: ض ∙ SS0 = SSX)

و(بالإنجليزية: أي عامل ب أن ≥ 2 يجب أن تكون هي نفسها القسمة على 2، حرفيا: لجميع الأرقام س الطبيعية و y، إذا (2 + س) * ص = ب فإن هذا يعني أن هناك عددا الطبيعي ض بحيث ض * 2 = (2 + س)).

ولست متأكدا 100٪ أن يسمح هذا في بناء جملة TNT و حساب التفاضل والتكامل اقتراحي ، انها كانت فترة من الوقت منذ أن كنت قد تصفحت GEB.

و(تحرير: لب = 2 <سوب> ن في مشكلة على الأقل؛ أستطيع أن أرى لماذا 10 <سوب> ن سيكون أكثر صعوبة من 10 ليس رئيس ولكن 11 < سوب> ن في أن يكون الشيء نفسه باستثناء استبدال مصطلح واحد "SS0" مع "SSSSSSSSSSS0".)

Answer 5

عند التعبير عن "b هي قوة 10"، فأنت في الواقع لا تحتاج إلى نظرية الباقي الصينية و/ولا ترميز التسلسلات المحدودة.يمكنك بدلاً من ذلك العمل على النحو التالي (نستخدم الرموز المعتادة مثل |، >، c-d، كاختصارات للصيغ/المصطلحات ذات المعنى الواضح):

1. بالنسبة للرقم الأولي p، دعونا نشير إلى EXP(p,a) ببعض الصيغ في TNT التي تقول أن "p هو عدد أولي وa هي قوة p".نحن نعرف بالفعل كيفية بناء واحدة.(لأسباب فنية، نحن لا نعتبر S0 قوة لـ p، لذلك ~EXP(p,S0).)

2. إذا كانت p أولية، فإننا نحدد EXP_ص(ج,أ) ≖ ⟨EXP(p,a) ∧ (ج-1)|(أ-1)⟩.هنا ، الرمز | هو اختصار لـ "الانقسامات" التي يمكن تعريفها بسهولة في TNT باستخدام كمية وضرب الوجودية واحدة ؛وينطبق الشيء نفسه على c-1 (a-1, resp.) والذي يعني "d بحيث Sd=c" (Sd=a, resp.).
   إذا كانت EXP(p,c) تحمل (أيc هي قوة p)، الصيغة EXP_ص(ج، أ) يقول أن "أ هي قوة ج" منذ ≡ 1 (mod c-1) إذن.

3. وجود خاصية P من الأرقام (أي.(الأعداد الصحيحة غير السالبة)، هناك طريقة لكيفية الإشارة، في TNT، إلى أصغر رقم بهذه الخاصية:⟨P(أ) ∧ ∀c:⟨a>ج → ~P(a)⟩⟩.

4. يمكننا ذكر الصيغة التي تعبر عن "b هي قوة 10" (لقراءة أفضل، نحذف الرمزين ⟨ و ⟩، ونكتب 2 و 5 بدلاً من SS0 و SSSSS0):
   ∃أ:∃ج:∃د:(EXP(2,a) ∧ EXP(5,c) ∧ EXP(5,d) ∧ d > b ∧ a⋅c=b ∧ ∀e:(e>5 ∧ e|c ∧ EXP₅(ه،ج) → ~EXP₅(e,d)) ∧ ∀e:("e هو الأصغر من نوعه EXP₅(ج،ه) ∧ EXP₅(د،ه)" → (د-2)|(ه-أ))).

توضيح: نكتب ب = أ⋅ج = 2^س⋅5^ذ (x,y>0) واختر d=5^ض>b بطريقة تجعل z وy من العناصر الأساسية (على سبيل المثالz قد يكون أوليًا).ثم "أصغر ه..." يساوي (5^ض)^ذ = د^ذ ≡ 2^ذ (mod d-2)، و(d-2)|(e-a) تعني وجود = 2^س = ه مود (د-2) = 2^ذ (لدينا 'd-2 > 2^ذ' و 'd-2 > a' أيضًا)، وبالتالي x = y.

ملاحظة: يمكن تكييف هذا النهج بسهولة لتحديد "b هي قوة n" لأي رقم n مع تحلل ثابت a₁أ₂...أ_ك, ، حيث كل من أ_أنا هي قوة رئيس ص_أنا و ص_أنا = ص_ي → أنا = ي.

Answer 6

وإليك ما خطرت لي:

و∀c: ∃d: <(ج * د = ب) → <(ج = SO) v∃e: (د = ه * SSO) >>

والذي يترجم إلى:

لجميع الأرقام ج، هناك عدد من د، بحيث لو الأوقات ج د يساوي ب ج ثم إما هو 1 أو هناك وجود عدد الإلكترونية بحيث د يساوي أضعاف ه 2.

أو

لجميع الأرقام ج، هناك عدد من د، بحيث لو ب عاملا من C و D ثم إما ج 1 أو د هو عامل من 2

أو

وإذا كان المنتج من رقمين هو ب ثم واحد منهم هو 1 أو واحد منهم يقبل القسمة على 2

أو

جميع المقسومات من ب إما 1 أو قابلة للقسمة من 2

أو

وب هي قوة من 2

Answer 7

وأعتقد أن معظم ما سبق قد دلل على أن ب يجب أن يكون من مضاعفات الرقم 4. كيف حول هذا: ∃b: ∀c: << ∀e: (ج ∙ ه) = ب & ~ ∃c ': ∃c '' :( محكمة أمن الدولة "∙ محكمة أمن الدولة '') = ج> → ج = 2>

وأنا لا أعتقد أن التنسيق على ما يرام، ولكن على ما يلي:

موجود هناك ب، ان هذه للجميع ج، ج إذا هو عامل من (ب) و (ج) هو رئيس الوزراء، ثم c يساوي 2.

Answer 8

وهنا هو ما خطرت لي على البيان "ب هي قوة 2"

و∃b: ∀a: ~ ∃c: ((أ * ss0) + sss0) * ج = ب

ووأعتقد أن هذا يقول "موجود هناك عدد ب، ان هذه لجميع الأرقام لذلك، هناك لا وجود عدد ج بحيث (أ * 2) + 3 (وبعبارة أخرى، عدد فردي أكبر من 2) تتضاعف بواسطة ج، يمنحك ب ". لذا، في حالة وجود ب، ولا يمكن أن تكون الصفر، وليس لديها المقسومات غريبة أكبر من 2، ثم لن يكون بالضرورة ب 1، 2، أو قوة أخرى من 2؟

Answer 9

لتعبير مفتوحة وهذا يعني أن ب هي قوة 2، لقد ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

وهذا يقول فعال أن لجميع لذلك، S (سا ∙ SS0) ليس عاملا من عوامل ب. ولكن في الشروط العادية، S (سا ∙ SS0) هو 1 + ((a + 1) * 2) أو 3 + 2a. يمكننا الآن إعادة صياغة البيان بأنه "لا يوجد عدد فردي وهذا هو ما لا يقل عن 3 هو عامل ب". وهذا صحيح إذا وفقط إذا ب هي قوة 2.

وأنا لا تزال تعمل على ب هو قوة 10 مشكلة.

Answer 10

ولي حل لب هو قوة اثنين هي: ∀x: ∃y x.y = ب (isprime (س) => س = SS0)

وisprime () لا ينبغي أن يكون من الصعب الكتابة.