BIT 술어

BIT predicate

수학과 컴퓨터 과학에서, BIT 술어 또는 Ackermann 부호화(BIT(i, j)는 숫자 i의 j번째 비트가 1인지 여부를 테스트하는 술어이다.

역사

BIT 술어는 1937년 빌헬름 아커만에 의해 그의 논문 "일반 집합론의 [1][2]일관성"에서 유전적으로 유한 집합을 자연수로 인코딩하는 것으로 처음 소개되었습니다.

이 부호화에서는, 각 자연수는 유한 집합을 부호화해, 각 유한 집합을 자연수로 나타낸다.X의 부호화X})가 " { 로 되어 있는 경우, 이 부호화는 다음과 같이 재귀적으로 정의됩니다.

2진수 체계에서는 n ( n=\(가 유한 X X를 인코딩하고i{\ n의 i {\ i번째 이진수가 i 로 인코딩됩니다X의(\ X입니다.따라서 숫자의 BIT 술어는 이 부호화 아래에서 유전적으로 유한한 집합 간의 멤버쉽 관계에 직접 대응합니다.

Ackermann 부호화는 원시 재귀 [3]함수입니다.

실행

올바른 시프트 연산자를 제공하는 C, C++, Java 또는 Python 등의 프로그래밍 언어 >>및 비트 부울 및 연산자 &BIT 술어 BIT(i, j)는 다음 식에 의해 구현될 수 있습니다.(i>>j)&1여기서 i의 비트는 i의 바이너리 표현에서 하위 비트부터 상위 비트까지 번호가 매겨지며, 1비트는 비트 [4]0으로 번호가 매겨집니다.

개인 정보 검색

컴퓨터 보안의 수학적 연구에서 개인정보 검색 문제는 클라이언트가 2진수 i를 격납하는 서버 집합과 통신하면서 서버에 j의 값을 누설하지 않고 BIT 술어 BIT(i, j)의 결과를 결정하기를 원하는 것으로 모델링할 수 있다.Chor et al.(1998)는 클라이언트가 [5]i의 완전한 값을 회복하는 데 필요한 것보다 훨씬 적은 양의 통신을 사용하여 개인 정보 검색 문제를 해결할 수 있도록 2개의 서버에 걸쳐 i를 복제하는 방법을 설명한다.

수리논리

BIT 술어는 종종 1차 로직의 맥락에서 조사됩니다.논리 시스템은 BIT 술어를 1차 로직에 추가하는 것으로부터 발생합니다.기술 복잡도에서는 BIT 술어를 FO에 추가한 복잡도 클래스 FO + BIT에 의해 보다 견고한 복잡도 [6]클래스가 생성됩니다.BIT 술어가 있는 1차 로직의 클래스 FO + BIT는 더하기 및 곱하기 [7]술어가 있는 1차 로직의 클래스 FO + PLUS + TIMES와 동일합니다.

Rado 그래프 구성

Rado 그래프: 예를 들어 0번째 비트 3이 0이 아니기 때문에 0에서 3까지의 에지가 있습니다.

1937년 애커만과 1964년 리처드 라도는 무한 라도 그래프를 만들기 위해 이 술어를 사용했다.이들의 구성에서 이 그래프의 정점은 2진법으로 쓰여진 음이 아닌 정수에 대응하며, BIT(j,i)가 [8]0이 아닐 때 i < j에 대해 정점 i에서 정점 j까지 무방향 에지가 있다.

레퍼런스

  1. ^ Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Mathematische Annalen. 114: 305–315. doi:10.1007/bf01594179. S2CID 120576556. Retrieved 2012-01-09.
  2. ^ Kirby, Laurence (2009). "Finitary Set Theory". Notre Dame Journal of Formal Logic. 50 (3): 227–244. doi:10.1215/00294527-2009-009.
  3. ^ Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. p. 261. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
  4. ^ 를 클릭합니다Venugopal, K. R. (1997). Mastering C++. Muhammadali Shaduli. p. 123. ISBN 9780074634547..
  5. ^ 를 클릭합니다Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu (1998). "Private information retrieval". Journal of the ACM. 45 (6): 965–981. doi:10.1145/293347.293350. S2CID 544823..
  6. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.
  7. ^ 임머맨(1999년, 페이지 14-16년)
  8. ^ 를 클릭합니다Rado, Richard (1964). "Universal graphs and universal functions" (PDF). Acta Arith. 9 (4): 331–340. doi:10.4064/aa-9-4-331-340..