آلة تورينج العالمية

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

قد يقول المنطق السليم إن الآلة الشاملة مستحيلة، لكن تورينج يثبت أنها ممكنة. ^{[ أ ]} اقترح أنه يمكننا مقارنة الإنسان أثناء عملية حساب عدد حقيقي بآلة لا تستطيع إلا التعامل مع عدد محدود من الشروط .${\displaystyle q_{1},q_{2},\dots ,q_{R}}$; والتي ستُسمى " تكوينات m ". ^{[ 2 ]} ثم وصف آلية عمل هذه الآلة، كما هو موضح أدناه، وجادل بما يلي:

أرى أن هذه العمليات تشمل جميع العمليات المستخدمة في حساب عدد ما. ^{[ 3 ]}

قدم تورينج فكرة مثل هذه الآلة في الفترة ما بين عامي 1936 و1937.

يقدم مارتن ديفيس حجة مقنعة مفادها أن مفهوم تورينج لما يُعرف الآن باسم "الحاسوب ذي البرنامج المخزن"، أي وضع "جدول الإجراءات" - تعليمات الآلة - في نفس "الذاكرة" التي تحتوي على بيانات الإدخال، قد أثر بشكل كبير على مفهوم جون فون نيومان لأول حاسوب أمريكي ذي رموز منفصلة (مقارنةً بالحاسوب التناظري) - وهو حاسوب EDVAC . ويستشهد ديفيس بمجلة تايم في هذا الصدد، حيث تقول: "كل من ينقر على لوحة المفاتيح  ... يعمل على نسخة من آلة تورينج"، وأن "جون فون نيومان [بنى] على عمل آلان تورينج". ^{[ 4 ]}

يُقدّم ديفيس حجّةً مفادها أن حاسوب تورينغ الآلي (ACE) قد "استبق" مفاهيم البرمجة الدقيقة ( الرمز المصغر ) ومعالجات RISC . ^{[ 5 ]} ويستشهد دونالد كنوث بعمل تورينغ على حاسوب ACE باعتباره تصميمًا "للأجهزة لتسهيل ربط الروتينات الفرعية"؛ ^{[ 6 ]} كما يُشير ديفيس إلى هذا العمل باعتباره استخدام تورينغ لـ"مكدس" الأجهزة. ^{[ 7 ]}

بينما كانت آلة تورينج تشجع على بناء الحواسيب ، كانت جامعة تورينج تشجع على تطوير علوم الحاسوب الناشئة . وقد اقترح مبرمج شاب بارع مُجمِّعًا مبكرًا، إن لم يكن أول مُجمِّع، لجهاز EDVAC. ^{[ 8 ]} وكان "أول برنامج جاد لفون نيومان..." هو ببساطة فرز البيانات بكفاءة. ^{[ 9 ]} ويلاحظ كنوت أن إرجاع الروتين الفرعي المُضمَّن في البرنامج نفسه، بدلاً من وجوده في سجلات خاصة، يُعزى إلى فون نيومان وجولدستين. ^{[ ب ]} ويذكر كنوت أيضًا أن

يمكن القول إن أول برنامج تفسيري هو "آلة تورينج العالمية"... وقد ذكر جون موتشلي البرامج التفسيرية بالمعنى التقليدي في محاضراته في مدرسة مور عام 1946... وشارك تورينج في هذا التطوير أيضًا؛ حيث كُتبت أنظمة تفسيرية لحاسوب بايلوت إيه سي إي تحت إشرافه. ^{[ 10 ]}

يشير ديفيس بإيجاز إلى أنظمة التشغيل والمترجمات باعتبارها نتاجًا لمفهوم البرنامج كبيانات. ^{[ 11 ]}

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

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

تُعدّ الدالة الشاملة نسخةً مجردةً من آلة تورينج العالمية ، وهي دالة قابلة للحساب يمكن استخدامها لحساب أي دالة أخرى قابلة للحساب. وتُثبت نظرية آلة تورينج العالمية وجود مثل هذه الدالة.

دون الإخلال بعمومية المسألة، يمكن افتراض أن مدخلات آلة تورينج تنتمي إلى الأبجدية {0، 1}؛ ويمكن ترميز أي أبجدية محدودة أخرى على هذه الأبجدية. يتحدد سلوك آلة تورينج M بواسطة دالة الانتقال الخاصة بها، والتي يمكن ترميزها بسهولة كسلسلة نصية على الأبجدية {0، 1}. يمكن استنتاج حجم أبجدية M ، وعدد الأشرطة التي تمتلكها، وحجم فضاء الحالة من جدول دالة الانتقال. يمكن تمييز الحالات والرموز من خلال مواقعها، فعلى سبيل المثال، يمكن اعتبار أول حالتين، اصطلاحًا، حالتي البداية والنهاية. بالتالي، يمكن ترميز أي آلة تورينج كسلسلة نصية على الأبجدية {0، 1}. إضافةً إلى ذلك، نفترض أن كل ترميز غير صالح يُقابله آلة تورينج بسيطة تتوقف فورًا، وأن أي آلة تورينج يمكن أن تحتوي على عدد لا نهائي من الترميزات عن طريق إضافة عدد عشوائي من الآحاد (مثلاً) في النهاية، تمامًا كما تعمل التعليقات في لغات البرمجة. ليس من المستغرب أن نتمكن من تحقيق هذا التشفير نظرًا لوجود عدد غودل والتكافؤ الحسابي بين آلات تورينغ والدوال التكرارية من النوع μ . وبالمثل، فإن تصميمنا يربط كل سلسلة ثنائية α بآلة تورينغ M _α .

انطلاقًا من الترميز المذكور أعلاه، أثبت كلٌ من إف سي هيني وآر إي ستيرنز في عام 1966 أنه إذا كانت لدينا آلة تورينج _Mα تتوقف عند المدخل x خلال N خطوة، فإنه توجد آلة تورينج عالمية متعددة الأشرطة تتوقف عند المدخلين α و x (المُعطى على أشرطة مختلفة) في CN log N ، حيث C ثابت خاص بالآلة لا يعتمد على طول المدخل x ، ولكنه يعتمد على حجم أبجدية M وعدد الأشرطة وعدد الحالات. وهذا في الواقع...${\displaystyle {\mathcal {O}}\left(N\log {N}\right)}$محاكاة باستخدام ترميز Big O لدونالد كنوث . [ ^{12 ] والنتيجة} المقابلة لتعقيد المساحة بدلاً من تعقيد الوقت هي أنه يمكننا المحاكاة بطريقة تستخدم على الأكثر CN خلية في أي مرحلة من مراحل الحساب،${\displaystyle {\mathcal {O}}(N)}$محاكاة. ^{[ 13 ]}

عندما ابتكر آلان تورينج فكرة الآلة الشاملة، كان يقصد أبسط نموذج حاسوبي قادر على حساب جميع الدوال الممكنة. في عام ١٩٥٦، طرح كلود شانون صراحةً مسألة إيجاد أصغر آلة تورينج شاملة ممكنة. بيّن أن رمزين يكفيان طالما استُخدم عدد كافٍ من الحالات (أو العكس)، وأنه من الممكن دائمًا استبدال الحالات بالرموز. كما بيّن أنه لا يمكن أن توجد آلة تورينج شاملة ذات حالة واحدة.

اكتشف مارفن مينسكي آلة تورينغ عالمية ذات 7 حالات و4 رموز في عام 1962 باستخدام أنظمة ذات علامتين . ومنذ ذلك الحين، اكتشف يوري روغوزين وآخرون آلات تورينغ عالمية صغيرة أخرى من خلال توسيع هذا النهج لمحاكاة نظام العلامات. إذا رمزنا بـ ( m , n ) لفئة آلات تورينغ العالمية ذات m حالة و n رمز، فقد تم العثور على الأزواج التالية: (15، 2)، (9، 3)، (6، 4)، (5، 5)، (4، 6)، (3، 9)، و(2، 18). ^{[ 14 ] [ 15 ] [ 16 ]} تستخدم آلة روغوزين (4، 6) 22 تعليمة فقط، ولا توجد آلة تورينغ عالمية قياسية معروفة ذات تعقيد وصفي أقل.

مع ذلك، يسمح تعميم نموذج آلة تورينج القياسي بإنتاج آلات تورينج عالمية أصغر. أحد هذه التعميمات هو السماح بتكرار كلمة بلا حدود على أحد جانبي مدخل آلة تورينج أو كليهما، مما يوسع تعريف العالمية ويُعرف باسم العالمية "شبه الضعيفة" أو "الضعيفة" على التوالي. وقد تم تقديم آلات تورينج عالمية ضعيفة صغيرة تحاكي الأوتومات الخلوية للقاعدة 110 لأزواج الحالة-الرمز (6، 2) و(3، 3) و(2، 4). ^{[ 17 ]} كما أن برهان عالمية آلة تورينج ذات حالتين وثلاثة رموز لولفرام يوسع مفهوم العالمية الضعيفة من خلال السماح ببعض التكوينات الأولية غير الدورية. تشمل المتغيرات الأخرى لنموذج آلة تورينج القياسي التي تُنتج آلات تورينج عالمية صغيرة آلات ذات أشرطة متعددة أو أشرطة متعددة الأبعاد، وآلات مقترنة بأوتومات محدود .

إذا سُمح لآلة تورينج بقراءة عدة رؤوس متتالية لمواضع الشريط، فلا حاجة لحالات داخلية، إذ يمكن ترميز "الحالات" في الشريط نفسه. على سبيل المثال، لنفترض شريطًا بستة ألوان: 0، 1، 2، 0A، 1A، 2A. ولنفترض شريطًا مثل 0، 0، 1، 2، 2A، 0، 2، 1، حيث توجد آلة تورينج ثلاثية الرؤوس فوق الثلاثية (2، 2A، 0). تقوم القواعد بتحويل أي ثلاثية إلى ثلاثية أخرى، ثم تحرك الرؤوس الثلاثة يمينًا أو يسارًا. على سبيل المثال، قد تحول القواعد (2، 2A، 0) إلى (2، 1، 0)، وتحرك الرأس يسارًا. بالتالي، في هذا المثال، تعمل الآلة كآلة تورينج ثلاثية الألوان بحالتين داخليتين A وB (لا يُمثلان بأي حرف). وينطبق الأمر نفسه على آلة تورينج ثنائية الرؤوس. لذا، يمكن لآلة تورينج ثنائية الرؤوس بدون حالات داخلية أن تكون شاملة بستة ألوان. لا يُعرف ما هو أقل عدد من الألوان اللازمة لآلة تورينج متعددة الرؤوس، أو ما إذا كان من الممكن وجود آلة تورينج عالمية ثنائية اللون بدون حالات داخلية مع رؤوس متعددة. وهذا يعني أيضًا أن قواعد إعادة الكتابة كاملة تورينج لأن القواعد الثلاثية مكافئة لقواعد إعادة الكتابة. عند تمديد الشريط إلى بعدين مع رأس يأخذ عينة من حرف وجيرانه الثمانية، يلزم لونان فقط، حيث يمكن، على سبيل المثال، ترميز لون في نمط ثلاثي رأسي مثل 110.

كذلك، إذا كانت المسافة بين الرأسين متغيرة (يوجد "ارتخاء" في الشريط بين الرأسين)، فإنه يمكن محاكاة أي نظام علامات بريدية ، بعضها عالمي. ^{[ 18 ]}

لمن يرغب في خوض تحدي تصميم آلة تورينج العالمية (UTM) وفقًا لمواصفات تورينج، يُرجى الاطلاع على مقال ديفيز في كوبلاند (2004) . يُصحح ديفيز الأخطاء الواردة في النص الأصلي، ويُبين كيف سيبدو تشغيل نموذج تجريبي. وقد نجح في تشغيل محاكاة (مبسطة نوعًا ما).

المثال التالي مأخوذ من كتاب تورينج (1937) . لمزيد من المعلومات حول هذا المثال، انظر أمثلة آلة تورينج .

استخدم تورينج سبعة رموز {A, C, D, R, L, N,  ;} لترميز كل خماسية؛ وكما هو موضح في مقال آلة تورينج ، فإن خماسياته من الأنواع N1 وN2 وN3 فقط. يُمثَّل عدد كل " تكوين m " (تعليمات، حالة) بالرمز "D" متبوعًا بسلسلة أحادية من الأحرف A، على سبيل المثال "q3" = DAAA. وبالمثل، يُرمِّز الرموز الفارغة بالرمز "D"، والرمز "0" بالرمز "DC"، والرمز "1" بالرمز DCC، وهكذا. أما الرموز "R" و"L" و"N" فتبقى كما هي.

بعد ترميز كل مجموعة من 5 عناصر، يتم "تجميعها" في سلسلة نصية بالترتيب الموضح في الجدول التالي:

وأخيرًا، يتم تجميع رموز جميع المجموعات الخماسية الأربعة معًا في رمز يبدأ بـ ";" ويفصل بينها ";" أي:

وضع هذا الرمز على مربعات متبادلة - مربعات "F" - تاركًا مربعات "E" (المعرضة للمحو) فارغة. تتكون عملية تجميع الرمز النهائية على شريط آلة U من وضع رمزين خاصين ("e") واحدًا تلو الآخر، ثم الرمز مفصولًا على مربعات متبادلة، وأخيرًا رمز النقطتين المزدوجتين " :: " (المساحات الفارغة موضحة هنا بـ "." للتوضيح):

يتولى جدول إجراءات آلة U (جدول انتقال الحالة) مسؤولية فك تشفير الرموز. ويتتبع جدول إجراءات تورينج موقعه باستخدام علامات "u" و"v" و"x" و"y" و"z" بوضعها في مربعات E على يمين "الرمز المميز" - على سبيل المثال، لتمييز التعليمات الحالية، يوضع الرمز z على يمين الفاصلة المنقوطة (;)، بينما يحافظ الرمز x على موقعه بالنسبة لتكوين DAA الحالي "m". ويقوم جدول إجراءات آلة U بنقل هذه الرموز (مسحها ووضعها في مواقع مختلفة) مع تقدم العملية الحسابية.

جدول إجراءات تورينج لآلته U معقد للغاية.

يقدم روجر بنروز أمثلة على طرق ترميز التعليمات للآلة العالمية باستخدام الرموز الثنائية فقط { 0، 1 }، أو { فارغ، علامة | }. ويذهب بنروز إلى أبعد من ذلك، فيكتب كامل شفرة الآلة العالمية الخاصة به. ويؤكد أنها بالفعل شفرة آلة عالمية، وهي عبارة عن رقم هائل يمتد على صفحتين كاملتين تقريبًا من الأصفار والآحاد. ^{[ 19 ]}

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

• آلة تورينج المتناوبة – نموذج حسابي مجرد 
• آلة العد – آلة مجردة تُستخدم في المنطق الصوري وعلوم الحاسوب النظرية 
• مُسند كلين T – مفهوم في نظرية الحوسبة 
• علامة وفراغ – حالات إشارة الاتصالات 
• أجهزة الحوسبة الافتراضية المكافئة لآلة تورينج 
• مُنشئ فون نيومان العالمي – الأوتومات الخلوي ذاتي التكاثر 

• سميث، ألفي راي. "آلة تورينغ عالمية لبطاقات العمل" (ملف PDF) . تم الاطلاع عليه بتاريخ 2 يناير 2020 .