في ١٥ يوليو ٢٠١٩، قدَّم محافظ بنك إنجلترا، مارك كارني، تصميمَ
الأوراق النقدية من فئة ٥٠ جنيهًا إسترلينيًّا، وتوقَّع أن تدخل
التداول بعد حوالي عامين. في عام ٢٠١٨، قرَّر بنك إنجلترا الاحتفاء
بشخصية علمية بطباعة صورته على الورقة النقدية الجديدة وفُتح باب
الترشيح العام لمدة ستة أسابيع لاختيار هذه الشخصية. بلغ إجمالي
الترشيحات ٢٢٧٢٩٩ ﻟ ٩٨٩ شخصية مؤهَّلة للانتخاب. ومن هنا، استقرت
اللجنة الاستشارية المعنية باختيار صور الشخصيات على الأوراق النقدية
على قائمةٍ قصيرة تضم ١٢ مرشحًا. بعد ذلك اتخذ محافظ البنك قراره
النهائي، ووقَع الاختيار على آلان تورنج. وقال في معرض تعليقه على ذلك:
«لقد كان آلان تورنج عالِم رياضيات فذًّا، وكان لعمله تأثير هائل على
أسلوب معيشتنا اليوم. باعتبار آلان تورنج رائد علم الكمبيوتر والذكاء
الاصطناعي، وباعتباره بطلَ حرب أيضًا، فقد كانت إسهاماته واسعة النطاق
ورائدة. إن تورنج عملاق يقف على كتفيه الكثيرون الآن.»1
كان تورنج (١٩١٢–١٩٥٤) عبقرية فذة استكشف حدود عمليات الحوسبة
وطبيعتها وتنبَّأ بظهور آلاتٍ ستُظهِر سلوكًا ذكيًّا، وتصدَّى لمسألة
ما إذا كانت الآلات تستطيع التفكير، وأسهمَ كذلك في علم الأحياء
الرياضية وآليات التشكل الحيوي، وكان له دور بالغ الأهمية في تحليل
الرموز السرية للرسائل الألمانية المشفَّرة إبَّان الحرب العالمية
الثانية (وظل إسهامه هذا طي الكتمان عقودًا). وفي منعطفٍ مأساوي
للأحداث، مات تورنج منتحرًا. كان قد أُلقي القبض عليه وأُدين بالشذوذ
الجنسي عام ١٩٥٢ الذي كان مُجرَّمًا في المملكة المتحدة آنذاك، ومِن ثَم
أُجبر على تناول علاج هرموني. وقد صدر عفو رسمي بحقه عام ٢٠١٣. ويُعَد
ظهوره على الورقة النقدية الجديدة شكلًا من إعادة الاعتبار الذي لم يكن
أحدٌ ليفكِّر فيه قبل بضعة عقود.2
على مدى صفحات هذا الكتاب، وصفنا الخوارزميات بأنها تتكوَّن من
خطوات بسيطة وسهلة لدرجة أنه يمكن تنفيذها باستخدام الورقة والقلم.
وبالنظر إلى أننا ننفِّذ الخوارزميات في برامج الكمبيوتر، فإن السؤال
عن ماهية الخوارزمية في الحقيقة سيساعدنا في فهم ما يمكن أن تحسبه في
الواقع. وهذا يتطلب منا التعمُّق أكثر في طبيعة هذه الخطوات البسيطة.
فالعمليات الحسابية التي يستطيع طالب المرحلة الابتدائية إجراءها
بالورقة والقلم، في النهاية، مختلفةٌ عن العمليات التي يمكن أن يجريها
خريج الجامعة. فهل يمكن أن نحدِّد بدقةٍ نوعيةَ الخطوات التي يمكن أن
تتكوَّن منها الخوارزمية؟ قدَّم تورنج إجابةً لهذا السؤال حتى قبل ظهور
أجهزة الكمبيوتر الرقمية. فقد قدَّم نموذجًا لآلة في عام ١٩٣٦ للإجابة
على السؤال المتعلِّق بما يمكن أن يفعله أي جهاز كمبيوتر. و«آلة تورنج»
عبارة عن آلة عبقرية بسيطة. وتتكوَّن من الأجزاء التالية:3
(١)
«شريط». ينقسم الشريط إلى مربَّعات أو «خانات». كل خانة
يمكن أن تكون إما فارغة أو تحتوي على رمز هجائي. ويمكن أن
يكون الشريط طويلًا لما لا نهاية.
(٢)
«رأس» يمكن أن يتحرك يمينًا أو يسارًا على طول الشريط،
ويتحرك في اتجاه واحد في كل مرة. يمكن للرأس قراءة الرمز
في الخلية التي تحته. ونطلق على الرمز في تلك الخلية
«الرمز الممسوح ضوئيًّا». ويمكن للرأس أن يمحو الرمز
الممسوح أو تستبدله.
(٣)
«وحدة للتحكم المحدود» وتسمَّى أيضًا «مسجل الحالات».
يمكن أن توجَد وحدة التحكم المحدود في أي مجموعة محدودة من
الحالات. يمكنك تشبيهها بقرصٍ منقوش عليه حالات ومزوَّد
بمؤشر يمكن أن يشير إلى أي حالة منها.
(٤)
«جدول توجيهات محدود». يحدِّد كل توجيه «الحركة» التالية
للآلة. هذا ما تفعله الآلة بناءً على الحالة الحالية
والرمز الممسوح.
هل يمكن أن نحدِّد بدقة نوعيةَ الخطوات التي يمكن أن تتكوَّن
منها الخوارزمية؟ قدَّم تورنج … نموذجًا لآلة في عام ١٩٣٦ للإجابة
على السؤال المتعلِّق بما يمكن أن يفعله أي جهاز كمبيوتر.
تتكوَّن الرموز الهجائية في تلك الآلة من الرقم ١ وعلامة
⋆. تُظهر وحدة التحكم
المحدود أن الآلة يمكن أن تكون في حالةٍ من سبع حالات وهي ، ، …، . ويحتوي جدول التعليمات على صفٍّ لكل حالة محتملة،
وعمود لكل رمز محتمَل، ونستخدم الرمز للإشارة إلى الخانة الفارغة، حتى يمكن أن نرى ذلك
الرمز. يشار إلى الحالة الحالية بالصف والرمز الممسوح ضوئيًّا بالعمود.
يحتوي كل إدخال في جدول التعليمات على ثلاث قيم تصف حركة، أو قد يحتوي
على شَرطة، ما يعني أن الآلة ليس لديها ما تفعله في هذه المجموعة
الثنائية من الصف والعمود.
تتكوَّن حركة الآلة من ثلاثة إجراءات:
(١)
قد تغيِّر الآلةُ الحالةَ الحالية أو تبقى عليها. الحالة
الجديدة هي العنصر الأول من القيم الثلاث في جدول
التعليمات المحدود.
(٢)
ستكتب الآلة رمزًا أسفل الرأس. قد يتطابق الرمز مع الرمز
الموجود بالفعل (وفي هذه الحالة يبقى الرمز الحالي في
الخانة). والرمز المراد كتابته هو العنصر الثاني في القيم
الثلاث.
(٣)
سيتحرك الرأس إما يسار الخانة الحالية أو يمينها . ويكون الانتقال هو العنصر الثالث في
القيم الثلاث.
يطبِّق مثال آلة تورنج خوارزميةً تحسب الفرق بين العددين و حين تكون ؛ وإلا فسيكون الناتج صفرًا. تسمَّى هذه العملية
«الطرح المبتور» ويُكتب بالصيغة a ∸ b. وبذلك يصبح لدينا
4 ∸ 2 = 2 و2 ∸ 4 =
0.
في البداية، نضع «مدخلات» الآلة على الشريط. والمُدخلات هنا عبارة عن
سلسلة محدودة من الرموز مأخوذة من هجائية الآلة. بذلك تكون جميع خانات
الشريط، الواقعة يمينه ويساره، فارغة. والمُدخلات في هذا النموذج لآلة
تورنج هي ١١١١ ⋆ ١١. تعبِّر
المُدخلات عن العددين أربعة واثنين في «نظام العد الأحادي»، يُفصل
بينهما بالرمز ⋆.
حين تبدأ هذه الآلة عملَها يكون الرأس على خانة المُدخلات أقصى
اليسار. تشير وحدة التحكم المحدود إلى الحالة . ثم تبدأ الآلة في العمل وتنفيذ تحرُّكاتها. إذا
تتبَّعنا عمل الآلة في أول ست حركات، فسنرى أنها تسير بالنمط
التالي:
(١)
الآلة في الحالة والرمز الممسوح هو ١:
يعطينا جدول التوجيهات (، ، )، ولذا ستغير الآلة الحالة إلى وستبدل خانة الرقم ١ إلى خانة فارغة
وتتحرك جهة اليمين. سيصبح الشريط والرأس كما يلي:
(٢)
بالنسبة إلى الحالة والرمز الممسوح ١، يعطينا جدول
التوجيهات (، 1، ). ستقرأ الآلة القيمة ١ وتكتبها وتترك
الخانة كما هي وستتحرك جهة اليمين، بحيث تبقى عند الحالة :
(٣)
تفعل الآلة كما في الخطوة ٢، حيث تقرأ القيمة ١ وتكتبها
وتبقى عند الحالة ، وتتحرك جهة اليمين:
(٤)
مرة أخرى، ستقرأ الآلة القيمة ١ وتكتبها وتبقى عند
الحالة وتتحرك جهة اليمين:
(٥)
تحرَّك الرأس تاركًا الرمز
⋆ وبقي عند
الحالة . التوجيهات هي (،
⋆، ). ستغيِّر الآلة حالتها إلى وتترك الرمز
⋆ على الشريط
وتتحرك جهة اليمين:
(٦)
تحرَّك الرأس مغادرًا الرمز ١ الواقع يمين الرمز
⋆ وأصبح عند
الحالة . التوجيهات هي (،
⋆، ). ستغيِّر الآلة حالتها إلى وتبدِّل الرمز
⋆ مكان الرمز ١
وتعود يسارًا:
ستستمر الآلة في العمل على هذه الوتيرة بحيث تؤدي التحركات التي
يُمليها جدول التوجيهات. إذا نظرنا من مستوًى أعلى، فسندرك أن الآلة
تنفِّذ حلقة. ففي كل تكرار، تجد الرمز ١ أقصى اليسار وتبدله إلى خانة
فارغة. بعد ذلك تبحث جهة اليمين عن الرمز ⋆. وعندما تجده، تستمر في
التحرُّك جهة اليمين حتى تجد الرمز ١ وتحوِّله إلى
⋆. لذا في كل تكرار، تشطب
الآلة أحد الرموز ١ يمين ويسار الرمز
⋆. وعند نقطة محدَّدة، لن
يعود ذلك ممكنًا. عندئذٍ، ستبدِّل الآلة كل رموز
⋆ إلى خاناتٍ فارغة وتنهي
عملها. سيحتوي الشريط على العدد ١١ المكافئ للعدد ٢ محاطًا بخانات
فارغة. وللإشارة إلى إنهاء العمل، تدخل الآلة الحالة ، حيث لا يوجد ما تفعله حسب جدول التوجيهات، وعندئذٍ
ستتوقف.
إذا زودنا الآلة بمُدخلات في صورة ١١
⋆ ١١١١، فستعمل الآلة بكامل
طاقتها إلى أن تتوقَّف وقد امتلأ الشريط بالخانات الفارغة، وتلك
الخانات تساوي صفرًا. إذا أعطينا الآلة أي مدخلات تتكون من من العدد واحد متبوعة بالعلامة النجمية ثم من العدد واحد، فستستمر في حركتها إلى أن تترك
الشريط إما بالقيمة من العدد واحد — إذا كانت — أو ستترك الخانات كلها فارغة.
تستخدم آلة تورنج هذه خوارزميةً لحساب عملية الطرح المبتور بناءً على
المُدخلات واتباع التعليمات التي يمليها جدول التوجيهات. الخطوات أولية
للغاية لدرجةِ أن رأس آلة تورنج يتنقل كثيرًا من أجل إجراء العملية.
سيستغرق ٢١ حركة لإيجاد أن 2 ∸ 4 = 0،
و34 حركة لإيجاد أن
4 ∸ 2 = 2. ولكن ما أبسط تلك
التحركات! بإمكان أي شخص متوسط الذكاء أن ينفِّذها. وهذه الطبيعة
البدائية للخطوات هي نفسها السر. فلست بحاجة إلى مؤهلاتٍ متقدمة لتنفيذ
خطوات آلة تورنج؛ كلُّ ما تحتاجه هو الاطلاع على الجدول والتحرك حول
شريط وقراءة رمز واحد وكتابته في المرة الواحدة، وتتبُّع مسار الحالة.
هذا كل ما في الأمر. ولكن الآلة ليست تافهة؛ لأن الإجابة على السؤال
الخاص بنوعية الخطوات التي يمكن أن تتألف منها خوارزميةٌ ما، هي
الخطوات التي يمكن أن تنفِّذها آلة تورنج.
في هذا الكتاب، تناولنا الخوارزميات بمستوًى أعلى وبخطواتٍ أعقدَ.
وهذا مريح لنا؛ لأن آلة تورنج تعمل بمستوًى من التفصيل المحدود يجعل
استخدامها لوصف الخوارزميات التي تناولناها غير عملي تمامًا. لكن كل
الخطوات التي تنطوي عليها الخوارزميات التي تناولناها يمكن عرضها
كخطوات لنموذجٍ منشأ على نحوٍ صحيح لآلة تورنج. لقد وصفنا نموذجًا
بسيطًا لآلة تورنج لتنفيذ عملية الطرح المبتور. لتنفيذ خوارزميةٍ
أعقدَ، كنا سنحتاج إلى نموذج لآلة تورنج ذي حالات أكثر ورموز هجائية
أكبر وجدول توجيهات أكبر. لكن ظل بإمكاننا بناء ذلك النموذج لو
شئنا.
إن بساطة آلة تورنج لا تعبِّر عن حدود إمكانياتها؛ فبناءً على أي
خوارزمية، يمكننا بناء آلة تورنج تنفِّذ تلك الخوارزمية. لما كانت
أجهزة الكمبيوتر تشغل الخوارزميات، فإن أي خوارزمية يستطيع الكمبيوتر
حسابها، يمكن أن تحسبها آلة تورنج. بعبارة أخرى، «كلُّ ما نستطيع فعله
باستخدام الخوارزميات، يمكن أن نفعله باستخدام آلة تورنج». هذا عرض
مسهب ﻟ «أطروحة تشيرش- تورنج»، التي سمِّيت نسبةً لتورنج وعالِم
الرياضيات الأمريكي ألونزو تشيرش (١٩٠٣–١٩٩٥)، أحد مؤسسي علم الكمبيوتر
النظري. وبما أنها «أطروحة»، فهي ليست شيئًا ثبتت صحته، ولا نعرف هل
يمكن إثباتها رياضيًّا أم لا. من المحتمل، من الناحية النظرية، أنه
يمكن عدم إثباتها إن اخترع شخصٌ ما شكلًا بديلًا للحوسبة يحسب الأشياء
التي يتعذَّر على آلة تورنج حسابها. ولا نظن أن ذلك شيء وارد حدوثه.
ولذا نعتبر آلة تورنج وصفًا رسميًّا لفكرة الخوارزميات.5
يمكنك تخيُّل أي كمبيوتر بالقدرات التي تريدها. سيصبح الكمبيوتر
أسرعَ بكثير من آلة تورنج التي تعمل على شريطٍ من الرموز كما ذكرنا.
ولكن أي شيء يحسبه الكمبيوتر بالخوارزميات، تستطيع آلة تورنج حسابه
أيضًا. يمكنك حتى أن تتخيَّل أجهزة كمبيوتر لم نخترعها حتى الآن. تعمل
أجهزة الكمبيوتر بوحدات «البت» التي لا توجد إلا بقيمتين هما: ٠ و١.
أما «أجهزة الكمبيوتر الكمية» فتعمل بوحدات «الكيوبت». عندما نفحص حالة
وحدات الكيوبت، سنجدها مكوَّنة من القيمة ٠ أو ١ مثل وحدات البت. لكن
عندما لا نفحص وحدات الكيوبت، فيمكن أن تكون في الحالتين الثنائيتين ٠
و١ فيما يسمَّى ﺑ «التراكب». يبدو الأمر كما لو كانت وحدات الكيوبت
تتكوَّن من كلٍّ من ٠ و١ إلى أن نقرِّر قراءتها، وعندها تقرِّر أن تصبح
قيمة من هاتين القيمتين. وهذا يتيح لأجهزة الكمبيوتر الكمية أن تعبِّر
عن عدة حالات من الحوسبة في وقتٍ واحد. وسيتيح لنا جهاز الكمبيوتر
الكمي حلَّ المسائل الحسابية السريعة التي لا يسهُل على أجهزة
الكمبيوتر التقليدية حلها. لكن للأسف، بناءُ كمبيوتر كميٍّ صعبٌ في ظل
التكنولوجيا الحالية. وحتى الكمبيوتر الكمي لا يستطيع إنجاز مهامَّ لا
تستطيع آلة تورنج إنجازها. وعلى الرغم من أن بإمكانه حل بعض المسائل
بكفاءة تفوق أي كمبيوتر عادي في الوقت الحالي أو أي آلة تورنج، فإنه لن
يستطيع حل أي مسائل لا تستطيع آلة تورنج حلها.
تتجسَّد قيود الحوسبة في آلات تورنج. فأي شيء يمكن للكمبيوتر القيام
به يمكننا إنجازه بالورقة والقلم بالعمل على شريط من الرموز. وكل شيء
تراه يُنفَّذ على أي جهاز رقمي هو في الواقع سلسلة من عمليات المعالجة
الأولية للرموز. في علوم الطبيعة، ننظر إلى الكون ونعتقد أن بمقدورنا
تفسير نواميسه باستخدام المبادئ الأساسية. أما في الحوسبة، فالعكس هو
الصحيح. فنحن نمتلك المبادئ الأساسية ونعتقد أنه يمكننا تحقيق نجاحات
باهرة باستخدامها.
عندما طرح تورنج آلته باعتبارها نموذجًا لحوسبة، لمَّا تكن أجهزة
الكمبيوتر الرقمية قد ظهرت بعد. وهذا لم يمنعه من استكشاف إمكانيات
أجهزة الحوسبة التي ستُصنع في المستقبل. عندما نفكِّر في حدود أجهزة
الكمبيوتر، ينبغي أن نتذكَّر أيضًا العجائب التي أنشأها العقل البشري
داخل هذه الحدود. فحدود الحوسبة لم تنتقص من إبداعنا لمواصلة تطوير
خوارزميات تصلح لكل مناحي الحياة. عندما اختُرعت الكتابة في بلادِ ما
بين النهرين، كان الغرض منها المساعدة في حفظ السجلات، وليس كتابة
الأعمال الأدبية. ربما كان الكتَّاب الأوائل محاسِبين، وليس مؤلِّفين،
ولكن من تلك البدايات المتواضعة برز ويليام شكسبير. ومن يعلم ما يمكن
أن تخرجه الخوارزميات في المستقبل.
تتجسَّد قيود الحوسبة في آلات تورنج. فأي شيء يمكن للكمبيوتر
القيام به يمكننا إنجازه بالورقة والقلم … وكل شيء تراه يُنفَّذ
على أي جهاز رقمي هو … سلسلة من عمليات المعالجة الأولية للرموز.