Сборник содержит работы по актуальным проблемам математической логики, еще не получившим достаточного освещения в отечественной литературе. Эти работы посвящены оценкам сложности алгоритмов и вычислений, классификациям рекурсивных функций и различным типам вычислительных устройств, связанных с такими классификациями. В частности, значительное место занимают исследования «ограниченных» машин Тьюринга и обобщений конечных автоматов. В ряде работ изучаются множества слов, распознаваемых обобщенными автоматами, причем обнаруживаются связи с грамматиками, введенными в работах Н. Хомского.Книга рассчитана на лиц, интересующихся современными проблемами математической логики, теории алгоритмов, теории автоматов, математической лингвистики и теории вычислительных машин.
Author(s): Козмидиади В.А. (ред.), Мучник А.А. (ред.)
Series: Библиотека кибернетического сборника
Publisher: Мир
Year: 1970
Language: Russian
Commentary: +OCR+
Pages: 432
I. КЛАССИФИКАЦИЯ РЕКУРСИВНЫХ ФУНКЦИЙ
А.Гжегорчик. Некоторые классы рекурсивных функций. Перевод А. Л. Мучника 9
Р.В.Ричи. Классы предсказуемо вычислимых функций. Перевод Н. Н. Катериночкиной . 50
Дж.П.Клив. Иерархия примитивно рекурсивных функций. Перевод С. С: Марченкова 94
П.Акст. Итерация примитивной рекурсии. Перевод А. Гагарина 114
П.Акст. Итерация относительной примитивной рекурсии. Перевод С. Каллибекова 118
Добавление редактора. О двух подходах к классификации рекурсивных функций 123
II. О СЛОЖНОСТИ ВЫЧИСЛЕНИЙ НА МАШИНАХ ТЬЮРИНГА
X.Ямада. Вычисления в реальное время и рекурсивные функции, не вычислимые в реальное время. Перевод В. Е. Фельдмана 139
М.Рабин. Вычисления в реальное время. Перевод В. Е. Фельдмана 156
А.Розенберг. Языки, определимые в реальное время. Перевод М. Афанасьева и М. В. Ломковской 168
Ф.К.Xенни, Р.Е.Стирнз. Моделирование многоленточной машины Тьюринга на двуленточной. Перевод Ю. А. Бухштаба 194
С.С.Раби, П.К.Фишер. Методы перевода и сложность вычислений. Перевод А. А. Мучника 213
Ф.К.Xенни. Вычисления на одноленточной машине Тьюринга с записью на ленте. Перевод Ю. Я. Брейтбарта 223
Ф.К.Xенни. Вычисления на машинах Тьюринга со входом. Перевод А. Набибина 249
П.Стрнад. Распознавание на машине Тьюринга со входом. Перевод Ю. А. Бухштаба 271
Дж.Хартманис Сложность вычислений на одноленточных машинах Тьюринга. Перевод А. А. Мучника 282
Р.Е.Стирнз, Дж.Xартманис, П.М.Льюис II. Иерархии вычислений с ограниченной памятью. Перевод М. И. Кановича 301
П.М.Льюис II, Р.Е.Стирнз, Дж.Хартманис. Границы памяти для разрешения контекстно-свободных и контекстных языков Перевод М. И. Кановича 320
Дж.Xартманис. Об объеме памяти, необходимом для распознавания бесконтекстных языков. Перевод М. В. Ломковской 339
Д.X.Янгер. Распознавание и анализ контекстно-свободных языков за время n3. Перевод В. Е. Фельдмана 344
Т.Касами. О времени машинного распознавания языков, порожденных линейными грамматиками Перевод В. Е. Фельдмана 363
Добавление к статье Касами. Распознавание металинейных языков по методу Т.Касами 369
М.Фишер, А.Розенберг. Решение задачи о пересечении начала координат в реальное время. Перевод В. Е. Фельдмана 372
П.Фишер, А.Мейер, А.Розенберг. Счетчиковые машины и счетчиковые языки. Перевод В. Е. Фельдмана 380
М.Блюм. Машинно-независимая теория сложности рекурсивных функций. Перевод В. А. Козмидиади 401
М.Блюм. Об объеме машин. Перевод А. А. Мучника 423
