이항 결합 논리학

Binary combinatory logic

BCL(Binary conbinatory logic, BCL)은 0과 1의 이진 용어를 사용하여 기호 0과 1만을 사용하여 완전한 결합 논리 제형을 만드는 컴퓨터 프로그래밍 언어다.[1] S와 K 결합기를 사용하면 복잡한 부울 대수 함수를 만들 수 있다. BCL은 프로그램 크기 복잡성 이론(콜모고로프 복잡성)에 응용이 있다.[1][2]

정의

S-K 베이시스

결합 논리학의 K와 S 결합기를 활용하면 논리 함수는 다음과 같이 결합자의 함수로 나타낼 수 있다.

이진 결합기로서의[3] 논리 연산 목록
부울 대수 S-K 베이시스
참(1) K(KK)
거짓(0) K(K(SK))s
AND SSK
NOT SS(S(SK)S)(KK)
OR S(SS)S(SK)
낸드 S(S(S(SS(K)(KK))))))))s
NOR S(S)(SS(K(K)))(KS))
XOR S(S(S)(S(SK))S)K

구문

Backus-Naur 형식: 

 <기간> ::=00 01 1 <기간> <기간>

의미론

BCL의 부조적 의미론은 다음과 같이 지정할 수 있다.

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

"이곳[...]"의 의미를 약화시킨다" ...". 여기 K 그리고 S KS-basis 콤비네이터, 그리고 ( ) 전투 논리의 응용 연산이다. (접두사) 1 왼쪽 괄호에 해당하며, 오른쪽 괄호는 해체를 위해 필요하지 않다.)

따라서 세 쌍둥이를 인코딩하는 방식(K, S, 왼쪽 괄호)에 따라 BCL의 등가 공식은 4가지가 있다. 이것들은 (00, 01, 1) (현재 버전과 같음), (01, 00, 1), (10, 11, 0)그리고 (11, 10, 0).

ECL의 운영 의미론(Turing 완전성을 위해 필요하지 않은)은 eta 축소와는 별도로, 특정 용어의 하위 용어에 대해 왼쪽에서 구문 분석하여 다음과 같은 재작성 규칙에 의해 매우 압축적으로 명시될 수 있다.

  • 1100xy → x
  • 11101xyz → 11xz1yz

어디에 x, y그리고 z 임의 하위단어(예를 들어, 파싱은 왼쪽에서 시작되므로, 10000 의 하위 용어가 아니다. 11010000.)

SK-Basis의 규칙 110 셀룰러 오토마타(Wolfram Language)의 한 단계.[3]

BCL은 Turing machine과 Cellular automata와 같은 알고리즘을 복제하는데 사용될 수 있으며,[3] BCL은 Turing complete이다.

참고 항목

참조

  1. ^ a b Tromp, John (2007), "Binary lambda calculus and combinatory logic", Randomness and complexity (PDF), World Sci. Publ., Hackensack, NJ, pp. 237–260, CiteSeerX 10.1.1.695.3142, doi:10.1142/9789812770837_0014, ISBN 978-981-277-082-0, MR 2427553.
  2. ^ Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, doi:10.3390/e11010085, MR 2534819
  3. ^ a b c Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com. Retrieved 2021-02-17.

추가 판독값

  • Tromp, John (October 2007). "Binary Lambda Calculus and Combinatory Logic". Randomness and Complexity, From Leibniz to Chaitin: 237–260. doi:10.1142/9789812770837_0014.

외부 링크