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

آلة بوست أو آلة بوست-تورينج ^{[ 1 ]} هي "صياغة برمجية" لنوع من آلات تورينج ، تتضمن صيغة معدلة من نموذج إميل بوست المكافئ لتورينج في الحوسبة . على الرغم من التشابه الكبير بين نموذجي بوست وتورينج، فقد طُوِّرا بشكل مستقل. نُشرت ورقة تورينج في مايو 1936، تلتها ورقة بوست في أكتوبر. تستخدم آلة بوست-تورينج أبجدية ثنائية ، وسلسلة لانهائية من مواقع التخزين الثنائية ، ولغة برمجة بدائية تتضمن تعليمات للتنقل ثنائي الاتجاه بين مواقع التخزين وتغيير محتوياتها واحدًا تلو الآخر. استخدم مارتن ديفيس مصطلحي "برنامج بوست-تورينج" و"آلة بوست-تورينج" في الفترة 1973-1974 (ديفيس 1973، ص 69 وما بعدها). وفي وقت لاحق من عام 1980، استخدم ديفيس مصطلح "برنامج تورينج-بوست" (ديفيس، في ستين، ص 241).  

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

يختلف نموذج بوست للحساب عن نموذج آلة تورينج في "تجزئة" إضافية للأفعال التي يقوم بها "الحاسوب" البشري أثناء عملية الحساب. ^{[ 2 ]}

يستخدم نموذج بوست " فضاءً رمزيًا " يتألف من "سلسلة لانهائية ثنائية الاتجاه من المساحات أو المربعات"، حيث يمكن أن يكون كل مربع في إحدى حالتين محتملتين، وهما "مُعلَّم" (بخط عمودي واحد) و"غير مُعلَّم" (فارغ). في البداية، يكون عدد محدود من المربعات مُعلَّمًا، بينما تكون البقية غير مُعلَّمة. ثم يتحرك "العامل" بين المربعات، بحيث يكون داخل مربع واحد فقط ويعمل فيه في كل مرة، وفقًا لـ"مجموعة توجيهات" ( تعليمات ) ثابتة ومحدودة، مرقمة بالتسلسل (1، 2، 3، ...، ن ). يبدأ العامل من مربع "مُختار كنقطة بداية"، ويتبع مجموعة التعليمات واحدة تلو الأخرى، بدءًا من التعليمات رقم 1.

هناك خمس عمليات أولية مختلفة يمكن للعامل القيام بها:

(أ) وضع علامة على المربع الذي يوجد فيه، إذا كان فارغًا

(ب) مسح العلامة الموجودة في المربع الذي توجد فيه، إذا كانت مُعلَّمة

(ج) الانتقال إلى المربع الموجود على يمينه

(د) الانتقال إلى المربع الموجود على يساره

(هـ) تحديد ما إذا كان الصندوق الذي يوجد فيه الصندوق مُعلَّمًا أم لا.

Then, the i^th "direction" (instruction) given to the worker is to be one of the following forms:

(The above indented text and italics are as in the original.) Post remarks that this formulation is "in its initial stages" of development, and mentions several possibilities for "greater flexibility" in its final "definitive form", including

1. replacing the infinity of boxes by a finite extensible symbol space, "extending the primitive operations to allow for the necessary extension of the given finite symbol space as the process proceeds",
2. using an alphabet of more than two symbols, "having more than one way to mark a box",
3. introducing finitely-many "physical objects to serve as pointers, which the worker can identify and move from box to box".

As briefly mentioned in the article Turing machine, Post, in his paper of 1947 (Recursive Unsolvability of a Problem of Thue) atomized the Turing 5-tuples to 4-tuples:

"Our quadruplets are quintuplets in the Turing development. That is, where our standard instruction orders either a printing (overprinting) or motion, left or right, Turing's standard instruction always order a printing and a motion, right, left, or none" (footnote 12, Undecidable, p. 300)

Like Turing, he defined erasure as printing a symbol "S0". And so his model admitted quadruplets of only three types (cf. Undecidable, p. 294):

q_iS_jLq_l,

q_iS_jRq_l,

q_iS_jS_kq_l

At this time he was still retaining the Turing state-machine convention – he had not formalized the notion of an assumed sequential execution of steps until a specific test of a symbol "branched" the execution elsewhere.

Wang (1957, but presented to the ACM in 1954) is often cited (cf. Minsky (1967), p. 200) as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set

write 0

write 1

move left

move right

إذا كان المسح 0، فانتقل إلى التعليمات i

إذا كان المسح الضوئي 1، فانتقل إلى التعليمات j

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

كان مارتن ديفيس طالبًا جامعيًا لدى إميل بوست. وقد أكمل درجة الدكتوراه مع ستيفن كلين تحت إشراف ألونسو تشيرش (ديفيس (2000) الحواشي الأولى والثانية ص.  188).

قدّم ديفيس النموذج التالي في سلسلة محاضرات لمعهد كورانت بجامعة نيويورك في الفترة 1973-1974. وهو النموذج الذي أطلق عليه ديفيس رسميًا اسم "آلة ما بعد تورينج" و"لغة ما بعد تورينج". ^{[ 2 ]} يُفترض أن تُنفّذ التعليمات بالتسلسل (ديفيس 1974، ص  71).

يظهر النموذج التالي كمقال بعنوان " ما هي العملية الحسابية؟" في كتاب ستين، الصفحات 241-267. ولسبب ما، أعاد ديفيس تسمية نموذجه إلى "آلة تورينج-بوست" (مع وجود خطأ واحد في الصفحة 256).

في النموذج التالي، يُسند ديفيس الرقم "1" إلى أمر "العلامة/الشرطة المائلة" في لغة بوست، والرقم "0" إلى المربع الفارغ. وكما قال ديفيس: "نحن الآن على استعداد لتقديم لغة برمجة تورينج-بوست. تحتوي هذه اللغة على سبعة أنواع من التعليمات:

اطبع 1

اطبع 0

انعطف يميناً

انعطف يسارًا

انتقل إلى الخطوة i إذا تم مسح 1 ضوئيًا

انتقل إلى الخطوة i إذا تم مسح 0

"قف

"إن برنامج تورينج-بوست هو عبارة عن قائمة من التعليمات، كل منها من أحد هذه الأنواع السبعة. بالطبع، في برنامج فعلي، يجب استبدال الحرف i في خطوة من النوع الخامس أو السادس بعدد صحيح موجب محدد." (ديفيس في ستين، ص  247).

"على الرغم من أن صياغة تورينج التي قدمناها أقرب في جوهرها إلى تلك التي قدمها إميل بوست في الأصل، إلا أن تحليل تورينج للحساب هو الذي جعل هذه الصياغة تبدو مناسبة للغاية. لقد لعبت هذه اللغة دورًا أساسيًا في علوم الحاسوب النظرية ." (ديفيس وآخرون، 1994، ص  129)

يُتيح هذا النموذج طباعة رموز متعددة. كما يُتيح استخدام B (فارغ) بدلاً من S _0. الشريط لا نهائي في كلا الاتجاهين. يتحرك إما رأس الطباعة أو الشريط، لكن تعريفاتهما لليمين واليسار تُشير دائمًا إلى النتيجة نفسها في كلتا الحالتين (استخدم تورينج نفس الاصطلاح).

اطبع σ؛ استبدل الرمز الممسوح ضوئيًا بـ σ

إذا كان الرمز الممسوح ضوئيًا هو σ، فانتقل إلى التعليمات الأولى المسماة L.

يمين؛ امسح المربع الموجود مباشرةً على يمين المربع الذي تم مسحه ضوئيًا حاليًا

يسارًا؛ امسح المربع الموجود مباشرةً على يسار المربع الذي تم مسحه ضوئيًا حاليًا

يختزل هذا النموذج إلى الإصدارات الثنائية { 0، 1 } المعروضة أعلاه، كما هو موضح هنا:

اطبع 0 = امسح؛ استبدل الرمز الممسوح ضوئيًا بـ 0 = B = فارغ

اطبع 1؛ استبدل الرمز الممسوح ضوئيًا بالرقم 1

إذا كانت القيمة 0، فانتقل إلى L؛ إذا كانت القيمة 0، فانتقل إلى التعليمات الأولى المسماة L

إذا كان الرمز الممسوح ضوئيًا هو 1، فانتقل إلى التعليمات "الأولى" المسماة L.

يمين؛ امسح المربع الموجود مباشرةً على يمين المربع الذي تم مسحه ضوئيًا حاليًا

يسارًا؛ امسح المربع الموجود مباشرةً على يسار المربع الذي تم مسحه ضوئيًا حاليًا

• ستيفن سي. كلين ، مقدمة في الرياضيات الميتافيزيقية، شركة نورث هولاند للنشر ، نيويورك، الطبعة العاشرة 1991، نُشرت لأول مرة عام 1952. الفصل الثالث عشر هو وصف ممتاز لآلات تورينج؛ يستخدم كلين نموذجًا يشبه نموذج بوست في وصفه ويقر بإمكانية تجزئة نموذج تورينج بشكل أكبر، انظر الحاشية 1.
• مارتن ديفيس ، محرر: غير القابل للتقرير، أوراق أساسية حول القضايا غير القابلة للتقرير، والمشاكل غير القابلة للحل، والوظائف القابلة للحساب ، دار نشر رافين، نيويورك، 1965. تشمل الأوراق تلك التي كتبها غودل ، وتشرش ، وروسر ، وكلين ، وبوست.
• مارتن ديفيس ، "ما هي العملية الحسابية؟"، في مجلة الرياضيات اليوم ، لين آرثر ستين، دار فينتج بوكس ​​(راندوم هاوس)، 1980. ورقة بحثية رائعة، ربما تكون الأفضل على الإطلاق في مجال آلات تورينج. يُبسّط ديفيس آلة تورينج إلى نموذج أبسط بكثير، استنادًا إلى نموذج بوست للعملية الحسابية. تتضمن الورقة نبذة مختصرة عن حياة إميل بوست.
• مارتن ديفيس ، قابلية الحوسبة: مع ملاحظات بقلم باري جاكوبس ، معهد كورانت للعلوم الرياضية، جامعة نيويورك، 1974.
• مارتن ديفيس ، رون سيغال ، إيلين ج. ويوكر ، (1994) الحوسبة، والتعقيد، واللغات: أساسيات علوم الحاسوب النظرية - الطبعة الثانية ، دار النشر الأكاديمية: هاركورت، بريس وشركاه، سان دييغو، 1994، رقم ISBN 0-12-206382-1(الطبعة الأولى، 1983).
• فريد هيني ، مقدمة في الحوسبة ، أديسون-ويسلي، 1977.
• مارفن مينسكي ، (1961)، عدم قابلية حل مشكلة بوست المتعلقة بـ "الوسم" بشكل متكرر ومواضيع أخرى في نظرية آلات تورينج ، حوليات الرياضيات، المجلد 74، العدد 3، نوفمبر 1961.
• روجر بنروز ، عقل الإمبراطور الجديد: حول الحواسيب والعقول وقوانين الفيزياء ، مطبعة جامعة أكسفورد، أكسفورد، إنجلترا، 1990 (مع تصويبات). انظر الفصل الثاني، "الخوارزميات وآلات تورينج". عرض مُعقّد للغاية (انظر ورقة ديفيس للحصول على نموذج أفضل)، ولكنه عرض شامل لآلات تورينج ومشكلة التوقف ، وحساب لامدا لتشرش .
• هاو وانغ (1957): "متغير لنظرية تورينج لآلات الحوسبة"، مجلة رابطة آلات الحوسبة (JACM) 4، 63-92.