آلة تورينغ

استمع على ساوندكلاود 🎧

حديثُنا اليوم هو عن آلة تورينغ، وهي آلةٌ مُجرَّدةٌ صَمَّمها وبرهنَ على خصائصها عالِمُ الرياضيات آلان تورينغ ونشر ذلك عام 1936، ونَعرِف أحدَ أشكال هذه الآلة اليوم باسمٍ آخر: الحاسوب.

آلةُ تورينغ هي عبارةٌ عن نموذجٍ رياضيٍّ يُعبِّرُ عن آلةٍ لها القدرة على القيام بعملياتٍ حَوسبيةٍ متعدِّدةٍ كجمعِ الأرقامِ وتمييزِ النّصوص والكثير الكثير. بشكلٍ أو بآخر فإنَّ آلة تورينغ هي التَّمثيلُ الرياضيُّ لما نسميه اليوم بالحاسوب.

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

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

بعد أن تعرَّفنا أنَّ آلة تورينغ لها حالةٌ تكون عليها ولديها شريط مُدخَلاتٍ ومُخرجَات، دعونا نرى كيف تعمل هذه الآلة بتفصيلٍ أكثر: تبدأ الآلةُ العملَ عبرَ قراءةِ النَّصِّ المُدخل على شريط الإدخال حرفاً حرفاً، وعند قراءةِ كُلِّ حرفٍ تُقرِّرُ الآلة -حسب تصمميها الموضوعة عليه- إنْ كانتْ ستغيّر حالتَها أم تبقى على ما هي عليه وتستطيعُ أيضاً أن تقرّر إن أرادت أن تكتب شيئاً ما.

تُمكِّنُ هذه الآليةُ البسيطةُ للعمل آلةََ تورينغ من القيام بمهامٍ عديدةٍ جداً بُرهِن على أنَّها نفسُ المَهامِ الّتي يستطيعُ الحاسوبُ المعاصر أن يَحلُّها.

كمثالٍ عمليٍ على آلة تورينغ:

يمثّل المخطَّط أعلاه آلةَ تورينغ تقرأ نصاً من الأصفار والواحدات وتُخبر المستخدم إن كان النصُّ المُدخَل مؤلفاً من أصفارٍ تتبعها واحدات وإن كان عددُ الأصفار هذه يساوي الواحدات أم لا.

يراودنا سؤال، هل توجد آلةُ تورينغ تستطيعُ قراءةَ مخططٍ لآلةِ تورينغ أخرى والتعاملَ معها؟ وما الذي نستطيعُ القيام به بوجود هذه الآلة؟

الجواب هو نعم؛ لكنَّ ما تستطيعُ هذه الآلةُ عملَه محدودٌ جداً. أحدُ ما بإمكانها إنجازُه هو مُحاكاة الآلة المدخلة بحيث أن الآلة القارئة تبدء بالتصرف حسب تصميم الآلة التي تقرأها، يُدعى هذا النوع من آلة تورينغ بآلة تورينغ الشاملة/الكونية Universal Turing Machine.

إن دقّقنا بهذه الآلة نرى أنَّ هنالك تشابهاتٍ كبيرةً بينها وبين الحاسوب المعاصر، إذ أنَّ هذه الآلة Universal Turing Machine تُمثّل الحاسوب، ويمثّل شريطُها ذاكرةَ الحاسوب، ويمثّل تصميمُ الآلة المكتوب على الشريط برامجَ الحاسوب؛ يقوم الحاسوب بقراءة البرامج و تنفيذها كما تفعل آلة تورينغ عندما تقرأ تصميم آلة تورينغ أخرى و تحكاكيها.

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

لا تستطيعُ آلة تورينغ -وبالنتيجة حواسيبُنا- حلَّ كُلِّ المسائل، فقد برهن آلان تورينغ على أنَّ هناك مجموعةً من المسائل يستحيلُ على آلته حلُّها، وأنَّه مهما طال الزمن لن يستطيعَ حاسوبٌ من حواسيبنا حلَّها.

كمثالٍ على المسائل التي لا يُمكن لآلة تورينغ حلَّها هي إن أُعطيتْ الآلة آلةً أُخرى كمدخل، هل بإمكانها أن تُحدِّد ما إن كانت الآلة المُدخلة ستُعطي نتيجةً أم لا؟ أي أنّه لو كان لدينا برنامجٌ يفحص البرامجَ الأخرى، هل بإمكانه تفحُّصُها جميعاً بشكلٍ دقيقٍ وأن يُخبرَنا دوماً ما إذا كانت هذه البرنامج ستقومُ بتنفيذِ عملها أم أنها ستبقى تعملُ (أو تَعلَقُ في حلقةٍ مفرغة) إلى نهاية الزمان؟

مع بساطة هذه المسألة فلا يُمكن حلُّها بشكلٍ عام، ولذلك كنتيجةٍ في واقعنا، لا يُمكن تصميم برنامج يتفحَّص البرامج دون تشغيلها ويُخبر المستخدم إن كانت هذه البرامج ستعمل أم لا دون مشاكل.

توجدُ أيضاً مجموعةٌ من المسائل التي يُمكن لآلة تورينغ حلُّها لكنَّها تأخذُ وقتاً طويلاً جداً إذ أنَّ إيجاد الحلِّ يُعتَبر في الواقعِ أمراً غيرَ عمليٍّ بشكلٍ عام.

أحدُ الأمثلة على هذه المسائل هي مسألةُ إيجادِ أقصر طريقٍ يمرُّ بمجموعة مدن، شَرْطَ ألا يمرَّ مستخدمُ الطريق بمدينةٍ معيّنة أكثرَ من مرّةٍ واحدة، ثمَّ يعودُ إلى حيث بدأ (مسألةُ إيجاد أقصر طريق هاملتوني).

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

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

تبقى الأسئلة الآن: هل هذه حُدودُ الحوسبة؟ هل سنصنع آلةً تتجاوز اختبار تورينغ بشكل عام؟ من سوف يجيب عن هذه الأسئلة؟ وحدَه الزمن سيكشف الإجابات.