الشكل الطبيعي (إعادة الكتابة المجردة)

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

بصورة رسمية، إذا كان ( A ،→) نظام إعادة كتابة مجرد ، فإن x ∈ A يكون في شكل طبيعي إذا لم يكن هناك y ∈ A بحيث x → y ، أي أن x هو مصطلح غير قابل للاختزال.

يكون الكائن a ضعيف التطبيع إذا وُجد على الأقل تسلسل واحد محدد من عمليات إعادة الكتابة يبدأ من a ويؤدي في النهاية إلى شكل طبيعي. يتمتع نظام إعادة الكتابة بخاصية التطبيع الضعيف أو يكون مُطَبِّعًا (ضعيفًا) (WN) إذا كان كل كائن فيه ضعيف التطبيع. يكون الكائن a قوي التطبيع إذا انتهى كل تسلسل من عمليات إعادة الكتابة يبدأ من a في النهاية بشكل طبيعي. يكون نظام إعادة الكتابة قوي التطبيع ، أو مُنهيًا ، أو نوثيريًا ، أو يتمتع بخاصية التطبيع (القوي) (SN)، إذا كان كل كائن من كائناته قوي التطبيع. ^{[ 2 ]}

يتمتع نظام إعادة الكتابة بخاصية الشكل الطبيعي (NF) إذا كان لكل عنصر a وشكله الطبيعي b ، يمكن الوصول إلى b من a بسلسلة من عمليات إعادة الكتابة، وإعادة الكتابة العكسية فقط إذا اختُزل a إلى b . يتمتع نظام إعادة الكتابة بخاصية الشكل الطبيعي الفريد (UN) إذا كان لكل شكل طبيعي a ، b ∈ S ، يمكن الوصول إلى a من b بسلسلة من عمليات إعادة الكتابة، وإعادة الكتابة العكسية فقط إذا كان a مساويًا لـ b . يتمتع نظام إعادة الكتابة بخاصية الشكل الطبيعي الفريد فيما يتعلق بالاختزال (UN ^→ ) إذا كان لكل حد يُختزل إلى الشكلين الطبيعيين a و b ، يكون a مساويًا لـ b . ^{[ 3 ]}

يعرض هذا القسم بعض النتائج المعروفة. أولاً، SN يستلزم WN. ^{[ 4 ]}

الالتقاء (يُختصر بـ CR) يستلزم NF، ويستلزم UN، ويستلزم UN ^→ . ^{[ 3 ]} لا تصح الاستدلالات العكسية عمومًا. {a→b,a→c,c→c,d→c,d→e} هو UN ^→ ولكنه ليس UN لأن b=e و b و e صيغتان طبيعيتان. {a→b,a→c,b→b} هو UN ولكنه ليس NF لأن b=c، و c صيغة طبيعية، و b لا يُختزل إلى c. {a→b,a→c,b→b,c→c} هو NF لعدم وجود صيغ طبيعية، ولكنه ليس CR لأن a يُختزل إلى b و c، و b و c ليس لهما اختزال مشترك.

WN و UN ^→ يستلزمان التقاء. وبالتالي، فإن CR و NF و UN و UN ^→ تتطابق إذا تحققت WN. ^{[ 5 ]}

أحد الأمثلة على ذلك هو أن تبسيط التعبيرات الحسابية ينتج عنه عدد - في الحساب، جميع الأعداد لها أشكال طبيعية. ومن الحقائق اللافتة للنظر أن جميع التعبيرات الحسابية لها قيمة فريدة، لذا فإن نظام إعادة الكتابة يتميز بالتطبيع القوي والتقارب: ^{[ 6 ]}

(3 + 5) × (1 + 2) ⇒ 8 × (1 + 2) ⇒ 8 × 3 ⇒ 24

(3 + 5) × (1 + 2) ⇒ (3 + 5) × 3 ⇒ 3 × 3 + 5 × 3 ⇒ 9 + 5 × 3 ⇒ 9 + 15 ⇒ 24

من أمثلة الأنظمة غير المعيارية (لا ضعيفة ولا قوية) العد إلى ما لا نهاية (1 ⇒ 2 ⇒ 3 ⇒ ...) والحلقات مثل دالة التحويل في حدسية كولاتز (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...، ولا تزال مسألة وجود حلقات أخرى لتحويل كولاتز مفتوحة). ^{[ 7 ]} مثال آخر هو نظام القاعدة الواحدة { r ( x , y )  → r ( y , x ) }، الذي لا يمتلك خصائص معيارية، إذ يبدأ من أي حد، مثلاً r (4,2)، تسلسل إعادة كتابة واحد، وهو r (4,2) → r (2,4) → r (4,2) → r (2,4) → ...، وهو تسلسل لا نهائي الطول. وهذا يقود إلى فكرة إعادة صياغة " التبديلية المعيارية " حيث يكون الحد في شكله الطبيعي إذا لم تنطبق عليه أي قواعد سوى التبديلية. ^{[ 8 ]}         

النظام { b → a , b → c , c → b , c → d } (الموضح في الصورة) هو مثال على نظام تطبيع ضعيف ولكنه ليس نظام تطبيع قوي. a و d هما شكلان طبيعيان، ويمكن اختزال b و c إلى a أو d ، ولكن الاختزال اللانهائي b → c → b → c → ... يعني أن b ولا c ليسا نظام تطبيع قوي.

• الشكل القانوني
• حساب التفاضل والتكامل لامدا المكتوب
• إعادة الصياغة
• البرمجة الوظيفية الكاملة
• حدسية باريندريجت – جيوفيرز – كلوب
• معضلة نيومان
• التطبيع عن طريق التقييم