En matemáticas e informática , el predicado BIT o codificación de Ackermann , a veces escrito BIT ( i , j ), es un predicado que prueba si el j- ésimo bit del número i es 1, cuando i está escrito en binario .
Historia
El predicado BIT fue introducido por primera vez como la codificación de conjuntos finitos hereditarios como números naturales por Wilhelm Ackermann en su artículo de 1937 The Consistency of General Set Theory . [1] [2]
En esta codificación, cada número natural codifica un conjunto finito y cada conjunto finito está representado por un número natural. Si la codificación de un conjunto se denota , entonces esta codificación se define de forma recursiva por
La codificación de Ackermann es una función recursiva primitiva . [3]
Implementación
En lenguajes de programación como C , C ++ , Java o Python que proporcionan un operador de desplazamiento a la derecha >>
y un operador booleano y bit a bit&
, la expresión puede implementar el predicado BIT BIT ( i , j ) (i>>j)&1
. Aquí los bits de i se numeran desde los bits de orden inferior hasta los bits de orden superior en la representación binaria de i , y los bits de las unidades se numeran como bit 0. [4]
Recuperación de información privada
En el estudio matemático de la seguridad informática, el problema de recuperación de información privada puede modelarse como uno en el que un cliente, comunicándose con una colección de servidores que almacenan un número binario i , desea determinar el resultado de un predicado BIT BIT ( i , j ) sin divulgar el valor de j a los servidores. Chor y col. (1998) describen un método para replicar i en dos servidores de tal manera que el cliente puede resolver el problema de recuperación de información privada utilizando una cantidad de comunicación sustancialmente menor de la que sería necesaria para recuperar el valor completo de i . [5]
Lógica matemática
El predicado BIT a menudo se examina en el contexto de la lógica de primer orden , donde los sistemas de lógica resultan de agregar el predicado BIT a la lógica de primer orden. En complejidad descriptiva , la clase de complejidad FO + BIT resultante de agregar el predicado BIT a FO da como resultado una clase de complejidad más robusta. [6] La clase FO + BIT, de lógica de primer orden con predicado BIT, es la misma que la clase FO + PLUS + TIMES, de lógica de primer orden con predicados de suma y multiplicación. [7]
Construcción del gráfico de Rado
Ackermann en 1937 y Richard Rado en 1964 utilizaron este predicado para construir el gráfico de Rado infinito . En su construcción, los vértices de este gráfico corresponden a los enteros no negativos, escritos en binario, y hay una arista no dirigida desde el vértice i al vértice j , para i < j , cuando BIT ( j , i ) es distinto de cero. [8]
Referencias
- ^ Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre" . Mathematische Annalen . 114 : 305–315. doi : 10.1007 / bf01594179 . S2CID 120576556 . Consultado el 9 de enero de 2012 .
- ^ Kirby, Laurence (2009). "Teoría de conjuntos finitarios" . Diario de Notre Dame de lógica formal . 50 (3): 227–244. doi : 10.1215 / 00294527-2009-009 .
- ^ Rautenberg, Wolfgang (2010). Una introducción concisa a la lógica matemática (3ª ed.). Nueva York : Springer Science + Business Media . pag. 261 . doi : 10.1007 / 978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
- ^ Venugopal, KR (1997). Dominar C ++ . Muhammadali Shaduli. pag. 123. ISBN 9780074634547..
- ^ Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudán, Madhu (1998). "Recuperación de información privada". Revista de la ACM . 45 (6): 965–981. doi : 10.1145 / 293347.293350 . S2CID 544823 ..
- ^ Immerman, Neil (1999). Complejidad descriptiva . Nueva York: Springer-Verlag. ISBN 0-387-98600-6.
- ^ Immerman (1999 , págs. 14-16)
- ^ Rado, Richard (1964). "Gráficos universales y funciones universales" (PDF) . Acta Arith . 9 (4): 331–340. doi : 10.4064 / aa-9-4-331-340 ..