بعض الأعداد الحقيقية التي لا يمكننا معرفتها وتحديدها أبدًا
لابُدّ أن معظمنا يذكر كيف تعلمّنا في المدرسة أن الأرقام العشرية للعدد باي ( pi أوπ ) ليس لها نهاية، 3.14159265359... حتى أن البعض منّا يتذكّر كيف بإمكانه تقريب القيم العليا والدنيا للعدد باي بأقرب قيمة ترغبها باستخدام طريقة قياس أجزاء المضلّعات. فمع اقتراب عدد أجزاء المضلّع إلى اللانهاية تقترب معها أطوال هذه الأجزاء إلى الصفر، وبالنتيجة تحصل على تقريب أكبر للعدد باي.
تقريب الحدود الدنيا والعليا لرقم باي باسخدام خماسي الأضلاع (اليسار)، سداسي الأضلاع (الوسط) وسباعي الأضلاع (اليمين).
العالم أرخميدس ( 212 -287م) هو في الواقع من يرجع الفضل له بابتكار "خوارزمية المضلّعات" هذه، والتي سادت لما يقارب 1000 سنة كأكثر الطرق دقّة وأفضلها في حساب القيمة التقريبية بأقرب شكل مرغوب للعدد باي. هذه الخوارزمية الهندسيّة الأولية تساعدنا في وضع تقريب لعدد حقيقي، باي، والذي يجب علينا تعيين قيمته بشكل واضح، إذ إننا لا نستطيع التعبير عنه في حالته الأساسية كعدد منطقي (كسر\نسبة).
في الواقع الدراسة الحقيقية لقابيلة الحساب بدأت منذ عام 1900 مع إعلان تأسيس برنامج هيلبرت فينيستس لإرساء المفاهيم والقواعد الأساسية للرياضيات. وهذا تم بعد أن أظهر هيلبرت بنفسه عام 1899 كيف أن التحليل الهندسي الذي ينحصر في الأعداد الحقيقية، والتي بدورها تنحصرأيضًا إلى وحدات حسابية، كيف تكون حصيلتها ما يُعرف بـ ديد كاند (Soare, 2013). وبالتالي فإن الأساس الذي بُني عليه برنامج هيلبرت (1904) كان في سبيل محاولة تسخير واستغلال ميّزة التناهي في البراهين الرياضية المختلفة من أجل إثبات أن التناقضات لا يمكن التوصّل إليها. بمعنى آخر، فإنه وفي حال كان بالإمكان تأسيس مثل هذا البرنامج المميّز، فإن البراهين الرياضية يمكن التعبير عنها بمفاهيم ورموز منطقية، كما هو الحال في ما يُعرف باللاتينية بالمبادىء الرياضيّة (Principia Mathematica Whitehead & Russell, 1910; 1912; 1913). وفي حال تمكّنا من الوصول إلى مثل ذلك البرنامج، فإن جميع البراهين الرياضيّة من ضمنها النظرية الأخيرة لثيوريم، فرضية رايمان وحدسية كونجيكشر، جميعها ستغدو نتائج حتمية للنظام الرياضي التي تمّ التعبير عنها به. فإذا ما تحقق ذلك في الواقع فإنه بإمكاننا نظريًا أن نقوم ببناء آلة بإمكانات كافية، يمكننا تشغيلها لمدة كافية بحيث تتمكّن من حل وكشف جميع القضايا والمبرهات الرياضية والتوّصل إلى فهمٍ كافٍ لها.
والجدير بالذكر أنه وبعد أقل من 30 سنة من البرنامج الذي ذكرناه سابقًا، قام العالم والفيلسوف الهنغاري Kurt Gödel بنشر ورقة بحثية بعنوان " Über formal unentscheidbare Sätze der Principia Ma thematica und verwandter Systeme I" ( الإطروحات غير المحسومة للمبادىء الرياضية والأنظمة المشابهة)، والذي قام، على إثر نظريته السادسة، بمحو أي أمل لبرنامج هيلبرت في تأسيس برنامج متكامل للحقائق الرياضية. وبيّن بعد حصوله مباشرةً على رسالة الدكتوراه الخاصة به أن مثل هذا البرنامج الذي وضعه هيلبرت، بالرغم من متانة أفكاره، سيكون غير كامل. إذ سيغدو هنالك دائمًا عبارات واضحة ويمكن التعبير عنها في النظام ولكن لايمكن حسابها وتفصيلها وفقًا لمسلّماتها:
نظرية عدم الاكتمال الأولى (Gödel, 1931a)
أي نظام منهجي ثابت F حيث بالإمكان القيام بعدد محدود من العمليات الرياضية فيه، هو غير كامل; مثال على ذلك أن هناك بعض العبارات والقوانين في F والتي لا يمكن برهنتها ولا نبذ صحّتها في F نفسها.
هذه الورقة البحثية كما ذكرنا أنهت اي أمل لبرنامج هيلبرت عام 1904. وكما يروي لنا سور (2013) فإن جون نيومان (John von Neumann) حصل وكان أحد الحاضرين كأحد المقدّمين لبرنامج هيلبرت عندما قام غوديل، وكان عمره 25 سنة آنذاك، بأخذ زمام المبادرة وصعد على المنصة ليقدم نظريّته. عندها تيّقن فون نيومان، والذي كان يُعتقد أنه الأذكى بين قرنائه على مر العصور، تيقّن مباشرةً أن برنامج هيلبرت قد انتهى.
أمضى فون نيومان الأسابيع التالية للبرنامج في محاولةٍ لوضع نظرية جديدة مبنيّة على الأساس الرياضي لبرهان عدم الكمال لغوديل، وذلك في سبيل برهنة أن الأنظمة المنهجية في برنامج هيلبرت ليست قاصرة فقط عن برهنة جميع العبارات والقوانين التي فيها، ولكن ليثبت أيضًا عجزها عن ضمان استمرارية صحة هذه العبارات مع الوقت. وعندما قدّم نيومان برهانه لغوديل، قام غوديل بارسال مذكّرة شكر وتقدير له وأعلمه أنه هو نفسه (غوديل) قد قام بكتابة هذه النظرية منذ أسابيع وأنها كانت في طور النشر.
تنصّ النظرية على ما يلي:
نظرية عدم الاكتمال الثانية (Gödel, 1931b)
لا يوجد نظام واضح ثابت يضم حساب بيانو (Peano arithmetic) يمكن أن يثبت استمراريته الخاصّة.
وقد صرّح عمومًا أنه لا يمكن لأي نظام منهجي "مثير للإهتمام بما يكفي" ليصيغ استمراريته الخاصة، لا يمكن له أن يثبت هذه الاستمرارية إلّا عندما يكون غير مستمرًّا في حدا ذاته. هذه النظرية المميزة أثبتت أحد المغالطات الكبيرة في برنامج هيلبرت الثاني، والذي بدأ عام 1918 بعنوان "Entscheidungsproblem" ( مشكلة القرارات)، والذي اشتمل على إمكانية بناء و برهة إمكانية وضع عملية استنتاج خاصّة والتي تتيح للمرء أن "يقرر صحة عبارة ما من عدم صحتها (Soare, 2013).
ومع هذه الوقائع المتتالية غدا الرياضيون مع حلول عام 1930م مرةً أخرى في صدام مع واقع عدم كماليّة الرياضيات من ناحية النتائح العملية، وقدّم هذا الواقع للمرة الأولى عام 1880 بواسطة جورج كانتور.
وهنا تبدأ قصّتنا...
تعاريف
ثابت أرخميدس (pi)، بالإضافة إلى العديد من القيم الثابتة الأخرى كثابت فيثاغورس (√2) و النسبة الذهبية (φ)، جميعها أمثلة عن عن أعداد حقيقة يمكن أن نقول عنها أنها معدودة، بالرغم ن كونها أيضًا غير كسرية( بمعنى أنها تمثل أعداد حقيقية والتي لا تُكتب على شكل أجزاء من العدد الصحيح). ومثل هذه القيم المعدودة يمكن تعريفها كالتالي:
أنها أعداد حقيقية يمكن إحصائها إلى أي درجة مرغوبة من الدقّة بواسطة خوارزمية محدّدة ومنتهية.
بمعنى آخر يمكن أن نقول عن قيمة ما بأنها معدودة إذا وجدت خوارزمية، ولنفرضها عدد أرقام القيمة n، تعيد أرقام القيمة n بشكل متكرر في كتابة العدد. وبشكل أبسط يمكننا التفكير في القيمة المعدود كما بنفس طريقة تفكير مارفين مينيسكي (Marvin Minsky) "هو قيمة بحيث لو كان لدينا آلة تيورينغ( وهو عالم رياضيات انكليزي)، والتي تقوم بطبع القيم n على شريطها الأولي، فإنها ستنتهين طباعتها بتكرار معيّن ومحدود معين لـn {مشفرّةً على شريطها}".
بصورة رياضية رسمية أكثر، فإننا نقول عن عدد حقيقي a بأنه معدود عندما يمكننا تقريبه إلى بواسطة دالّة معينة من مجموعة الأعداد الطيبعية N إلى مجموعة الأعداد الحقيقية Z، بحيث اذا كان لدينا أي عدد موجب n فإننا سمحصل وفق تلك الدالة على (f(n كالتالي:
تعريف معاصر للقيمة المعدودة الحقيقية a بحيث n و (f(n قيم موجبة
ومن التعاريف الماثلة الأخرى للقيم المعدودة هو أنه هناك دالة، بحيث هامش مجال الخطأ موجب هو ε فإنها ستعطينا عددا نسبيًّا r، بحيث تغدو القيمة |r - a| مساوية أو أقل من مجال الخطأ ε .
تاريخ
كما أن العالم جورج كانتور أمضى الربع الأخير من القرن التاسع عشر في دراسة القيم المعدودة التي انبثقت من ابتكاره للمبرهنة القطرية (diagonal argument)، كذلك فإن العلماء قد أمضوا عام 1930 الفوائد والنتائج للدراسات والنظريات حول القيم المعدودة (Soare, 2013). وبشكل محدد فإن التاريخ يسطر لنا مساهمة عظيمةً لإثنين من أبرز العلماء في ذلك الحين وهما: شورتش ألونزو و وآلان تيورينغ.
إلى اليسار لدينا تشورش ألونزو وإلى اليمين هو آلان تيورينغ ( من صور جامعة برينيستون).
ألونزو تشروتش
ألونزو تشورتش (1903- 1995) كان عالم رياضيّات ومنطقيّ أمريكي والذي نال شهادة الدكتوراه على يد أوسولد فيبلان في جامعة بيرنيستون عام 1920. وكانت أول ورقة بحثية قام بنشرها بعنوان تحولّات لورينتز (Lorentz transformations). وأكثر النتائج شهرة والتي وصل إليها كانت إثبات أن عملية علاج المعضلات الرياضية الخاصّة بهيلبرت (Entscheidungsproblem) غير قابلة للحسم بشكل كامل ( ودُعيَ هذا الإثبات فيما بعد بنظرية تشرتش)، بالإضافة إلى إثبات عدم إمكانية الجزم بصحة ما يُعرف بحساب بيانو (Peano arithmetic)، ومن إنجازاته أيضًا ابتكار حساب- λ وإفصاحه عما أصبح يُطلق عليه في أيامنا أطروحة تشرتش-تيوريتغ والتي تتطرق إلى طبيعة الدوال القابلة للعدّ.
آلان تيورينغ
العالم المشهور آلان تيورينغ (1912-1954) كان رياضيًّا انكليزيًّا معروفًا بلقب البراعة والقوة " tour de force" وذلك بسبب جهوده الكبيرة واسهامه الواسع في فك وتحليل آلة التشفير الخاصة بدول المحور أثناء الحرب العالمية الثانية. بالنسبة للرياضيين فإن اسم تيورينغ يرتبط ليس فقط بالعبقرية الفذة، بل أيضًا بالبصيرة الاستثنائية في علوم الرياضيات والمنطق.
ولد تيورينغ في لندن سنة 1912، ومع بلوغه سن الـ17 ذهب طالبًا جامعة الملك، جامعة كامبردج، لدراسة الرياضيات. حاز على تكريم الخريجين الأوائل عام 1934 وتم انتخابه في نفس السنة ليصبح عضوًا في فريق الملك بسبب أطروحته الفريدة، والتي أثبتت نظرية الحد أو النهاية المركزية (Central Limit Theorem). نشر أولى أوراقه البحثية " القيم المعدودة وعلاقتها مع تطبيق هليبرتEntscheidungsproblem" عام 1936. وقد تم نشر هذه الورقة البحثية على قسمين، نشرت في مجلة مجتمع لندن للرياضيّين في 30 تشرين الثاني\ نوفمبر و23 كانون الأول\ ديسيمبر عام 1936. في كانون الأول من نفس السنة سافر تيورينغ إلى جامعة برينسيتون للدراسة من أجل التحضير لرسالة الدكتوراه في الرياضيات تحت إشراف العالم تشورتش. ونال إجازة الدكتوراه سنة 1938. كانت أطروحته بعنوان "أنظمة المنطق المعتمدة على الأرقام التراتبية" والتي قدّمت مفهوم منطق الأرقام التراتبية و الحساب النسبي – مضيفًا ما يُعرف بـ آلات أوراكل (oracle machines) كتحسين على آلة تيورينغ الخاصّة به، متيحًا بذلك إمكانية دراسة المشكلات المنطقية التي تتعدى قدرة آلة تيورينغ القديمة. بالرغم من أنه أّشيد إليه من قبل فون نيومان لكي يصبح عضوًا مساعدًا في دراسات ما بعد الدكتوراه، بعد حصوله على رسالة الدكتوراه الخاصّة به، إلّا أنّه رفض هذه الدعوة وعاد إلى موطنه انكلترا.
عدم قابليّة العد
حسنًا، كان يروي لنا روبرت سور (Copeland et al, 2013 p. 207) ، أنه بحلول عام 1931 أصبح المنطق المُعتمد في الحساب أمرًا بسيطًا يسيرًا. وذلك بعد العديد من التفسيرات والنظريات الفريدة للعديد من العلماء البارزين. فغوديل ولد عام 1906 وكان في سن الـ 25 عندما برهن النقص في الأنظمة الرياضية السابقة. في حين كان تشورتش بعمر 33 سنة عندما أثبت النقص في برنامج هيلبرت (Entscheidungsproblem) بابتكاره لمفهوم "الحساب الفعّال" اعتمادًا على حساب – λ الذي اكتشفه هو أيضًا. وأخيرًا أتى تيورينغ ليثبت ويرسي دعائم ما أثبته تشورتش في نفس السنة بفضل ابتكاره الفريد والذي أطلق عليه اسم آلة تيوريتغ. وكان قد ولد سنة 1912، أي كان بعمر الـ 24 عندما خرج بتلك الأفكار المميزة.
Entscheidungsproblem
وهو مصطلح ألماني يعني آلية اتخاذ القرارات. ويعود هذا المفهوم، والذي يتضمّن ايجاد خوارزمية معينة قادرة على إثبات صحة أو خطأ مُدخلات وقضايا رياضية معينة عن طريقة عدد محدد من المسلمّات الرياضيّة، يعود إلى القرن السابع عشر عندما تخيّله ولأوّل مرّة العالم لايبنيز (Davis, 2000). ولاحقًا وتبعًا للعديد من الأنظمة المنهجية الناشئة، قام كل من سكرودير 1895، لونهيام 1915، هيلبرت 1918 وأخيرًا بيهام 1921 قبل أن يقوم كل من هيلبرت وأكيرمان معًا بنشر إعلان رسمي عام 1928 بعنوان " Grundzuge der theoretischen Logi" والذي يعني "أساسيات المنطق الرياضي".
يمكن إثبات مفهوم Entscheidungsproblem عندما نتمكن من معرفة الإجراء الذي يتيح لنا فرصة تحديد صحة أوخطأ أي عبارة رياضية بواسطة عدد معين من التعابير والقوانين المنطقية.
حل تشورتش
بدأ مستشار أطروحة تورينغ، ألونزو تشورتش، بالعمل على حل القضية عام 1933. ولقد طرح حلّه الخاص وأطلق عليه الدوّال المعدودة الفعّالة وقدّمه إلى غوديل في آذار من عام 1934. ومن المفترض أن غوديل رفض توجّه تشورتش باعتباره "غير مُرضٍ تمامًا" (Soare , 2013). واعتمادًا على مبدأ حساب – λ فإن نظرية وتوجه تشورتش كان كالتالي:
التعريف الأول للمعدوديّة (تشورتش ، 1934) :
الدالة تكون معدودة إذا وفقط إذا كانت معرّفة في λ .
عمل تشورتش وتلميذه الدؤوب ستيفن كليين معًا على تعريف الدوال المختلفة على أنّها معرّفة في λ منذ عام 1931. ومع حلول عام 1934 تمكّن العالمان من إثبات أن الدوال العددية النظرية جميعها معرفّة وفق λ. ومع ذلك فقد علم غوديل أن الدوال التكرارية التي أشار إليها في ورقته البحثية عام 1931 لم تتضمن جميع الدوال المعدودة لذلك ستشكل تلك الفرضية أساسًا هشًّا للمقولة التي تفترض معدودية جميع الأرقام. وللتعويض عن هذا النقص قام غوديل في ربيع عام 1934 بتوسيع نظريّته السابقة بناءًا على مفهوم جاك هالبراند (1908-1931) ووضع أسس ما يُعرف بالدوال التكرارية لهارباند-غوديل (تُعرف في وقتنا الحاضر بنظرية الدوال التكرارية فقط)، كما وأطلق على التحسينات التي أضافها إلى بحثه عام 1931 ما يُعرف في حاضرنا بـ " الدوال التكرارية الأوليّة " . قام كل من تشورتش وكليين بعد حضورهم لعدّة محاضرات لغوديل، قاما بمراجعة تعريفهم الخاص للمعدودية وتعديلها بحيث تتخذ من نظرية هيربراند-غوديل أساسًا لها:
التعريف الثاني للمعدودية (تشورتش 1936)
الدالة المبنية على أساس الأعداد الصحيحة الموجبة تكون معدودة فقط إذا كانت تكرارية
وتمكّن كل من تشورتش وكليين لاحقًا من توضيح أمرٍ هام وهو أن الدوال المعرفة على λ التي استخدموها في تعريفهم الأول و كذلك الدوال التكرارية لغوديل – هيرابند التي أسست تعريفهم الثاني، كلا التعريفين كانا متشابهين وذو أساس واحد. ومع ذلك فإن غوديل لم يتسطع تقبّل تعريف تشورتش (غوديل 1995)، واختلف معه بشكل جوهري في مبادئه وتبريراته. تمثّل جوهر الخلاف الأساسي وفقًا لسيج (1994, p,90) أن " الخطوات الحسابية لا بُد أن تكون وفق رموز محدودة وهي (هنا) مفترضة وبشكل مباشر أنها تكراريّة" ويضيف أيضًا " وهذه النقطة بالتحديد هي التي تشكل عائقًا كبيرًا أمام قبول تحليل تشورتش" وهذه النقطة الحساسة " كانت ثغرة واضحة لدى اطروحات كل من تشورتش نفسه وغوديل".
حل تورينغ
في هذه الأثناء انتقل تورينغ إلى جامعة برينستون للعمل على إيجاد حلول لكل من قضية هليبرت (Entscheidungsproblem) بالإضافة إلى وضع تعريف ثابت ووواضح لمفهوم المعدوديّة. وخلال اجتماع محفل الرياضيين الثاني والأربعون في لندن في 30تشرين الثاني للعام 1936، قام تيورينغ بطرح تعريفه النهائي للمعدودية كالتالي (Soare , 2013) :
تعريف تيورينغ للمعدودية (1936)
يمكن القول عن دالة بأنّها قابلة للحساب بشكل بديهي (بشكل عملي) فقط وفقط إذا كانت قابلة للحساب بواسطة آلة تيورينغ، والتي هي عبارة عن آلة أوتوماتيكية (a-machine) كما عبر عنها تيورينغ (1936).
نوّه تيورينغ في ورقته البحثية إلى التشابه ما بين تعريفه وتعريف تشورتش في بحثه قبل سبعة أشهر، معلّقًا " في إحدى الأوراق البحثية السابقة لألونزو تشورتش قدّم ما دعاه "الحساب الفعّال" والتي تواكب نظريتي حول "المعدودية" في الفكرة الأساسية ولكنها تختلف عنها في طريقة التعريف مضيفًا أن تشورتش وصل إلى نتائج مشابهة حول برنامج هلبرت Entscheidungsproblem.
وبخلاف تشورتش وكليين فإن تعريف تورينغ لم يعتمد على الدوال التكرارية لغوديل (1931) أو دوال غوديل- هيرباند (1934). وعوضًا عن ذلك شرع تورينغ يتحدّث عن دراسة وتحليل كيفية قيام البشر بالحسابات المختلفة، مظهرًا خطوةً بخطوة كيف يمكن القيام بنفس العملية بواسطة آلة. وفي خضمّ هذا التحليل المميز، كتب غاندي (1988) لاحقًا " تحليل تورينغ يقدّم لنا أكثر من مجرّد فكرة بل يتعدّاها إلى كونه نظريّة وبدون أن يعرّج إلى أي مصدر لتلك الآلات التي تحدّث عنها. وبدلًا من ذلك يبدو أن آلات تيرونغ هي نتيجة ، أو تجميعةٍ ونتاجٍ، لتحليله الفريد عن طريقة حسابات البشر للقيم" (Soare , 2013).
وقد ابتكر تورينغ نموذج أولي، وطرح مفهوم الآلات الأتوماتيكية أو ما يُعرف بآلات تورينغ. ويمكن تعريف آلات تورينغ وفق ما يلي:
آلة تورينغ (a-machines) هي نموذج رياضي لطريقة حسابيّة تمثّل آلة تجريديّة تقوم بمعالجة الرموز المُدخلة على أجزاء من الشريط التي تزوّد بها ووفق قواعد وأوامر موضوعة لها مسبقًا. وبغض النظر عن بساطة التصميم، وبفرض أي خوارزمية حاسوبية، فإنه بالإمكان بناء آلة تورينغ بحيث تماثل منطق تلك الخوارزمية.
التشابه الكبير بين تعريف تيورينغ وبين وجهة نظر غوديل لطريقة الحساب (Soare , 2013)
لكن تييورينغ أظهر المزيد. لقد أوضح أن الوظائف الحسابية المحددة بهذه الطريقة هي بالضبط تلك الوظائف التي يمكنك من خلالها بناء آلة مع عدد محدود من الأجزاء التي ستقوم بما يلي. إذا قمت بتدوين أي عدد n₁ و n₂ و ... nᵣ على قصاصة من الورق ووضعت القصاصة في الماكينة وشغلت الساعد فإنها وبعد عدد محدود من الدورات ستتوقف الآلة وستتحدد قيمة الدالة في القضية الرياضيّة n₁ و n₂ و ... و nᵣ وسيتم طباعة هذه النتيجة على الورق.
الأرقام الغير قابلة للحساب
نحن نعلم أن مجموعة الأرقام الحقيقية غير قابلة للعد ، وبالتالي فإن مجموعة الأرقام القابلة للحساب قابلة للعد أيضًا، وهذا يعني أيضًا أن معظم الأرقام الحقيقية غير قابلة للحساب. ينبثق إثبات أن الأرقام القابلة للحساب قابلة للإحصاء و العد بديهيًّا من حقيقة أنه قد يتم إنتاجها جميعًا بواسطة ماكينات تورينج، والتي تتضمن عدد محدود من الأوامر والمعالجات الحسابيّة (أي يمكن وضعها بشكل متوافق مع الأرقام الطبيعية). وبشكلٍ أدقّ:
مسوّدة صغيرة لبرهنة قابليّة الأرقام المعدودة للحساب
من خلال تعيين رقم غوديل لكل تعريف لجهاز تيورينج ينتج مجموعة فرعية S من الأرقام الطبيعية المقابلة والمتوافقة مع الأرقام القابلة للحساب. A الناتجة عن عملية غامر ( أو سوريجيكشون وهي عملية حسابية رياضية معروفة) على S للأعداد القابلة للحساب تُظهر أن الأرقام القابلة للحساب قابلة للعد على أكثر تقدير.
المثال A على ثابت شانتين Ω
قام العالم الرياضي الأمريكي-الأرجنتيني عام 1975 بطرح عدد حقيقي غير قابل للحساب، والذي يُطلق عليه الآن ثابت شانتين، أوميجا Ω. والذي يمثّل احتمال انتهاء أو توقّف برنامج مبني بشكل عشوائي:
تجربة شانتين التخيليّة (Barmpalias, 2018)
لنفترض أننا نقوم بتشغيل جهاز تورينج عالمي على برنامج ثنائي عشوائي. وعلى وجه التحديد ، كلما تطلب الأمر الجزء التالي من البرنامج ، نقلب قطعة نقود ونقوم بإدخال المخرجات الثنائية إلى الجهاز. ما هو احتمال توقف آلة تورينج؟
تجربة شيتين التخيليّة هي في الواقع مثال نموذجي لما يُعرف بظاهر أو مشكلة التوقف الذاتي (halting problem). مشكلة التوقف الذاتي هي مشكلة تحديد، من خلال برنامج كمبيوتر عشوائي ومدخلات مختلفة، ما إذا كان البرنامج سيتعطّل عن العمل (يتوقف) أو سيستمر في العمل بصورة دائمة. وفي سياق آلات التحديد الذاتي ، يأخذ احتمال التوقف Ωᵤ لآلة تورينج U التعبير التالي:
احتمال التوقّف لآلة تورينج U باعتبار المُدخلات هي σ
حيث يمثل σ البرامج الثنائية العشوائية المحدودة U(σ)↓ يدل على أن U سوف يتوقف عند الإدخال σ. أثبتت ورقة تورينج البحثية عام 1936 أنه لا يمكن أن توجد خوارزمية عامة لحل مشكلة التوقف لجميع أزواج الإدخال البرمجية الممكنة. فلا يوجد احتمال توقف قابل للحساب. يعتمد إثبات هذه الحقيقة على خوارزمية ،باعتبار أن الأرقام الأولى n من Ω ، تحل مشكلة توقف آلة تورينج بالنسبة للبرامج التي يصل طولها إلى n. وبما أن مشكلة التوقف غير قابلة للحسم بشكل نهائيّ ، فلا يمكن حسابها.
المثال B: قضيّة القندس المشغول :
قام تيبور رادو عام 1963 في ورقة بحثية نشرها بعنوان " الدوال الغير قابلة للحساب"، قام بطرح المشكلة التالية:
ما هو أكبر عدد محدد من 1s يمكن إنتاجه على شريط فارغ باستخدام آلة تورينج ذات الحالات n؟
أصبحت المشكلة فيما بعد معروفة باسم مشكلة "القندس المشغول". باعتبارها لعبة، فإنه غالبًا ما يتم توصيف المشكلة كما يلي: العثور على برنامج إنهاء ذي حجم معين ينتج عنه أكبر قدر ممكن من المخرجات. تحتوي المشكلة على تعبير طبيعي كدالة رياضية (BB(n حيث إذا كان n يمثل عدد الحالات ، فإن (BB(n يمثل أكبر عدد محدد من 1s يمكن كتابته على شريط فارغ بواسطة جهاز تورينج بهذا الحجم. ونحصل على :BB (1) = 1 ، BB (2) = 4 ، BB (3) = 6. بالنسبة إلى (BB(4 فإن المشكلة تزداد صعوبةً. والجدير بالذكر أن إثبات أن BB (4) = 13 فحسب كانت أطروحة للرسالة دكتوراه. قيمة (BB(5 غير معروفة ، ولكنها غالبًا 4098 على الأقل (بواسطة Marxen & Buntrock في عام 1989) ، أما قيمة (6)BB فهي على الأقل 3.5 × 10¹⁸²⁶⁷ (وجدت بواسطة Kropitz في عام 2010).
وما نستسنتجه أن دالة (BB(n هي خير مثال على دالة غير قابلة للحساب. أي أنه لا يوجد جهاز تورينج Mᴮᴮ يمكنه حساب وظيفة BB. وهذا يمكن إثباته بالتناقض التالي:
دليل على أن (BB(n غير قابل للحساب (Roberts، 2016)
نبدأ بافتراض أن دالة القندس المشغول (BB(n قابلة للحساب ، وأن هناك آلة تورينج Mᴮᴮ تتضمن β من الحالات يمكنها أن تأخذ n كمدخلات ،وتكتب رقم (BB(n لـ 1s كإخراج وثم توقف. ولنفترض أن المحو يرمز إلى تسلسل إعادة بدء لآلة تورينج مؤلفًا من 1s ومكتوبًا في البداية على الشريط. ولفترض أن التضعيف ترمز إلى تقييم آلة تورينج للدالة n + n.
عند إعطاء شريط يحتوي على n 1s ، فإنه سينتج 2n 1s على الشريط ، ثم يتوقف. الآن قم بإنشاء الروتين " تضعيف | تقييم BB | محو " واعتبر أن n0 هي عدد حالات هذا الجهاز. وافترض أن أمر "تنظيف- n0 " يشيريرمز إلى قيام آلة تورينج بكتابة n0 على شريط فارغ في البداية. ولنعتبر أن N تدل على مجموع n₀ + n₀.
دع BadBB تشير إلى الأوامر "محو n₀ | تضعيف | تقييم BB | محو ". يحتوي هذا الجهاز على عدد من الحالات قدره (N (n₀ + n₀. سيؤدي تشغيل BadBB إلى إنتاج BB(N) 1s على الشريط قبل مسح جميع 1s والتوقف. لكن خطوة الأمر "محور أو تنظيف" ستستمر على الأقل عددًا من الخطوات أو الدورات قدرها (BB(N ، لذلك يجب أن يكون وقت حساب BadBB أكبر تمامًا من (BB(N ، مما يتعارض مع تعريف الدالّة (BB(n.
بصرف النظر عن كونها لعبة رياضية مثيرة للاهتمام وصعبة ، فإن مشكلة القندس المشغول لها أيضا أبعاد أخرى في الممارسة العمليّة. بالنسبة لـقضية هيلبرت (Entscheidungsproblem) ، لفترض أن أي تخمين رياضي يمكن دحضه بواسطة ما يُعرف بـ الأدلة المضادّة / الوجودية ومن خلال عدد لا يحصى من الحالات (مثل تخمين Goldbach). إذا كانت هذه التخمينات صحيحة ، فإن ماكينة تيورينج التي تبحث عن أدلة مضادة لن تتوقف. وإذا لم يكن هذا صحيحًا ، فستتوقف آلة تيورينج وتقوم بإخطارنا بأنه قد وجدت مثالًا مضادًا. إذا قمنا بمحاكاة جهاز تيورينج بوضعيات مختلفة لـ (n (n-state ومعرفة قيمة (BB (n ، فيمكننا أن نقرر ما إذا كانت دالة تيورينج ستتوقف عن العمل بعد أن نقوم بإعطائها الأوامر لإنجاز ذلك العدد المحدد من الخطوات. وبالمقابل إذا لم تتوقف الماكينة ، بعد عدد خطوات (BB(n، فإننا عندها سنعرف أنها لن تتوقف أبدًا ، وبالتالي لا توجد أمثلة مضادة للقضية مالطروحة على آلة تيورينج، مما يثبت أن التخمين صحيح.
بالرغم من أن ما توصلنا إليه صحيح نظريًّا، إلا أنه غير قابل للتطبيق حاليًّا في الممارسة.
وويكيبيديا تطرح سببين لذلك:
* من الصعب للغاية إثبات قيم دالّة "القندس المشغول" الحالة والنقطة ، (BB (6 ذات قيمة 3.5 × 10¹⁸² على الأقل ومن المفترض أن يحتاج المرء إلى 20 إلى 50 احتمال على الأقل لصنع آلة مفيدة لحل مثل تلك القضايا الرياضيّة. علاوة على ذلك ، فإن الحالات القليلة التي تمّ حلّها ، تم ذلك باستخدام طريقة التحقق اليدوي لكل آلة تورينج ذات حالة n، وهذا لن يكون ممكنًا عمليًا لجهاز ذي حالات أكبر.
* وحتى إذا وجد المرء طريقة أكثر فعالية لحساب حالات (BB (n، فإن قيمة الدالة ستصبح كبيرة جدًا وبسرعة خياليّة، نعلم أن (BB(17 أكبر من G ، رقم Graham. يتطلب (BB (6 قدرة حاسوبيّة أكبر بكثير من تلك الموجودة والمعروفة حاليًّا في كوننا ليتم تنفيذها مباشرة (لويد ، 2001).
المثال C: رصف أو تجانب بينروز
تجانب بينروز هو مثال على التجانب غير الدوري الذي يتم إنشاؤه بواسطة مجموعة غير دورية من التجانب الأولي. ولأن هذه الأنماط غير دورية ، فإنها تفتقر إلى التناظر الانتقالي. كما أنها متشابهة ذاتيا ("كسرية") ، لأنها تظهر كما هي في المقاييس الأكبر والأكبر.
تجانب بينروز
في الواقع إن مسألة ما إذا كانت مجموعة القطع المرتصفة ستغطي الأسطح جميعها كانت من تخمين ها ووانغ 1961. يعتمد الاختبار على استخدام القطع المرتصفة لمحاكاة آلة تيروينج، بحيث تتم هندسة القطع المرتصفة بطريقة لا تغطي المستوى كاملًا إلا إذا كانت آلة تيورينج تعمل بشكل مستمر بدءًا من شريط فارغ. ونظرًا لأن قضيّة التوقف (halting) غير قابلة للحسم، فإنه يجب أن تكون مشكلة التجانب غير قابلة للحسم أيضًا وبالتالي لا يمكن حلها.
الخاتمة
في وقتنا الراهن، في مجال الرياضيات وعلوم الكمبيوتر، تُعدّ ماكينات تورينج الطريقة الأساسية لتحديد الدوال القابلة للحساب(Soare ، 2013 ص. 213). ومع ذلك ، تقديراً لتشورتش لإدراكه جوهر هذه الدوال أولاً ، أصبحت صياغة فرضية العصر الحديث حول طبيعة الدوال الحسابية تُعرف الآن باسم أطروحة تشورتش - تورنج:
أطروحة تورتش- تيورينغ
تكون الدالة قابلة للحساب فقط وفقط إذا كانت قابلة للحساب بواسطة ماكينة تيورينج، أو ما يوافقها بشرط اعتماد الدوال التكرارية كأساس لها.
ونتائجها هي كالتالي:
لا توجد طريقة للحساب تنفذها عملية أوتوماتيكية آلية يمكن أن تكون أقوى من آلة تورينج.
على الرغم من اعتماده هذا المنهج على نطاق واسع، إذ لا توجد في الواقع طريقة واضحة لإثبات أو دحض صلاحيّتها، على الرغم من ذلك لا يزال هذا الاقتراح مجرد تخمين. ويتوفر المزيد من التفاصيل حول مراحل تطوّر الرسالة البحثية هذه على ويكيبيديا.
المصدر:
1. Uncomputable Numbers. Real numbers we can never know the… | by Jørgen Veisdal | Cantor’s Paradise | Medium
ترجمة:
نادرحوري
مراجعة وتدقيق:
علي الحمد
"مهندس كهربائي، مهتم في فلسفة الرياضيات والمنطقانية"
Comments