شرح آلات تورنغ

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

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

سؤال تورنغ

في عام 1928 سأل ديفيد هيلبرت: هل توجد طريقة آلية تقرر، لكل عبارة رياضية، هل يمكن إثباتها؟ هذه هي مسألة القرار (Entscheidungsproblem). وللإجابة عنها كان على أحد أن يحدد بدقة ما الطريقة الآلية. ففي ورقته عام 1936 «حول الأعداد القابلة للحساب» (On Computable Numbers)، تخيّل تورنغ موظفًا يعمل بالقلم والورق، وجرّد عمله إلى أصغر خطواته: انظر إلى رمز واحد، وغيّره، وانتقل إلى رمز مجاور، وتذكّر شيئًا قليلًا عما كنت تفعله. وكانت النتيجة آلة تورنغ.

آلة بومب (يسار) وصورة آلان تورنغ (يمين)
آلة بومب (يسار) وصورة آلان تورنغ (يمين)

الآلة

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

البرامج بوصفها جداول قواعد

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

الآلة الشاملة

كانت أهم فكرة لتورنغ أن جدول القواعد نفسه يمكن أن يُكتب على الشريط. فآلة تورنغ الشاملة تقرأ وصفًا لأي آلة أخرى ومدخلها، ثم تحاكيها خطوة بخطوة. وهكذا تستطيع آلة واحدة ثابتة أن تشغّل كل برنامج: وهذا هو المبدأ الذي يقوم عليه كل حاسوب ذي برنامج مخزن، حيث البرمجيات مجرد بيانات في الذاكرة. وكل نظام يستطيع محاكاة آلة تورنغ شاملة يسمى تامًا وفق تورنغ (Turing complete)، ومن ذلك كل لغات البرمجة، ولعبة الحياة لكونواي، والأتمتة الخلوية Rule 110.

أطروحة تشرش–تورنغ

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

مسألة التوقف

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

القنادس المشغولة

في عام 1962 حوّل تيبور رادو مسألة التوقف إلى لعبة: من بين كل الآلات ذات n حالة والرمزين 0 و1 التي تتوقف عندما تبدأ على شريط فارغ، أيها يكتب أكبر عدد من الآحاد، وكم خطوة يمكن أن تستغرق آلة كهذه؟ هذه الأعداد، أي قيم القندس المشغول، تنمو أسرع من أي دالة قابلة للحساب، لأن وجود طريقة لحسابها يعني حل مسألة التوقف. والقيم المعروفة هي 6 و21 و107 خطوات لحالتين وثلاث وأربع حالات؛ أما لخمس حالات فإن بطلة هاينر ماركسن (Heiner Marxen) ويورغن بونتروك (Jürgen Buntrock) تستغرق 47,176,870 خطوة، وهي قيمة أثبتها عام 2024 تعاون bbchallenge عبر الإنترنت ببرهان تحققت منه الحواسيب. ولست حالات تُعرف آلات تعمل عددًا من الخطوات أكبر من أن يُكتب بالترميز المعتاد.

استكشفها بنفسك

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

الأسئلة المتداولة

هل بُنيت آلة تورنغ يومًا؟

ليس كما وصفها تورنغ، لأن شريطها لا نهاية له، لكن الفكرة سرعان ما تبعتها حواسيب حقيقية ذات برامج مخزنة، ساعد تورنغ نفسه في تصميمها بعد الحرب العالمية الثانية. ومنذ ذلك الحين بنى الهواة نماذج عاملة من الخشب ومن LEGO بل حتى داخل لعبة الحياة، وكلها بشريط محدود، وهذا يكفي لأي حساب ينتهي.

ما الفرق بين عددي الخطوات 14 و21 لثلاث حالات؟

هناك سؤالان للقندس المشغول: أكبر عدد من الآحاد المكتوبة، وأكبر عدد من الخطوات المقطوعة. فلثلاث حالات، تكتب الآلة الموجودة في المحاكي الحد الأقصى وهو ستة آحاد في 14 خطوة، بينما تستغرق آلة أخرى ذات ثلاث حالات الحد الأقصى وهو 21 خطوة لكنها لا تترك إلا خمسة آحاد. أما لحالتين وأربع وخمس حالات، فآلة واحدة تفوز بالأمرين.

هل تعني التمامية وفق تورنغ القوة؟

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

لماذا لا يستطيع الحاسوب ببساطة تشغيل برنامج ليرى هل يتوقف؟

التشغيل يُظهر أن البرنامج يتوقف، إن كان يتوقف، لكن إذا لم يتوقف بعد فلا يمكنك أن تعرف هل لن يتوقف أبدًا أم يحتاج فقط إلى وقت أطول. ويُظهر برهان تورنغ أنه لا توجد طريقة أذكى تنجح مع كل برنامج، وإن كان السؤال يمكن الإجابة عنه لكثير من البرامج بعينها.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

افتح محاكي آلة تورنغ