Издательство Мир, 1970. — 432 с. Сборник переводов.
Сборник содержит работы по актуальным проблемам математической
логики, еще не получившим достаточного освещения в отечественной
литературе. Эти работы посвящены оценкам сложности алгоритмов и
вычислений, классификациям рекурсивных функций и различным типам
вычислительных устройств, связанных с такими классификациями. В
частности, значительное место занимают исследования «ограниченных»
машин Тьюринга и обобщений конечных автоматов. В ряде работ
изучаются множества слов, распознаваемых обобщенными автоматами,
причем обнаруживаются связи с грамматиками, введенными в работах Н.
Хомского.
Книга рассчитана на лиц, интересующихся современными проблемами математической логики, теории алгоритмов, теории автоматов, математической лингвистики и теории вычислительных машин. СОДЕРЖАНИЕ Предисловие I. Классификация рекурсивных функций
А. Гжегорчик. Некоторые классы рекурсивных функций. Перевод А.А. Мучника
Р.В. Ричи. Классы предсказуемо вычислимых функций. Перевод Н.Н. Катериночкиной
Дж.П. Клив. Иерархия примитивно рекурсивных функций. Перевод С.С. Марченкова
П. Акст. Итерация примитивной рекурсии. Перевод А. Гагарина
П. Акст. Итерация относительной примитивной рекурсии. Перевод С. Каллибекова
Добавление редактора. О двух подходах к классификации рекурсивных функций II. О сложности вычислении на машинах Тьюринга
Х. Ямада. Вычисления в реальное время и рекурсивные функции, не вычислимые в реальное время. Перевод В.Е. Фельдмана
М. Рабин. Вычисления в реальное время. Перевод В. Е. Фельдмана
А. Розенберг. Языки, определимые в реальное время. Перевод М. Афанасьева и М.В. Ломковской
Ф.К. Хенни, Р.Е. Стирнз. Моделирование многоленточной машины Тьюринга на двуленточной. Перевод Ю.А. Бухштаба
С.С. Раби, П.К. Фишер. Методы перевода и сложность вычислений. Перевод А.А. Мучника
Ф.К. Хенни. Вычисления на одноленточной машине Тьюринга с записью на ленте. Перевод Ю.Я. Брейтбарта
Ф. К. Хенни. Вычисления на машинах Тьюринга со входом. Перевод А. Набибина
П. Стрнад. Распознавание на машине Тьюринга со входом. Перевод Ю.А. Бухштаба
Дж. Хартманис. Сложность вычислений на одноленточных машинах Тьюринга. Перевод А.А. Мучника
Р.Е. Стирнз, Дж. Хартманис, П.М. Льюис II. Иерархии вычислений с ограниченной памятью. Перевод М.И. Кановича
П.М. Льюис II, Р.Е. Стирнз, Дж. Хартманис. Границы памяти для разрешения контекстно-свободных и контекстных языков Перевод М.И. Кановича
Дж. Хартманис. Об объеме памяти, необходимом для распознавания бесконтекстных языков. Перевод М.В. Ломковской
Д.Х. Янгер. Распознавание и анализ контекстно-свободных языков за время n3. Перевод В.Е. Фельдмана
Т. Касами. О времени машинного распознавания языков, порожденных линейными грамматиками Перевод В.Е. Фельдмана
Добавление к статье Касами. Распознавание металинейных языков по методу Т. Касами
М. Фишер, А. Розенберг. Решение задачи о пересечении начала координат в реальное время. Перевод В. Е. Фельдмана
П. Фишер, А. Мейер, А. Розенберг. Счетчиковые машины и счетчиковые языки. Перевод В.Е. Фельдмана
М. Блюм. Машинно-независимая теория сложности рекурсивных функций. Перевод В. А. Козмидиади
М. Блюм. Об объеме машин. Перевод А.А. Мучника
Книга рассчитана на лиц, интересующихся современными проблемами математической логики, теории алгоритмов, теории автоматов, математической лингвистики и теории вычислительных машин. СОДЕРЖАНИЕ Предисловие I. Классификация рекурсивных функций
А. Гжегорчик. Некоторые классы рекурсивных функций. Перевод А.А. Мучника
Р.В. Ричи. Классы предсказуемо вычислимых функций. Перевод Н.Н. Катериночкиной
Дж.П. Клив. Иерархия примитивно рекурсивных функций. Перевод С.С. Марченкова
П. Акст. Итерация примитивной рекурсии. Перевод А. Гагарина
П. Акст. Итерация относительной примитивной рекурсии. Перевод С. Каллибекова
Добавление редактора. О двух подходах к классификации рекурсивных функций II. О сложности вычислении на машинах Тьюринга
Х. Ямада. Вычисления в реальное время и рекурсивные функции, не вычислимые в реальное время. Перевод В.Е. Фельдмана
М. Рабин. Вычисления в реальное время. Перевод В. Е. Фельдмана
А. Розенберг. Языки, определимые в реальное время. Перевод М. Афанасьева и М.В. Ломковской
Ф.К. Хенни, Р.Е. Стирнз. Моделирование многоленточной машины Тьюринга на двуленточной. Перевод Ю.А. Бухштаба
С.С. Раби, П.К. Фишер. Методы перевода и сложность вычислений. Перевод А.А. Мучника
Ф.К. Хенни. Вычисления на одноленточной машине Тьюринга с записью на ленте. Перевод Ю.Я. Брейтбарта
Ф. К. Хенни. Вычисления на машинах Тьюринга со входом. Перевод А. Набибина
П. Стрнад. Распознавание на машине Тьюринга со входом. Перевод Ю.А. Бухштаба
Дж. Хартманис. Сложность вычислений на одноленточных машинах Тьюринга. Перевод А.А. Мучника
Р.Е. Стирнз, Дж. Хартманис, П.М. Льюис II. Иерархии вычислений с ограниченной памятью. Перевод М.И. Кановича
П.М. Льюис II, Р.Е. Стирнз, Дж. Хартманис. Границы памяти для разрешения контекстно-свободных и контекстных языков Перевод М.И. Кановича
Дж. Хартманис. Об объеме памяти, необходимом для распознавания бесконтекстных языков. Перевод М.В. Ломковской
Д.Х. Янгер. Распознавание и анализ контекстно-свободных языков за время n3. Перевод В.Е. Фельдмана
Т. Касами. О времени машинного распознавания языков, порожденных линейными грамматиками Перевод В.Е. Фельдмана
Добавление к статье Касами. Распознавание металинейных языков по методу Т. Касами
М. Фишер, А. Розенберг. Решение задачи о пересечении начала координат в реальное время. Перевод В. Е. Фельдмана
П. Фишер, А. Мейер, А. Розенберг. Счетчиковые машины и счетчиковые языки. Перевод В.Е. Фельдмана
М. Блюм. Машинно-независимая теория сложности рекурсивных функций. Перевод В. А. Козмидиади
М. Блюм. Об объеме машин. Перевод А.А. Мучника