Sistema de numeración unario

El sistema numérico unario es el sistema numérico más simple para representar números naturales: para representar un número N, se repite un símbolo que representa 1 N tiempos.

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,...

Unario es un sistema numérico biyectivo. Sin embargo, debido a que el valor de un dígito no depende de su posición, no es una forma de notación posicional y no está claro si sería apropiado decir que tiene una base (o "base") de 1, ya que se comporta de manera diferente a todas las demás bases.

El uso de marcas de conteo al contar es una aplicación del sistema numérico 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 una cuenta.

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 la concatenación de cadenas. La operación de conteo de peso o población de Hamming que cuenta el número de bits distintos de cero en una secuencia de valores binarios también puede interpretarse 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 numéricos posicionales estándar, el sistema unario es inconveniente y, por lo tanto, no se usa en la práctica para cálculos grandes. Ocurre en algunas descripciones de problemas de decisión en informática teórica (p. ej., algunos problemas P-completos), donde se usa para "artificialmente" disminuir el tiempo de ejecución o los requisitos 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. Usar 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 de base más grande) es proporcional al logaritmo de base 2 (o de base más grande) del número, mientras que la entrada unaria es proporcional al número mismo. 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 fuertemente NP-completos de 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 duros para los cuales todos los valores de los parámetros son como máximo polinomialmente grandes.

Aplicaciones

La numeración unaria se usa 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 Church para representar números dentro del cálculo lambda.