آلة زينون

بدء الحلقة

حلقة النهاية

إذا توقفت آلة تورنغ،

اكتب 1 في الموضع الأول لشريط الإخراج ثم اخرج من الحلقة؛

ومن ناحية أخرى، محاكاة خطوة واحدة متتالية من آلة تورنغ المقدمة على المدخلات المقدمة؛

قابلية الحساب

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

نهاية البرنامج

• لا تستطيع آلات زينون حل مشكلة التوقف الخاصة بها.
• انظر كذلك
• الحساب في الحد
• تسلسل سبيكر
• مفارقة روس-ليتلوود

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

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

آلات تورنغ ذات الزمن اللانهائي

من جانب آخر، النموذج الأكثر رسمية لآلة زينون هو آلة تورنغ ذات الزمن اللانهائي. تم تعريفها لأول مرة في عمل غير منشور لجيفري كيدر وتم التوسع فيها من قبل جويل هامكينز وآندي لويس، في آلات تورنغ ذات الزمن اللانهائي، وهي امتداد لنموذج آلة تورنغ الكلاسيكي، لتشمل الزمن غير المحدود؛ أي الزمن الذي يتجاوز كل الزمن المحدود. تتمتع آلة تورنغ الكلاسيكية بمكانة في الخطوة (في حالة البداية، مع شريط فارغ، رأس القراءة في الخلية 0) وإجراء للانتقال من حالة واحدة إلى الحالة التالية. بهذه الطريقة يتم تعريف حالة آلة تورنغ لجميع الخطوات المقابلة لعدد طبيعي. تحافظ آلة تورنغ ذات الزمن اللانهائي على هذه الخصائص، ولكنها تحدد كذلك حالة الجهاز عند الترتيبات الحدية، أي الترتيبات التي لا تكون ولا خليفة لأي ترتيبي. تتكون حالة آلة تورنغ من ثلاثة أجزاء:

موقع رأس القراءة والكتابة

الحالة

تعريف

ومن ناحية أخرى، آلة زينون هي آلة تورنغ يمكنها اتخاذ عدد لا نهائي من الخطوات، ثم الاستمرار في اتخاذ المزيد من الخطوات. يمكن اعتبار هذا بمثابة مهمة عظمى حيث يتم أخذ من الوحدات الزمنية لأداء الخطوة ؛ وبالتالي، فإن الخطوة الأولى تستغرق 0.5 وحدة زمنية، والثانية تستغرق 0.25، والثالثة 0.125 وهكذا، بحيث بعد وحدة زمنية واحدة، سيتم تنفيذ عدد لا نهائي من الخطوات.

بدء البرنامج

اكتب 0 في الموضع الأول لشريط الإخراج؛

محتويات الشريط

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

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