آلة زينون

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

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

تعريف

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

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

رسم متحرك لآلة تورينج ذات الزمن اللانهائي استنادًا إلى تجربة مصباح تومسون الفكرية. تتناوب الخلية بين $0$ و $1$ للخطوات السابقة $\omega$ . تصبح الخلية $1$ في $\omega$ حيث أن التسلسل لا يتقارب.

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

1. الحالة
2. موقع رأس القراءة والكتابة
3. محتويات الشريط

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

$T(\lambda )_{k}=\limsup _{n\rightarrow \lambda }T(n)_{k}$

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

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

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

بدء البرنامج
  اكتب 0 في الموضع الأول لشريط الإخراج؛
  بدء الحلقة
    محاكاة خطوة واحدة متتالية من آلة تورنغ المقدمة على المدخلات المقدمة؛
    إذا توقفت آلة تورنغ،
      اكتب 1 في الموضع الأول لشريط الإخراج ثم اخرج من الحلقة؛
  حلقة النهاية
نهاية البرنامج

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

ومع ذلك، فإن آلات تورنغ ذات الزمن اللانهائي قادرة على تنفيذ الخوارزمية المحددة، والتوقف في الوقت المحدد $\omega$ مع الحل الصحيح، حيث أنهم يحددون حالتهم للخطوات غير المحدودة. جميع المجموعات قابلة للحل بواسطة آلات تورنغ ذات الزمن اللانهائي، و $\Delta _{2}^{1}$ المجموعات شبه قابلة للحسم.

لا تستطيع آلات زينون حل مشكلة التوقف الخاصة بها.

انظر أيضا

• الحساب في الحد
• تسلسل سبيكر
• مفارقة روس-ليتلوود