Смальян Р. Теория формальных систем

М.: Наука, 1981. — 207 с. — (Математическая логика и основания математики).В этой книге в систематической форме и, фактически, начиная с «азов», излагается обширный комплекс математических результатов, касающихся ряда фундаментальных понятий, предназначенных для точного описания и исследования формально-дедуктивного метода в математике и тесно связанного с этим методом понятия алгорифма.
Фундаментальным теоретическим обобщением выработанных в процессе развития математической логики методов точного определения основных логико-математических языков и методов формально-дедуктивного (аксиоматического) построения математических теорий явилось введенное Э. Постом понятие канонического исчисления в данном алфавите. Им же было указано, что в рамках теории канонических исчислений можно определить понятие алгорифма, эквивалентное понятию машины А. Тьюринга. Порождающие системы, называемые в настоящее время порождающими грамматиками, по существу представляют собой канонические исчисления частных типов (при этом, некоторые типы порождающих грамматик имеют такой же «объем», как понятие канонического исчисления). Понятие канонического исчисления сравнимо по «уровню фундаментальности» с понятием машины Тьюринга.