المنطق التوافقي الثنائي
المنطق التوافقي الثنائي ( BCL ) هو لغة برمجة حاسوبية تستخدم المصطلحات الثنائية 0 و1 لإنشاء صياغة كاملة للمنطق التوافقي باستخدام الرمزين 0 و1 فقط. [ 1 ] وباستخدام مُركِّبات S وK، يُمكن إنشاء دوال جبر بولياني معقدة. ولـ BCL تطبيقات في نظرية تعقيد حجم البرنامج ( تعقيد كولموغوروف ). [ 1 ] [ 2 ]
تعريف
SK Basis
باستخدام مُركِّبات K و S في المنطق التوافقي ، يمكن تمثيل الدوال المنطقية كدوال للمُركِّبات:
| الجبر البولياني | SK Basis | |
|---|---|---|
| صحيح (1) | ك(ك ك) | |
| خطأ (0) | K(K(SK)) | |
| و | إس إس كيه | |
| لا | SS(S(S(S(SK))S))(KK) | |
| أو | S(SS)S(SK) | |
| ذاكرة NAND | S(S(K(S(SS(K(KK))))))))S | |
| ولا | S(S(S(SS(K(K(KK)))))(KS)) | |
| XOR | S(S(S(SS)(S(S(SK)))S))K |
بناء الجملة
< المصطلح > ::= 00 | 01 | 1 < المصطلح > < المصطلح >علم الدلالة
يمكن تحديد الدلالات الدلالية لـ BCL على النحو التالي :
[ 00 ] == K[ 01 ] == S[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )
حيث [...]يرمز الرمز " " إلى "معنى ...". هنا K، Sيمثل كل من و مُركِّبات أساس KS ، و ( )هي عملية التطبيق في المنطق التوافقي . (يُقابل البادئة 1قوسًا مفتوحًا، ولا حاجة للأقواس المغلقة للتوضيح).
وبالتالي، توجد أربع صيغ متكافئة لـ BCL، اعتمادًا على طريقة ترميز الثلاثية (K، S، قوس مفتوح). وهذه الصيغ (كما في النسخة الحالية) هي: ، ، و .(00, 01, 1)(01, 00, 1)(10, 11, 0)(11, 10, 0)
يمكن تحديد الدلالات التشغيلية لـ BCL، بصرف النظر عن اختزال إيتا (وهو أمر غير مطلوب لاكتمال تورينج)، بشكل مضغوط للغاية من خلال قواعد إعادة الكتابة التالية للمصطلحات الفرعية لمصطلح معين ، مع التحليل من اليسار:
1100xy → x11101xyz → 11xz1yz
حيث أن xو yو zهي مصطلحات فرعية اختيارية. (لاحظ، على سبيل المثال، أنه نظرًا لأن التحليل يتم من اليسار، 10000فإن ليس مصطلحًا فرعيًا من 11010000.)
يمكن استخدام BCL لتكرار الخوارزميات مثل آلات تورينج والأتمتة الخلوية ، [ 3 ] BCL كاملة تورينج .
انظر أيضاً
مراجع
- 1 2 ترومب، جون (2007)، "حساب لامدا الثنائي والمنطق التوافقي"، العشوائية والتعقيد (ملف PDF) ، دار النشر العالمية للعلوم، هاكنساك، نيوجيرسي، الصفحات 237-260 ، CiteSeerX 10.1.1.695.3142 ، doi : 10.1142/9789812770837_0014 ، ISBN 978-981-277-082-0MR 2427553 .
- ↑ ديفاين، شون (2009)، "رؤى حول الإنتروبيا الخوارزمية"، إنتروبي ، 11 (1): 85-110 ، Bibcode : 2009Entrp..11...85D ، doi : 10.3390/e11010085 ، MR 2534819
- 1 2 3 وولفرام، ستيفن (2021-12-06). "المُركِّبات: نظرة على الذكرى المئوية" . writings.stephenwolfram.com . arXiv : 2103.12811 . مؤرشف من الأصل في 2020-12-06 . تم الاسترجاع في 2021-02-17 .
للمزيد من القراءة
- ترومب، جون (أكتوبر 2007). "حساب لامدا الثنائي والمنطق التوافقي" . العشوائية والتعقيد، من لايبنتز إلى تشايتين : 237-260 . doi : 10.1142/9789812770837_0014 . ISBN 978-981-277-082-0.
- ترومب، جون (أبريل 2023). "البتات الوظيفية: نظرية المعلومات الخوارزمية القائمة على حساب لامدا" (ملف PDF) . tromp.github.io.
روابط خارجية
- ملعب جون لحساب التفاضل والتكامل لامدا والمنطق التوافقي
- تطبيق بسيط بلغة C
- حساب التفاضل والتكامل لامدا في 383 بايت
- براونر، بول (10 يناير 2018). "قائمة تشغيل مخططات لامدا على يوتيوب" . يوتيوب . مؤرشف من الأصل بتاريخ 21 ديسمبر 2021.
- نظرية المعلومات الخوارزمية
- المنطق التوافقي