Предикат BIT - BIT predicate

В математика и Информатика, то Предикат BIT или Кодирование Аккермана, иногда пишется BIT (я, j), это предикат который проверяет, jth немного числа я равно 1, когда я записывается в двоичном формате.

История

Предикат BIT был впервые представлен как кодирование наследственно конечные множества так как натуральные числа от Вильгельм Аккерманн в его статье 1937 года[1][2](Непротиворечивость общей теории множеств).

Каждое натуральное число кодирует конечное множество, и каждое конечное множество представлено натуральным числом. двоичная система счисления.Если число п кодирует конечный набор А и я-я двоичная цифра п равно 1, то набор, закодированный я является элемент из А.

Кодировка Аккермана - это примитивная рекурсивная функция.[3]

Реализация

В языках программирования, таких как C, C ++, Ява, или Python которые обеспечивают оператор сдвига вправо >> и побитовое логическое значение и оператор &, предикат BIT BIT (я, j) может быть реализовано выражением(i >> j) & 1. Здесь кусочки я пронумерованы от младших битов к старшим битам в двоичное представление из я, с единичным битом, пронумерованным как бит 0.[4]

Получение частной информации

В математическом исследовании компьютерной безопасности поиск частной информации Проблема может быть смоделирована как проблема, в которой клиент, обменивающийся данными с набором серверов, хранящих двоичное число я, хочет определить результат предиката BIT BIT (я, j) без разглашения стоимости j к серверам. Чор и др. (1998) описать метод репликации я через два сервера таким образом, что клиент может решить проблему поиска частной информации, используя существенно меньший объем связи, чем было бы необходимо для восстановления полной стоимостия.[5]

Математическая логика

Предикат BIT часто рассматривается в контексте логика первого порядка, где мы можем исследовать систему, полученную в результате добавления предиката BIT к логике первого порядка. В описательная сложность, класс сложности FO + BIT, полученный в результате добавления предиката BIT к FO приводит к более надежному классу сложности.[6] Класс FO + BIT логики первого порядка с предикатом BIT аналогичен классу FO + PLUS + TIMES логики первого порядка с предикатами сложения и умножения.[7]

Построение графа Rado

Граф Rado: например, есть ребро от 0 до 3, потому что 0-й бит 3 не равен нулю.

Аккерман в 1937 г. и Ричард Радо в 1964 году использовал этот предикат для построения бесконечного График Rado. По своему построению вершины этого графа соответствуют неотрицательным целым числам, записанным в двоичной системе, и есть неориентированное ребро из вершины я к вершине j, для я < j, когда BIT (j,я) отличен от нуля.[8]

использованная литература

  1. ^ Акерманн, Вильгельм (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Mathematische Annalen. 114: 305–315. Дои:10.1007 / bf01594179. Получено 2012-01-09.
  2. ^ Кирби, Лоуренс (2009). "Теория финитарных множеств". Журнал формальной логики Нотр-Дам. 50 (3): 227–244. Дои:10.1215/00294527-2009-009.
  3. ^ Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк: Springer Science + Business Media. п.261. Дои:10.1007/978-1-4419-1221-3. ISBN  978-1-4419-1220-6.
  4. ^ Венугопал, К. Р. (1997). Освоение C ++. Мухаммадали Шадули. п. 123. ISBN  9780074634547..
  5. ^ Чор, Бенни; Кушилевиц, Эял; Гольдрайх, Одед; Судан, Мадху (1998). «Поиск частной информации». Журнал ACM. 45 (6): 965–981. Дои:10.1145/293347.293350.CS1 maint: ref = harv (ссылка на сайт).
  6. ^ Иммерман, Нил (1999). Описательная сложность. Нью-Йорк: Springer-Verlag. ISBN  0-387-98600-6.
  7. ^ Иммерман (1999), стр. 14–16).
  8. ^ Радо, Ричард (1964). «Универсальные графики и универсальные функции» (PDF). Acta Arith. 9 (4): 331–340. Дои:10.4064 / aa-9-4-331-340..