El sistema de numeración unario es el sistema de numeración más simple para representar números naturales : [1] para representar un número N , un símbolo que representa 1 se repite N veces. [2]
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, ... [3]
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. [ cita requerida ]
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. [4] (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. [5] [6]
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 . [7] 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 puede interpretarse como una conversión de números unarios a binarios . [8] Sin embargo, la multiplicación es más engorrosa y a menudo se ha utilizado como un caso de prueba para el diseño de máquinas de Turing . [9] [10] [11]
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. [12] [13] [ enlace muerto permanente ] 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. [14]
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. [15]
Aplicaciones
La numeración unaria se utiliza como parte de algunos algoritmos de compresión de datos, como la codificación Golomb . [16] También forma la base de los axiomas de Peano para formalizar la aritmética dentro de la lógica matemática . [17] Una forma de notación unaria llamada codificación Church se utiliza para representar números dentro del cálculo lambda . [18]
Ver también
- Codificación unaria
- Codificación one-hot
Referencias
- ^ Hodges, Andrew (2009), Uno a nueve: La vida interior de los números , Anchor Canada, p. 14, ISBN 9780385672665.
- ^ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994), Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , informática y computación científica (2ª ed.), Academic Press, p. 117, ISBN 9780122063824.
- ^ Hext, Jan (1990), Estructuras de programación: máquinas y programas , Estructuras de programación, 1 , Prentice Hall, p. 33, ISBN 9780724809400.
- ^ Woodruff, Charles E. (1909), "The Evolution of Modern Numerals from Ancient Tally Marks" , American Mathematical Monthly , 16 (8–9): 125–33, doi : 10.2307 / 2970818 , JSTOR 2970818.
- ^ Hsieh, Hui-Kuang (1981), "Chinese Tally Mark", The American Statistician , 35 (3): 174, doi : 10.2307 / 2683999
- ^ Lunde, Ken; Miura, Daisuke (27 de enero de 2016), "Propuesta para codificar cinco marcas de conteo ideográficas", Consorcio Unicode (PDF) , Propuesta L2 / 16-046
- ^ Sazonov, Vladimir Yu. (1995), "Sobre números factibles", Lógica y complejidad computacional (Indianapolis, IN, 1994) , Lecture Notes in Comput. Sci., 960 , Springer, Berlín, págs. 30–51 , doi : 10.1007 / 3-540-60178-3_78 , ISBN 978-3-540-60178-4, MR 1449655. Ver en particular la p. 48.
- ^ Blaxell, David (1978), "Record linkage by bit pattern matching", en Hogben, David; Fife, Dennis W. (eds.), Ciencias de la computación y estadísticas - Décimo simposio anual sobre la interfaz , Publicación especial de NBS, 503 , Departamento de Comercio de EE. UU. / Oficina nacional de estándares, págs. 146–156.
- ^ Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison Wesley, Ejemplo 7.7, págs. 158-159 , ISBN 978-0-201-02988-8.
- ^ Dewdney, AK (1989), The New Turing Omnibus: Sixty-Six Excursions in Computer Science , Computer Science Press, p. 209, ISBN 9780805071665.
- ^ Rendell, Paul (2015), "5.3 Ejemplo más grande de TM: multiplicación unaria", Universalidad de la máquina de Turing del juego de la vida , emergencia, complejidad y computación, 18 , Springer, págs. 83-86, ISBN 9783319198422.
- ^ Arora, Sanjeev ; Barak, Boaz (2007), "El modelo computacional —y por qué no importa" (PDF) , Computational Complexity: A Modern Approach (edición preliminar de enero de 2007), Cambridge University Press, §17, págs. 32–33 , consultado el 10 de mayo de 2017.
- ^ Feigenbaum, Joan (otoño de 2012), CPSC 468/568 HW1 Solution Set (PDF) , Departamento de Ciencias de la Computación, Universidad de Yale , consultado el 21 de octubre de 2014.
- ^ Moore, Cristopher ; Mertens, Stephan (2011), La naturaleza de la computación , Oxford University Press, pág. 29, ISBN 9780199233212.
- ^ Garey, MR ; Johnson, DS (1978), " Resultados de NP-completitud ' fuertes': motivación, ejemplos e implicaciones", Journal of the ACM , 25 (3): 499–508, doi : 10.1145 / 322077.322090 , MR 0478747.
- ^ Golomb, SW (1966), "Codificaciones de longitud de ejecución" , IEEE Transactions on Information Theory , IT-12 (3): 399–401, doi : 10.1109 / TIT.1966.1053907.
- ^ Magaud, Nicolas; Bertot, Yves (2002), "Cambiando las estructuras de datos en la teoría de tipos: un estudio de los números naturales", Tipos para pruebas y programas (Durham, 2000) , Lecture Notes in Comput. Sci., 2277 , Springer, Berlín, págs. 181–196, doi : 10.1007 / 3-540-45842-5_12 , ISBN 978-3-540-43287-6, MR 2044538.
- ^ Jansen, Jan Martin (2013), "Programación en el cálculo λ: de Church a Scott y viceversa", La belleza del código funcional: ensayos dedicados a Rinus Plasmeijer con motivo de su 61 cumpleaños , Lecture Notes in Computer Science, 8106 , Springer-Verlag, págs. 168–180, doi : 10.1007 / 978-3-642-40355-2_12 , ISBN 978-3-642-40354-5.
enlaces externos
- Secuencia OEIS A000042 (Representación unaria de números naturales)