معضلة نيومان

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
📷 يحتوي على 26 صور
الموسوعة الحرة

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

أثبت ماكس نيومان هذه اللمة لأول مرة عام ١٩٤٢. [ ١ ] [ ٢ ] واقترح جيرار هويه برهانًا أبسط بكثير (مذكور أدناه) . [ ٣ ] وهناك عدد من البراهين الأخرى. [ ٤ ]

بيان وإثبات

اللمة تركيبية بحتة وتنطبق على أي علاقة. ونظرًا للسياق الذي تُطبق فيه عادةً، فقد وردت أدناه بمصطلحات أنظمة إعادة الكتابة المجردة (وهي ببساطة مجموعة تُسمى عناصرها مصطلحات، مزودة بعلاقة).→{\displaystyle \to }يُطلق عليه اسم الاختزال، وانظر المقالة المقابلة لتعريفات الإنهاء، والالتقاء، والالتقاء المحلي، والأشكال الطبيعية).

مبرهنة نيومان ( [ 5 ] [ 6 ] [ 7 ] [ 8 ] ) — إذا كان نظام إعادة الكتابة المجرد منتهيًا ومتقاربًا محليًا، فإنه متقارب، ولكل مصطلح شكل طبيعي فريد . 

دليل

لأن→{\displaystyle \to }عند انتهاء العملية، يمكننا إجراء استقراء مدروس جيدًا علىu{\displaystyle u}على امتداد→{\displaystyle \to }نثبت أن كل رسم بياني

رسم تخطيطي مع أسهم u → ∗ v , u → ∗ w {\displaystyle u\to ^{*}v,u\to ^{*}w} (الأسهم منقطة للتعبير عن أنها تمثل تسلسلات من عدد كبير من خطوات الاختزال)
رسم تخطيطي بالأسهمu→*v،u→*w{\displaystyle u\to ^{*}v,u\to ^{*}w}(الأسهم منقطة للتعبير عن أنها تمثل تسلسلات من خطوات اختزال متعددة بشكل تعسفي)

يمكن توسيع ذلك ليشمل رسمًا تخطيطيًا

رسم بياني بأسهم u → ∗ v → ∗ t , u → ∗ w → ∗ t {\displaystyle u\to ^{*}v\to ^{*}t,u\to ^{*}w\to ^{*}t}
رسم تخطيطي بالأسهمu→*v→*ت،u→*w→*ت{\displaystyle u\to ^{*}v\to ^{*}t,u\to ^{*}w\to ^{*}t}

حيث تمثل الأسهم المنقطة تسلسلات من عمليات اختزال عديدة بشكل تعسفي بواسطة→{\displaystyle \to }.

الحالة الأساسية: إذاu=v{\displaystyle u=v}أوu=w{\displaystyle u=w}هذا أمر تافه.

الخطوة الاستقرائية: وإلا، فسيكون لدينا على الأقل اختزال واحد على كل جانب:

alt=مخطط مع أسهم u → v 0 → ∗ v , u → w 0 → ∗ w {\displaystyle u\to v_{0}\to ^{*}v,u\to w_{0}\to ^{*}w}
alt=رسم تخطيطي مع أسهمu→v0→*v،u→w0→*w{\displaystyle u\to v_{0}\to ^{*}v,u\to w_{0}\to ^{*}w}

من خلال التقاء المناطق المحلية، يمكن توسيع هذا المخطط ليشمل:

alt=مخطط مع أسهم u → v 0 → ∗ v , u → w 0 → ∗ w , v 0 → ∗ t , w 0 → ∗ t {\displaystyle u\to v_{0}\to ^{*}v,u\to w_{0}\to ^{*}w,v_{0}\to ^{*}t,w_{0}\to ^{*}t}
alt=رسم تخطيطي مع أسهمu→v0→*v،u→w0→*w،v0→*ت،w0→*ت{\displaystyle u\to v_{0}\to ^{*}v,u\to w_{0}\to ^{*}w,v_{0}\to ^{*}t,w_{0}\to ^{*}t}

ثم عن طريق فرضية الاستقراء علىv0{\displaystyle v_{0}}:

alt=مخطط مع أسهم u → v 0 → ∗ v → ∗ v 1 , u → w 0 → ∗ t → ∗ v 1 , v 0 → ∗ t , w 0 → ∗ w {\displaystyle u\to v_{0}\to ^{*}v\to ^{*}v_{1},u\to w_{0}\to ^{*}t\to ^{*}v_{1},v_{0}\to ^{*}t,w_{0}\to ^{*}w}
alt=رسم تخطيطي مع أسهمu→v0→*v→*v1،u→w0→*ت→*v1،v0→*ت،w0→*w{\displaystyle u\to v_{0}\to ^{*}v\to ^{*}v_{1},u\to w_{0}\to ^{*}t\to ^{*}v_{1},v_{0}\to ^{*}t,w_{0}\to ^{*}w}

وأخيرًا، من خلال فرضية الاستقراء علىw0{\displaystyle w_{0}}:

alt=مخطط بالأسهم u → v 0 → ∗ v → ∗ v 1 → ∗ w 1 , u → w 0 → ∗ t → ∗ v 1 , v 0 → ∗ t , w 0 → ∗ w → ∗ w 1 {\displaystyle u\to v_{0}\to ^{*}v\to ^{*}v_{1}\to ^{*}w_{1},u\to w_{0}\to ^{*}t\to ^{*}v_{1},v_{0}\to ^{*}t,w_{0}\to ^{*}w\to ^{*}w_{1}}
alt=رسم تخطيطي مع أسهمu→v0→*v→*v1→*w1،u→w0→*ت→*v1،v0→*ت،w0→*w→*w1{\displaystyle u\to v_{0}\to ^{*}v\to ^{*}v_{1}\to ^{*}w_{1},u\to w_{0}\to ^{*}t\to ^{*}v_{1},v_{0}\to ^{*}t,w_{0}\to ^{*}w\to ^{*}w_{1}}

مبرهنة إريكسون لخاصية المضلع

وقد أظهر كيمو إريكسون نتيجةً مشابهةً في عام 1993. [ 9 ] [ 10 ] تذكر أن نظام إعادة الكتابة المجرد يكون متقاربًا محليًا إذا كان لأي اختزالينأ→ب{\displaystyle a\to b}وأ→ج{\displaystyle a\to c}، يوجدد{\displaystyle d}بحيثب→*د{\displaystyle b\to ^{*}d}وج→*د{\displaystyle c\to ^{*}d}وإذا كان مطلوبًا بالإضافة إلى ذلك أن تكون سلاسل التخفيضب→*د{\displaystyle b\to ^{*}d}وج→*د{\displaystyle c\to ^{*}d}إذا كان للنظام نفس الطول، فإنه يُقال إنه يتمتع بخاصية المضلع . ومن أمثلة أنظمة إعادة الكتابة التي تتمتع بخاصية المضلع: فرز الفقاعات ولعبة إطلاق الرقائق .

مبرهنة خاصية المضلع لإريكسون ( [ 9 ] [ 10 ] ) - إذا كان نظام إعادة الكتابة المجرد منتهيًا وله خاصية المضلع، فإنه يكون متقاربًا، وكل سلسلة منتهية من الاختزالات من حالة معينة لها نفس الطول. 

دليل

بحسب نظرية نيومان، فإن النظام متصل، ولكل عنصر شكل طبيعي فريد. لكل عنصرu{\displaystyle u}، يُعرِّفرل(u){\displaystyle rl(u)}ليكن طول أقصر سلسلة اختزال منu{\displaystyle u}إلى شكله الطبيعي.

التنصيبرل(u){\displaystyle rl(u)}. لورل(u)=0{\displaystyle rl(u)=0}، ثمu{\displaystyle u}هو بالفعل في شكله الطبيعي. وإلا،رل(u)≥1{\displaystyle rl(u)\geq 1}ونطبق خاصية المضلع وفرضية الاستقراء.

مراجع

  1. ↑ نيومان، ماكس (1942). "حول النظريات ذات التعريف التوافقي لـ "التكافؤ"". حوليات الرياضيات . 43 (2): 223– 243.
  2. ↑ فان أوستروم، فينسنت. "برهان نيومان على لِمّة نيومان" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 15 أبريل 2024.
  3. ↑ هويه، جيرار (1980). "الاختزالات المتقاربة: الخصائص المجردة وتطبيقاتها على أنظمة إعادة كتابة المصطلحات" . مجلة ACM . 27 (4): 797-821 . doi : 10.1145/322217.322230 .
  4. ↑ كلوب، يان ويليم (1990). "أنظمة إعادة كتابة المصطلحات: من تشرش-روسر إلى كنوت-بنديكس وما بعدهما". الأوتوماتا واللغات والبرمجة: الندوة الدولية السابعة عشرة . سلسلة محاضرات في علوم الحاسوب . المجلد 443. جامعة وارويك، إنجلترا: سبرينغر. الصفحات 350-369 . doi : 10.1007/BFb0032044 . ISBN   978-3-540-52826-5.
  5. ↑ بادر، فرانز؛ نيبكو، توبياس (1998). إعادة صياغة المصطلحات وما إلى ذلك . مطبعة جامعة كامبريدج. doi : 10.1017/CBO9781139172752 . ISBN 0-521-77920-0.
  6. ↑ تيريز (2003). أنظمة إعادة كتابة المصطلحات . سلسلة كامبريدج في علوم الحاسوب النظرية. مطبعة جامعة كامبريدج.
  7. ↑ هاريسون، جون (2009). دليل المنطق العملي والاستدلال الآلي . مطبعة جامعة كامبريدج. ص 260. ISBN  978-0-521-89957-4.
  8. ↑ كوهن، بول موريتز (1980). الجبر الشامل . دار نشر دي. ريدل. الصفحات 25-26 . ISBN  90-277-1254-9.
  9. 1 2 إريكسون، كيمو (1993). الألعاب المتقاربة بقوة ومجموعات كوكسيتر (أطروحة دكتوراه). ستوكهولم: KTH .
  10. 1 2 إريكسون، كيمو (1996). "التقارب القوي ولعبة الأرقام". المجلة الأوروبية للتوافقية . 17 (4): 379-390 . doi : 10.1006/eujc.1996.0031 .