نظام الوسوم

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

لأن جميع العمليات المشار إليها يتم تنفيذها في انتقال واحد، فإن آلة الوسم لها حالة واحدة فقط.

نظام الوسوم هو ثلاثية ( م ، أ ، ب )، حيث

• m هو عدد صحيح موجب ، ويسمى رقم الحذف .
• A عبارة عن أبجدية محدودة من الرموز، أحدها يمكن أن يكون رمز توقف خاص . جميع السلاسل المحدودة (التي قد تكون فارغة) على A تسمى كلمات .
• P هي مجموعة من قواعد الإنتاج ، حيث يتم تعيين كلمة P(x) (تسمى قاعدة إنتاج ) لكل رمز x في A. قاعدة الإنتاج (مثلاً P( H ) ) المعينة لرمز التوقف لا تلعب أي دور في العمليات الحسابية، ولكن من أجل التبسيط، يتم اعتبارها P( H ) = 'H' .

الكلمة المتوقفة هي كلمة إما تبدأ برمز التوقف أو يقل طولها عن m .

يُعرَّف تحويل t (يُسمى عملية الوسم ) على مجموعة الكلمات غير المتوقفة، بحيث إذا كان x يُمثل الرمز الأيسر للكلمة S ، فإن t ( S ) هو نتيجة حذف الرموز m الموجودة على يسار S وإضافة الكلمة P(x) إلى اليمين. وبالتالي، يُعالج النظام رأس الكلمة المكون من m رمزًا إلى ذيل ذي طول متغير، لكن الذيل الناتج يعتمد فقط على الرمز الأول من الرأس.

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

يُستخدم مصطلح نظام الوسوم m غالبًا للتأكيد على عدد الحذف. وتختلف التعريفات إلى حد ما في المراجع (انظر المراجع)، والتعريف المقدم هنا هو تعريف روغوزين. ^{[ 2 ]}

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

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

نظام ذو علامتين الأبجدية: {أ، ب، ج، ح} قواعد الإنتاج: أ --> ccbaH ب --> جكا ج --> ج ج حساب الكلمة الأولى: باء أكا caccbaH ccbaHcc baHcccc هككككا (قف). 

نظام ذو علامتين الأبجدية: {أ، ب، ج} قواعد الإنتاج: أ --> ب ج ب --> أ ج --> أأأ حساب الكلمة الأولية: aaa <--> n=3 أبجد سي بي سي كااا aaaaa <--> 5 aaabc abcbc cbcbc cbcaaa كااااااا aaaaaaaa <--> 8 aaaaaabc aaaabcbc aabcbcbc bcbcbcbc bcbcbca bcbcaa bcaaa aaaa <--> 4 aabc بي سي بي سي bca aa <--> 2 قبل الميلاد أ <--> 1 (وقف) 

لكل قيمة m > 1، تكون مجموعة أنظمة العلامات m كاملة تورينج ؛ أي أنه لكل قيمة m > 1، يوجد نظام علامات m يحاكي آلة تورينج T المعطاة . على وجه الخصوص، يمكن إنشاء نظام علامات 2 لمحاكاة آلة تورينج شاملة ، كما فعل وانغ (1963) وكوك ومينسكي ( 1964) .

على النقيض من ذلك، يمكن إثبات أن آلة تورينغ هي آلة تورينغ شاملة من خلال إثبات قدرتها على محاكاة فئة كاملة من أنظمة العلامات ذات m علامة. على سبيل المثال، أثبت روغوزين (1996) عالمية فئة أنظمة العلامات الثنائية ذات الأبجدية { _{a₁, ..., aₙ, H} وقواعد الإنتاج المقابلة {aₙₙW₁, ..., aₙₙWₙ₋₁, aₙₙ, H}، حيث Wₖ} هي كلمات غير _{فارغة ؛} ثم أثبت _عالمية آلة تورينغ صغيرة _{جدًا (} ذات _{4 حالات} و 6 رموز ) _من خلال إظهار قدرتها على _{محاكاة هذه} الفئة من أنظمة العلامات .

يُعد نظام الوسمتين محاكاة فعالة لآلات تورينج العالمية، في${\displaystyle O(t^{2}\log t)}$الوقت. هذا إذا${\displaystyle M}$هي آلة تورينج حتمية أحادية الشريط تعمل في زمن${\displaystyle t}$ثم هناك نظام ذو علامتين يحاكي ذلك في${\displaystyle O(t^{2}\log t)}$الوقت. ^{[ 3 ]}

يُعد هذا الإصدار من مشكلة التوقف من بين أبسط مشاكل القرار غير القابلة للتقرير وأسهلها وصفاً :

بفرض وجود عدد صحيح موجب n وقائمة من n + 1 كلمة عشوائية P1 _، P2 _، ...، Pn، Q _على الأبجدية { 1، 2، ...، n }، هل يؤدي تطبيق عملية الوسم t : ijX → XPi بشكل متكرر إلى تحويل Q _في النهاية إلى كلمة طولها أقل من 2؟ أي، هل تنتهي المتتالية Q ، t1 ( Q )، t2 ( Q )، ^t3 ( ^{Q )} ، ... ؟

يختلف التعريف أعلاه عن تعريف بوست (1943) ، الذي لا تستخدم أنظمة الوسوم الخاصة به رمز التوقف، بل تتوقف فقط عند الكلمة الفارغة، مع تعريف عملية الوسم t على النحو التالي:

• إذا كان x يمثل الرمز الأيسر لكلمة غير فارغة S ، فإن t ( S ) هي العملية التي تتكون من إلحاق الكلمة P(x) أولاً بالطرف الأيمن من S ، ثم حذف الرموز m الموجودة في أقصى اليسار من النتيجة - حذف الكل إذا كان هناك أقل من m رمزًا.

إن الملاحظة المذكورة أعلاه بشأن اكتمال تورينج لمجموعة أنظمة العلامات m ، لأي m > 1، تنطبق أيضًا على أنظمة العلامات هذه كما تم تعريفها في الأصل بواسطة بوست.

نظام الوسوم الدوري هو تعديل لنظام الوسوم الأصلي. تتكون الأبجدية من رمزين فقط، 0 و 1 ، وتتألف قواعد الإنتاج من قائمة من قواعد الإنتاج التي تُدرس بالتسلسل، وتعود إلى بداية القائمة بعد دراسة قاعدة الإنتاج "الأخيرة" فيها. لكل قاعدة إنتاج، يُفحص الرمز الأيسر من الكلمة؛ فإذا كان الرمز 1 ، تُضاف قاعدة الإنتاج الحالية إلى نهاية الكلمة اليمنى؛ وإذا كان الرمز 0 ، فلا تُضاف أي أحرف إلى الكلمة؛ وفي كلتا الحالتين، يُحذف الرمز الأيسر. يتوقف النظام عندما تصبح الكلمة فارغة. ^{[ 4 ]}

نظام العلامات الدورية الإنتاجات: (010، 000، 1111) حساب الكلمة الأولى: 11001 كلمة الإنتاج ---------- -------------- 010 11001 ٠٠٠ ١٠٠١٠١٠ 1111 001010000 010 01010000 ٠٠٠ ١٠١٠٠٠٠ 1111 010000000 010 10000000 . . . . 

يُحاكى نظام علامات m ذو الأبجدية {a1, ..., an} وقواعد الإنتاج المقابلة {P1, ..., Pn} بواسطة نظام علامات دوري ذي m * n قاعدة _إنتاج ( Q1 _, ... , _Qn , - _, - , ... _, - ) _، حيث تكون جميع قواعد الإنتاج باستثناء أول n قاعدة إنتاج عبارة عن سلسلة فارغة (يرمز لها بـ ' - ' ₎ . تمثل Qk ترميزات لقواعد _{الإنتاج} المقابلة لها ، ويتم الحصول عليها باستبدال كل رمز من رموز أبجدية نظام العلامات بسلسلة ثنائية طولها n كما يلي (يجب تطبيق هذه الترميزات أيضًا على الكلمة الأولى في عملية حساب نظام العلامات):

أ 1 = 100...00 أ 2 = 010...00 . . . a n = 000...01

أي أن الحرف _k يُشفّر كسلسلة ثنائية تحتوي على الرقم 1 في الموضع k ^من اليسار، والأصفار في باقي المواضع. وبالتالي، تُشفّر الأسطر المتتالية لحسابات نظام الوسوم على أنها كل سطر ( ^m *n ) من محاكاتها بواسطة نظام الوسوم الدوري.

نظام ذو علامتين قواعد الإنتاج: (a --> bb, b --> abH, H --> H) ترميز الأبجدية: أ = 100، ب = 010، ح = 001 ترميزات الإنتاج: (bb = 010 010, abH = 100 010 001, H = 001) نظام العلامات الدورية الإنتاجات: (010 010, 100 010 001, 001, -, -, -) حساب نظام الوسوم الكلمة الأولى: با abH Hbb (قف) حساب نظام العلامات الدورية الكلمة الأولى: 010 100 (=ba) كلمة الإنتاج ---------- ------------------------------- * 010 010 010 100 (=ba) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 إيقاف محاكى --> 001 010 010 (=Hbb) 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ... 

• آلة قائمة الانتظار
• لعبة كونواي للحياة

• كوك، جون ؛ مينسكي، مارفن (1964). "شمولية أنظمة الوسوم مع P=2". مجلة رابطة آلات الحوسبة . 11 : 15-20 . doi : 10.1145/321203.321206 . hdl : 1721.1/6107 . S2CID 2799125 . 
• كوك، ماثيو (2004). "الشمولية في الأوتوماتا الخلوية الأولية" . الأنظمة المعقدة . 15 : 1-40 . doi : 10.25088/ComplexSystems.15.1.1 . مؤرشف (PDF) من الأصل بتاريخ 28 مايو 2016.
• دي مول، ليزبيث (يناير 2008). "أنظمة الوسوم ووظائف كولاتز" . علوم الحاسوب النظرية . 390 (1): 92-101 . doi : 10.1016/j.tcs.2007.10.020 . hdl : 1854/LU-436211 .
• مينسكي، مارفن ل. (نوفمبر 1961). "عدم قابلية حل مسألة "الوسم" لبوست بشكل متكرر ومواضيع أخرى في نظرية آلات تورينج". حوليات الرياضيات . 2. 74 (3): 437-455 . doi : 10.2307/1970290 . JSTOR 1970290 . 
• مينسكي، مارفن ل. (1967). الحوسبة: الآلات المحدودة واللامحدودة . إنجلوود كليفس، نيوجيرسي: برنتيس هول . الصفحات 267-273 . ISBN  978-0131655638. إل سي سي إن 67-12342 . 
• بوست، إميل (1943). "الاختزالات الرسمية لمسألة القرار التوافقي" . المجلة الأمريكية للرياضيات . 65 (2): 197-215 . doi : 10.2307/2371809 . JSTOR 2371809 . (يتم تقديم أنظمة الوسوم في الصفحة  203 وما بعدها .)
• روغوزين، يوري (20 نوفمبر 1996). "آلات تورينغ العالمية الصغيرة" . علوم الحاسوب النظرية . 168 (2): 215-240 . doi : 10.1016/S0304-3975(96)00077-1 .
• وانغ، هاو (1963). “أنظمة العلامات وأنظمة التأخر”. الرياضيات أنالن . 152 : 65– 74. دوى : 10.1007 / BF01343730 . S2CID 120383146 . 

• https://mathworld.wolfram.com/TagSystem.html
• https://mathworld.wolfram.com/CyclicTagSystem.html
• https://www.wolframscience.com/nks/p95/ (أنظمة الوسم الدوري)
• https://www.wolframscience.com/nks/p669/ (محاكاة أنظمة الوسوم)