مدار ترکیبی باینری

منطق ترکیبی دودویی (BCL) یک زبان برنامه‌نویسی کامپیوتری است که با استفاده از عبارات دودویی ۰ و ۱، یک فرمولاسیون کامل از مدار منطقی را فقط با همین نمادها ایجاد می‌کند. با استفاده از ترکیب‌کننده‌های S و K، می‌توان توابع پیچیده جبر بولی را ساخت. BCL همچنین کاربردهایی در نظریه پیچیدگی اندازه برنامه (یچیدگی کولموگوروف) دارد.

تعریف[ویرایش]

قواعد SK[ویرایش]

با استفاده از ترکیب‌کننده‌های K و S در مدار منطقی، می‌توان توابع منطقی را به‌عنوان توابعی از ترکیب‌کننده‌ها نشان داد:

لیست عملیات منطقی به عنوان ترکیب کننده های باینری ^[۱]
	جبر بولی	اساس SK
	TRUE (1)	K(KK)
	FALSE (0)	K(K(SK))
	AND	SSK
	NOT	SS(S(S(S(SK))S))(KK)
	OR	S(SS)S(SK)
	NAND	S(S(K(S(SS(K(KK)))))))S
	NOR	S(S(S(SS(K(K(KK)))))(KS))
	XOR	S(S(S(SS)(S(S(SK)))S))K

معناشناسی[ویرایش]

[ 00 ] == K
[ 01 ] == S
[ 1 < term1> < term2> ] == ( [ < term1>] [ < term2>] )

که "[...]" اختصار "معنای ..." است. در اینجا K و S تترکیب کننده‌های پایه k-s هستند و ( ) عملیات کاربرد در مدار منطقی را نشان می‌دهد. (پیشوند ۱ معادل یک پرانتز باز است و پرانتز بسته برای رفع ابهام ضروری نیست.)

بنابراین، چهار فرم معادل از BCL وجود دارد که بسته به نحوه رمزگذاری سه‌گانه (K، S، پرانتز باز) متفاوت است. این چهار فرم عبارتند از: (۰۰، ۰۱، ۱) (همانطور که در نسخه کنونی آمده)، (۰۱، ۰۰، ۱)، (۱۰، ۱۱، ۰) و (۱۱، ۱۰، ۰).

معنای عملی BCL، به جز کاهش eta (که برای کامل بودن تورینگ ضروری نیست)، می‌تواند به‌طور بسیار مختصر با قوانین بازنویسی زیر برای زیرعبارات یک عبارت مشخص، از سمت چپ بیان شود:

1100xy → x
11101xyz → 11xz1yz

که در آن x ، y ، و z زیرعبارات دلخواه هستند. (توجه کنید که به عنوان مثال، از آنجایی که تجزیه از سمت چپ انجام می‌شود، 10000 زیرعبارتی از 11010000 نیست.)

BCL می‌تواند برای بازتولید الگوریتم‌هایی مانند ماشین های تورینگ و hتوماتای سلولی استفاده شود^[۲]؛ بنابراین BCL تورینگ کامل است.

بیشتر بخوانید[ویرایش]

Iota and Jot

منابع[ویرایش]

1- خطای لوآ در پودمان:Citation/CS1/en/Identifiers در خط 47: attempt to index field 'wikibase' (a nil value)..

2- خطای لوآ در پودمان:Citation/CS1/en/Identifiers در خط 47: attempt to index field 'wikibase' (a nil value). 3-Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com (به English). Archived from the original on 2020-12-06. Retrieved 2021-02-17.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.

در ادامه مطلب[ویرایش]

خطای لوآ در پودمان:Citation/CS1/en/Identifiers در خط 47: attempt to index field 'wikibase' (a nil value).

لینک های خارجی[ویرایش]

This article "مدار ترکیبی باینری" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:مدار ترکیبی باینری. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

↑ ^۱٫۰ ^۱٫۱ Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com (به English). Archived from the original on 2020-12-06. Retrieved 2021-02-17.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
↑ Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com (به English). Archived from the original on 2020-12-06. Retrieved 2021-02-17.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.