برهان تورينج

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة

برهان تورينج هو برهانٌ وضعه آلان تورينج في 12 نوفمبر 1936 ونُشر لأول مرة عام 1937 [ 1 ] بعنوان " حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار ". كان هذا البرهان الثاني (بعد نظرية تشرش ) لنفي مسألة القرار لهيلبرت ؛ أي الفرضية القائلة بأن بعض الأسئلة الرياضية البحتة التي تُجاب بنعم أو لا لا يمكن الإجابة عليها بالحساب ؛ أو بتعبير أدق، أن بعض مسائل القرار " غير قابلة للتقرير " بمعنى أنه لا توجد خوارزمية واحدة تُعطي إجابة صحيحة بنعم أو لا لكل حالة من حالات المسألة. يقول تورينج نفسه: "ما سأثبته يختلف تمامًا عن نتائج غودل المعروفة ... سأُبين الآن أنه لا توجد طريقة عامة تُحدد ما إذا كانت صيغة معينة U قابلة للإثبات في K [ مبادئ الرياضيات ]". [ 2 ]

أتبع تورينج هذا البرهان ببرهانين آخرين. يعتمد البرهان الثاني والثالث على البرهان الأول. وتعتمد جميعها على تطويره " آلات حاسوبية " شبيهة بالآلة الكاتبة تخضع لمجموعة بسيطة من القواعد، وعلى تطويره اللاحق " آلة حاسوبية شاملة ".

ملخص البراهين

في برهانه على أن مسألة القرار لا حل لها، انطلق تورينج من برهانين قاداه إلى برهانه النهائي. تُعدّ نظريته الأولى أكثر صلة بمسألة التوقف ، بينما تُعدّ الثانية أكثر صلة بنظرية رايس .

البرهان الأول : أنه لا يوجد "جهاز حاسوب" قادر على تحديد ما إذا كان "جهاز حاسوب" معين (مُمثَّل بالأعداد الصحيحة 1، 2، 3، ...) "خاليًا من الدوائر" (أي يستمر في طباعة رقمه بالنظام الثنائي إلى ما لا نهاية): "...ليس لدينا عملية عامة للقيام بذلك في عدد محدود من الخطوات" (ص  132، المرجع نفسه ). يُظهر برهان تورينج، على الرغم من أنه يبدو أنه يستخدم "العملية القطرية"، في الواقع أن جهازه (المسمى H) لا يستطيع حساب رقمه الخاص، ناهيك عن حساب العدد القطري بأكمله ( حجة كانتور القطرية ): "يكمن الخطأ في الحجة في افتراض أن B [العدد القطري] قابل للحساب" [ 3 ]. لا يتطلب البرهان الكثير من الرياضيات.

البرهان الثاني : ربما يكون هذا البرهان أكثر ألفة للقراء باعتباره نظرية رايس : "يمكننا أن نبين كذلك أنه لا يمكن أن توجد آلة E، عند تزويدها بـ SD ["البرنامج"] لآلة M عشوائية، ستحدد ما إذا كانت M ستطبع رمزًا معينًا (0 على سبيل المثال) " [ أ ]

البرهان الثالث : "بالنسبة لكل آلة حاسوب M، نقوم بإنشاء صيغة Un(M) ونبين أنه إذا كانت هناك طريقة عامة لتحديد ما إذا كانت Un(M) قابلة للإثبات، فإنه توجد طريقة عامة لتحديد ما إذا كانت M تطبع 0 على الإطلاق". [ 2 ]

يتطلب البرهان الثالث استخدام المنطق الصوري لإثبات اللمة الأولى، متبوعًا ببرهان لفظي موجز لللمة الثانية:

اللمة 1: إذا ظهر الرمز S1 [الرمز "0"] على الشريط في تكوين كامل لـ M، فإن Un(M) قابلة للإثبات. [ 4 ] اللمة 2: [العكس] إذا كانت Un(M) قابلة للإثبات، فإن الرمز S1 [الرمز "0"] يظهر على الشريط في تكوين كامل لـ M. [ 5 ]

وأخيرًا، في 64 كلمة ورمزًا فقط، يثبت تورينج بالبرهان بالخلف أن "مسألة هيلبرت القرار لا يمكن أن يكون لها حل". [ 2 ]

ملخص البرهان الأول

ابتكر تورينج مجموعة كبيرة من الاختصارات. راجع قائمة المصطلحات في نهاية المقال للاطلاع على التعريفات.

بعض التوضيحات الرئيسية:

تحاول آلة تورينج H طباعة عدد قطري من الأصفار والآحاد. يتم إنشاء هذا العدد القطري عندما تقوم H فعليًا "بمحاكاة" كل آلة "ناجحة" قيد التقييم وطباعة "الرقم" R (1 أو 0) للآلة "الناجحة" R.

أمضى تورينج جزءًا كبيرًا من بحثه في "بناء" آلاته فعليًا لإقناعنا بصحتها. وقد استلزم ذلك استخدامه لأسلوب البرهان بالتناقض . يجب أن نؤكد على الطبيعة "البنائية" لهذا البرهان. يصف تورينج ما يمكن أن يكون آلة حقيقية، قابلة للبناء بالفعل. العنصر الوحيد المشكوك فيه هو وجود الآلة "د"، والذي سيُثبت هذا البرهان في النهاية استحالته.

يبدأ تورينج البرهان بالتأكيد على وجود آلة "قرار/تحديد" D. عند إدخال أي SD (سلسلة من الرموز A، C، D، L، R، N، فاصلة منقوطة "؛")، فإنها ستحدد ما إذا كانت هذه SD (سلسلة الرموز) تمثل "آلة حاسوب" إما "دائرية" - وبالتالي "غير مرضية u" - أو "خالية من الدوائر" - وبالتالي "مرضية s".

سبق أن أوضح تورينج في تعليقه أن جميع "آلات الحوسبة" - وهي الآلات التي تحسب رقمًا ما على شكل 1 و0 إلى ما لا نهاية - يمكن كتابتها كـ SD على شريط "الآلة العالمية" U. وقد كرّس معظم عمله الذي أدى إلى برهانه الأول لإثبات وجود آلة عالمية بالفعل، أي أن هناك بالفعل آلة عالمية U. لكل رقم N، يوجد بالفعل SD فريد، فكل آلة تورينج لها SD. يمكن تشغيل كل SD على شريط U بواسطة U وسينتج نفس "المخرجات" (الشكلان 1 و0) التي تنتجها الآلة الأصلية.

لم يُعلّق تورينج على كيفية عمل الآلة D. لنفترض جدلاً أن D ستتحقق أولاً مما إذا كانت سلسلة الرموز "مُصاغة بشكل صحيح" (أي على شكل خوارزمية وليست مجرد مجموعة عشوائية من الرموز)، وإذا لم تكن كذلك، فستتجاهلها. ثم ستبدأ عملية "البحث عن الدوائر". وللقيام بذلك، ربما ستستخدم "أساليب استدلالية" (حيل: مُعلّمة أو مُكتسبة). لأغراض البرهان، هذه التفاصيل غير مهمة.

ثم يصف تورينج (بشكل عام) الخوارزمية (الطريقة) التي ستتبعها آلة يسميها H. تحتوي الآلة H بداخلها على آلة اتخاذ القرار D (وبالتالي فإن D هي "روتين فرعي" من H). تُعبَّر خوارزمية الآلة H في جدول تعليمات H، أو ربما في وصفها القياسي على شريط، وتُدمج مع الآلة الشاملة U؛ لم يحدد تورينج هذا الأمر.

أثناء وصفه للآلة العالمية U، أثبت تورينج أن برنامج الآلة (SD) (سلسلة من الأحرف تشبه "البرنامج") يمكن تحويله إلى عدد صحيح (في النظام الثماني) والعكس صحيح. أي عدد N (في النظام الثماني) يمكن تحويله إلى برنامج (SD) بالاستبدالات التالية: 1 بالحرف A، 2 بالحرف C، 3 بالحرف D، 4 بالحرف L، 5 بالحرف R، 6 بالحرف N، 7 بالفاصلة المنقوطة ";".

اتضح أن الرقم الفريد (DN) للآلة H هو الرقم "K". نستنتج أن K رقم طويل جدًا، ربما يتكون من عشرات الآلاف من الأرقام. لكن هذا ليس مهمًا لما سيأتي لاحقًا.

تتولى الآلة H مسؤولية تحويل أي رقم N إلى سلسلة رموز SD مكافئة لتختبرها الآلة الفرعية D. (في لغة البرمجة: تُمرر H رمز SD عشوائيًا إلى D، وتُعيد D إما "مُرضٍ" أو "غير مُرضٍ"). كما تتولى الآلة H مسؤولية الاحتفاظ بسجل R للأرقام الناجحة (نفترض أن عدد رموز SD "الناجحة"، أي R، أقل بكثير من عدد رموز SD المختبرة، أي N). أخيرًا، تطبع H على جزء من شريطها رقمًا قطريًا "مُهيأً بيتا" B'. تُنشئ H هذا الرقم B' عن طريق "محاكاة" (بالمعنى الحاسوبي) "حركات" كل آلة/رقم "مُرضٍ"؛ وفي النهاية، ستصل هذه الآلة/الرقم قيد الاختبار إلى "رقمها" R (1 أو 0)، وستقوم H بطباعته. ثم يكون H مسؤولاً عن "تنظيف الفوضى" التي خلفتها المحاكاة، وزيادة N والمضي قدماً في اختباراتها، إلى ما لا نهاية .

ملاحظة: جميع هذه الآلات التي يبحث عنها H هي ما أطلق عليه تورينج اسم "آلات الحوسبة". تقوم هذه الآلات بحساب الأرقام الثنائية والعشرية في سلسلة لا نهائية مما أطلق عليه تورينج اسم "الأرقام": الرموز 1 و0 فقط.

مثال لتوضيح البرهان الأول

مثال: لنفترض أن الآلة H اختبرت 13472 رقمًا وأنتجت 5 أرقام صحيحة، أي أن H حوّلت الأرقام من 1 إلى 13472 إلى سلاسل رمزية (SD) وأرسلتها إلى D للاختبار. ونتيجة لذلك، أحصت H خمسة أرقام صحيحة، وعالجت الرقم الأول حتى وصل إلى أول "رقم" له، والثاني حتى الثاني، والثالث حتى الثالث، والرابع حتى الرابع، والخامس حتى الخامس. أصبح العدد الآن N = 13472، وR = 5، وB' = ".10011" (على سبيل المثال). تُزيل H البيانات غير الصحيحة من شريطها، وتتابع عملها.

يقوم الجهاز H بزيادة قيمة N إلى 13473 ويحولها إلى سلسلة الرموز ADRLD. إذا اعتبرت الآلة الفرعية D أن ADRLD غير مُرضية، فإن H يُبقي سجل العد R عند 5. ثم يزيد H قيمة N إلى 13474 ويتابع. من ناحية أخرى، إذا اعتبرت D أن ADRLD مُرضية، فإن H يزيد قيمة R إلى 6. ثم يحول H قيمة N (مرة أخرى) إلى ADLRD [هذا مجرد مثال، من المحتمل أن تكون ADLRD غير مُجدية] ويُشغلها باستخدام الآلة العامة U حتى تُطبع الآلة قيد الاختبار (U التي تُشغل ADRLD) رقمها السادس، أي 1 أو 0. سيطبع H هذا الرقم السادس (مثل "0") في منطقة "الإخراج" من شريطه (مثل B' = ".100110").

يقوم H بتنظيف الفوضى، ثم يزيد الرقم N إلى 13474.

تنهار العملية برمتها عندما يصل H إلى رقمه K. لنتابع مثالنا. لنفترض أن عدد مرات النجاح/التسجيل R هو 12. يصل H أخيرًا إلى رقمه ناقص 1، أي N = K-1 = 4335...321 4 ، وهذا الرقم غير ناجح. ثم يزيد H قيمة N لينتج K = 4335...321 5 ، أي رقمه. يحول H هذا الرقم إلى "LDDR...DCAR" ويمرره إلى آلة القرار D. يجب أن تُرجع آلة القرار D قيمة "مرضية" (أي: يجب على H، بحكم التعريف ، الاستمرار في الاختبار إلى ما لا نهاية ، لأنه "خالٍ من الدوائر"). لذا، يزيد H الآن قيمة R من 12 إلى 13، ثم يعيد تحويل الرقم قيد الاختبار K إلى SD الخاص به ويستخدم U لمحاكاته. لكن هذا يعني أن H سيحاكي حركاته الخاصة. ما هو أول شيء ستفعله المحاكاة؟ تقوم هذه المحاكاة K-aka-H إما بإنشاء N جديد أو "إعادة ضبط" N "القديم" إلى 1. تقوم هذه "K-aka-H" إما بإنشاء R جديد أو "إعادة ضبط" R "القديم" إلى 0. تقوم Old-H "بتشغيل" K-aka-H الجديد حتى تصل إلى رقمها الثاني عشر.

لكنها لا تصل أبدًا إلى الرقم الثالث عشر؛ إذ يصل K-aka-H في النهاية إلى 4335...321 5 ، مرة أخرى، ويتعين على K-aka-H إعادة الاختبار. لن يصل K-aka-H أبدًا إلى الرقم الثالث عشر. من المحتمل أن آلة H تطبع نسخًا من نفسها إلى ما لا نهاية على شريط فارغ. لكن هذا يناقض الفرضية القائلة بأن H آلة حاسوبية مرضية وغير دائرية تستمر في طباعة الأصفار والآحاد للأرقام القطرية إلى الأبد. (سنرى الشيء نفسه إذا أُعيد ضبط N إلى 1 وR إلى 0).

إذا لم يصدق القارئ ذلك، فيمكنه كتابة "نموذج أولي" لآلة القرار D (سيعيد النموذج الأولي "D" القيمة "مرضي") ثم يرى بنفسه ما يحدث في اللحظة التي تصادف فيها الآلة H رقمها الخاص.

ملخص البرهان الثاني

لا يتجاوز طولها صفحة واحدة، والمقطع الذي ينتقل من المقدمات إلى الخاتمة غامض.

يستخدم تورينج أسلوب البرهان بالخلف . فهو يؤكد وجود آلة E، التي عند إعطائها الوصف القياسي (أي "البرنامج") لآلة M، ستحدد ما إذا كانت M ستطبع رمزًا معينًا (مثلاً 0). وهو لا يؤكد أن هذه الآلة M هي "آلة حاسوب".

بافتراض وجود الآلة E، فإن تورينج يتابع على النحو التالي:

  1. إذا كانت الآلة E موجودة، فإن الآلة G موجودة أيضاً، وهي التي تحدد ما إذا كانت الآلة M تطبع 0 بشكل متكرر لا نهائي، و
  2. إذا كانت E موجودة، فهناك عملية أخرى [يمكننا تسمية العملية/الآلة G' كمرجع] تحدد ما إذا كانت M تطبع 1 بشكل متكرر لا نهائي، لذلك
  3. عندما نجمع G مع G'، نحصل على عملية تحدد ما إذا كان M يطبع عددًا لا نهائيًا من الأرقام، و
  4. إذا حددت العملية "G مع G'" أن M تطبع عددًا لا نهائيًا من الأشكال، فإن "G مع G'" تكون قد حددت أن M خالية من الدوائر، ولكن
  5. لا يمكن أن توجد هذه العملية "G مع G" التي تحدد ما إذا كانت M خالية من الدوائر، وفقًا للبرهان 1، لذلك
  6. الآلة E غير موجودة.

تفاصيل البرهان الثاني

تكمن صعوبة البرهان في الخطوة الأولى. وسيسهل على القارئ فهم الأمر إذا أدرك أن تورينج لا يشرح عمله الدقيق. (باختصار: إنه يستخدم بعض أوجه التكافؤ بين "العوامل الوجودية" و"العوامل الشاملة" بالإضافة إلى تعابيرها المكافئة المكتوبة باستخدام عوامل منطقية).

إليكم مثالًا: لنفترض أننا نرى أمامنا موقف سيارات مليئًا بمئات السيارات. قررنا التجول في الموقف بأكمله بحثًا عن: "سيارات ذات إطارات مثقوبة (سيئة)". بعد ساعة تقريبًا، وجدنا سيارتين "بإطارات سيئة". يمكننا الآن أن نقول بيقين: "بعض السيارات ذات إطارات سيئة". أو يمكننا أن نقول: "ليس صحيحًا أن 'جميع السيارات ذات إطارات جيدة'". أو: "صحيح أن: 'ليست كل السيارات ذات إطارات جيدة'". لنذهب إلى موقف سيارات آخر. هنا نكتشف أن "جميع السيارات ذات إطارات جيدة". قد نقول: "لا توجد سيارة واحدة ذات إطار سيئ". وهكذا نرى أنه إذا استطعنا قول شيء عن كل سيارة على حدة، فيمكننا قول شيء عن جميعها مجتمعة.

هذا ما يفعله تورينج: من M، يُنشئ مجموعة من الآلات { M1 ، M2 ، M3 ، M4 ، ...، Mn }، ويكتب عن كل آلة جملة: " تطبع X على الأقل صفرًا واحدًا"، ويسمح بقيمتين فقط للصواب : صحيح = فراغ، أو خطأ = :0:. يحدد تورينج قيمة الصواب للجملة لكل آلة على حدة، ويُنشئ سلسلة من الفراغات أو :0:، أو مزيج منهما. قد نحصل على شيء كهذا: " M1 تطبع صفرًا" = صحيح، و" M2 تطبع صفرًا" = صحيح، و" M3 تطبع صفرًا" = صحيح، و" M4 تطبع صفرًا" = خطأ، ... و" Mn تطبع صفرًا" = خطأ. يحصل بذلك على السلسلة.

BBB:0::0::0: ... :0: ... إلى ما لا نهاية

إذا كان هناك عدد لا نهائي من الآلات Mn ، وإذا أنتجت كل آلة قيمة "صحيح"، فإن التعبير الموجود على الشريط سيكون

BBBBB....BBBB... إلى ما لا نهاية

وهكذا، قام تورينج بتحويل العبارات المتعلقة بكل آلة على حدة إلى "عبارة" واحدة (سلسلة نصية) تشملها جميعًا. وبمعرفة الآلة (التي يسميها G) التي أنتجت هذه العبارة، يمكنه اختبارها باستخدام آلته E لتحديد ما إذا كانت تُنتج القيمة 0 أم لا. في المثال الأول أعلاه، نرى أنها تُنتجها بالفعل، لذا نعلم أن ليس كل الآلات M في تسلسلنا تُنتج القيمة 0. أما المثال الثاني فيُظهر أنه بما أن السلسلة النصية فارغة، فإن كل آلة Mn في تسلسلنا قد أنتجت القيمة 0.

كل ما تبقى لتورينغ هو إنشاء عملية لإنشاء سلسلة من Mn من M واحد.

لنفترض أن M يطبع هذا النمط:

M => ...AB01AB0010AB…

يقوم تورينج بإنشاء آلة أخرى F تأخذ M وتعالج سلسلة من Mn التي تحول تباعاً أول n من الأصفار إلى "شريط الصفر" ( 0 ):

يُصرّح، دون الخوض في التفاصيل، بأنّ هذه الآلة F قابلة للبناء بالفعل. يمكننا أن نرى أنّ أحد أمرين قد يحدث: إمّا أن تنفد الآلات التي تحتوي على أصفار من F، أو أن تستمرّ في إنشاء آلات إلى ما لا نهاية "لإلغاء الأصفار".

يجمع تورينج الآن الآلتين E وF في آلة مركبة G. تبدأ G بالآلة الأصلية M، ثم تستخدم F لإنشاء جميع الآلات اللاحقة M1، M2، ...، Mn. بعد ذلك، تستخدم G الآلة E لاختبار كل آلة بدءًا من M. إذا اكتشفت E أن آلة ما لا تطبع الصفر أبدًا، فإن G تطبع :0: لتلك الآلة. إذا اكتشفت E أن آلة ما تطبع الصفر (نفترض ذلك، لم يذكر تورينج ذلك)، فإن G تطبع  :: أو تتخطى هذا الإدخال ببساطة، تاركةً المربعات فارغة. يمكننا أن نرى أن هناك احتمالين.

لن يطبع G أي أصفار على الإطلاق، إذا طبعت جميع Mn أصفارًا، أو سيطبع G أصفارًا إلى ما لا نهاية إذا لم تطبع جميع M أصفارًا، أو سيطبع G أصفارًا لفترة من الوقت ثم يتوقف.

والآن، ماذا يحدث عندما نطبق E على G نفسها؟

إذا حددت E(G) أن G لا تطبع صفرًا أبدًا، فإننا نعلم أن جميع Mn قد طبعت أصفارًا. وهذا يعني أنه بما أن جميع Mn أتت من M، فإن M نفسها تطبع أصفارًا إلى ما لا نهاية . أو إذا حددت E(G) أن G تطبع صفرًا، فإننا نعلم أن ليس كل Mn تطبع أصفارًا؛ وبالتالي فإن M لا تطبع أصفارًا إلى ما لا نهاية .

بما أننا نستطيع تطبيق نفس العملية لتحديد ما إذا كانت الآلة M تطبع الرقم 1 بشكل متكرر لا نهائي، فعند دمج هاتين العمليتين، يمكننا تحديد ما إذا كانت الآلة M تستمر في طباعة الرقمين 1 و0 إلى ما لا نهاية ، أو لا تستمر . وبالتالي، لدينا طريقة لتحديد ما إذا كانت الآلة M خالية من الدوائر. وبحسب البرهان الأول، فإن هذا مستحيل. لذا، فإن الادعاء الأول بوجود E خاطئ: E غير موجودة.

ملخص البرهان الثالث

هنا يثبت تورينج أن " مسألة قرار هيلبرت لا يمكن أن يكون لها حل". [ 2 ] هنا

...يُبين أنه لا توجد عملية عامة لتحديد ما إذا كانت صيغة معينة U من حساب التفاضل والتكامل الوظيفي K قابلة للإثبات. ( المرجع نفسه ).

يتطلب كل من اللمتين رقم 1 ورقم 2 تشكيل عبارة "إذا وفقط إذا" الضرورية (أي التكافؤ المنطقي ) المطلوبة في البرهان:

تكون المجموعة E قابلة للتحديد حسابيًا إذا وفقط إذا كانت كل من E ومكملتها قابلة للتعداد حسابيًا (فرانزين، ص 67).

يُبرهن تورينج على وجود صيغة Un (M) التي تنص، في جوهرها، على أنه "في تكوين كامل ما لـ M، يظهر الصفر على الشريط" (ص  146). هذه الصيغة صحيحة، أي أنها "قابلة للإنشاء"، ويُبين كيفية تحقيق ذلك.

ثم يثبت تورينج لمتين، تتطلب الأولى منهما كل الجهد المبذول. (الثانية هي عكس الأولى). ثم يستخدم البرهان بالخلف لإثبات نتيجته النهائية:

  1. توجد صيغة Un (M). هذه الصيغة صحيحة، و
  2. إذا أمكن حل مسألة القرار، فإنه توجد عملية آلية لتحديد ما إذا كان Un (M) قابلاً للإثبات (الاشتقاق)، و
  3. بحسب اللمتين 1 و2: يمكن إثبات Un (M) إذا وفقط إذا ظهر الصفر في "تكوين كامل" ما لـ M، و
  4. إذا ظهر الرقم 0 في أي "تكوين كامل" للآلة M، فإن هناك عملية ميكانيكية ستحدد ما إذا كانت الآلة M العشوائية ستطبع الرقم 0 أم لا، و
  5. بحسب البرهان الثاني، لا توجد عملية ميكانيكية تحدد ما إذا كانت القيمة M العشوائية ستطبع 0 أم لا ، لذلك
  6. Un (M) غير قابل للإثبات (إنه صحيح، ولكنه غير قابل للإثبات ) مما يعني أن مشكلة القرار غير قابلة للحل.

تفاصيل البرهان الثالث

[إذا كان القراء يعتزمون دراسة البرهان بالتفصيل، فعليهم تصحيح نسخهم من صفحات البرهان الثالث بالتصويبات التي قدمها تورينج. كما ينبغي أن يكون لدى القراء خلفية متينة في (أ) المنطق، (ب) ورقة كورت غودل : " حول القضايا غير القابلة للتقرير رسميًا في كتاب برينسيبيا ماثيماتيكا والأنظمة ذات الصلة ". [ ب ] وللمساعدة في ورقة غودل، يمكنهم الرجوع، على سبيل المثال ، إلى إرنست ناجل وجيمس ر. نيومان ، برهان غودل ، مطبعة جامعة نيويورك، 1958.]

لمتابعة التفاصيل الفنية، سيحتاج القارئ إلى فهم تعريف "قابل للإثبات" وأن يكون على دراية بـ "الدلائل" المهمة.

"قابل للإثبات" يعني، بمعنى غودل، أن (1) نظام البديهيات نفسه قوي بما يكفي لإنتاج (التعبير عن) الجملة "هذه الجملة قابلة للإثبات"، و (2) أنه في أي برهان "جيد الصياغة" تعسفي، تؤدي الرموز من خلال البديهيات والتعريفات والاستبدال إلى رموز النتيجة.

الدليل الأول: "لنضع وصف الآلة M في الصيغة القياسية الأولى للفقرة 6". تصف الفقرة 6 "ترميز" الآلة M المحدد للغاية على شريط "الآلة الشاملة" U. يتطلب هذا من القارئ معرفة بعض خصائص آلة تورينج الشاملة U ونظام الترميز.

(أ) الآلة العامة هي مجموعة من التعليمات "العامة" الموجودة في "جدول التعليمات". وبصرف النظر عن ذلك، على شريط U، توجد "آلة حاسوبية" M على شكل "رمز M". يمكن لجدول التعليمات العام طباعة الرموز A، C، D، 0، 1، u، v، w، x، y، z، :  على الشريط . ويمكن للآلات المختلفة M طباعة هذه الرموز بشكل غير مباشر فقط عن طريق إصدار أوامر لـ U بطباعتها.

(ii) تتكون "شفرة الآلة" M من بضعة أحرف فقط والفاصلة المنقوطة، أي D، C، A، R، L، N،  ; . ولن تظهر الأرقام (الرموز) 1 و 0 في أي مكان ضمن "شفرة" M. إذا أرادت M من U طباعة رمز من المجموعة الفارغة، 0، 1، فإنها تستخدم إحدى الشفرات التالية لإخبار U بطباعتها. ولزيادة الأمور تعقيدًا، يُطلق تورينج على هذه الرموز S0 وS1 وS2، أي

فارغ = S0 = D
0 = S1 = DC
1 = S2 = DCC

(iii) إن "آلة الحوسبة"، سواء كانت مدمجة مباشرة في طاولة (كما توضح أمثلته الأولى)، أو كرمز آلة M على شريط الآلة العالمية U، تطبع رقمها على شريط فارغ (إلى يمين رمز M، إن وجد) على شكل 1 و 0 بشكل مستمر إلى اليمين.

(رابعًا) إذا كانت "آلة الحوسبة" هي U+"رمز M"، فإن "رمز M" يظهر أولًا على الشريط؛ للشريط طرف أيسر، ويبدأ "رمز M" من هناك ويستمر إلى اليمين على مربعات متبادلة. عندما ينتهي رمز M (وهو أمر حتمي، نظرًا لافتراض أن هذه الرموز عبارة عن خوارزميات محدودة)، ستبدأ "الأرقام" بالرقمين 1 و 0 على مربعات متبادلة، وتستمر إلى اليمين إلى ما لا نهاية. يستخدم تورينج المربعات المتبادلة (الفارغة) (المسماة "E" - مربعات "قابلة للمسح") لمساعدة U+"رمز M" في تتبع مكان العمليات الحسابية، سواء في رمز M أو في "الأرقام" التي تطبعها الآلة.

(خامساً) يُقصد بـ"التكوين الكامل" طباعة جميع الرموز الموجودة على الشريط، بما في ذلك رمز M و"الأشكال" حتى تلك النقطة، بالإضافة إلى الشكل الذي يتم مسحه ضوئيًا حاليًا (مع طباعة مؤشر على يسار الرمز الممسوح ضوئيًا؟). إذا فسرنا معنى تورينج بشكل صحيح، فسيكون هذا مجموعة طويلة جدًا من الرموز. لكن يبقى غير واضح ما إذا كان يجب تكرار رمز M بالكامل؛ إذ يكفي طباعة تعليمات رمز M الحالية بالإضافة إلى طباعة جميع الأشكال التي تحمل علامة الشكل.

(vi) قام تورينج بتقليص العدد الهائل من التعليمات الممكنة في "رمز M" (مرة أخرى: رمز M الذي سيظهر على الشريط) إلى مجموعة أساسية صغيرة، واحدة من ثلاث مجموعات مشابهة لما يلي: {qi Sj Sk R ql}. على سبيل المثال، إذا كانت الآلة تنفذ التعليمة رقم qi وكان الرمز Sj موجودًا على المربع الذي يتم مسحه ضوئيًا، فسيتم طباعة الرمز Sk والتحرك يمينًا ثم الانتقال إلى التعليمة ql . التعليمات الأخرى متشابهة، حيث ترمز إلى "اليسار" L و"عدم الحركة" N. هذه المجموعة هي التي يتم ترميزها بواسطة سلسلة الرموز qi = DA...A، Sj = DC...C، Sk = DC...C، R، ql = DA....A. يتم فصل كل تعليمة عن الأخرى بواسطة الفاصلة المنقوطة. على سبيل المثال، {q5, S1 S0 L q3} تعني: التعليمة رقم 5: إذا كان الرمز الممسوح ضوئيًا هو 0، فسيتم طباعة فراغ ، والتحرك يسارًا، ثم الانتقال إلى التعليمة رقم 3. يتم ترميزها على النحو التالي

; DAAAADCDLDAAA

الدليل الثاني: يستخدم تورينج أفكارًا طُرحت في ورقة غودل، أي "تطبيق غودل" على (جزء على الأقل من) صيغة Un (M). يظهر هذا الدليل فقط كحاشية في الصفحة 138 ( ديفيس (1965) ، ص 138 ): "يُرمز إلى متتالية من r أعداد أولية بـ ^ (r)" ( المرجع نفسه ). [هنا، r داخل الأقواس "مرفوع"]. تظهر "متتالية الأعداد الأولية" هذه في صيغة تُسمى F^(n). 

الدليل الثالث: هذا يُعزز الدليل الثاني. محاولة تورينج الأصلية لإثبات ذلك تستخدم التعبير التالي:

(الاتحاد الأوروبي) N(u) & (x)(...إلخ...) [ 6 ]

في وقت سابق من الورقة، استخدم تورينج هذا التعبير (ص  138) وعرّف N(u) بأنه "u عدد صحيح غير سالب" ( المرجع نفسه ) (أي عدد غودل). ولكن، مع تصحيحات بيرنايز، تخلى تورينج عن هذا النهج (أي استخدام N(u))، والموضع الوحيد الذي يظهر فيه "عدد غودل" صراحةً هو عندما استخدم F^(n).

ماذا يعني هذا بالنسبة للبرهان؟ الدليل الأول يعني أن فحصًا بسيطًا لرمز M على الشريط لن يكشف ما إذا كان الرمز 0 قد طُبع بواسطة U+"M-code". قد يبحث جهاز اختبار عن ظهور DC في إحدى سلاسل الرموز التي تُمثل تعليمة. ولكن هل ستُنفذ هذه التعليمة؟ لا بد من وجود شيء ما "يُشغل الكود" لمعرفة ذلك. قد يكون هذا الشيء جهازًا، أو قد يكون سطورًا في برهان رسمي، أي اللمة رقم 1.

تشير الدلائل الثانية والثالثة إلى أن البرهان صعب، لأن أساسه ورقة غودل.

في المثال التالي، سنقوم فعليًا بإنشاء "نظرية" بسيطة - برنامج آلة ما بعد تورينج صغير "لتشغيلها". سنرى مدى سهولة تطبيق نظرية مصممة بشكل صحيح. البرهان، كما سنرى، هو ببساطة "اختبار" للنظرية نقوم به عن طريق إدخال "مثال برهان" في البداية ونرى ما يظهر في النهاية.

يتطلب كل من اللمتين رقم 1 ورقم 2 تشكيل عبارة "إذا وفقط إذا" الضرورية (أي التكافؤ المنطقي) المطلوبة في البرهان:

تكون المجموعة E قابلة للتقرير الحسابي إذا وفقط إذا كانت كل من E ومكملتها قابلة للتعداد الحسابي. (فرانزن، ص 67)

وكما قال فرانزين:

يقال إن الجملة A قابلة للتقرير في نظام رسمي S إذا كان من الممكن إثبات A أو نفيها في S. (فرانزين، ص 65)

وقد عرّف فرانزين مصطلح "قابل للإثبات" في وقت سابق من كتابه:

النظام الصوري هو نظام من البديهيات (المُصاغة بلغة مُحددة رسميًا) وقواعد الاستدلال (وتُسمى أيضًا قواعد الاستدلال)، تُستخدم لاستنباط نظريات النظام. النظرية هي أي عبارة بلغة النظام يُمكن الحصول عليها من خلال سلسلة من تطبيقات قواعد الاستدلال، بدءًا من البديهيات. البرهان هو سلسلة منتهية من هذه التطبيقات، تُفضي إلى نظرية كنتيجة لها. ( المرجع نفسه، ص ١٧)

وبالتالي فإن "الجملة" هي سلسلة من الرموز، والنظرية هي سلسلة من سلاسل الرموز.

يواجه تورينج المهمة التالية:

لتحويل "برنامج" آلة تورينج العالمية ، والرموز العددية على الشريط (أرقام تورينج، الرموز "1" و "0")، إلى "نظرية" - أي سلسلة (طويلة بشكل هائل) من الجمل التي تحدد الإجراءات المتتالية للآلة، وجميع أرقام الشريط، وموقع "رأس الشريط".

وبالتالي، ستكون "سلسلة الجمل" عبارة عن سلاسل من سلاسل الرموز. وستقتصر الرموز الفردية المسموح بها على رموز غودل المحددة في بحثه. (في المثال التالي، نستخدم الرمزين "<" و ">" حول "شكل" للإشارة إلى أن "الشكل" هو الرمز الذي يقوم الجهاز بمسحه ضوئيًا).

مثال لتوضيح البرهان الثالث

فيما يلي، علينا أن نتذكر أن كل "آلة حاسوبية" من آلات تورينج هي مولد/منشئ للأرقام الثنائية يبدأ العمل على "شريط فارغ". إذا تم بناؤها بشكل صحيح، فإنها تستمر في العمل بلا توقف، لكن تعليماتها محدودة دائمًا. في براهين تورينج، كان لشريط تورينج "طرف أيسر" ولكنه يمتد إلى اليمين بلا حدود. ولأغراض التوضيح أدناه، سنفترض أن "الآلة" ليست آلة شاملة، بل هي "آلة مخصصة" أبسط ذات تعليمات موضحة في الجدول.

يستند مثالنا إلى نموذج مُعدَّل لآلة تورينج، وهو نموذج ما بعد تورينج. يطبع هذا النموذج الرمزين 0 و1 فقط. يُعتبر الشريط الفارغ عبارة عن جميع الأحرف b. يتطلب نموذجنا المُعدَّل إضافة تعليمتين إلى تعليمات ما بعد تورينج السبع. الاختصارات التي سنستخدمها هي:

R، يمين: انظر إلى اليمين وحرك الشريط إلى اليسار، أو حرك رأس الشريط إلى اليمين. L، يسار  : انظر إلى اليسار وحرك الشريط إلى اليمين، أو حرك رأس الشريط إلى اليسار. E، امسح المربع الممسوح ضوئيًا (على سبيل المثال، اجعل المربع فارغًا). P0،: اطبع 0 في المربع الممسوح ضوئيًا. P1،: اطبع 1 في المربع الممسوح ضوئيًا. Jb_n، انتقل إذا كان فارغًا إلى التعليمات رقم n، J0_n، انتقل إذا كان 0 إلى التعليمات رقم n، J1_n، انتقل إذا كان 1 إلى التعليمات رقم n، توقف.

في حالات R و L و E و P0 و P1، بعد إتمام مهمتها، تستمر الآلة إلى التعليمات التالية بالتسلسل العددي؛ وينطبق الشيء نفسه على القفزات إذا فشلت اختباراتها.

لكن اختصارًا، ستستخدم أمثلتنا ثلاثة مربعات فقط. وستبدأ هذه المربعات دائمًا بثلاثة مربعات فارغة مع وجود المربع الممسوح ضوئيًا على اليسار: أي bbb. باستخدام رمزين 1 و0 ومربع فارغ، يمكننا الحصول على 27 تكوينًا مختلفًا.

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

يجب أن نتوخى الحذر هنا، لأنه من المحتمل جدًا أن تترك الخوارزمية (مؤقتًا) فراغات بين الأرقام، ثم تعود لملء الفراغات. والأرجح أن الخوارزمية قد تفعل ذلك عمدًا. في الواقع، آلة تورينج تفعل ذلك - فهي تطبع على مربعات متبادلة، تاركةً فراغات بين الأرقام لتتمكن من طباعة رموز التحديد.

كان تورينج يترك دائمًا مربعات متبادلة فارغة حتى تتمكن آلته من وضع رمز على يسار الرقم (أو حرف إذا كانت الآلة هي الآلة الشاملة وكان المربع الممسوح ضوئيًا موجودًا بالفعل في "البرنامج"). في مثالنا البسيط، سنتجاوز ذلك ونضع رموزًا ( ) حول الرمز الممسوح ضوئيًا، كما يلي:

b(b)0 تعني: "الشريط فارغ على يسار الفراغ الأيسر، لكن الفراغ الأيسر 'مفعّل'، والمربع الممسوح ضوئيًا فارغ، '0'، والفراغات على اليمين". 1(0)1 تعني: "الشريط فارغ على اليسار، إذن 1، والمربع الممسوح ضوئيًا هو '0'".

لنكتب برنامجًا بسيطًا:

البداية: موقف 1، يمين، موقف 1، يمين، موقف 1، يمين، يسار

تذكر أننا نبدأ دائمًا بشريط فارغ. يقوم التكوين الكامل بطباعة الرموز على الشريط متبوعة بالتعليمات التالية:

إعدادات البداية: (ب) P1، الإعداد رقم 1: (1) R، الإعداد رقم 2: 1 (ب) P1، الإعداد رقم 3: 1 (1) R، الإعداد رقم 4: 11 (ب) P1، الإعداد رقم 5: 11 (1) H

لنضف كلمة "قفزة" إلى الصيغة. عند القيام بذلك، نكتشف سبب ضرورة تضمين رموز الشريط في التكوين الكامل. (في الواقع، سنرى ذلك بشكل أوضح أدناه). يطبع هذا البرنامج الصغير ثلاثة أرقام "1" إلى اليمين، ثم يعكس الاتجاه ويتحرك إلى اليسار لطباعة أصفار حتى يصل إلى مساحة فارغة. سنطبع جميع الرموز التي يستخدمها جهازنا:

البداية: P1، R، P1، R، P1، P0، L، J1_7، H (b)bb P1، (1)bb R، 1(b)b P1، 1(1)b R، 11(b) P1، 11(1) P0، 11(0) L، 1(1)0 J1_7 1(1)0 L (1)10 J0_7 (1)10 L (b)110 J0_7 (b)110 H

هنا في النهاية نجد أن الفراغ الموجود على اليسار قد "دخل حيز التنفيذ" لذلك نتركه كجزء من التكوين الكلي.

بافتراض أننا أنجزنا عملنا على النحو الصحيح، نضيف الشروط الابتدائية ونرى "إلى أين تتجه النظرية". والنتيجة النهائية - العدد 110 - هي البرهان.

  • كانت مهمة تورينج الأولى هي كتابة تعبير عام باستخدام الرموز المنطقية للتعبير بالضبط عما سيفعله Un(M) الخاص به.
  • تتمثل مهمة تورينج الثانية في "تحويل هذه السلسلة الطويلة للغاية من سلاسل الرموز إلى سلسلة غودل" باستخدام أسلوب غودل في تعيين الأعداد الأولية للرموز ورفع الأعداد الأولية إلى قوى الأعداد الأولية، وفقًا لطريقة غودل.

المضاعفات

برهان تورينج معقدٌ بسبب كثرة التعريفات، ومُشوَّشٌ بما أسماه مارتن ديفيس "تفاصيل تقنية تافهة" و"...تفاصيل تقنية غير صحيحة كما هي مُعطاة". [ ج ] نشر تورينج نفسه "تصحيحًا" عام 1938: "المؤلف مدينٌ لـ ب. بيرنايز لتنبيهه إلى هذه الأخطاء". [ 7 ]

على وجه التحديد، يشوب البرهان الثالث في صيغته الأصلية أخطاء تقنية جسيمة. وحتى بعد اقتراحات بيرنايز وتصحيحات تورينج، بقيت أخطاء في وصف الآلة الشاملة . ومن المثير للارتباك، أنه نظرًا لعدم تمكن تورينج من تصحيح ورقته الأصلية، فإن بعض النصوص في متن الورقة تشير إلى محاولته الأولى المعيبة.

يمكن العثور على تصحيحات بيرنايز في ديفيس (1965) ، الصفحات 152-154 ؛ أما الأصل فيمكن العثور عليه بعنوان "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار. تصحيح"، وقائع الجمعية الرياضية في لندن (2)، 43 (1938)، 544-546. 

تحتوي النسخة الإلكترونية من ورقة تورينج على هذه التصحيحات في ملحق؛ ومع ذلك، يجب العثور على تصحيحات الآلة العالمية في تحليل قدمه إميل بوست .

في البداية، كان بوست (انظر هودجز، ص 125) هو عالم الرياضيات الوحيد الذي أولى اهتمامًا دقيقًا بتفاصيل البرهان  ، ويعود ذلك أساسًا إلى أنه توصل في الوقت نفسه إلى اختزال مماثل لمفهوم "الخوارزمية" إلى إجراءات أولية شبيهة بالآلات، لذا أبدى اهتمامًا شخصيًا بالبرهان. ومن الغريب (ربما تدخلت الحرب العالمية الثانية) أن بوست استغرق نحو عشر سنوات لتحليله في ملحق بحثه " عدم قابلية حل مشكلة ثو بشكل متكرر" ، 1947. [ د ]

تظهر مشاكل أخرى: فقد علّق بوست في ملحقه بشكل غير مباشر على صعوبة البحث، وبشكل مباشر على "طبيعته الموجزة" [ هـ ] و"شكله البديهي" في البراهين. [ هـ ] واضطر بوست إلى استنتاج نقاط مختلفة:

إذا كان نقدنا صحيحًا، يُقال إن الآلة خالية من الدوائر إذا كانت آلة تورينج حاسوبية... تطبع عددًا لا نهائيًا من الأصفار والآحاد. ونظريتا تورينج المعنيتان هما في الواقع ما يلي: لا توجد آلة تورينج... يمكنها، عند تزويدها بعدد صحيح موجب اختياري n، تحديد ما إذا كان n هو DN لآلة تورينج حاسوبية... خالية من الدوائر. [ثانيًا]، لا توجد آلة تورينج اصطلاحية، عند تزويدها بعدد صحيح موجب اختياري n، تحديد ما إذا كان n هو DN لآلة تورينج حاسوبية... تطبع رمزًا معينًا (مثل 0). [ f ]

مسرد المصطلحات التي استخدمها تورينج

1. عدد قابل للحساب - عدد يمكن حساب جزءه العشري بواسطة آلة (أي بوسائل محدودة مثل الخوارزمية).

2M - آلة ذات جدول تعليمات محدود ورأس مسح/طباعة. تقوم M بتحريك شريط لانهائي مقسم إلى مربعات، كل منها "قادر على حمل رمز". تعليمات الآلة هي كالتالي فقط: التحرك مربعًا واحدًا إلى اليسار، التحرك مربعًا واحدًا إلى اليمين، طباعة الرمز p على المربع الممسوح ضوئيًا، مسح المربع الممسوح ضوئيًا، إذا كان الرمز هو p، فقم بتنفيذ التعليمة aaa، إذا لم يكن الرمز الممسوح ضوئيًا هو p، فقم بتنفيذ التعليمة aaa، إذا لم يكن هناك أي رمز ممسوح ضوئيًا، فقم بتنفيذ التعليمة aaa، إذا كان الرمز الممسوح ضوئيًا أي رمز، فقم بتنفيذ التعليمة aaa [حيث "aaa" هو مُعرِّف التعليمة].

3 آلة حاسوبية - آلة تقوم بطباعة نوعين من الرموز، وتسمى رموز النوع الأول "الأرقام" وهي رموز ثنائية فقط 1 و 0؛ أما رموز النوع الثاني فهي أي رموز أخرى.

أربعة أرقام - الرموز 1 و 0 ، والمعروفة أيضًا باسم "رموز النوع الأول"

5 -m-configuration — مُعرِّف التعليمات، إما رمز في جدول التعليمات، أو سلسلة من الرموز التي تمثل رقم التعليمات على شريط الآلة العالمية (على سبيل المثال "DAAAAA = #5").

ستة رموز من النوع الثاني - أي رموز أخرى غير 1 و 0

7 دائري - آلة حسابية فاشلة. تفشل في طباعة الرقمين 0 أو 1 اللذين يمثلان العدد الذي تحسبه بالنظام الثنائي إلى ما لا نهاية.

8- بدون دائرة — آلة حاسوب ناجحة. تطبع، إلى ما لا نهاية، الرقمين 0 أو 1 اللذين يمثلان بالنظام الثنائي العدد الذي تحسبه.

9 متسلسلة — كما في "المتسلسلة المحسوبة بواسطة الآلة": رموز من النوع الأول، والمعروفة أيضًا بالأرقام أو الرموز 0 و1.

10 متتابعات قابلة للحساب — يمكن حسابها بواسطة آلة خالية من الدوائر

11 SD – الوصف القياسي: سلسلة من الرموز A، C، D، L، R، N، ; على شريط آلة تورينج

12 DN — رقم الوصف : تم تحويل SD إلى رقم: 1=A، 2=C، 3=D، 4=L، 5=R، 6=N، 7=؛

13 M(n) — آلة رقمها التسلسلي هو الرقم "n"

14 مرضية - SD أو DN تمثل آلة خالية من الدوائر

15 U — جهاز مزود بجدول تعليمات "عالمي". إذا تم تزويد U بشريط مكتوب على بدايته SD لجهاز حاسوب M، فسوف يقوم U بحساب نفس التسلسل الذي يقوم به M.

16 β' — "بيتا-برايمد": ما يسمى "العدد القطري" المكون من الرقم n (أي 0 أو 1) من التسلسل القابل للحساب n [أيضًا: العدد القابل للحساب لـ H، انظر أدناه]

17 u — غير مرضٍ، أي دائري، SD

18 ثانية — مرضية، أي خالية من الدوائر SD

19 د - جهاز موجود في ح (انظر أدناه). عند تزويده ببطاقة SD لأي جهاز حاسوب م، سيقوم د بفحص بطاقة SD الخاصة بـ م، وإذا كانت دائرية، فسيضع عليها علامة "u"، وإذا كانت خالية من الدوائر، فسيضع عليها علامة "s".

20 H — آلة حاسوبية. تقوم H بحساب B'، وتحتفظ بـ R و N. تحتوي H على D و U وآلة (أو عملية) غير محددة تحتفظ بـ N و R وتزود D بما يعادل SD من N. تقوم E أيضًا بحساب أشكال B' وتجميع أشكال B'.

21 R — سجل أو إحصاء لعدد حالات SD الناجحة (الخالية من الدوائر) التي تم اختبارها بواسطة D

22 N — رقم، يبدأ من 1، يتم تحويله إلى SD بواسطة الآلة E. تحتفظ E بـ N.

23 ألف — رقم. الرقم المميز لـ H.

مطلوب للإثبات #3

5 -معرّف التعليمات (m-configuration ) هو مُعرّف التعليمات، إما رمز في جدول التعليمات، أو سلسلة من الرموز تُمثّل رقم التعليمات على شريط الآلة العالمية (مثل "DAAAAA = التعليمات رقم 5"). في ذاكرة تورينج SD، يظهر معرّف التعليمات (m-configuration) مرتين في كل تعليمة، السلسلة الموجودة في أقصى اليسار هي "التعليمات الحالية"، والسلسلة الموجودة في أقصى اليمين هي التعليمات التالية.

24 التكوين الكامل - رقم المربع الممسوح ضوئيًا (الشكل 1 أو 0 )، والتسلسل الكامل لجميع الرموز الموجودة على الشريط، وتكوين m (معرف التعليمات، إما رمز أو سلسلة من الرموز التي تمثل رقمًا، على سبيل المثال "التعليمات DAAAA = #5").

25 RSi(x, y) — "في التكوين الكامل x لـ M، يكون الرمز الموجود على المربع y هو Si؛ "التكوين الكامل" هو التعريف رقم 5

26 I(x, y) — "في التكوين الكامل x لـ M، يتم مسح المربع y"

27 Kqm(x) — "في التكوين الكامل x لـ M، يكون تكوين الآلة (رقم التعليمات) هو qm"

28 F(x,y) — "y هو الخلف المباشر لـ x" (يتبع استخدام غودل لـ "f" كدالة الخلف).

29 G(x,y) — "x يسبق y"، ليس بالضرورة مباشرة

30 Inst{qi, Sj Sk L ql} هو اختصار، وكذلك Inst{qi, Sj Sk R ql} و Inst{qi, Sj Sk N ql} . انظر أدناه.

يُقلّص تورينج مجموعة تعليماته إلى ثلاثة "أشكال أساسية" - شكل واحد لليسار، وآخر لليمين، وثالث لعدم الحركة. Si و Sk هما رمزان على الشريط.

شريط لاصقأخير
m-configرمزالعملياتm-config
تشينعمPSk، Lqm
تشينعمPSk، Rqm
تشينعمPSk، Nqm

على سبيل المثال، العمليات في السطر الأول هي PSk = PRINT symbol Sk from the collection A, C, D, 0, 1, u, v, w, x, y, z,  : , then move tape LEFT.

ثم قام باختصارها إلى: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

في البرهان رقم 3، يُطلق على أول هذه العناصر اسم "Inst{qi Sj Sk L ql}"، ويُبين كيفية كتابة وصف الجهاز بالكامل كعملية ربط منطقية (أو منطقية): تُسمى هذه السلسلة "Des(M)"، أي "وصف-M". بمعنى آخر، إذا كان الجهاز يطبع 0 ثم 1 و0 بالتناوب على المربعات إلى اليمين إلى ما لا نهاية، فقد يكون لديه الجدول (يظهر مثال مشابه في الصفحة 119).

q1، فارغ، P0، R، q2 q2، فارغ، P-فارغ، R، q3 q3، فارغ، P1، R، q4 q4، فارغ، P-فارغ، R، q1

(تم اختزال هذا إلى الشكل القياسي باستخدام تعليمات "p-blank"، لذا فهو يختلف قليلاً عن مثال تورينج.) إذا تم وضعها في شكل "Inst()"، فستكون التعليمات كما يلي (مع الأخذ في الاعتبار أن: S0 فارغ، S1 = 0، S2 = 1):

Inst {q1 S0 S1 R q2} Inst {q2 S0 S0 R q3} Inst {q3 S0 S2 R q4} Inst {q4 S0 S0 R q1}

سيكون الاختزال إلى الوصف القياسي (SD) كما يلي:

; دادكردا  ; دداددرداا  ; DAAADDCCRDAAAA  ; داااداددرا  ;

يتوافق هذا مع المثال الذي ذكره في الكتاب (حيث ستكون هناك مسافة فارغة بين كل حرف ورقم). تستخدم الآلة العالمية U المربعات الفارغة البديلة كمواضع لوضع "مؤشرات".

ملحوظات

  1. ↑ النص المائل، ديفيس (1965) ، ص 134
  2. ↑ أعيد طبعه في ديفيس (1965) ، ص 5
  3. ↑ تعليق ديفيس في ديفيس (1965) ، ص 145
  4. ↑ أعيد طبعه في ديفيس (1965) ، ص 293
  5. 1 2 بوست في ديفيس (1965) ، ص 299
  6. ↑ بوست في ديفيس (1965) ، ص 300

مراجع

الاقتباسات

  1. ↑ تورينج، آلان ماثيسون (1937). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار" (ملف PDF) . وقائع الجمعية الرياضية بلندن . 42 : 230-265 . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . {{cite journal}}: صيانة CS1: التاريخ والسنة ( رابط )
  2. 1 2 3 4 ديفيس (1965) ، ص. 145.
  3. ↑ ديفيس (1965) ، ص 132.
  4. ↑ ديفيس (1965) ، ص 147.
  5. ↑ ديفيس (1965) ، ص 148.
  6. ↑ ديفيس (1965) ، ص 146.
  7. ↑ ديفيس (1965) ، ص 152.

المراجع

  • ديفيس، مارتن (1965). غير القابل للتقرير، أوراق أساسية حول القضايا غير القابلة للتقرير، والمسائل غير القابلة للحل، والدوال القابلة للحساب . نيويورك: دار رافين للنشر.تتضمن هذه المجلد ورقتين بحثيتين لبوست المشار إليهما أعلاه. وتشمل الأوراق الأخرى أوراقاً بحثية لغودل، وتشرش، وروسر، وكلين.
    • ديفيس، مارتن (2004). غير القابل للتقرير: أوراق أساسية حول القضايا غير القابلة للتقرير، والمسائل غير القابلة للحل، والدوال القابلة للحساب . دوفر. ISBN 9780486432281.
  • فرانزين، توركيل (2005). نظرية غودل: دليل غير مكتمل لاستخدامها وإساءة استخدامها . إيه كيه بيترز.
  • هودجز، أندرو (1983). آلان تورينج: اللغز . نيويورك: سيمون وشوستر .انظر الفصل "روح الحقيقة" للاطلاع على تاريخ يؤدي إلى برهانه ومناقشته.
  • رايشنباخ، هانز (1947). عناصر المنطق الرمزي . نيويورك: منشورات دوفر.
  • تورينج، أ.م. (1937). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار". وقائع الجمعية الرياضية بلندن . 2. 42 (1): 230-265 . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . 
  • تورينج، أ.م. (1938). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار. تصحيح" . وقائع الجمعية الرياضية بلندن . 2. 43 (6): 544-546 . doi : 10.1112/plms/s2-43.6.544 . مؤرشف من الأصل في 7 أكتوبر 2003.هذه هي الورقة التاريخية التي يُعرّف فيها تورينج آلات تورينج ، ويُظهر أن مشكلة القرار غير قابلة للحل.