Sistema de numeración unario - Unary numeral system
| Sistemas de numeración |
|---|
| Sistema de numeración hindú-árabe |
| asiático del este |
| americano |
| Alfabético |
| Anterior |
| Sistemas posicionales por base |
| Sistemas de numeración posicional no estándar |
| Lista de sistemas de numeración |
El sistema de numeración unario es el sistema de numeración más simple para representar números naturales : para representar un número N , un símbolo que representa 1 se repite N veces.
En el sistema unario, el número 0 (cero) está representado por la cadena vacía , es decir, la ausencia de un símbolo. Los números 1, 2, 3, 4, 5, 6, ... se representan en unario como 1, 11, 111, 1111, 11111, 111111, ...
En el marco de la notación posicional , el unario es el sistema numérico de base biyectiva - 1 . Sin embargo, debido a que el valor de un dígito no depende de su posición, se puede argumentar que unario no es un sistema posicional.
El uso de marcas de conteo en el conteo es una aplicación del sistema de numeración unario. Por ejemplo, usando la marca de conteo | , el número 3 se representa como ||| . En las culturas de Asia oriental, el número 3 se representa como三, un carácter dibujado con tres trazos. (Uno y dos se representan de manera similar). En China y Japón, el carácter 正, dibujado con 5 trazos, a veces se usa para representar 5 como un recuento.
Los números unarios deben distinguirse de los repunits , que también se escriben como secuencias de unos, pero tienen su interpretación numérica decimal habitual .
Operaciones
La suma y la resta son particularmente simples en el sistema unario, ya que implican poco más que una concatenación de cadenas . La operación de conteo de población o ponderación de Hamming que cuenta el número de bits distintos de cero en una secuencia de valores binarios también se puede interpretar como una conversión de números unarios a binarios . Sin embargo, la multiplicación es más engorrosa y a menudo se ha utilizado como caso de prueba para el diseño de máquinas de Turing .
Complejidad
En comparación con los sistemas de numeración posicional estándar , el sistema unario es inconveniente y, por lo tanto, no se utiliza en la práctica para grandes cálculos. Ocurre en algunas descripciones de problemas de decisión en informática teórica (por ejemplo, algunos problemas P-completos ), donde se utiliza para reducir "artificialmente" los requisitos de tiempo de ejecución o de espacio de un problema. Por ejemplo, se sospecha que el problema de la factorización de enteros requiere más que una función polinomial de la longitud de la entrada como tiempo de ejecución si la entrada se da en binario , pero solo necesita un tiempo de ejecución lineal si la entrada se presenta en unario. Sin embargo, esto es potencialmente engañoso. El uso de una entrada unaria es más lento para cualquier número dado, no más rápido; la distinción es que una entrada binaria (o base más grande) es proporcional al logaritmo de base 2 (o base más grande) del número, mientras que la entrada unaria es proporcional al número en sí. Por lo tanto, aunque el requisito de tiempo de ejecución y espacio en unario se ve mejor en función del tamaño de entrada, no representa una solución más eficiente.
En la teoría de la complejidad computacional , la numeración unaria se usa para distinguir problemas NP-completos de los problemas que son NP-completos pero no fuertemente NP-completos. Un problema en el que la entrada incluye algunos parámetros numéricos es fuertemente NP-completo si permanece NP-completo incluso cuando el tamaño de la entrada se hace artificialmente más grande al representar los parámetros en unario. Para tal problema, existen casos difíciles para los cuales todos los valores de los parámetros son polinomialmente grandes como máximo.
Aplicaciones
La numeración unaria se utiliza como parte de algunos algoritmos de compresión de datos, como la codificación Golomb . También forma la base de los axiomas de Peano para formalizar la aritmética dentro de la lógica matemática . Se utiliza una forma de notación unaria llamada codificación de Church para representar números dentro del cálculo lambda .