Теория последовательностей или теория строк, называемая также чистым синтаксисом — изучает символьные строки, над конечными алфавитами, в виде символов, знаков, обозначений или меток. Теория строк является основой , информатики, логики и метаматематики, особенно теории доказательствJohn Corcoran and Matt Lavine, «Discovering string theory». Bulletin of Symbolic Logic. 19 (2013) 253-4.. Порождающая грамматика, может рассматриваться, как рекурсивное определение, в теории строк.
Наиболее простой операцией над строками является конкатенация:
Соединение двух строк, для получения более длинной строки, информация о которой складывается из суммы значений этих строк.
ABCDE — конкатенация AB и CDE, в символах ABCDE = AB ^ CDE.
Строки и конкатенация строк могут рассматриваться как алгебраическая система со свойствами, напоминающими свойства сложения целых чисел. В современной математике такая система называется .
В 1956 году, Алонзо Черч писал: «Как и любая другая отрасль математики, теоретический синтаксис может и, в конечном итоге, должен изучаться с помощью аксиоматического метода»Alonzo Church, Introduction to Mathematical Logic, Princeton UP, Princeton, 1956. Черч, очевидно, не знал, что теория строк уже имела две аксиоматизации, предложенную в 1930-х годах: одну — , другую — Альфредом ТарскиJohn Corcoran, William Frank and Michael Maloney, «String theory», Journal of Symbolic Logic, vol. 39 (1974) pp. 625—637. По случайному совпадению, первое англоязычное изложение аксиоматических основ теории конкатенации Тарского 1933 года появилось в 1956 году — в тот же год, когда Черч призвал к подобной аксиоматизацииPages 173-4 of Alfred Tarski, The concept of truth in formalized languages, reprinted in Logic, Semantics, Metamathematics, Hackett, Indianapolis, 1983, pp. 152—278. Как отмечал сам Тарский, используя другую терминологию, серьёзные трудности возникают, если строки трактовать как токены, а не как типы в смысле различие типа и токена, предложенного Пирсом.
Примечания
Литература (перевод Сергея Корчевого)
Категория:Философия языка Категория:История логики Категория:Синтаксис Категория:Логика