Operaciones a bit a bit: NOT, AND, OR y XOR

Seguimos con la racha de entradas encadenadas. Si la entrada de los tipos de configuración RAID nos llevó a definir el concepto de información de paridad ahora a raíz de esa entrada vamos a hablar de las operaciones bit a bit.

Hablamos de operaciones a nivel de bit porque con ellas trabajamos directamente sobre los bits, dígitos binarios, a nivel individual. Este tipo de operaciones son muy utilizadas en computación, a la hora de cifrar datos o, como comentábamos en el otro artículo, para realizar los cálculos de paridad. Es posible que te suenen los nombres de estas operaciones, pues son operaciones lógicas que ya vimos en su día en un artículo sobre LibreOffice Calc o también en la entrada sobre el álgebra booleana.

NOT: La operación NOT también podría ser llamada complemento y es un operador unario. Realiza la negación lógica de cada bit, es decir, invierte su valor. Por ejemplo, la operación NOT 1010 daría como resultado 0101.

AND: La operación AND, o conjunción lógica, funciona de forma similar a una multiplicación: sólo nos devolverá 1 si todas las entradas son 1, en el resto de casos devolvería 0. Es decir 0 AND 0 es igual a 0, 1 AND 0 es igual 0 y solo 1 AND 1 es igual a 1. Por ejemplo: 100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000. Cuando hacemos la operación AND la secuencia que dará como resultado no puede ser más larga que la mayor de las secuencias operadas.

OR: La operación OR, o disyunción lógica, dará como salida 1 siempre que una o más de sus entradas sean 1. Es decir, 1 OR 1 es igual a 1, 1 OR 0 es igual a 1 y solo 0 OR 0 es igual a 0. Por ejemplo: 1000 OR 0011 = 1011. Cuando hacemos la operación OR la secuencia que dará como resultado no puede ser más corta que ninguna de las secuencias operadas.

XOR: La operación XOR, u OR exclusivo, dará como salida 1 siempre que solo una de las dos entradas sea 1. Es decir, que 0 XOR 0 será igual a 0, 1 XOR 1 será igual a 0 pero 1 XOR 0 o 0 XOR 1 serán igual a 1. Por ejemplo 1010 XOR 1001 = 0011 Dado que es complicado revertir su resultado es muy utilizada en algoritmos de cifrado.

Problema de Parada (o problema de Halting)

Vamos con un poco de teoría de la computación ¿Qué es el problema de paro, de parada o de Halting? Consiste en determinar si existe una máquina de Turing capaz de determinar si cualquier Máquina de Turing se va a detener o no. Dada una máquina de Turing M y una palabra w se determinará si M acabará en un número finito de pasos usando w como dato de entrada.

El problema es indecidible, según el propio Turing ninguna máquina de Turing puede resolverlo. Es decir, no puede existir un programa genérico que demuestre que todos los programas del mundo terminan, se puede hacer para un programa concreto pero no existe la solución general.

Existen varias demostraciones de por qué es indecidible, vamos a ver una demostración escrita en javascript.

Imaginemos que alguien escribe una función f que recibe como parámetros una función y sus argumentos, y que tiene un código capaz de comprobar si esta se detendrá o no.

var f = function (funcion, argumentos) { ... }; // Aquí iría un código correcto que supuestamente calcularía si la máquina para o no

Vamos a suponer que esa función está correcta, funciona y nos devuelve true si el programa termina, y false si caería en un bucle infinito. Entonces podríamos usarla como subrutina dentro de otra función más grande llamada g como la que viene a continuación:

var g = function (funcion) {
//Pasamos en el parámetro funcion la función y sus argumentos 
  if (f(funcion,funcion)) {
    while (true); //esto provoca un bucle infinito
  }
  else {
    return false;
  }
}

Esto vendría a decir que g(funcion) termina siempre y cuando funcion(funcion) nunca termina.

Entonces ¿qué ocurre si la pasásemos a la función g como parámetro su propio código? Es decir ¿qué pasa si g evalúa a g? Pues que llegamos a una contradicción: g(g) termina siempre y cuando g(g) nunca termina. Por tanto, al llevarnos a una paradoja dicho algoritmo no puede existir.