Ikkilik kombinatsion mantiq - Binary combinatory logic
 | Bu maqola tushunarsiz bo'lishi yoki tushunishi juda qiyin bo'lishi mumkin. (Iyul 2020) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
 | Bu maqola mavzu bilan tanish bo'lmaganlar uchun etarli bo'lmagan kontekstni taqdim etadi. (Iyul 2020) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Ikkilik kombinatsion mantiq (BCL) ning formulasidir kombinatsion mantiq faqat 0 va 1 belgilaridan foydalangan holda.[1] BCL dastur o'lchamlari murakkabligi nazariyasida dasturlarga ega (Kolmogorovning murakkabligi ).[1][2]
Ta'rif
Sintaksis
<muddat> ::= 00 | 01 | 1 <muddat> <muddat>Semantik
The denotatsion semantika BCL quyidagicha ko'rsatilishi mumkin:
[ 00 ] == K[ 01 ] == S[1] == ([ ] [ ])
qayerda "[...]ma'nosini "qisqartiradi" ...". Bu yerda K va S ular KS-baza kombinatorlari va ( ) bo'ladi dastur operatsiya, ning kombinatsion mantiq. (Prefiks 1 chap qavsga to'g'ri keladi, o'ng qavs ajratish uchun keraksiz.)
Shunday qilib, uchlikni (K, S, chap qavs) kodlash uslubiga qarab, BCL ning to'rtta ekvivalent formulasi mavjud. Bular (00, 01, 1) (hozirgi versiyada bo'lgani kabi), (01, 00, 1), (10, 11, 0)va (11, 10, 0).
The operatsion semantika BCL, eta-reduksiyadan tashqari (bu shart emas Turing to'liqligi ), quyidagilar tomonidan juda ixcham belgilanishi mumkin qayta yozish berilgan muddat subtermlari uchun qoidalar, tahlil qilish chapdan:
1100xy → x11101xyz → 11xz1yz
qayerda x, yva z o'zboshimchalik bilan subtermiyalardir. (E'tibor bering, masalan, ajralish chapdan, 10000 subtermi emas 11010000.)
Shuningdek qarang
Adabiyotlar
- ^ a b Tromp, Jon (2007), "Ikkilik lambda hisobi va kombinatsion mantiq", Tasodifiylik va murakkablik (PDF), Jahon ilmiy ishlari. Publ., Hackensack, NJ, 237–260 betlar, CiteSeerX 10.1.1.695.3142, doi:10.1142/9789812770837_0014, ISBN 978-981-277-082-0, JANOB 2427553.
- ^ Devine, Shon (2009), "Algoritmik entropiya tushunchalari", Entropiya, 11 (1): 85–110, doi:10.3390 / e11010085, JANOB 2534819