نظام شبه ثيو

في علوم الحاسوب النظرية والمنطق الرياضي ، يُعرف نظام إعادة كتابة السلاسل ( SRS ) ، والذي كان يُطلق عليه تاريخيًا نظام شبه-ثو ، بأنه نظام إعادة كتابة للسلاسل من أبجدية (عادةً ما تكون محدودة ) . بالنظر إلى علاقة ثنائية${\displaystyle R}$بين سلاسل ثابتة على الأبجدية، تسمى قواعد إعادة الكتابة ، ويرمز لها بـ${\displaystyle s\rightarrow t}$، يقوم نظام التكرار المتسلسل (SRS) بتوسيع علاقة إعادة الكتابة لتشمل جميع السلاسل التي يظهر فيها الجانب الأيسر والأيمن من القواعد كسلاسل فرعية ، أي${\displaystyle usv\rightarrow utv}$، أين${\displaystyle s}$،${\displaystyle t}$،${\displaystyle u}$، و${\displaystyle v}$هي سلاسل نصية.

يتطابق مفهوم نظام شبه-ثو بشكل أساسي مع عرض أحادي . وبالتالي، فإنهما يشكلان إطارًا طبيعيًا لحل مشكلة الكلمات للأحاديات والمجموعات.

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

نظام إعادة كتابة السلاسل أو نظام شبه ثو هو عبارة عن مجموعة من العناصر${\displaystyle (\Sigma ,R)}$أين

• ${\displaystyle \Sigma }$هي أبجدية، يُفترض عادةً أنها محدودة. ^{[ 5 ]} عناصر المجموعة${\displaystyle \Sigma ^{*}}$(* هي نجمة كلين هنا) هي سلاسل محدودة (ربما فارغة) على${\displaystyle \Sigma }$تُسمى أحيانًا بالكلمات في اللغات الرسمية ؛ وسنسميها هنا ببساطة بالسلاسل النصية.
• ${\displaystyle R}$هي علاقة ثنائية على السلاسل من${\displaystyle \Sigma }$، أي،${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$كل عنصر${\displaystyle (u,v)\in R}$يُطلق عليها اسم قاعدة (إعادة الكتابة) وعادة ما تُكتب${\displaystyle u\rightarrow v}$.

إذا كانت العلاقة${\displaystyle R}$إذا كان النظام متناظرًا ، فإنه يُسمى نظام ثو .

قواعد إعادة الكتابة في${\displaystyle R}$يمكن توسيع ذلك بشكل طبيعي ليشمل سلاسل أخرى في${\displaystyle \Sigma ^{*}}$عن طريق السماح بإعادة كتابة السلاسل الفرعية وفقًا لـ${\displaystyle R}$بصورة أكثر رسمية، علاقة إعادة الكتابة بخطوة واحدة${\displaystyle {\xrightarrow[{R}]{}}}$ناتج عن${\displaystyle R}$على${\displaystyle \Sigma ^{*}}$لأي سلاسل${\displaystyle s,t\in \Sigma ^{*}}$:

${\displaystyle s{\xrightarrow[{R}]{}}t}$إذا وفقط إذا كان هناك${\displaystyle x,y,u,v\in \Sigma ^{*}}$بحيث${\displaystyle s=xuy}$،${\displaystyle t=xvy}$، و${\displaystyle u\rightarrow v}$.

منذ${\displaystyle {\xrightarrow[{R}]{}}}$هي علاقة على${\displaystyle \Sigma ^{*}}$الزوجان${\displaystyle (\Sigma ^{*},{\xrightarrow[{R}]{}})}$يتوافق مع تعريف نظام إعادة الكتابة المجردة . من الواضح${\displaystyle R}$هي مجموعة فرعية من${\displaystyle {\xrightarrow[{R}]{}}}$يستخدم بعض المؤلفين رمزًا مختلفًا للسهم في${\displaystyle {\xrightarrow[{R}]{}}}$(مثال)${\displaystyle {\underset {R}{\Rightarrow }}}$) وذلك لتمييزه عن${\displaystyle R}$نفسها (${\displaystyle \rightarrow }$) لأنهم يريدون لاحقًا أن يكونوا قادرين على حذف الرمز السفلي مع الاستمرار في تجنب الالتباس بين${\displaystyle R}$وإعادة الكتابة بخطوة واحدة الناتجة عن${\displaystyle R}$.

من الواضح أنه في نظام شبه ثو، يمكننا تكوين سلسلة (محدودة أو غير محدودة) من السلاسل الناتجة عن البدء بسلسلة أولية${\displaystyle s_{0}\in \Sigma ^{*}}$وإعادة كتابتها بشكل متكرر عن طريق استبدال سلسلة فرعية واحدة في كل مرة:

${\displaystyle s_{0}\ {\xrightarrow[{R}]{}}\ s_{1}\ {\xrightarrow[{R}]{}}\ s_{2}\ {\xrightarrow[{R}]{}}\ \ldots }$

يمكن تمثيل إعادة الصياغة التي تتضمن صفرًا أو أكثر من الخطوات من خلال الإغلاق المتعدي الانعكاسي لـ${\displaystyle {\xrightarrow[{R}]{}}}$، ويرمز إليه بـ${\displaystyle {\xrightarrow[{R}]{*}}}$(انظر نظام إعادة الكتابة المجرد#المفاهيم الأساسية ). يُطلق على هذا اسم علاقة إعادة الكتابة أو علاقة الاختزال .${\displaystyle \Sigma ^{*}}$ناتج عن${\displaystyle R}$.

بشكل عام، المجموعة${\displaystyle \Sigma ^{*}}$تشكل السلاسل النصية على أبجدية ما شبه زمرة حرة مع العملية الثنائية لدمج السلاسل النصية ( يرمز لها بـ${\displaystyle \cdot }$وتُكتب بشكل ضربي عن طريق حذف الرمز). في نظام الاختزال البسيط، علاقة الاختزال${\displaystyle {\xrightarrow[{R}]{*}}}$متوافق مع عملية المونويد، مما يعني أن${\displaystyle x{\xrightarrow[{R}]{*}}y}$يشير إلى${\displaystyle uxv{\xrightarrow[{R}]{*}}uyv}$لجميع السلاسل${\displaystyle x,y,u,v\in \Sigma ^{*}}$. منذ${\displaystyle {\xrightarrow[{R}]{*}}}$هو بحكم التعريف طلب مسبق ،${\displaystyle \left(\Sigma ^{*},\cdot ,{\xrightarrow[{R}]{*}}\right)}$يشكل ترتيبًا جزئيًا أحاديًا .

وبالمثل، فإن الإغلاق الانعكاسي المتعدي المتناظر لـ${\displaystyle {\xrightarrow[{R}]{}}}$، المشار إليه${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$(انظر نظام إعادة الكتابة المجرد#المفاهيم الأساسية )، هي علاقة تطابق ، أي أنها علاقة تكافؤ (بحكم التعريف)، وهي متوافقة أيضًا مع دمج السلاسل النصية.${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$يُطلق عليها اسم تطابق ثو الناتج عن R. في نظام ثو، أي إذا كان R متناظرًا، فإن علاقة إعادة الكتابة${\displaystyle {\xrightarrow[{R}]{*}}}$يتطابق مع تطابق ثو${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$.

منذ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$إذا كانت تطابقًا، فيمكننا تعريف أحادي العامل${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$من المونويد الحر${\displaystyle \Sigma ^{*}}$باستخدام تطابق ثو بالطريقة المعتادة . إذا كان أحاديًا${\displaystyle {\mathcal {M}}}$متماثل مع​${\displaystyle {\mathcal {M}}_{R}}$ثم نظام شبه ثو${\displaystyle (\Sigma ,R)}$يُطلق عليه اسم عرض أحادي لـ${\displaystyle {\mathcal {M}}}$.

نحصل فورًا على بعض الروابط المفيدة جدًا مع مجالات أخرى في الجبر. على سبيل المثال، الأبجدية { a , b } مع القواعد { ab → ε, ba → ε}، حيث ε هي السلسلة الفارغة ، هي تمثيل للمجموعة الحرة على مولد واحد. أما إذا كانت القواعد { ab → ε} فقط، فسنحصل على تمثيل للمونويد ثنائي الدورة .

تتعزز أهمية أنظمة شبه-ثو كعرض للمونيدات من خلال ما يلي:

نظرية : كل أحادي له تمثيل على الشكل${\displaystyle (\Sigma ,R)}$وبالتالي، يمكن تمثيلها دائمًا بنظام شبه-ثو، وربما على أبجدية لا نهائية. ^{[ 6 ]}

في هذا السياق، المجموعة${\displaystyle \Sigma }$تُسمى مجموعة مولدات${\displaystyle {\mathcal {M}}}$، و${\displaystyle R}$يُطلق عليها مجموعة العلاقات المحددة${\displaystyle {\mathcal {M}}}$يمكننا تصنيف المونيدات على الفور بناءً على طريقة عرضها.${\displaystyle {\mathcal {M}}}$يُطلق عليه اسم

• مولدة بشكل نهائي إذا${\displaystyle \Sigma }$محدود.
• يتم تقديمها بشكل نهائي إذا كان كلاهما${\displaystyle \Sigma }$و${\displaystyle R}$محدودة.

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

بشكل ملموس، ابتكر بوست ترميزًا على شكل سلسلة محدودة لحالة آلة تورينج بالإضافة إلى شريط، بحيث يمكن تنفيذ إجراءات هذه الآلة بواسطة نظام إعادة كتابة السلاسل الذي يعمل على ترميز السلسلة هذا. تتكون أبجدية الترميز من مجموعة واحدة من الأحرف.${\displaystyle S_{0},S_{1},\dotsc ,S_{m}}$بالنسبة للرموز الموجودة على الشريط (حيث${\displaystyle S_{0}}$(فارغ)، مجموعة أخرى من الأحرف${\displaystyle q_{1},\dotsc ,q_{r}}$بالنسبة لحالات آلة تورينج، وأخيراً ثلاثة أحرف${\displaystyle q_{r+1},q_{r+2},h}$التي لها أدوار خاصة في عملية الترميز.${\displaystyle q_{r+1}}$و${\displaystyle q_{r+2}}$هي حالات داخلية إضافية بديهية لآلة تورينج تنتقل إليها عند التوقف، بينما${\displaystyle h}$يشير إلى نهاية الجزء غير الفارغ من الشريط؛ آلة تصل إلى${\displaystyle h}$ينبغي أن يتصرف بنفس الطريقة كما لو كان هناك فراغ، و${\displaystyle h}$كانت في الخلية التالية. تبدأ السلاسل التي تمثل ترميزات صالحة لحالات آلة تورينج بـ${\displaystyle h}$، متبوعًا بصفر أو أكثر من أحرف الرموز، متبوعًا بحرف حالة داخلي واحد فقط${\displaystyle q_{i}}$(الذي يرمز إلى حالة الآلة)، متبوعًا بحرف رمزي واحد أو أكثر، متبوعًا بنهاية${\displaystyle h}$. حروف الرمز مأخوذة مباشرة من محتويات الشريط، وحرف الحالة الداخلية يشير إلى موضع الرأس؛ الرمز الذي يلي حرف الحالة الداخلية هو الرمز الموجود في الخلية الموجودة حاليًا أسفل رأس آلة تورينج.

مرحلة انتقالية حيث تكون الآلة في حالة${\displaystyle q_{i}}$ورؤية الرمز${\displaystyle S_{k}}$يكتب الرمز الخلفي${\displaystyle S_{l}}$يتحرك إلى اليمين، وينتقل إلى الحالة${\displaystyle q_{j}}$يتم تنفيذ ذلك عن طريق إعادة الكتابة

${\displaystyle q_{i}S_{k}\to S_{l}q_{j}}$

بينما يتم تنفيذ هذا الانتقال، بدلاً من الانتقال إلى اليسار، عن طريق إعادة الكتابة

${\displaystyle S_{p}q_{i}S_{k}\to q_{j}S_{p}S_{l}}$

مع وجود نسخة واحدة لكل رمز${\displaystyle S_{p}}$في تلك الخلية إلى اليسار. في حالة وصولنا إلى نهاية الجزء الذي تمت زيارته من الشريط، نستخدم بدلاً من ذلك

${\displaystyle hq_{i}S_{k}\to hq_{j}S_{0}S_{l}}$،

إطالة السلسلة بحرف واحد. لأن جميع عمليات إعادة الكتابة تتضمن حرف حالة داخلي واحد.${\displaystyle q_{i}}$بما أن الترميزات الصحيحة لا تحتوي إلا على حرف واحد من هذا النوع، وكل عملية إعادة كتابة تُنتج حرفًا واحدًا فقط من هذا النوع، فإن عملية إعادة الكتابة تتبع بدقة مسار آلة تورينج المُرمّزة. وهذا يُثبت أن أنظمة إعادة كتابة السلاسل النصية كاملة تورينج.

سبب وجود رمزين متوقفين${\displaystyle q_{r+1}}$و${\displaystyle q_{r+2}}$يكمن هدفنا في أن تنتهي جميع آلات تورينج المتوقفة عند نفس الحالة الكلية ، وليس عند حالة داخلية معينة فقط . وهذا يتطلب مسح الشريط بعد التوقف، لذا${\displaystyle q_{r+1}}$يلتهم الرمز الموجود على يساره حتى يصل إلى${\displaystyle h}$، حيث يتحول إلى${\displaystyle q_{r+2}}$والذي بدلاً من ذلك يلتهم الرمز الموجود على يمينه. (في هذه المرحلة، لا يُحاكي نظام إعادة كتابة السلسلة آلة تورينج، لأنها لا تستطيع إزالة الخلايا من الشريط). بعد اختفاء جميع الرموز، نكون قد وصلنا إلى السلسلة النهائية.${\displaystyle hq_{r+2}h}$.

سيؤدي إجراء اتخاذ القرار بشأن المسألة اللفظية أيضًا إلى إجراء لتحديد ما إذا كانت آلة تورينج المعطاة ستتوقف عند بدء تشغيلها في حالة كلية معينة.${\displaystyle t}$، عن طريق اختبار ما إذا${\displaystyle t}$و${\displaystyle hq_{r+2}h}$تنتمي هذه العناصر إلى نفس فئة التوافق فيما يتعلق بنظام إعادة كتابة السلاسل النصية هذا. من الناحية الفنية، لدينا ما يلي:

اللمة. ليكن${\displaystyle M}$أن تكون آلة تورينج حتمية و${\displaystyle R}$كن نظام إعادة كتابة السلاسل الذي يتم تنفيذه${\displaystyle M}$كما هو موضح أعلاه. ثم${\displaystyle M}$سيتوقف عند بدء التشغيل من الحالة الكلية المشفرة كـ${\displaystyle t}$إذا وفقط إذا${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$(أي، إذا وفقط إذا${\displaystyle t}$و${\displaystyle hq_{r+2}h}$هل هذه متطابقة لـ${\displaystyle R}$).

الذي - التي${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$لو${\displaystyle M}$يتوقف عند بدء التشغيل من${\displaystyle t}$مباشرة من عملية البناء${\displaystyle R}$(ببساطة تشغيل${\displaystyle M}$إلى أن يتوقف، يقوم ببناء برهان على${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$)، لكن${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$كما يسمح ذلك لآلة تورينج${\displaystyle M}$التراجع إلى الوراء. وهنا يصبح من المهم أن${\displaystyle M}$هو حتمي، لأنه في هذه الحالة تكون جميع الخطوات الأمامية فريدة؛ في${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$المشي من${\displaystyle t}$ل${\displaystyle hq_{r+2}h}$يجب أن تتبع الخطوة الأخيرة للخلف نظيرتها كخطوة للأمام، لذا فإن هاتين الخطوتين تلغي إحداهما الأخرى، وبالاستقراء يمكن حذف جميع الخطوات للخلف من هذه المسيرة. وبالتالي إذا${\displaystyle M}$لا يتوقف عند بدء التشغيل من${\displaystyle t}$أي، إذا لم يكن لدينا${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$إذن، ليس لدينا أيضاً${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$لذلك، اتخاذ القرار${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$يُخبرنا هذا بحل مشكلة التوقف لـ${\displaystyle M}$.

يتمثل أحد القيود الواضحة لهذه الحجة في أنه من أجل إنتاج شبه مجموعة${\displaystyle \Sigma ^{*}{\big /}{\overset {*}{\underset {R}{\leftrightarrow }}}}$في حالة المسائل الكلامية غير القابلة للحل، يجب أولاً أن يكون لدينا مثال ملموس لآلة تورينج${\displaystyle M}$حيث تكون مشكلة التوقف غير قابلة للحل، ولكن جميع آلات تورينغ المختلفة التي تدخل في إثبات عدم قابلية حل مشكلة التوقف العامة تتضمن كعنصر آلة تورينغ افتراضية تحل مشكلة التوقف، لذا لا يمكن لأي من هذه الآلات أن توجد فعليًا؛ كل ما يثبته ذلك هو وجود آلة تورينغ ما تكون مشكلة القرار فيها غير قابلة للحل. ومع ذلك، فإن وجود آلة تورينغ ما ذات مشكلة توقف غير قابلة للحل يعني أن مشكلة التوقف لآلة تورينغ شاملة غير قابلة للحل (لأنها تستطيع محاكاة أي آلة تورينغ)، وقد تم بناء أمثلة ملموسة لآلات تورينغ شاملة.

يُعد نظام شبه-ثو أيضًا نظامًا لإعادة كتابة المصطلحات ، وهو نظام يحتوي على كلمات أحادية (دوال) تنتهي بنفس المتغير الذي تنتهي به مصطلحات الجانبين الأيمن والأيسر، ^{[ 8 ]} على سبيل المثال قاعدة المصطلحات${\displaystyle f_{2}(f_{1}(x))\rightarrow g(x)}$وهو ما يعادل قاعدة السلسلة${\displaystyle f_{1}f_{2}\rightarrow g}$.

يُعدّ نظام شبه ثو نوعًا خاصًا من أنظمة ما بعد الكلاسيكية ، ولكن يمكن اختزال أي نظام ما بعد كلاسيكي إلى نظام شبه ثو. كلا النظامين كاملان تورينج ، وبالتالي فهما مكافئان لقواعد نعوم تشومسكي غير المقيدة ، والتي تُسمى أحيانًا قواعد شبه ثو . ^{[ 9 ]} لا تختلف القواعد الرسمية عن نظام شبه ثو إلا في فصل الأبجدية إلى رموز طرفية وغير طرفية، وتحديد رمز بداية من بين الرموز غير الطرفية. يُعرّف عدد قليل من المؤلفين نظام شبه ثو على أنه ثلاثي.${\displaystyle (\Sigma ,A,R)}$، أين${\displaystyle A\subseteq \Sigma ^{*}}$تُسمى هذه مجموعة البديهيات . وفقًا لهذا التعريف "التوليدي" لنظام شبه-ثو، فإن القواعد النحوية غير المقيدة هي ببساطة نظام شبه-ثو ذو بديهية واحدة، حيث تُقسّم الأبجدية إلى رموز طرفية وغير طرفية، وتُجعل البديهية رمزًا غير طرفي. ^{[ 10 ]} إن الحيلة البسيطة المتمثلة في تقسيم الأبجدية إلى رموز طرفية وغير طرفية هي حيلة قوية؛ إذ تسمح بتعريف التسلسل الهرمي لتشومسكي بناءً على تركيبة الرموز الطرفية وغير الطرفية التي تحتويها القواعد. كان هذا تطورًا حاسمًا في نظرية اللغات الرسمية .

في الحوسبة الكمومية، يمكن تطوير مفهوم نظام ثو الكمومي. ^{[ 11 ]} وبما أن الحوسبة الكمومية قابلة للعكس بطبيعتها، فإن قواعد إعادة الكتابة على الأبجدية${\displaystyle \Sigma }$يشترط أن تكون ثنائية الاتجاه (أي أن النظام الأساسي هو نظام ثو، وليس نظام شبه ثو). على مجموعة فرعية من أحرف الأبجدية${\displaystyle Q\subseteq \Sigma }$يمكن للمرء أن يلحق مساحة هيلبرت${\displaystyle \mathbb {C} ^{d}}$ويمكن لقاعدة إعادة الكتابة التي تنقل سلسلة فرعية إلى أخرى أن تُجري عملية وحدوية على حاصل الضرب الموتري لفضاء هيلبرت المرفق بالسلاسل؛ وهذا يعني أنها تحافظ على عدد الأحرف من المجموعة${\displaystyle Q}$على غرار الحالة الكلاسيكية، يمكن للمرء أن يثبت أن نظام ثو الكمومي هو نموذج حسابي عالمي للحوسبة الكمومية، بمعنى أن العمليات الكمومية المنفذة تتوافق مع فئات الدوائر الموحدة (مثل تلك الموجودة في BQP عند ضمان إنهاء قواعد إعادة كتابة السلسلة في غضون عدد كبير من الخطوات في حجم الإدخال)، أو بشكل مكافئ آلة تورينج الكمومية .

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

بناءً على اقتراح ألونسو تشيرش ، أثبت إميل بوست في ورقة بحثية نُشرت عام 1947 أن "مسألة معينة من مسائل ثو" غير قابلة للحل، وهو ما ذكره مارتن ديفيس بأنه "...أول برهان على عدم قابلية حل مسألة من الرياضيات الكلاسيكية - في هذه الحالة مسألة الكلمات الخاصة بأنصاف المجموعات." ^{[ 12 ]}

ويؤكد ديفيس أيضًا أن البرهان قدمه بشكل مستقل أ. أ. ماركوف . ^{[ 13 ]}

• نظام L
• خوارزمية ماركوف - نوع من أنظمة إعادة كتابة السلاسل
• لغز MU