La teoría de la concatenación , también llamada teoría de cuerdas , teoría de cadenas de caracteres o sintaxis teórica , estudia las cadenas de caracteres sobre alfabetos finitos de caracteres, signos, símbolos o marcas. La teoría de cuerdas es fundamental para la lingüística formal , la informática, la lógica y las metamatemáticas, especialmente la teoría de pruebas. [1] Una gramática generativa puede verse como una definición recursiva en la teoría de cuerdas.
La operación más básica en cadenas es la concatenación ; conecte dos cadenas para formar una cadena más larga cuya longitud sea la suma de las longitudes de esas dos cadenas. ABCDE es la concatenación de AB con CDE, en los símbolos ABCDE = AB ^ CDE. Las cadenas y la concatenación de cadenas pueden tratarse como un sistema algebraico con algunas propiedades que se asemejan a las de la suma de números enteros; en las matemáticas modernas, este sistema se denomina monoide libre .
En 1956 Alonzo Church escribió: "Como cualquier rama de las matemáticas, la sintaxis teórica puede, y finalmente debe, ser estudiada por el método axiomático". [2] Church evidentemente no sabía que la teoría de cuerdas ya tenía dos axiomatizaciones de la década de 1930: una de Hans Hermes y otra de Alfred Tarski . [3] Casualmente, la primera presentación en inglés de los fundamentos axiomáticos de la teoría de cuerdas de 1933 de Tarski apareció en 1956, el mismo año en que Church pidió tales axiomatizaciones. [4] Como el propio Tarski señaló usando otra terminología, surgen serias dificultades si las cadenas se interpretan como tokens en lugar de tipos en el sentido de la distinción de token de tipo de Pierce , que no debe confundirse con distinciones similares subyacentes a otras distinciones de token de tipo .
Referencias
- ^ John Corcoran y Matt Lavine, "Descubriendo la teoría de cuerdas". Boletín de Lógica Simbólica . 19 (2013) 253–4.
- ^ Iglesia de Alonzo, Introducción a la lógica matemática , Princeton UP, Princeton, 1956
- ^ John Corcoran , William Frank y Michael Maloney, "Teoría de cuerdas", Journal of Symbolic Logic , vol. 39 (1974) págs. 625-637
- ^ Páginas 173–4 de Alfred Tarski, El concepto de verdad en lenguajes formalizados , reimpreso en Logic, Semantics, Metamathematics , Hackett, Indianapolis, 1983, pp. 152–278