Теория конкатенации , называемая также теорией струн , теория символьной или теоретический синтаксис , исследование символьных строки над конечными алфавитами символов, знаки, символы или знаки. Теория струн лежит в основе формальной лингвистики , информатики, логики и метаматематики, особенно теории доказательств. [1] порождающая грамматика может рассматриваться в качестве рекурсивного определения в теории струн.
Самая основная операция со строками - это конкатенация ; соедините две строки, чтобы сформировать более длинную строку, длина которой равна сумме длин этих двух строк. ABCDE - это соединение AB с CDE в символах ABCDE = AB ^ CDE. Строки и объединение строк можно рассматривать как алгебраическую систему с некоторыми свойствами, напоминающими свойства сложения целых чисел; в современной математике эта система называется свободным моноидом .
В 1956 году Алонзо Черч писал: «Как и любой раздел математики, теоретический синтаксис может и в конечном итоге должен изучаться аксиоматическим методом». [2] Черч, очевидно, не знал, что теория струн уже имела две аксиоматизации 1930-х годов: одну Гансом Гермесом и одну Альфредом Тарским . [3] По совпадению, первое английское изложение аксиоматических основ теории струн Тарским 1933 года появилось в 1956 году - в том же году, когда Черч призвал к такой аксиоматизации. [4] Как заметил сам Тарский, используя другую терминологию, серьезные трудности возникают, если строки истолковываются как лексемы, а не типы в смысле разграничения лексемы типа Пирса , не путать с подобными различиями, лежащими в основе других различий лексемы типа .
Рекомендации
- ^ Джон Коркоран и Мэтт Лавин, «Открывая теорию струн». Вестник символической логики . 19 (2013) 253–4.
- ^ Алонзо Черч, Введение в математическую логику , Принстон, США, Принстон, 1956
- ^ Джон Коркоран , Уильям Франк и Майкл Мэлони, "Теория струн", Журнал символической логики , том. 39 (1974) стр. 625–637
- ^ Страницы 173–4 Альфреда Тарского, Концепция истины в формализованных языках , перепечатанная в Logic, Semantics, Metamat Mathematics, Hackett, Indianapolis, 1983, pp. 152–278