В математике и информатике , в БИТОМ предикате или кодировании Ackermann , иногда письменный BIT ( я , J ), является предикатом , который проверяет , является ли J - й битого числа я равен 1, когда я записываюсь в двоичном виде .
История
BIT предикат впервые был введен как кодирование наследственно конечных множества как натуральные числа по Wilhelm Аккерман в своей 1937 бумаге непротиворечивости общей теории множеств . [1] [2]
В этом кодировании каждое натуральное число кодирует конечный набор , и каждый конечный набор представлен натуральным числом. Если кодировка набора обозначается , то эта кодировка определяется рекурсивно как
Кодирование Аккермана - это примитивная рекурсивная функция . [3]
Выполнение
В языках программирования, таких как C , C ++ , Java или Python, которые предоставляют оператор сдвига вправо >>
и побитовое логическое значение и оператор &
, предикат BIT BIT ( i , j ) может быть реализован с помощью выражения (i>>j)&1
. Здесь биты I пронумерованы от младших битов к битам высокого порядка в двоичном представлении о I , с теми , которые пронумерованы бит , как бит 0. [4]
Получение частной информации
В математическом исследовании компьютерной безопасности проблема поиска частной информации может быть смоделирована как проблема, в которой клиент, взаимодействуя с набором серверов, хранящих двоичное число i , желает определить результат предиката BIT BIT ( i , j ) без разглашения значения j серверам. Чор и др. (1998) описывают метод репликации i на двух серверах таким образом, чтобы клиент мог решить проблему поиска частной информации, используя существенно меньший объем связи, чем было бы необходимо для восстановления полного значения i . [5]
Математическая логика
Предикат BIT часто исследуется в контексте логики первого порядка , где системы логики являются результатом добавления предиката BIT к логике первого порядка. В описательном сложности , то класс сложность FO + БИТ в результате добавления к BIT предиката FO приводит к более надежному классу сложности. [6] Класс FO + BIT логики первого порядка с предикатом BIT аналогичен классу FO + PLUS + TIMES логики первого порядка с предикатами сложения и умножения. [7]
Построение графа Rado
Аккерман в 1937 году и Ричард Радо в 1964 году использовали этот предикат для построения бесконечного графа Радо . По своей конструкции вершины этого графа соответствуют неотрицательным целым числам, записанным в двоичном формате, и существует неориентированное ребро от вершины i к вершине j , для i < j , когда BIT ( j , i ) отличен от нуля. [8]
Рекомендации
- ^ Акерманн, Вильгельм (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre" . Mathematische Annalen . 114 : 305–315. DOI : 10.1007 / bf01594179 . S2CID 120576556 . Проверено 9 января 2012 .
- ^ Кирби, Лоуренс (2009). «Теория финитарных множеств» . Журнал формальной логики Нотр-Дам . 50 (3): 227–244. DOI : 10.1215 / 00294527-2009-009 .
- ^ Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science + Business Media . п. 261 . DOI : 10.1007 / 978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
- ^ Венугопал, КР (1997). Освоение C ++ . Мухаммадали Шадули. п. 123. ISBN 9780074634547..
- ^ Чор, Бенни; Кушилевиц, Эяль; Гольдрайх, Одед; Судан, Мадху (1998). «Поиск частной информации». Журнал ACM . 45 (6): 965–981. DOI : 10.1145 / 293347.293350 . S2CID 544823 ..
- ^ Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. ISBN 0-387-98600-6.
- ^ Иммерман (1999 , стр. 14-16)
- ^ Радо, Ричард (1964). «Универсальные графики и универсальные функции» (PDF) . Acta Arith . 9 (4): 331–340. DOI : 10,4064 / аа-9-4-331-340 ..