الحالة
الخطوات
الرموز على الشريط
الوضع

في الحالة تقرأ تكتب تتحرك الحالة التالية

مزيد عن آلات تورنغ

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

آلة تورنغ أبسط حاسوب ممكن: رأس يقرأ رمزًا واحدًا من شريط لا نهاية له، ويكتب رمزًا، ويتحرك خلية واحدة يسارًا أو يمينًا، ويغيّر حالته، متبعًا جدولًا قصيرًا من القواعد. اخترعها آلان تورنغ عام 1936، وكل ما يفعله حاسوبك يمكن من حيث المبدأ أن يُنجز بهذه الطريقة. اكتب قواعدك الخاصة أو حمّل مثالًا، واضغط «تشغيل»، وشاهد الشريط يتغير خطوة بخطوة، مع مخطط لتاريخه الكامل في الأسفل. اختر برنامجًا أو اكتب برنامجك، وأدخل المدخل واضغط «تشغيل»، أو «خطوة» لتتبع قاعدة واحدة في كل مرة؛ ويتراجع «رجوع» عن خطوة واحدة. كل سطر في البرنامج قاعدة واحدة: الحالة، والرمز المقروء، والرمز المكتوب، والحركة (L أو R، أو N لعدم الحركة)، والحالة التالية، مثل A 0 -> 1 R B. استخدم _ للخلية الفارغة. تبدأ الآلة في حالة القاعدة الأولى، عند أول رمز من المدخل، وتتوقف عند H أو accept أو reject، أو عندما لا تنطبق أي قاعدة. يعرض المخطط الشريط بعد كل خطوة، من الأعلى إلى الأسفل.

كيف يعمل

  1. اختر برنامجًا مثالًا أو اكتب قواعد مثل A 0 -> 1 R B، قاعدة في كل سطر، ثم اكتب المدخل.
  2. اضغط «تشغيل» لمشاهدة الرأس يتحرك، أو «خطوة» لتتبع قاعدة واحدة في كل مرة؛ ويتراجع «رجوع» عن خطوة واحدة.
  3. اقرأ الحالة والخطوات والرموز على الشريط في البطاقات، وتاريخ الشريط في المخطط.

كيف تعمل الآلة

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

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

أي آلة ذات n حالة، تبدأ على شريط فارغ، تكتب أكبر عدد من الآحاد (1) قبل أن تتوقف؟ طرح تيبور رادو (Tibor Radó) هذا السؤال عام 1962. تُسمى الآلات البطلة القنادس المشغولة، وهي تنمو أسرع من أي دالة يستطيع الحاسوب حسابها. حالتان تعطيان 4 آحاد في 6 خطوات، وثلاث حالات 6 آحاد، وأربع حالات 13 واحدًا في 107 خطوات. أما البطلة ذات الحالات الخمس، التي اكتُشفت عام 1989، فتكتب 4,098 واحدًا في 47,176,870 خطوة، وفي عام 2024 أثبت تعاون عبر الإنترنت، برياضيات تحققت منها الحواسيب، أنه لا توجد آلة أخرى ذات خمس حالات تتوقف وتعمل مدة أطول.

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

كيف أكتب قاعدة؟

قاعدة واحدة في كل سطر: الحالة الحالية، والرمز الذي تقرؤه، والرمز الذي تكتبه، والحركة (L أو R أو N)، والحالة التالية، مثل A 0 -> 1 R B. السهم والفواصل اختيارية. استخدم _ للخلية الفارغة و# للتعليق. تبدأ الآلة في حالة القاعدة الأولى؛ والحالة التالية المسماة H أو halt توقفها، أما accept وreject فتوقفانها مع حكم.

هل تستطيع آلة تورنغ حقًا حساب أي شيء؟

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

لماذا لا يتوقف العدّاد أبدًا؟

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

كيف يستطيع القندس المشغول ذو الحالات الخمس أن يعمل 47 مليون خطوة هنا؟

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

هل يُرسل أي شيء إلى خادم؟

لا. يعمل البرنامج في متصفحك، ويبقى برنامجك ومدخلك في التخزين المحلي لهذا المتصفح.

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

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

الانتقال إلى المحرر