تكوين أمثلة آلات تورينج. القدرة الحسابية الصحيحة للوظائف على آلة Turing
آلة تورينج (MT) عبارة عن منفذ مجردة (آلة حوسبة مجردة).
مجموعات الخوارزميات هي الاسم الذي يطلق على عدد من الطرق المحددة لبناء خوارزميات جديدة من عدة خوارزميات معينة.
تشكل النظريات حول توليفات الخوارزميات جزءًا مهمًا من النظرية العامة للخوارزميات. بعد أن تم إثباتها مرة واحدة ، فإنها تتيح للمرء أن يقتنع في المستقبل بجدوى الخوارزميات المعقدة والمرهقة دون كتابة المخططات التي تحددها فعليًا.
مجموعات الخوارزميات لآلة تورينج موصوفة بالعمليات على آلات تورينج.
1. عملية التكوين.
لنفترض أن M 1 و M 2 هما آلات تورينج لها نفس الأبجدية الخارجية أ «(أ 0 ، أ 1 ، ... ، أ ع). دعونا نشير إلى مجموعات حالاتهم على أنها Q1 «(q 0 ، q 1 ، ... ، q n) و Q2« (q 0 "، q 1" ، ... ، q m ").
تعريف.
تكوين الماكينات M 1 و M 2 عبارة عن آلة ، يُشار إليها بـ M = M 1 × M 2 ، والتي يحتوي برنامجها على الأبجدية A ، مجموعة الحالات Q «(q 0 ، q 1 ، ... ، q n ، q n + 1 ، ... ، q n + m) ويتم الحصول عليها من برامج الآلات M 1 و M 2 على النحو التالي: في كل مكان في برنامج الجهاز الأولي M 1 حيث توجد" 1 أضعاف "الحالة النهائية للرمز" q "، الآلة M 2) ؛ تظل جميع الرموز الأخرى في برامج الآلات M 1 و M 2 دون تغيير (أخيرًا ، يبقى إعادة ترقيم جميع حالات الآلة M: (q 0 ، q 1 "، q 2 ، ... ، q n ، q 0" ، q 2 "، ... ، q m")).
يبدأ التكوين في "العمل" مثل الآلة M 1 ، ولكن في تلك الحالات التي يجب أن تتوقف فيها الآلة M 1 ، يكون هناك تبديل إلى برنامج الآلة M 2 بسبب استبدال q 1 بـ q 0 ". ومن الواضح أن عملية التكوين ترابطية ، ولكنها ليست تبادلية.
تشغيلها يعادل التشغيل المتسلسل للآلات T1 و T2.
يوضح الشكل تكوين آلات تورينج التي تنفذ عامل التراكب لـ n = 1 و m = 1.
الصورة 1.
تعريف.
التكرار لآلة تورينج M هو الآلة
2. تشغيل الفرع.
لنفترض أن M 1 و M 2 و M 3 هي آلات تورينج لها نفس الأبجدية الخارجية A «(a 0 ، a 1 ، ... ، a i ، ... ، a j ، ... ، a p) ومجموعات الحالات على التوالي: Q1« (q 0 ، q 1 ، ... ، q n) ، Q2 «(q 0" ، q 1 "، ... ، q m") ، Q3 "(q 0" ، q "1"
تعريف.
نتيجة عملية التفريع على آلات Turing M 1 و M 2 و M3 هي آلة Turing M ، ويتم الحصول على برنامجها من برامج الآلات M 1 و M 2 و M 3 على النحو التالي: برنامج الآلة M1 مكتوب ، ثم يتم تخصيص برامج الآلة M 2 و M 3. إذا لوحظ الرمز a i في الحالة النهائية q 1 للجهاز M1 ، فسيتم نقل التحكم إلى الجهاز M 2 ، أي يتم استبدال الرمز q 1 بالرمز q 0 "وتبدأ الآلة M 2 في العمل. ومع ذلك ، إذا لوحظ الرمز a j في الحالة النهائية q 1 من الجهاز M 1 ، يتم نقل التحكم إلى الجهاز M 3 ، أي يتم استبدال الرمز q 1 بالرمز q 0" ويبدأ الجهاز M 3 في العمل. تظل جميع الشخصيات الأخرى في برامج الآلات M 1 و M 2 دون تغيير. تنتهي الآلة M في الحالة النهائية q 1 (في الختام ، يبقى إجراء إعادة ترقيم مستمرة لحالات الآلة M).
تتم الإشارة إلى نتيجة عملية التفريع على آلات Turing M 1 و M 2 و M3 على النحو التالي:
بالنسبة لآلات Turing المكونة من حرفين (آلات Turing ذات الأبجدية المكونة من حرفين) ، تتم الإشارة إلى عملية التفريع على آلات Turing التعسفية M1 و M2 و M3 على النحو التالي:
أولئك. إذا لوحظ الرمز 0 أثناء تشغيل الجهاز M1 في الحالة q 1 ، فسيتم نقل التحكم إلى الجهاز M2 ، وإلا ، إلى الجهاز M3.
3. عملية ركوب الدراجات.
دع M هو آلة تورينج مع الأبجدية A «(أ 0 ، أ 1 ، ... ، أ ع) ومجموعة الحالة Q« (ف 0 ، ف 1 ، ... ، ف ن).
تعريف.
ستسمى نتيجة عملية الحلقات آلة تورينج ، ويُشار إليها بـ (i = 0،2،3، ...، n؛ j = 0،1،2، ...، p؛ s = 0،2،3، ...، n)
يتم الحصول على برنامجها من برنامج الجهاز M عن طريق استبدال الأمر q i a j ®q 1 a t r ، rн (L ، R ، L) ، t = 0،1،2 ، ... p ، الرمز q 1 بالرمز q s في e.
2.4 متغيرات آلة تورينج
يسمح نموذج آلة تورينج بالتمديدات. يمكن للمرء أن يفكر في آلات Turing التي تحتوي على عدد عشوائي من الأشرطة والأشرطة متعددة الأبعاد مع قيود مختلفة. ومع ذلك ، فإن كل هذه الآلات كاملة Turing وتم تصميمها بواسطة آلة Turing العادية.
كمثال على هذا التكافؤ ، ضع في اعتبارك اختزال أي MT إلى MT يعمل على شريط شبه لانهائي.
النظرية:لأي آلة تورينج ، هناك آلة تورينج مكافئة تعمل على شريط شبه لانهائي.
دليل:
تأمل في دليل يو جي كاربوف. إن إثبات هذه النظرية بناء ، أي أننا سنقدم خوارزمية يمكن من خلالها ، لأي آلة تورينج ، إنشاء آلة تورينج مكافئة لها خاصية معلنة. أولاً ، نقوم بترقيم خلايا شريط العمل MT بشكل تعسفي ، أي نحدد الموقع الجديد للمعلومات على الشريط:
الصورة 1.
ثم نعيد ترقيم الخلايا ، وسنفترض أن الرمز "*" غير موجود في قاموس الترجمة الآلية:
الصورة 1.
2.5 تورنج الحوسبة والقدرة على اتخاذ القرار
لقد ثبت أعلاه أن فئات الوظائف القابلة للحساب باستخدام الوظائف العودية ، أو آلات تورينج ، أو خوارزميات ماركوف العادية تتطابق. هذا يسمح لنا بالنظر في مفهوم "الخوارزمية الحسابية" غير متغير لطريقة الوصف. يتم ملاحظة الاختلافات فقط في استخدام الكائنات الخوارزمية. إذا كانت الكائنات للوظائف العودية عبارة عن أرقام ووظائف عددية ، ويتم تحديد عملية الحساب بواسطة مشغلي التراكب والتكرار والتقليل والتكرار ، فإن هذه الكائنات بالنسبة لآلات تورينج هي رموز الأبجدية للذاكرة الخارجية والداخلية ، ويتم تحديد عملية الحساب بواسطة البروتوكول باستخدام وظائف الخروج والانتقال وحركة الرأس. بالنسبة لخوارزمية Markov العادية ، تكون هذه الكائنات عبارة عن كلمات أو تسلسلات أحرف ، ويتم تحديد عملية الحساب بقواعد أو منتجات بديلة تغير تكوين وهيكل تسلسل الأحرف الأصلي إلى النتيجة المرجوة.
الوظيفة الحسابية (العددية) هي دالة يكون نطاقها مجموعة فرعية من المجموعة N ، ومجالها عنصر من عناصر المجموعة N.
بالنسبة للمشكلات الحسابية ، يكون الموقف المعتاد عندما تحتاج إلى إيجاد خوارزمية لحساب دالة عددية f (x 1، x 2،…، x n) اعتمادًا على القيم الصحيحة للوسيطات x 1، x 2،…، x n.
الوظيفة f: N n → N تسمى قابلة للحساب إذا كانت هناك خوارزمية تسمح لأي مجموعة من قيم الوسائط الخاصة بها لحساب قيمة الوظيفة (أو تشير إلى أن الوظيفة غير محددة في هذه المجموعة). نظرًا لأن تعريف الوظيفة القابلة للحساب يستخدم المفهوم البديهي للخوارزمية ، فإن مصطلح "وظيفة قابلة للحساب بشكل حدسي" غالبًا ما يستخدم بدلاً من مصطلح "وظيفة قابلة للحساب". وبالتالي ، فإن مشكلة الكتلة لها حل إذا كانت الوظيفة الحسابية المقابلة لهذه المشكلة قابلة للحساب بشكل حدسي.
تسمى الدالة f (x 1، x 2، ...، x n) قابلة للحساب بشكل فعال إذا كان للقيم المعطاة k 1، k 2،…، k n للوسيطات ، يمكنك العثور على قيمة الوظيفة f (k 1، k 2،…، k n) باستخدام بعض الإجراءات الميكانيكية الموجودة (الخوارزمية).
بدلاً من توضيح مفهوم الخوارزمية ، يمكن للمرء أن يفكر في تنقيح مفهوم "الوظيفة الحسابية". عادة ، يتصرفون بالطريقة التالية:
1. يتم تقديم فئة محددة بدقة من الوظائف.
2. تأكد من أن جميع الوظائف من هذه الفئة قابلة للحساب.
3. قبول الفرضية (الأطروحة) القائلة بأن فئة الوظائف الحسابية تتطابق مع فئة الوظائف المقدمة.
تسمى الوظيفة القابلة للحساب إذا كانت هناك خوارزمية تحسبها. "الحوسبة" هي أحد المفاهيم الأساسية لنظرية الخوارزميات ، وهي ثابتة على الوظيفة المحسوبة والخوارزمية. الفرق بين الوظيفة القابلة للحساب والخوارزمية هو الفرق بين وصف الوظيفة والطريقة التي يتم بها حساب قيمها في ضوء قيم الوسيطات المستقلة.
أطروحة تورينج. يمكن تنفيذ أي خوارزمية بديهية باستخدام بعض آلات تورينج.
يترتب على أطروحة تورينج أنه إذا ظهرت مشكلات خوارزمية ، فيجب حلها على أساس بناء آلات تورينج ، أي أن المفهوم الرسمي للخوارزمية كافٍ. علاوة على ذلك ، في مشاكل الخوارزمية ، لا يتعلق الأمر في الغالب ببناء خوارزمية ، ولكن حول قابلية حساب بعض الوظائف التي تم إنشاؤها بطريقة خاصة.
وتجدر الإشارة إلى أنه في هذه الحالات يكفي استخدام الأبجدية (0 ، |) ، حيث يكون 0 حرفًا فارغًا. على سبيل المثال ، يتم ترميز الأرقام الطبيعية ، بما في ذلك 0 ، في هذه الأبجدية على النحو التالي: 0 - |؛ 1 - || ؛ 2-
ن - ||… | (ن + 1 مرات). تسمى الوظيفة الجزئية الرقمية n المحلية f (x1، x2، ...، xn) Turing computable إذا كان هناك آلة M تحسبها بالمعنى التالي: 1. إذا كانت مجموعة قيم الوسيطة
مشكلة التطبيق الذاتي
وفقًا لتعريف آلة تورينج ، هذا هو الثلاثي تي =
ف: تشيأ ajأ ® ف صأ مثلأ شارعأ ، أ = 1 ، 2 ، ... ، ك ، أين S1-R ، S2-ل, S3- ج . (*)
في هذه الحالة ، يمكننا أن نفترض أن هناك بعض الأبجديات الشائعة أ 0و س 0، حيث يتم كتابة الأحرف أ و ف لجميع آلات تورينج. ثم الرموز تشيأ, ajأ ، ف صأ, مثلأ, شارعأهي رموز الحروف الهجائية أ 0و س 0.
يتيح هذا الأسلوب ترقيم جميع آلات Turing ، أي تخصيص رقم (رمز) معين لكل جهاز فريد من نوعه لهذا الجهاز ، والذي يمكن من خلاله تمييزه عن الأجهزة الأخرى. هنا ننظر في إحدى طرق الترقيم.
ترقيم جوديل لآلات تورينج. يترك p1، p2، p3 ، ... - سلسلة من الأعداد الأولية مرتبة بترتيب تصاعدي ، على سبيل المثال ، 2 ، 3 ، 5 ، 7 ، 11 ، 13 ، ...
رقم آلة تورينج مع البرنامج (*)يسمى رقم
ن (T) = .
مثال
آلة تنفذ وظيفة س(x)= س + 1 ، لديه برنامج في الأبجدية {0, } . عدد هذا البرنامج مع مراعاة حقيقة أن أ 0 = 0 , أ 1= | سيكون الرقم:
ن (T) = 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3.
من الواضح ، ليست كل الأعداد الطبيعية هي أرقام لآلات تورينج. من ناحية أخرى ، إذا ن هو رقم بعض الآلات ، في الأبجديات العامة ، ثم يمكن استعادة برنامجها بشكل فريد من هذا الرقم.
سيارة تيتنطبق على الكلمة ن(ت)(أي إلى رمز رقمك الخاص) ، يسمى ذاتي التطبيق .
من الممكن بناء آلات قابلة للتطبيق ذاتيًا وآلات غير قابلة للتطبيق ذاتيًا. على سبيل المثال ، الآلة من المثال المعطى قابلة للتطبيق ذاتيًا. سيارة تي، التي لا تحتوي على حرف فاصل في الأجزاء الصحيحة من البرنامج (في نص الجدول) ، لا تنطبق على أي كلمة ، وبالتالي على الكلمة ن(ت).
مشكلة التطبيق الذاتييتكون مما يلي: للإشارة إلى خوارزمية ستحدد ، في ضوء أي آلة تورينج ، ما إذا كانت قابلة للتطبيق ذاتيًا أم لا.
وفقًا لأطروحة تورينج ، يجب البحث عن مثل هذه الخوارزمية في شكل آلة تورينج. يجب أن تكون هذه الآلة قابلة للتطبيق على رموز الأرقام لجميع آلات Turing ، واعتمادًا على نتيجة معالجة أكواد الآلات المختبرة ، سيكون لها تكوينات نهائية مختلفة.
دعونا ، على سبيل المثال ، هذه السيارة تيمطبق على الكود ن(ت * ) . إذا كان الجهاز تي * قابل للتطبيق ذاتيًا ، ثم التكوين النهائي للجهاز تيلديه الشكل أ" q0 | ب"، وإذا كان الجهاز تي * ليس ذاتي التطبيق ، ثم التكوين النهائي للجهاز تيلديه الشكل أ" q0 0 ب ". هنا أ "، ب" ، أ "، ب"- كلمات.
نظريةمشكلة التطبيق الذاتي غير قابلة للحل من الناحية الحسابية ، أي أنه لا توجد آلة تورينج تحل هذه المشكلة بالمعنى أعلاه.
ويترتب على النظرية أنه لا توجد خوارزمية عامة لحل مشكلة التطبيق الذاتي. في حالات معينة محددة ، قد توجد مثل هذه الخوارزميات.
دعونا نستخدم نتائج هذه النظرية لإثبات عدم القدرة على تقرير مشكلة قابلية التطبيق على الكلمة الأولية.
مشكلة قابلية التطبيق على الكلمة الأولى يتكون مما يلي: إنشاء خوارزمية بواسطة الجهاز تيوكلمة X سوف تقوم بتثبيت الجهاز القابل للتطبيق تيبالمناسبة X أم لا (خلاف ذلك مشكلة توقف).
فيما يتعلق بآلات تورينج ، على غرار صياغة مشكلة التطبيق الذاتي ، تتم صياغة هذه المشكلة على النحو التالي: هل من الممكن بناء آلة تكون قابلة للتطبيق على جميع كلمات النموذج ن(T) 0 X ، أين تيآلة عشوائية X هي كلمة تعسفية ، وإذا كان الجهاز تيتنطبق على الكلمة X أ" q0 | ب " , وإذا كانت السيارة تيلا ينطبق على الكلمة X ، من شأنه أن يؤدي إلى التكوين النهائي أ" q0 0 ب " . هنا أ "، ب"و أ "، ب"- كلمات تعسفية.
نظريةمشكلة قابلية التطبيق على الكلمة الأولية غير قابلة للحل حسابيًا ، أي أنه لا توجد آلة تورينج تحل هذه المشكلة بالمعنى أعلاه.
كما هو مذكور أعلاه بالنسبة لمشكلة التطبيق الذاتي ، فإن الخطوة الأولية الأولى هي الترقيم. لذلك ، أدناه يتم النظر في هذه المشكلة وحلها باستمرار للخوارزميات وأنواعها الرئيسية الثلاثة من النماذج الخوارزمية.
ترقيم الخوارزمية
يلعب ترقيم الخوارزميات دورًا مهمًا في دراستها وتحليلها. نظرًا لأنه يمكن تحديد أي خوارزمية على أنها كلمة محدودة (يتم تمثيلها كتسلسل محدود من الرموز لبعض الأبجدية) ، وأن مجموعة جميع الكلمات المحددة في الأبجدية المحددة قابلة للعد ، فإن مجموعة جميع الخوارزميات تكون أيضًا قابلة للعد. وهذا يعني وجود تعيين واحد لواحد بين مجموعة الأعداد الطبيعية ومجموعة الخوارزميات ، أي إمكانية تخصيص رقم لكل خوارزمية.
ترقيم الخوارزميات هو في نفس الوقت ترقيم جميع الوظائف المحسوبة خوارزميًا ، ويمكن أن تحتوي أي وظيفة على عدد لا حصر له من الأرقام.
يجعل وجود الترقيم من الممكن العمل مع الخوارزميات بنفس الطريقة كما هو الحال مع الأرقام. يعد الترقيم مفيدًا بشكل خاص في دراسة الخوارزميات التي تعمل مع خوارزميات أخرى.
يجب أن تكون هناك مشكلة كتلة معينة مع مجموعة من الكائنات الأولية X ومجموعة من الكائنات المطلوبة Y. لوجود حل لمشكلة الكتلة ، من الضروري أن تكون عناصر المجموعتين X و Y كائنات بناءة. لذلك ، يمكن تعداد عناصر هذه المجموعات بالأرقام الطبيعية. اجعل x∈ X كائنًا أوليًا ، قم بالإشارة إليه بواسطة n (x) رقمه. إذا كان مطلوبًا في مشكلة الكتلة الحصول على الكائن المطلوب y∈ Y بالرقم n (y) من الكائن الأولي x ، فإننا نحدد دالة حسابية f: Nn → N بحيث أن f (n (x)) = n (y).
كمثال على بناء وظائف حسابية لمشكلات الكتلة ، ضع في اعتبارك مشاكل الكتلة.
1. إذا تم إعطاء مصفوفة] من الأعداد الطبيعية ، فيمكن ربطها بعدد طبيعي 2x1 ، 3x2 ، ... p (n) xn ، حيث p (n) هي العدد الأولي n. ضع في اعتبارك على سبيل المثال مصفوفة بطول 5:
] 2x13x25x37x411x5.
يحدد هذا الترقيم الدالة الحسابية f (على سبيل المثال ، f (73500) = f (22315372110) = 20315272113 = 4891425).
2. أي رقم منطقي له عدد طبيعي. تعداد مجموعة الأشياء المطلوبة للمشكلة تافه:
("نعم" ، "لا") أ (1 ، 0). بالنسبة لمسألة كتلة معينة ، يمكنك بناء دالة حسابية لحجة واحدة باستخدام الحيلة من المثال السابق ، أو يمكنك التفكير في وظيفة من ثلاث وسيطات (ثلاثة أرقام من العناصر الثلاثية الأصلية).
3. يمكن ترقيم نصوص البرنامج على النحو التالي: يمكن اعتبار أي برنامج كسجل لرقم في نظام الأرقام 256-ary (إذا تم استخدام أحرف جدول ASCII لكتابة البرنامج).
يتيح لنا الانتقال من مشكلة الكتلة إلى وظيفة حسابية تقليل مسألة وجود حل لمشكلة الكتلة إلى مسألة وجود طريقة فعالة لحساب قيم دالة حسابية من حجتها (حجتها).
ترقيم مجموعات الأرقام
في نظرية الخوارزميات ، انتشرت تقنية تجعل من الممكن اختصار دراسة وظائف عدة متغيرات لدراسة وظائف متغير واحد. وهو يعتمد على تعداد مجموعات الأرقام بحيث يكون هناك تطابق حيوي بين مجموعات الأرقام وأرقامها ، والوظائف التي تحدد رقمها من مجموعة من الأرقام ومن عدد مجموعة الأرقام نفسها تكرارية عامة. على سبيل المثال ، بالنسبة للدالة التي تحتوي على متغيرين مستقلين (x ، y) ، قد يبدو هذا التعيين h (x ، y) كما يلي:
الصورة 1.
دع الأزواج (x ، y) تشكل مجموعة مرتبة جزئيًا N (2). إذا كانت h (x ، y) = n ، فهناك مخطط عكسي: x = h -1 1 (n) و y = h -1 2 (n) ، أي h (h -1 1 (n) ، h -1 2 (n)) = n. يتيح لك هذا حساب الرقم n لأي زوج (x ، y) ، وعلى العكس ، حساب قيم x و y من الرقم n:
باستخدام هذه القواعد ، يمكن للمرء حساب ترقيم المضاعفات h 2 (x ، y ، z) = h (h (x ، y) ، z) = n ، وعلى العكس ، من خلال عدد الثلاثي - القيم x ، y ، z. على سبيل المثال ، إذا كانت H 2 (x ، y ، z) = n ، ثم z = h -1 2 (n) ، y = h -1 2 (h -1 1 (n)) ، x = h -1 1 (h -1 1 (n)) ، h 2 (x ، y ، z) = h (h -1 1 (h -1 1 (n) ، h -1 2 (n) ح -1 2 (ن)). تشكل الثلاثيات (x ، y ، z) مجموعة مرتبة جزئيًا N (3). وبالمثل ، بالنسبة لعدد عشوائي من الأرقام لدينا:
h n-1 (x1، x2، ...، xn) = h (h ... h (h (x1، x2)، x3) ... x n-1)، xn). إذا كانت h n-1 (x1 ، x2 ، ... ، xn) = m ، إذن xn = h -1 2 (m) ، x n-1 = h -1 2 (h -1 1 (m)) ، ......................... ، x2 = h -1 2 (h -1 1 (... h -1 1 (m) ...)) ، x1 = h -1 2 (h (... h (m) ...)).
بوجود ترقيم لمجموعات المجموعات N (1) ، N (2) ، ... ، N (i) ، ... ، N (n ، حيث N (i) هي مجموعة مجموعات الأرقام (i) ، يمكننا إنشاء ترقيم مجمّع لمجموعات عشوائية من الأرقام M = N (1) N (2) ... N (i) .. N (n) ، حيث M بالنسبة لأي n N لدينا h (x1 ، n) x2 ، h (x1 ،). ) ، ن − 1).
إذا كانت h (x، 1x، 2 ...، x) n = m، إذن h n − 1 (x، 1x، 2 ...، x) n = h -1 1 (m)، n = h -1 2 (m) +1. باستخدام الصيغ أعلاه ، يمكنك استرداد قيم x1 ، x2 ، ... ، xn.
معلومات مماثلة.
التعريف والتشغيل وطرق تعريف آلة تورينج
تُفهم آلة تورينج على أنها آلة افتراضية (مجردة) تتكون من الأجزاء التالية (الشكل 3.1.)
1) شريط لا نهاية له في كلا الاتجاهين ، مقسم إلى خلايا ، كل منها يمكن أن يحتوي على حرف واحد فقط من الأبجدية ، بالإضافة إلى حرف فارغ l ؛
2) جهاز التحكم (رأس العمل) ، والذي يمكن أن يكون في أي وقت في إحدى الحالات من المجموعة. في كل حالة ، يتم وضع الرأس مقابل الخلية ويمكنه قراءة (عرض) أو كتابة حرف من الأبجدية فيه أ.
أرز. 3.1. آلة تورينج
يتكون عمل MT من سلسلة من الخطوات الأولية (الدورات). تقوم كل خطوة بما يلي:
1. يقرأ رئيس العمل (وجهات النظر) الشخصية ؛
2. اعتمادًا على حالته والرمز الملحوظ ، يولد الرأس رمزًا ويكتبه على الخلية المرصودة (ربما =) ؛
3. يتحرك الرأس خلية واحدة إلى اليمين (ص)، غادر (ل)أو البقاء (هـ);
4. يدخل الرئيس حالة داخلية مختلفة. (ربما =).
تسمى الحالة الأولية ، - النهائية. عند دخول الحالة النهائية ، تتوقف الآلة.
تسمى الحالة الكاملة لمنصة الترجمة إعدادات . هذا هو توزيع الحروف في خلايا الشريط وحالة رأس العمل والخلية المراقبة. التكوين في لباقة رتتم كتابتها على النحو التالي: ، حيث توجد الكلمة الفرعية على يسار الخلية المراقبة ، وهي الحرف الموجود في الخلية المراقبة ، وهي الكلمة الفرعية إلى اليمين.
التكوين الأولي والنهائي يسمى قياسي.
هناك 3 طرق لوصف تشغيل MT:
عرض نظام القيادة
جدول الوظائف
رسم بياني (رسم بياني) للتحولات.
دعونا ننظر إليهم بأمثلة.
مثال 1أنشئ MT الذي ينفذ سلسلة من كلمتين في الأبجدية. الكلمات الموجودة على الشريط مفصولة بعلامة *. التكوين الأولي قياسي.
نظام أوامر MT له الشكل:
في الحالة ، يتحرك الرأس إلى اليمين إلى حرف فارغ.
يتم محو الحرف الموجود في أقصى اليمين.
يتم مسح علامة النجمة إذا كانت الكلمة الأولى فارغة.
يتم إزاحة الكلمة اليمنى إلى اليسار بمقدار موضع واحد حرفًا بحرف.
التحول إلى التكوين الهدف القياسي.
جدول الوظائف
| أ | ب | * | ل | |
| - | ||||
| - | ||||
| - | ||||
| - |
تعني الشرطات في الجدول أنه لا يمكن مصادفة l في الحالات.
|
|
|||
التكوين النهائي القياسي.
سيتم فهم حساب وظيفة القاموس على MT على النحو التالي. دع الكلمة تكتب على الشريط في التكوين الأولي. إذا تم تحديد القيمة ، فبعد عدد محدود من الخطوات (الدورات) ، يجب أن تنتقل الآلة إلى التكوين النهائي ، حيث يتم كتابة الكلمة على الشريط. خلاف ذلك ، يجب أن يعمل MT إلى أجل غير مسمى.
باستخدام MT ، يمكنك وصف أداء العمليات الحسابية على الأرقام. في هذه الحالة ، يتم تقديم الأرقام على الشريط ككلمات في أبجدية تتكون من أرقام لبعض نظام الأرقام ، ومفصولة بعلامة خاصة غير مدرجة في هذه الأبجدية ، على سبيل المثال ، *. النظام الأكثر استخدامًا هو النظام الأحادي ، ويتألف من حرف واحد -1. الرقم X على الشريط مكتوب بالكلمة (أو مختصر) في الأبجدية أ = (1).
تكون الوظيفة العددية قابلة للحساب بشكل صحيح (أو قابلة للحساب ببساطة) بمعنى تورينج إذا كان هناك MT يأخذ التكوين إلى التكوين عندما = ذ، أو يعمل إلى أجل غير مسمى عند عدم تحديده.
مثال 2عملية إضافة رقمين في رمز أحادي.
الترتيب الأولي:
التكوين النهائي: أي تتلخص الإضافة في الواقع في تحديد رقم بإلى الرقم أ. للقيام بذلك ، يتم مسح 1 الأول واستبداله بـ 1.
نقدم وصفًا لـ MT في شكل جدول وظيفي:
| * | ل | ||
| - | |||
| - | |||
| - |
يمكن عمليا استخدام الطرق المذكورة أعلاه لوصف الترجمة الآلية للخوارزميات البسيطة فقط ، منذ ذلك الحين للأوصاف المعقدة تصبح مرهقة للغاية. وبالمثل ، فإن وصف الوظائف العودية بأبسط وظائف وعوامل التراكب والتكرار البدائي والتقليل سيكون أمرًا مرهقًا للغاية. لذلك ، يتم إثبات التكرار البدائي أو الجزئي لوظيفة ما باستخدام وظائف أخرى تم بالفعل إثبات تكرارها البدائي أو الجزئي.
وبالمثل ، يمكن بناء آلات تورينج للخوارزميات المعقدة باستخدام MTs الموجودة. يسمى هذا البناء بتكوين MT.
دعونا نصف 4 طرق رئيسية لتكوين MT:
التكوين المتسلسل (التراكب) ؛
تكوين مواز
المتفرعة
تكوين متسق الماكينات والتي تحسب وظائف القاموس وفي الأبجدية أ، آلة تي، والتي تحسب الوظيفة. يتم وصف التكوين المتسلسل على النحو التالي:
ويشار إليه.
عادةً ما يتم استخدام التركيب المتسلسل لوصف الأقسام الخطية للخوارزميات.
إثبات النظرية في إمكانية بناء آلة تي، وهو تكوين متسلسل لآلتين تعسفيتين ويتم تنفيذه عن طريق تحديد الحالة النهائية بالحالة الأولية.
مثال 3أنشئ خوارزمية مضاعفة 2 * X في رمز أحادي باستخدام آلة نسخ تترجم الكلمة a إلى الكلمة a * a وآلة إضافة. يبدو MT المرغوب فيه كما يلي:
| | | |
|||||||||||||
| | |
||||||||||||||
تكوين مواز الآلات والتي تحسب وظائف القاموس والحروف الهجائية أو فيعلى التوالي ، اسم الجهاز تي، والتي تحسب وظيفة القاموس. هنا تُستخدم العلامة لفصل الكلمات في تركيبة MT المتوازية.
| |
ويتم وضع علامة:.
في الواقع ، يتلقى التكوين المتوازي من اثنين من MTs كمدخل كلمة تتكون من كلمتين بأبجديات مختلفة ويخرج كلمة تتكون من كلمتين ، أي يتكون من جهازين يعملان بشكل متزامن ومستقل.
لتنفيذ تركيبة متوازية ، يتم استخدام آلة بشريط مزدوج. ترجع الحاجة إلى ذلك إلى حقيقة أن الحساب ويحدث بالتتابع في الوقت المناسب ، والمحسوب ، على سبيل المثال ، أولاً ، قد يتطلب مساحة أكبر من a ، ويفسد كلمة b. تعمل آلة الشريط ذات الطابقين على النحو التالي: تتم إعادة كتابة الكلمة b في الطابق الثاني ومسحها في الطابق الأول ، ويتم حسابها في الطابق الأول ، ويتم حسابها في الطابق الثاني ، ثم إعادة كتابتها إلى الطابق الأول ، ربما باستخدام وردية.
لتنفيذ التكوين المتوازي نالآلات المستخدمة ن-شريط أرضي.
فريق الترجمة الآلية بشريط من طابقين مكتوب على النحو التالي: أين الحروف المكتوبة في الطابقين الأول والثاني على التوالي.
مثال 4. تنفيذ التركيب المتوازي للآلات ووظائف الحوسبة في النظام الثنائي و أ + بفي النظام الأحادي.
كلمة الإدخال لها الشكل:.
دعونا نصف تشغيل MT بواسطة نظام من الأوامر:
الحركة لليمين لكلمة ب
إعادة كتابة كلمة ب بالدور الثاني
تحرك لليسار لكلمة أ
إضافة 1 إلى X.
الحركة لليمين لكلمة ب.
التعداد ب إلى الطابق الأول مع الجمع المتزامن للأرقام أو ب.T على التوالي. تمت إضافة أوامر في الأقواس المتعرجة إلى نظام الأوامر
الحالة النهائية لمنصة ماجنت بأكملها.
تجدر الإشارة إلى أنه في جميع الحالات في بداية الخوارزمية ، من الضروري إدخال فحص للبيانات الأولية للقيم الخاصة (في أغلب الأحيان لـ 0) ، يمكن أن يؤدي عدم الامتثال لهذا المطلب إلى حلقة.
يمكن استخدام تركيبة الترجمة الآلية لبناء خوارزميات معقدة. السؤال الذي يطرح نفسه: هل يمكن تنفيذ أي خوارزمية كتكوين من الترجمة الآلية؟ الجواب على هذا السؤال هو أطروحة تورينج ، التناظرية لأطروحة تشرش: يمكن تنفيذ أي خوارزمية باستخدام آلات تورينج والعكس صحيح ، وأي عملية تنفذ بواسطة آلة تورينج هي خوارزمية.
أطروحة تورينج ليست نظرية ، من المستحيل إثباتها ، لأن يحتوي على فكرة غير رسمية " الخوارزمية". ومع ذلك ، فإن الممارسة الرياضية طويلة المدى هي تأكيد موثوق لهذه الأطروحة: لمدة 50 عامًا ، لم يتم العثور على خوارزمية بالمعنى البديهي الذي لا يمكن تنفيذه باستخدام آلات تورينج.
الهدف من العمل:اكتساب المهارات العملية في كتابة الخوارزميات باستخدام تكوين آلات تورينج.
المرجع النظري
يمكن عمليا استخدام الطرق المذكورة أعلاه لوصف الترجمة الآلية للخوارزميات البسيطة ، وإلا يصبح الوصف مرهقًا للغاية. يمكن بناء آلات تورينج للخوارزميات المعقدة باستخدام MTs الأولية الموجودة بالفعل ، ويسمى هذا البناء تكوين MT.
دعونا نصف 4 طرق رئيسية لتكوين MT:
التكوين المتسلسل (التراكب) ؛
تكوين مواز
المتفرعة
1. التكوين المتسلسل لآلات تورينج
تكوين متسقأو تراكبآلات تورينج و 
و 
في الأبجدية أ،دعا السيارة م، والتي تحسب الوظيفة 
.
يتم وصف التكوين المتسلسل على النحو التالي:
والمشار إليها 
أو 
.
2. التركيب المتوازي لآلات تورينج
تكوين مواز
الآلات 
و 
، وظائف قاموس الحوسبة 
و 
بالأبجديات أو في،على التوالي ، اسم الجهاز م، والتي تحسب وظيفة القاموس. وقع هنا 
تستخدم لفصل الكلمات في تكوين الترجمة الآلية المتوازية.
التركيب المتوازي MT 
و 
يصور على النحو التالي:
ويشار إليه: 
.
في الواقع ، يتلقى التركيب المتوازي من اثنين من MTs كمدخل كلمة تتكون من كلمتين بأبجديات مختلفة ، وعند الإخراج ينتج أيضًا كلمة تتكون من كلمتين ، أي يتكون من جهازين يعملان بشكل متزامن ومستقل. لتنفيذ تركيبة متوازية ، يتم استخدام آلة بشريط مزدوج.
تعمل آلة الشريط ذات الطابقين على النحو التالي:
1) كلمة 
أعيد كتابتها في الطابق الثاني من الشريط ومسحها على الأول ،
2) محسوبة 
في الطابق الأول،
3) محسوبة 
في الطابق الثاني
4)
أعيد كتابتها في الطابق الأول ، ربما مع التحول.
تتم كتابة أمر MT بشريط ذي طابقين على النحو التالي:
,
أين 
- حروف مكتوبة على التوالي في الطابقين الأول والثاني. تشير إلى أطوال الكلمة 
، على التوالى، 
.
سوف نوضح تشغيل آلة Turing بشريط ذي طبقتين. بشكل عام ، أطوال الكلمات 
و 
لا تتطابق مع بعضها البعض ، ولكن من أجل بساطة الصورة نفترض أنها متساوية. ثم يتم تنفيذ النقاط 1) -4) على MT بشريط من طابقين على النحو التالي:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
لتنفيذ التكوين المتوازي ن يتم استخدام آلات تورينج ن– شريط أرضي.
3. التفرع أو التفرع الشرطي في تكوين آلات تورينج
نظرا لماكينات تورينج 
و 
، وظائف قاموس الحوسبة 
و 
والجهاز 
، الذي يقيم بعض المسند ص(
)
مع الشفاء (أي بدون محو الكلمة
),
ثم يمكن بناء آلة تورينج لتنفيذ التفريع 
، والتي تحسب الوظيفة:
تم توضيح تفرع آلات تورينج على الرسوم البيانية للتكوين على النحو التالي:
والمشار إليها 
، هنا 
- نتيجة الآلة 
، الذي يأخذ القيم "1" إذا كان المسند ص(
)=
”حقيقي”
و "0" إذا كان المسند ص(
)=
“خطأ شنيع”
,
هي آلة تورينج تقوم بنسخ كلمة الإدخال 
.
4 . دورة في تكوين آلات تورينج
دورةفي التكوين ، يتم تنفيذ الترجمة الآلية وفقًا لنفس مبادئ التفرع.
" الوداع ف (
)=
”حقيقي”
، بكمل 
»,
أين
- كلمة على الشريط قبل التنفيذ الأول 
وبعد الإعدام التالي .
بالنسبة لصورة الدورة ، نقدم بعض الرموز ، دعنا:
هي آلة تورينج التي تنفذ حساب المسند ف (
)
;
–MT التي تنفذ نسخ كلمة الإدخال 
;
–MT ، يتم تنفيذه في دورة وإدراك 
;
–MT ، يتم تنفيذه عند الخروج من الحلقة والإدراك 
.
بعد ذلك ، يمكن وصف التركيب الدوري لآلات تورينج ، أو الدورة ، على النحو التالي:
البرمجة بتركيبات آلات تورينج:
1) إنشاء مخططات كتلة للخوارزميات المعقدة بدرجة من التفصيل بحيث تتوافق كتلها مع MTs الأولية ؛
2) بناء MTs أولية تنفذ الكتل البسيطة ؛
3) الجمع بين MTs الأولية في تكوين MTs.
مثال.إنشاء تركيبة مسرح ماجنت يتم تنفيذها 
.
- آلة تورينج التي تقوم بنسخ كلمة الإدخال ؛
–MT ، والتي تنفذ وظيفة ضبط الثابت على صفر ؛
–MT مسند الحوسبة مع الاسترداد 
;
- MT التي تنفذ وظيفة الاختيار 
- تلك الحجة من 
الحجج
–MT ، والتي تنفذ وظيفة تقليل الحجة 
بمقدار 1 في رمز أحادي (يمسح الحرف الموجود في أقصى اليسار) ؛
- MT الذي يقوم بجمع رقمين في رمز أحادي.
وتجدر الإشارة إلى أنه في أي حال ، في بداية تنفيذ الخوارزمية ، من الضروري التحقق من بيانات الإدخال للتأكد من صحتها (على سبيل المثال ، تساوي الوسيطة إلى 0 عند القسمة).
الشكل 1.6
يستخدم الشكل 1.6 الترميز التالي:
T 1 ، T 2 - آلات تورينج ؛
ST 1 ، ST 2 - أنظمة قيادة للآلات T 1 و T 2 ، على التوالي ؛
x - المعلومات الأولية للجهاز T 1 ؛
T 1 (x) - نتيجة الآلة T 1 ؛
T 2 (T 1 (x)) - نتيجة عمل الجهاز T 2.
ضع في اعتبارك ، على سبيل المثال ، تكوين جهازين ، أولهما يؤدي عملية النسخ ، والثاني - عملية إضافة الأرقام في رمز أحادي. يوضح الشكل 1.7 مخطط الجمع بين الآلات ومثال على شريط مع النتائج التي تم الحصول عليها.
الشكل 1.7
يسمح لك التكوين الموضح في الشكل 1.7 بإجراء عملية مضاعفة الرقم باستخدام آلات النسخ والإضافة المعروفة بالفعل. وبالتالي ، من خلال تجميع خوارزميات لآلات تورينج لحل مجموعة من العمليات (على سبيل المثال ، العمليات الحسابية) ، يمكن للمرء أن يؤلف آلات تورينج لحل المشكلات الأكثر تعقيدًا. في الوقت نفسه ، يتم تقليل تطوير خوارزمية عامة إلى تجميعها من تلك العمليات التي تُعرف بالفعل خوارزميات التنفيذ على جهاز Turing. يشبه هذا النهج استخدام الإجراءات والوظائف في البرمجة.
ومع ذلك ، فإن استخدام تكوين الآلات يفترض أن الخوارزميات لأداء العمليات الأولية معروفة ، والتي تتكون منها الخوارزمية العامة. لذلك ، عند حل المشكلات التعسفية ، لا يستبعد هذا النهج الحاجة إلى تطوير خوارزميات جديدة ، وبالتالي تطوير آلات تورينج بوحدات تحكم مختلفة. من الممكن تنفيذ أي خوارزمية دون تغيير هيكل وحدة التحكم باستخدام آلة Turing العامة.
1.2.2 آلة تورينج العامة
إذا تم تقديم بعض آلات Turing (أي الحروف الأبجدية للإدخال وإشارات الإخراج والحالات والموضع الأولي للرأس والحالة الأولية للجهاز ، بالإضافة إلى جدول تشغيل الجهاز والشريط الذي يحتوي على المعلومات الأولية) ، فمن الممكن إجراء جميع تحويلات المعلومات يدويًا التي تهدف هذه الآلة من أجلها. في الواقع ، في هذه الحالة ، يتم تنفيذ محاكاة آلة تورينج.
عند تحليل العمليات التي يتم إجراؤها في محاكاة آلة تورينج ، يمكن إثبات أن المحاكاة تختزل لتكرار الإجراءات التالية في كل خطوة:
Ä قراءة حرف من خلية الشريط التي يقع فوقها الرأس.
ابحث عن أمر في جدول تشغيل الجهاز. يتم إجراء البحث حسب الحالة الحالية للجهاز وقيمة حرف القراءة.
Ä اختر من الأمر الحرف المراد كتابته على الشريط واكتبه.
اختيار رمز حركة الرأس من الأمر وتحريكه.
Ä تحديد حالة آلة جديدة من الأمر وتغيير الحالة الحالية إلى حالة جديدة. يتبع ذلك الانتقال إلى الخطوة التالية وتكرار هذه الخطوات.
|
|
 |
|||||
 |
|||||
الشكل 1.8
وتتمثل طبيعة هذه العمليات الأولية في أنه يمكن إجراؤها جميعًا بواسطة آلة تورينج أخرى تحاكي تشغيل الآلة الأصلية. يتم شرح جوهر النمذجة في الشكل 1.8.
إذا كان الجهاز T يحتوي على مجموعة تعليمات ST ويقوم بمعالجة شريط بالمعلومات X ، فيمكن محاكاة تشغيله بواسطة جهاز آخر U يحتوي على مجموعة التعليمات الخاصة به SU. من أجل المحاكاة ، عند إدخال الجهاز U ، من الضروري إرسال ليس فقط شريط به معلومات X , ولكن أيضًا نظام القيادة (جدول العمل) ST. يمكن تسجيل نظام الأوامر هذا على نفس الشريط مثل المعلومات الأصلية.
 |
الشكل 1.9
ميزة مهمة لآلة المحاكاة هي أن نظام القيادة الخاص بها SU (وبالتالي هيكل وحدة التحكم) لا يعتمد على خوارزمية الآلة المحاكية T. آلة تورينج التي يمكنها محاكاة تشغيل أي آلة تورينج أخرى تسمى عالمية. يظهر شكل متغير لهيكل آلة تورينج العامة (UMT) في الشكل 1.9.
ينقسم شريط UMT إلى ثلاث مناطق: منطقة البيانات ومنطقة الوضع ومنطقة القيادة.
تحتوي منطقة البيانات على المعلومات الأولية التي ستتم معالجتها بواسطة آلة تورينج المحاكاة. في نفس المنطقة ، يتم تسجيل نتائج عمل UMT.
تحتوي منطقة الوضع على الحالة الحالية Q t ورمز الإدخال الحالي X t الذي تمت قراءته من خلية منطقة البيانات في دورة معينة.
تحتوي منطقة الأوامر على نظام الأوامر الخاص بالجهاز الذي تمت محاكاته. يتم فرز الأوامر في مجموعات. تتضمن المجموعة الأولى أوامر تبدأ بالحرف Q 0 ، والثانية - بالحرف Q 1 وما إلى ذلك. داخل كل مجموعة ، يتم ترتيب الأوامر حسب قيمة الحرف X t. وبالتالي ، يتم ترتيب الأوامر الموجودة على الشريط حيث يتم وضعها في جدول تشغيل الجهاز المحاكى.
تتم قراءة المعلومات من الشريط والكتابة على الشريط باستخدام ثلاثة رؤوس: D d - رأس البيانات ، G r - رأس الوضع ، G c - رأس الأوامر. يمكن لكل رأس أن يتحرك في منطقته الخاصة من الشريط.
قبل بدء تشغيل UMT ، يجب تسجيل المعلومات ذات الصلة في كل منطقة من الشريط. يجب تثبيت الرؤوس فوق الرمز الأيسر في كل منطقة.
يحدث عمل UMT في دورات ، في كل دورة يتم محاكاة تنفيذ أمر واحد من الآلة المحاكاة. يظهر الرسم البياني لعمل UMT في الشكل 1.10.
 |
الشكل 1.10
يستخدم الشكل 1.10 الترميز التالي:
Q G إلى P (G إلى L ، G r P ، G r L ، G d P ، G d L) - تحريك أحد الرؤوس
يمين او يسار
Q (G to) ، (G d) ، (G r) - المعلومات التي قرأها أحد الرؤساء ؛
Q (G to) à (G r) - قراءة البيانات بواسطة رأس الأمر وكتابة هذه البيانات
باستخدام رأس الوضع إلى منطقة وضع الشريط ؛
Q a متغير مساعد يأخذ القيمة 1 ، es-
ما إذا كانت الأحرف التي يقرأها الرؤوس to و р تتطابق ؛
Q in - متغير مساعد يأخذ القيمة 1 ، es-
ما إذا كانت رموز الحالة الحالية (Q t) والنهائية (Q z) هي نفسها
Q p هي إشارة تأخذ القيمة 1 إذا كان رأس الأمر عند
التحرك إلى اليسار تجاوز حدود منطقة القيادة ؛
يتم تنفيذ الخطوات التالية في كل دورة UMT:
ش البحث عن منطقة القيادة ؛
أنت تبحث عن فريق في المنطقة ؛
ش محاكاة تنفيذ الأوامر.
يبدأ البحث في منطقة الأمر بمقارنة الحالة الحالية Q t من منطقة الوضع بالحالة Q i المسجلة في بداية الأمر الأول في منطقة الأوامر. إذا لم تكن هذه الحالات متساوية ، فحينئذٍ ينتقل رأس الأمر إلى بداية الأمر التالي ، حيث يتم تنفيذ خمس خطوات رئيسية إلى اليمين (الحالات U 0 - U 4). إذا تطابق الحرفان Q t و Q i ، فسيكون رأس الأوامر في بداية الأمر الأول للمنطقة المرغوبة. بعد ذلك ، يبدأ البحث عن أمر مطابق للرموز Q t و X t لمنطقة الوضع. للقيام بذلك ، يتم تعيين رأس الوضع على حرف منطقة الوضع X t ، ويتم وضع رأس الأمر فوق حرف X i في الأمر الحالي.
يتم إجراء البحث عن فريق في منطقة بنفس طريقة البحث عن منطقة فريق. في هذه الحالة ، يتحرك رأس الأمر إلى اليمين بخمس خطوات (تنص على U 5 - U 9) حتى تتم مقارنة الأحرف X t و X i.
يبدأ تنفيذ الأمر (الحالات U 10 - U 17) بتحريك رأس الأمر خطوة واحدة إلى اليمين ، وبعد ذلك تتم كتابة الحرف Y t الذي تم قراءته من الأمر الذي تم العثور عليه إلى منطقة البيانات باستخدام رأس البيانات بدلاً من الحرف الذي تمت قراءته مسبقًا X t. بعد الخطوة التالية من رأس الأمر إلى اليمين ، تتم قراءة رمز حركة رأس البيانات (Y d) من الأمر الموجود ويتم نقل رأس البيانات وفقًا لهذا الرمز (P ، L). يوجد أدناه الحرف المعالج التالي (X t +1) ، والذي تمت كتابته في منطقة الوضع بمساعدة رأس الوضع لإعداد الدورة التالية. بعد ذلك ، يتم تعيين رؤوس الأوامر والوضع بحيث يمكن كتابة الحالة التالية Q t +1 في منطقة الوضع (الدول
U 14، U 15). في الحالة U 16 ، يتم التحقق من شرط إنهاء القرار. إذا كان رمز الحالة التالية لا يتطابق مع رمز الحالة النهائية للجهاز المحاكى (Q z) ، فلن يكتمل حل المشكلة ، وفي الحالة U 17 ، ينتقل رأس الأمر إلى موضعه الأصلي (إلى بداية الأمر الأول للمنطقة الأولى). في هذه الحالة ، يكون UMT جاهزًا لأداء الدورة التالية ، أي لمحاكاة تنفيذ الأمر التالي.
إذا تزامن الرمزان Q t و Q z ، ينتهي حل المشكلة ويدخل UMT في الحالة النهائية U z.
عند تحليل عملية تشغيل UMT ، يمكن استخلاص نتيجة مهمة مفادها أن خوارزمية عملية UMT لا تعتمد على المشكلة المحددة التي تحلها آلة Turing المحاكاة. لذلك ، لا يتغير هيكل وحدة التحكم UMT عند محاكاة الآلات المختلفة ، أي لا تعتمد على المهام المراد حلها. هذا هو السبب في أن UMT هي بالفعل آلة عالمية يمكن من خلالها تنفيذ أي خوارزمية دون تغيير هيكلها.
نظرًا لأن عملية تحديد أمر UMT التالي وتنفيذه مرتبطان بالتعداد المتسلسل لخلايا الشريط ، فإن حل المشكلات على UMT يتطلب الكثير من الوقت. لذلك ، فإن آلة تورينج ، بما في ذلك الماكينة العامة ، لم يتم بناؤها مطلقًا ، ولكن من السهل أن ترى فيها نظيرًا لأجهزة الكمبيوتر الحديثة. لذا فإن نظام الأوامر في منطقة أوامر UMT مشابه لبرنامج الآلة ، بينما يلعب زوج الرموز Q t و X t دور عنوان أمر الجهاز.
ومع ذلك ، فإن آلة تورينج هي أداة مناسبة إلى حد ما لوصف الخوارزميات وتستخدم على نطاق واسع في نظرية الخوارزميات.
أسئلة التحكم
ما هو تكوين آلات تورينج؟
ü2. ما هي تركيبة آلات تورينج المستخدمة؟
ü 3. هل يمكن لآلة تورينج محاكاة تشغيل آلة أخرى
تورينج؟
ü 4. ما هي الإجراءات التي يتم تنفيذها في هذه الحالة؟
ü5. اشرح هيكل آلة تورينج العامة؟
6. ما هي المعلومات المسجلة في مناطق شريط UMT؟
ü7.What هي مجموعة تعليمات آلة تورينج؟
ü 8. ما هي الخطوات التي تتضمنها دورة عمل UMT؟
ü9. اشرح محتويات الخطوة "search command zone".
ü10. اشرح محتويات الخطوة "تنفيذ الأمر".
ü 11. ما هي ميزات عملية معالجة المعلومات باستخدام
الشكل يشبه الرسم البياني:
قيمة جدول الآلة
الجدول 1
بعض العمليات على آلات تورينج
يتم تحديد تشغيل آلة Turing بالكامل من خلال البيانات الأولية ونظام القيادة. ومع ذلك ، من أجل فهم كيفية قيام آلة معينة بحل مشكلة ما ، كقاعدة عامة ، هناك حاجة إلى تفسيرات ذات مغزى مثل تلك المقدمة للآلة. 
. غالبًا ما يمكن جعل هذه التفسيرات أكثر رسمية ودقيقة باستخدام المخططات الانسيابية وبعض العمليات على آلات تورينج. أذكر أن تكوين الوظائف 
و 
تسمى وظيفة 
، والتي يتم الحصول عليها عن طريق التقديم 
لنتيجة الحساب 
. بغرض 
مع هذا 
، ضرورية وكافية ل 
تم تحديده على 
، أ 
تم تحديده على 
.
نظرية 1. لو 
و 
هي تورينج قابلة للحساب ، ثم تكوينها 
هي أيضا تورينج قابلة للحساب.
يترك 
- آلة تحسب 
، أ 
- آلة تحسب 
، ومجموعة دولهم ، على التوالي 
و 
.
لنقم ببناء مخطط انتقالي للآلة 
من الرسوم البيانية 
و 
على النحو التالي: تحديد الرأس الأولي 
مخططات الآلة 
بنقطة النهاية 
مخططات الآلة 
(بالنسبة لأنظمة التعليمات ، هذا يعادل حقيقة أن نظام التعليمات 
تعيين لنظام القيادة 
ولهذا 
في فرق 
استبدل ب 
). نحصل على رسم تخطيطي مع ( 
) تنص على. الحالة الأولية 
دعنا نعلن 
ونهائي 
. لتبسيط التدوين ، سنفترض 
و 
التوابع العددية لمتغير واحد.
يترك 
مُعرف. ثم 
و
. سيارة 
ستمر بنفس تسلسل التكوينات مع الاختلاف بدلاً من 
سوف تمر 
. هذا التكوين هو التكوين الأولي القياسي للجهاز. 
، لهذا 
. ولكن منذ كل الأوامر 
الواردة في 
، الذي - التي
وبالتالي 
. لو 
غير محدد إذن 
أو 
لا يتوقف ، وبالتالي الجهاز 
لن تتوقف. إذن السيارة 
يحسب 
.
الآلة بنيت بهذه الطريقة 
سوف يسمى تكوين الآلات 
و 
وتعيين 
(أو 
(
)) ، وكذلك للتوضيح في مخطط كتلة:
تكوين آلات تورينج
يترك 
,
,
- ثلاث آلات تورينج بنفس الأبجدية الخارجية 
، مع أبجديات الحالات الداخلية 
,
,
والبرامج 
,
,
على التوالى.
تعبير
الآلات 
و 
مُسَمًّى سيارةتي
الذي هو برنامج اتحاد المجموعات 
و
، أين 
يشير إلى مجموعة الأوامر المستلمة من 
استبدال كل شيء 
على 
.
شوكات آلة تورينج
آلات المتفرعة
,
,
بواسطة 
، بشكل رمزي
مُسَمًّى سيارةتي
، الذي يتم الحصول على برنامجه على النحو التالي: from 
أوامر مستبعدة 
و 
ل 
، سيتم استدعاء المجموعة الناتجة 
؛ ثم.
آلة تورينج العالمية
يمكن تفسير مجموعة التعليمات الخاصة بجهاز Turing على أنها وصف لتشغيل جهاز معين وكبرنامج ، على سبيل المثال. مجموعة من الوصفات الطبية التي تؤدي بشكل لا لبس فيه إلى نتيجة. عند تحليل الأمثلة ، يتم قبول التفسير الثاني عن غير قصد ، أي نحن نعمل كآلية قادرة على إعادة إنتاج عمل أي آلة تورينج. إن اليقين بأنهم سيفعلون ذلك جميعًا بالطريقة نفسها (إذا لم يرتكبوا أخطاء ، والتي ، بالمناسبة ، يُفترض أيضًا في تشغيل آلة تورينج) هو اليقين في الأساس من وجود خوارزمية لإعادة إنتاج تشغيل آلة تورينج وفقًا لبرنامج معين ، أي. نظام القيادة. في الواقع ، ليس من الصعب إعطاء وصف شفهي لمثل هذه الخوارزمية. عملها الرئيسي دوري ويتكون مما يلي: "للتكوين الحالي 
ابحث في نظام الأوامر عن أمر بالجانب الأيسر 
. إذا كان الجانب الأيمن من هذا الأمر هو 
، ثم استبدل في التكوين الحالي 
على 
(اتضح التكوين 
) ؛ إذا كان الجانب الأيمن لديه الشكل 
، ثم استبدل 
على 
. قد يكون الوصف اللفظي للخوارزمية غير دقيق ويحتاج إلى إضفاء الطابع الرسمي. نظرًا لأن آلة Turing تتم الآن مناقشتها على أنها إضفاء الطابع الرسمي على مفهوم الخوارزمية ، فمن الطبيعي طرح مشكلة إنشاء آلة Turing التي تنفذ خوارزمية إعادة الإنتاج الموصوفة. بالنسبة لآلات تورينج التي تحسب وظائف متغير واحد ، فإن صياغة هذه المشكلة هي: بناء آلة تورينج 
، والتي تحسب دالة من متغيرين وذلك لأي جهاز 
مع نظام القيادة 
، لو 
محددة (على سبيل المثال ، إذا كان الجهاز 
يتوقف عند البيانات الأولية 
) و 
لا تتوقف إذا 
لا يتوقف. سيتم استدعاء أي جهاز مع الخاصية المذكورة أعلاه آلة تورينج العالمية. من السهل تعميم هذه الصيغة على أي عدد من المتغيرات.
المشكلة الأولى التي تنشأ عند بناء آلة عالمية 
، يرتبط بحقيقة أن 
مثل أي آلة تورينج أخرى ، يجب أن يكون لها أبجدية ثابتة 
ومجموعة ثابتة من الدول 
. لذلك ، نظام القيادة 
والبيانات الأولية لآلة تعسفية 
لا يمكن نقلها فقط إلى آلة الشريط 
(هناك دائما سيارة 
، الحروف الهجائية 
و 
وهو الأفضل في السلطة 
و 
أو ببساطة لا تتطابق).
المخرج هو شخصيات من 
و 
مشفرة بأحرف في الأبجدية 
. يترك 
,
. سنفترض دائما ذلك 
و 
(هذان الحرفان موجودان دائمًا في الأبجدية لأي آلة تعمل مع الأرقام). دلالة على الرموز 
و 
خلال 
و 
وتعريفهم على أنهم 
؛ لأي شخص آخر 
؛ للوضع النهائي 
، لو 
. شفرة 
لهذه الآلة 
دائمًا بطول (تنسيق) 
، والرمز 
- شكل 
. حرف او رمز 
,
دعنا نقدم في 
، أي. 
,
,
. رمز الرمز 
، المكونة من رموز الأحرف التي تتكون منها هذه الكلمة ، تشير 
. وهكذا ، فإن الصقل النهائي لصياغة مشكلة آلة عالمية 
يتعلق الأمر بحقيقة أنه لأي آلة 
والكلمات 
الأبجدية 
.
إن وجود آلة تورينج عالمية يعني أن مجموعة التعليمات 
أي سيارة 
يمكن تفسيره بطريقتين: إما على أنه وصف لتشغيل الجهاز الأصلي 
، أو كبرنامج لآلة عالمية 
. بالنسبة للمهندس الحديث الذي يصمم نظام التحكم ، فإن هذا الظرف طبيعي. إنه يعلم جيدًا أن أي خوارزمية تحكم يمكن تنفيذها إما في الأجهزة - عن طريق بناء دائرة مناسبة ، أو في البرنامج - عن طريق كتابة برنامج لجهاز كمبيوتر تحكم عالمي.
ومع ذلك ، من المهم أن ندرك أن فكرة الجهاز الخوارزمي العالمي لا علاقة لها تمامًا بتطوير الوسائل التقنية الحديثة لتنفيذها (الإلكترونيات ، فيزياء الحالة الصلبة ، وما إلى ذلك) وليست حقيقة تقنية ، ولكنها حقيقة رياضية تصف في المصطلحات الرياضية المجردة التي لا تعتمد على الوسائل التقنية ، وعلاوة على ذلك ، فهي تستند إلى عدد صغير للغاية من المفاهيم الأولية الأولية للغاية. من المميزات أن الأعمال الأساسية لنظرية الخوارزميات (على وجه الخصوص ، عمل تورينج) ظهرت في الثلاثينيات ، قبل إنشاء أجهزة الكمبيوتر الحديثة.
يحافظ هذا التفسير المزدوج على المستوى المجرد على الإيجابيات والسلبيات الرئيسية لخيارين للتنفيذ الهندسي. آلة ملموسة 
يعمل بشكل أسرع بالإضافة إلى جهاز التحكم في الجهاز 
إلى حد ما مرهقة (أي عدد الحالات والأوامر كبير). ومع ذلك ، فإن قيمتها ثابتة ، وبمجرد إنشائها ، فهي مناسبة لتنفيذ خوارزميات كبيرة بشكل تعسفي. كل ما هو مطلوب هو كمية كبيرة من الشريط ، والذي يعتبر بشكل طبيعي أرخص وأكثر ترتيباً من جهاز التحكم. بالإضافة إلى ذلك ، عند تغيير الخوارزمية ، لا تحتاج إلى إنشاء أجهزة جديدة ، ما عليك سوى كتابة برنامج جديد.