أمثلة على آلة تورينج

فيما يلي أمثلة لتكملة مقال آلة تورينج .

الجدول التالي هو أول مثال قدمه تورينج (تورينج 1937):

"1. يمكن بناء آلة لحساب التسلسل 0 1 0 1 0 1..." (0 <فراغ> 1 <فراغ> 0...) ^{[ 1 ]}

فيما يتعلق بالأفعال التي تقوم بها الآلة فعلياً، يذكر تورينج (1936) ^{[ 2 ]} ما يلي:

"يُفهم من هذا الجدول [المثال] (وجميع الجداول اللاحقة من نفس النوع) أنه بالنسبة للتكوين الموصوف في العمودين الأولين، يتم تنفيذ العمليات في العمود الثالث بالتتابع، ثم تنتقل الآلة إلى التكوين m في العمود الأخير." ^{[ 2 ]}

يوضح ذلك جليًا عندما يختزل الجدول أعلاه إلى تعليمة واحدة تُسمى "b"، ^{[ 3 ]} ، مع أن تعليمته تتكون من 3 أسطر. للتعليمة "b" ثلاثة احتمالات رمزية مختلفة {لا شيء، 0، 1}. يتبع كل احتمال سلسلة من الإجراءات حتى نصل إلى العمود الأيمن، حيث يكون التكوين النهائي هو "b".

كما لاحظ عدد من المعلقين بما في ذلك تورينج (1937) نفسه، (على سبيل المثال، بوست (1936)، بوست (1947)، كلين (1952)، وانغ (1954)) فإن تعليمات تورينج ليست ذرية - يمكن إجراء المزيد من التبسيطات على النموذج دون تقليل قوته الحسابية؛ انظر المزيد في آلة بوست-تورينج .

كما ورد في مقال آلة تورينج ، اقترح تورينج تجزئة طاولته بشكل أكبر من خلال السماح بعملية طباعة/مسح واحدة فقط متبوعة بحركة شريط واحدة لليسار/اليمين/اليسار. ويقدم لنا هذا المثال لأول طاولة صغيرة تم تحويلها: ^{[ 4 ]}

لا يزال بيان تورينج يشير إلى خمس عمليات ذرية. عند تعليمة معينة (تكوين m)، فإن الآلة:

1. يلاحظ رمز الشريط أسفل الرأس
2. بناءً على الرمز المرصود، يتم الانتقال إلى تسلسل التعليمات المناسب للاستخدام
3. يطبع الرمز S _j أو يمسحه أو لا يفعل شيئًا
4. يحرك الشريط إلى اليسار أو اليمين أو لا يحركه على الإطلاق
5. ينتقل إلى التكوين النهائي m لهذا الرمز

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

(q _i ) اختبار رمز الشريط أسفل الرأس: إذا كان الرمز S ₀ انتقل إلى q _i .01، وإذا كان الرمز S ₁ انتقل إلى q _i .11، وإذا كان الرمز S ₂ انتقل إلى q _i .21، إلخ.

(q _i .01) اطبع الرمز S _j 0 أو امسح أو لا تفعل شيئًا، ثم انتقل إلى q _i .02

(q _i .02) حرك الشريط يسارًا أو يمينًا أو لا تحركه على الإطلاق، ثم انتقل إلى qm0

(س _1.11 ) اطبع الرمز S _j 1 أو امسحه أو لا تفعل شيئًا، ثم انتقل إلى س _1.12

(س _1.12 ) حرك الشريط يسارًا أو يمينًا أو لا تحركه على الإطلاق، ثم انتقل إلى س1

(س _1.21 ) اطبع الرمز S _j 2 أو امسح أو لا تفعل شيئًا، ثم انتقل إلى س _1.22

(س _1.22 ) حرك الشريط يسارًا أو يمينًا أو لا تحركه على الإطلاق، ثم انتقل إلى س2

(إلخ - يجب احتساب جميع الرموز)

تقوم ما يسمى بآلات الحالة المحدودة "النموذجية" بإجراء اختبارات الرموز "بالتوازي"؛ انظر المزيد في البرمجة المصغرة .

في المثال التالي لما تقوم به الآلة، سنشير إلى بعض خصائص نماذج تورينج:

إن عادة كتابة الأرقام على مربعات متبادلة فقط مفيدة للغاية: سأستخدمها دائماً. ^{[ 2 ]}

لذا، عند الطباعة، يتخطى مربعًا واحدًا من كل مربعين. تُسمى المربعات المطبوعة مربعات F؛ أما المربعات الفارغة بينها فتُستخدم كعلامات وتُسمى مربعات E، أي قابلة للمسح. مربعات F بدورها هي مربعات الأرقام، ولا تحمل إلا الرمزين 1 أو 0، وهما رمزان أطلق عليهما اسم "الأرقام" (كما في "الأعداد الثنائية").

في هذا المثال، يبدأ الشريط فارغًا، ثم تُطبع عليه الأرقام. وللاختصار، تُعرض هنا فقط بنود الجدول.

يتم عرض نفس "التشغيل" مع جميع عمليات طباعة الشريط الوسيطة والحركات هنا:

إن إلقاء نظرة فاحصة على الجدول يكشف عن بعض المشاكل في مثال تورينج نفسه - لم يتم احتساب جميع الرموز.

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

هذا روتين فرعي مهم للغاية يستخدم في روتين "الضرب".

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

لإنجاز مهمتها، ستحتاج آلة تورينج هذه إلى 5 حالات تشغيل فقط، والتي تسمى {s1 _، s2 _، s3 _، s4 _، s5 _} . كل حالة تقوم بـ 4 إجراءات:

1. اقرأ الرمز الموجود أسفل العنوان
2. اكتب رمز الإخراج الذي تحدده الحالة
3. حرك الشريط إلى اليسار أو إلى اليمين حسب ما تقرره الدولة
4. يتم الانتقال إلى الحالة التالية التي تحددها الحالة الحالية

عملية الطباعة : يطبع الرمز S أو E ، أو يمسح، أو لا يفعل شيئًا.

تشغيل تسلسلات الآلة عبر 16 تكوينًا للآلة (المعروفة أيضًا باسم حالات تورينج):

يمكن وصف سلوك هذه الآلة بأنه حلقة تكرارية: تبدأ من s1 _، وتستبدل أول 1 بـ 0، ثم تستخدم s2 _للتحرك إلى اليمين، متجاوزةً 1 وأول 0 تصادفه. بعد ذلك، تتخطى s3 _{التسلسل} التالي من 1 (لا يوجد تسلسل في البداية) وتستبدل أول 0 تجده بـ 1. تعود _s4 إلى اليسار، متجاوزةً 1 حتى تجد 0 وتنتقل إلى s5 _. ثم تتحرك s5 _إلى اليسار، متجاوزةً 1 حتى تجد 0 الذي كتبته s1 في _الأصل .

يستبدل ذلك الصفر بالواحد، وينتقل موضعًا واحدًا إلى اليمين، ويدخل s ₁ مرة أخرى لجولة أخرى من الحلقة.

يستمر هذا حتى يجد s ₁ الرقم 0 (وهو الرقم 0 الموجود في منتصف سلسلتي الرقم 1) وعندها تتوقف الآلة.

وصف بديل

يصف وصف آخر المشكلة بأنها كيفية تتبع عدد مرات ظهور الرقم "1". لا يمكننا استخدام حالة واحدة لكل عدد ممكن (حالة لكل من 0، 1، 2، 3، 4، 5، 6، إلخ)، لأنه سيتطلب ذلك عددًا لا نهائيًا من الحالات لتمثيل جميع الأعداد الطبيعية، وآلة الحالة محدودة - لذا سيتعين علينا تتبع ذلك باستخدام الشريط بطريقة ما.

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

يكمن السر في أنه قبل نقل الرقم "1"، يتم وضع علامة "مأخوذ" عليه باستبداله بالرقم "0". وعند العودة، يتم ملء الفراغ "0" بالرقم "1"، ثم ينتقل إلى الفراغ التالي ، ويضع علامة "0" عليه، ويكرر العملية، ناقلاً الرقم "1" إلى الفراغ التالي، وهكذا. مع كل عملية نقل ذهابًا وإيابًا، يقترب المؤشر "0" خطوة واحدة من المركز . بهذه الطريقة يتم تتبع عدد الأرقام "1" التي تم نقلها.

عندما يعود، تبدو العلامة "0" بالنسبة له بمثابة نهاية مجموعة "1" - أي "1" تم أخذها بالفعل غير مرئية بالنسبة له (على الجانب الآخر من العلامة "0")، وهكذا يكون الأمر كما لو أنه يعمل على عدد (N-1) من "1" - على غرار البرهان بالاستقراء الرياضي .

تشغيل كامل يوضح نتائج "الحركات" الوسيطة.

استُخلص جدول تعليمات تورينج التالي من بيترسون: ^{[ 5 ]} "يكتب قندس مشغول ثلاثي الحالات 6 آحاد قبل أن يتوقف". يُحرّك بيترسون رأس القراءة/الكتابة؛ وفي النموذج التالي، يتحرك الشريط. الصفر هو الحرف الفارغ: يبدأ الشريط بجميع الخلايا أصفارًا.

يُظهر رسم "الحالة" لآلة القندس المشغولة ذات الحالات الثلاث التسلسلات الداخلية للأحداث اللازمة لتنفيذ "الحالة" فعليًا. وكما ذُكر سابقًا، أوضح تورينج (1937) تمامًا أن هذا هو التفسير الصحيح للخماسيات التي تصف التعليمات. ^{[ 1 ]} لمزيد من المعلومات حول تجزئة خماسيات تورينج، انظر آلة ما بعد تورينج .

يوضح الجدول التالي التشغيل "المضغوط" - حالات تورينج فقط:

الدورة الكاملة لآلة القندس المشغولة ذات الحالات الثلاث. تظهر حالات تورينج الناتجة (ما أسماه تورينج "تكوينات-م" - "تكوينات الآلة") مُظللة باللون الرمادي في العمود أ، وكذلك تحت تعليمات الآلة (الأعمدة من أ إلى أ):