<![CDATA[
المثال الأول: آلة تورينج الأولية
في هذا القسم، سنستعرض مثالًا مبسطًا لآلة تورينج تهدف إلى تغيير حالة خلية معينة على الشريط. هذا المثال يمثل نقطة انطلاق ممتازة لفهم كيفية عمل الآلات.
لنفرض أن لدينا آلة تورينج بسيطة تتكون من الحالات التالية:
- الحالة Q0: حالة البداية.
- الحالة Q1: حالة تغيير رمز الخلية.
- الحالة Q2: حالة التوقف (الحالة النهائية).
الشريط الأولي قد يحتوي على سلسلة من الرموز، على سبيل المثال: “10101”. هدفنا هو تغيير أول “1” إلى “X”.
جدول الانتقال لهذه الآلة سيكون كالتالي:
- من Q0، إذا كان الرأس يقرأ “1”، انتقل إلى Q1، اكتب “X”، وتحرك إلى اليمين.
- من Q1، إذا كان الرأس يقرأ أي رمز (سواء “0” أو “1”)، ابق في Q1، لا تغير الرمز، وتحرك إلى اليمين.
- من Q1، إذا كان الرأس يقرأ رمز الفراغ (B)، انتقل إلى Q2، لا تغير الرمز، وتوقف.
باختصار، تبدأ الآلة في Q0، تقرأ أول “1”، وتغيره إلى “X”، ثم تنتقل إلى Q1. في Q1، تتحرك الآلة عبر الشريط، دون تغيير أي رموز، حتى تصل إلى نهاية الشريط.
المثال الثاني: جمع رقمين أحاديين
هذا المثال يوضح كيف يمكن لآلة تورينج إجراء عملية جمع بسيطة. في هذا المثال، سنستخدم الترميز الأحادي لتمثيل الأعداد، حيث يمثل عدد علامات “1” الرقم. على سبيل المثال، “111” يمثل الرقم 3.
لتنفيذ عملية الجمع، سنحتاج إلى آلة تورينج قادرة على:
- قراءة رقمين مفصولين بعلامة (على سبيل المثال، “+”).
- تحويل العلامة “+” إلى “1”.
- تحريك كل “1” إلى اليسار لتمثيل مجموع الرقمين.
الشريط الأولي: “11+111”
الخطوات:
- تقرأ الآلة “1” وتتحرك إلى اليمين.
- تتحرك الآلة إلى اليمين حتى تجد “+”.
- تغير “+” إلى “1”.
- تتحرك إلى أقصى اليسار.
- تتحرك إلى اليمين، وتجمع “1”s.
النتيجة النهائية: “11111” (الرقم 5).
جدول الانتقال سيكون أكثر تعقيدًا بعض الشيء، ولكنه يتبع نفس المبدأ الأساسي للتحكم في الرأس وقراءة وكتابة الرموز على الشريط.
المثال الثالث: نسخ سلسلة من الرموز
في هذا المثال، سنعرض آلة تورينج قادرة على نسخ سلسلة من الرموز. هذا مثال مفيد لفهم كيفية التعامل مع البيانات وتكرارها.
الهدف: إذا كان لدينا على الشريط السلسلة “ABC”، نريد أن نحصل على “ABCABC”.
الخطوات:
- تبدأ الآلة بقراءة الرمز الأول (A)، وتسجيله في الذاكرة الداخلية.
- تتحرك الآلة إلى أقصى اليمين حتى تجد رمز الفراغ.
- تكتب A في موقع الفراغ.
- تكرر الخطوات السابقة لـ B و C.
- تعود إلى بداية السلسلة الأصلية.
هذه العملية تتطلب حالات متعددة لتتبع الرموز التي يجب نسخها والتحكم في اتجاه حركة الرأس.
المثال الرابع: التحقق من توازن الأقواس
آلة تورينج يمكنها أيضًا فحص ما إذا كانت سلسلة من الأقواس (مثل “{[()]}”) متوازنة. هذا مثال ممتاز على استخدام الذاكرة الداخلية للآلة لتتبع الحالة.
الخطوات:
- عند قراءة قوس مفتوح (مثل “(“)، تقوم الآلة بتخزينه في الذاكرة (أو علامة مؤقتة على الشريط).
- عند قراءة قوس مغلق (مثل “)”)، تقارن الآلة هذا القوس بالقوس المخزن في الذاكرة.
- إذا كانا متطابقين، تحذف الآلة القوس المخزن.
- إذا لم يكن هناك قوس مخزن أو كان القوسان غير متطابقين، يتم رفض السلسلة.
- تكرر العملية حتى يتم فحص جميع الأقواس. إذا انتهى الشريط وكانت الذاكرة فارغة، فإن السلسلة متوازنة.
هذا المثال يوضح كيف يمكن لآلة تورينج التعامل مع هياكل البيانات المعقدة.
المثال الخامس: إجراء عملية حسابية معقدة (ضرب)
على الرغم من أن آلة تورينج بسيطة من حيث المبدأ، إلا أنها قادرة على إجراء عمليات حسابية معقدة مثل الضرب. هذا المثال يوضح الإمكانات الحسابية الكاملة لآلات تورينج.
الترميز: سنستخدم الترميز الأحادي، حيث يمثل عدد علامات “1” الأعداد.
الخطوات:
- لنفرض أننا نريد ضرب 2 × 3 (11 * 111).
- تبدأ الآلة بتكرار العدد الأول (2) بعدد مرات يساوي العدد الثاني (3).
- كلما يتم تكرار “11”، يتم تحريك الرأس إلى اليمين وكتابة “1” في نهاية الشريط.
- بعد الانتهاء من التكرار، يجب على الآلة تنظيف الشريط وإظهار النتيجة (111111).
هذه العملية تتطلب العديد من الحالات والتحركات للتحكم في الرأس وتتبع التقدم.
المثال السادس: مقارنة عددين
يمكن لآلة تورينج أيضًا أن تقارن بين عددين لتحديد أيهما أكبر.
الخطوات:
- الخطوة 1: قراءة العددين (العدد الأول والعدد الثاني) مفصولين بعلامة مثل “*”.
- الخطوة 2: تقوم الآلة بحذف “1” من كلا العددين بالتناوب حتى يتبقى “1” واحد فقط في أحد العددين أو يختفي أحدهما.
- الخطوة 3: إذا تبقى “1” في العدد الأول، فإن العدد الأول أكبر. إذا تبقى “1” في العدد الثاني، فإن العدد الثاني أكبر. إذا لم يتبق “1” في أي من العددين، فالعددان متساويان.
هذه العملية تتطلب تتبع دقيق لمواقع “1” وحذفها.
المثال السابع: تمييز اللغات الرسمية
آلات تورينج قادرة على التعرف على اللغات الرسمية. يمكن لآلة تورينج أن تحدد ما إذا كانت سلسلة معينة تنتمي إلى لغة رسمية معينة أم لا.
مثال: لنفترض أن لدينا لغة تتكون من سلاسل “a^n b^n” (أي عدد “a” متبوعًا بنفس عدد “b”).
الخطوات:
- تقرأ الآلة “a” وتحوله إلى رمز مختلف (مثل “X”).
- تتحرك الآلة إلى اليمين للعثور على “b” وتقوم بتحويلها إلى رمز مختلف (مثل “Y”).
- تكرر هذه العملية حتى يتم تحويل جميع “a”s و”b”s.
- إذا انتهى الشريط ولم تتبق أي رموز “a” أو “b”، فإن السلسلة تنتمي إلى اللغة.
المثال الثامن: محاكاة آلات تورينج أخرى
إحدى الخصائص الأكثر إثارة للاهتمام لآلات تورينج هي قدرتها على محاكاة آلات تورينج الأخرى. هذا يعني أنه يمكن لآلة تورينج واحدة أن تقوم بعمل أي شيء يمكن لآلة تورينج أخرى القيام به.
الخطوات:
- يجب على الآلة أن تقرأ وصف آلة تورينج الأخرى (أي جدول الانتقال الخاص بها).
- يجب أن تحاكي الآلة سلوك الآلة الأخرى، بما في ذلك قراءة وكتابة الرموز، وحركة الرأس، وتغيير الحالات.
هذه القدرة على المحاكاة تجعل آلات تورينج نموذجًا حاسوبيًا عالميًا.
المثال التاسع: آلة تورينج متعددة الأشرطة
على الرغم من أن آلات تورينج الأساسية تستخدم شريطًا واحدًا، إلا أنه يمكننا أيضًا تصور آلات تورينج متعددة الأشرطة. هذا يعني أن الآلة تحتوي على عدة أشرطة يمكنها القراءة والكتابة عليها بشكل مستقل.
الخصائص:
- كل شريط له رأس خاص به.
- يمكن للآلة أن تقرأ وتكتب على أشرطة متعددة في وقت واحد.
- آلة تورينج متعددة الأشرطة أكثر سهولة في البرمجة من آلة تورينج ذات الشريط الواحد، ولكنها لا تتمتع بقوة حوسبة أكبر.
يمكن محاكاة آلة تورينج متعددة الأشرطة باستخدام آلة تورينج ذات شريط واحد.
المثال العاشر: آلة تورينج غير حتمية
آلة تورينج غير الحتمية تسمح للآلة بالقيام بعدة انتقالات محتملة من حالة معينة. هذا يعني أنه يمكن للآلة أن “تخمن” أو “تجرب” مسارات مختلفة.
الخصائص:
- في كل خطوة، يمكن للآلة أن تختار من بين عدة انتقالات ممكنة.
- إذا كان هناك مسار يؤدي إلى حالة قبول، فإن الآلة تقبل الإدخال.
- آلة تورينج غير الحتمية لا تملك قوة حوسبة أكبر من آلة تورينج الحتمية، ولكنها قد تكون أسهل في التصميم لبعض المشاكل.
خاتمة
كما رأينا، آلة تورينج هي نموذج حاسوبي قوي ومرن. هذه الأمثلة تقدم لمحة عن قدراتها المتنوعة، من العمليات الحسابية البسيطة إلى معالجة اللغات. على الرغم من بساطة تصميمها، إلا أن آلة تورينج قادرة على محاكاة أي عملية حوسبة يمكن تصورها. إن فهم هذه الأمثلة يمنحنا رؤية أعمق في أسس علوم الحاسوب ونظرية الحوسبة.