BIT predikát - BIT predicate
v matematika a počítačová věda, BIT predikát nebo Ackermann kódování, někdy psáno BIT (i, j), je predikát který testuje, zda jth bit čísla i je 1, když i je zapsán binárně.
Dějiny
BIT predikát byl poprvé představen jako kódování dědičně konečné sady tak jako přirozená čísla podle Wilhelm Ackermann ve svém příspěvku z roku 1937[1][2](Konzistence obecné teorie množin).
Každé přirozené číslo kóduje konečnou množinu a každá konečná množina je reprezentována přirozeným číslem. Toto mapování používá binární číselná soustava Pokud číslo n kóduje konečnou množinu A a ith binární číslice n je 1, pak je sada kódována i je živel z A.
Ackermannovo kódování je a primitivní rekurzivní funkce.[3]
Implementace
V programovacích jazycích, jako je C, C ++, Jáva nebo Krajta které poskytují a operátor posunu doprava >>
a a bitový Boolean a operátor &
, predikát BIT BIT (i, j) lze implementovat výrazem(i >> j) a 1
. Tady kousky i jsou číslovány od bitů nižšího řádu po bity vysokého řádu v binární reprezentace z i, přičemž ty bity jsou očíslovány jako bit 0.[4]
Získávání soukromých informací
V matematické studii o počítačové bezpečnosti se vyhledávání soukromých informací problém lze modelovat jako ten, ve kterém klient komunikuje s kolekcí serverů, které ukládají binární číslo i, si přeje určit výsledek BIT predikátu BIT (i, j) bez vyzrazení hodnoty j na servery. Chor a kol. (1998) popsat způsob replikace i přes dva servery takovým způsobem, že klient může vyřešit problém s vyhledáváním soukromých informací pomocí podstatně menšího množství komunikace, než by bylo nutné k obnovení úplné hodnotyi.[5]
Matematická logika
BIT predikát je často zkoumán v kontextu logika prvního řádu, kde můžeme zkoumat systém vyplývající z přidání predikátu BIT do logiky prvního řádu. v popisná složitost, třída složitosti FO + BIT vyplývající z přidání predikátu BIT do FO má za následek robustnější třídu složitosti.[6] Třída FO + BIT logiky prvního řádu s predikátem BIT je stejná jako třída FO + PLUS + TIMES logiky prvního řádu s predikáty sčítání a násobení.[7]
Konstrukce Rado grafu

Ackermann v roce 1937 a Richard Rado v roce 1964 použil tento predikát ke konstrukci nekonečna Rado graf. Ve své konstrukci vrcholy tohoto grafu odpovídají nezáporným celým číslům zapsaným v binárním formátu a je zde neorientovaná hrana z vrcholu i na vrchol j, pro i < j, když BIT (j,i) je nenulová.[8]
Reference
- ^ Ackermann, Wilhelm (1937). „Die Widerspruchsfreiheit der allgemeinen Mengenlehre“. Mathematische Annalen. 114: 305–315. doi:10.1007 / bf01594179. Citováno 2012-01-09.
- ^ Kirby, Laurence (2009). „Finitary Set Theory“. Deník Notre Dame formální logiky. 50 (3): 227–244. doi:10.1215/00294527-2009-009.
- ^ Rautenberg, Wolfgang (2010). Stručný úvod do matematické logiky (3. vyd.). New York: Springer Science + Business Media. str.261. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
- ^ Venugopal, K. R. (1997). Mastering C ++. Muhammadali Shaduli. str. 123. ISBN 9780074634547..
- ^ Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Súdán, Madhu (1998). Msgstr "Načítání soukromých informací". Deník ACM. 45 (6): 965–981. doi:10.1145/293347.293350.CS1 maint: ref = harv (odkaz).
- ^ Immerman, Neil (1999). Popisná složitost. New York: Springer-Verlag. ISBN 0-387-98600-6.
- ^ Immerman (1999, s. 14–16)
- ^ Rado, Richarde (1964). "Univerzální grafy a univerzální funkce" (PDF). Acta Arith. 9 (4): 331–340. doi:10,4064 / aa-9-4-331-340..