Читать онлайн «Машины Тьюринга и рекурсивные функции»

машины тьюринга и рекурсивные функции >тЧ nri - 1 у 1 1 г ж г . I г J-4 г/ г,2 у —► г ут — i — 1 ут — I Selecta Mathematica II Herausgegeben von KONRAD JACOBS H. -D. Ebbinghaus Turing-Maschinen und berechenbare Funktionen I F. -K. Mahn Turing-Maschinen und berechenbare Funktionen II H. -D. Ebbinghaus Turing-Maschinen und berechenbare Funktionen III H. -D. Ebbinghaus Aufzahlbarkc-it H. Hermes Entscheidungsproblem und Dominospiele K. Jacobs Turing-Maschinen und zufallige 0-1-FoIgen K. Jacobs Maschinenerzeugte 0-1-Folgen SPRINGER-VERLAG Berlin-Heidelberg-New York 1970 «СОВРЕМЕННАЯ МАТЕМАТИКА» Популярная серия Машины Тьюринга и рекурсивные функции Г. -Д. Эббинхауз, К. Якобе Ф. -К. Ман, Г. Хермес Перевод с немецкого Э. Г. Белаги ИЗДАТЕЛЬСТВО «МИР» Москва 197 2 УДК 517. 11 Этот коллективный труд немецких математиков содержит элементарное изложение теории машин Тьюринга и рекурсивных функций — важного раздела современной математической логики, нашедшего широкое применение в кибернетике. Помимо основ этой теории, книга содержит ряд существенных результатов, включая достижения последнего времени (в частности, результаты Колмогорова о связи машин Тьюринга с основаниями теории вероятностей). Изложение ведется строго, но доступно, содержит много примеров и пояснений. Книгу с интересом прочтут читатели разных категорий, начиная от учащихся старших классов школ с математической специализацией и кончая научными работниками и преподавателями высшей школы. Редакция литературы по математическим наукам 2-2-3 37-72 МАШИНЫ ТЬЮРИНГА И РЕКУРСИВНЫЕ ФУНКЦИИ Г. -Д. Эббинхауз, К. Якобе, Ф. -К. Ман, Г. Хермес Редактор Н. И. Плужникова Художник А. В. Шипов Художественный редактор В. И. Шаповалов Технический редактор Е. Д. Кузнецова Корректор К. Л. Водяницкая Сдано в набор 17/IV 1972 г. Подписано к печати 6/1X 1972 г. Бумага № 1 84х 1 087з2 = 4-1 3 бум. л. 13. 86 усл. печ. л. Уч. -изд. л. 12,41. Изд. № 1/6656. Цена 89 к. Зак. 2901. ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер. , 2 Ордена Трудового Красного Знамени Первая Образцовая типография имени А. А. Жданова Главполиграфпрома Государственного комитета Совета Министров СССР по делам издательств, полиграфии и книжной торговли Москва, М-54, Валовая, 28. ОТ ПЕРЕВОДЧИКА Предлагаемая вниманию читателей книга Г. -Д. Эббин- хауза, К. Якобса, Ф. -К. Мана и Г. Хермеса «Машины Тьюринга и рекурсивные функции» представляет собой перевод второго томика серии «Selecta Mathematica»; в русское издание включена также статья К. Якобса «Машинно-порожденные 0-1 -последовательности» из первого томика той же серии. Серия «Selecta Mathematica» задумана ее редактором и одним из авторов Конрадом Якобсом, профессором Математического института университета Эрлангена — Нюрнберга, как собрание математических текстов, доступных студентам начальных курсов и преподавателям математики средних школ и позволяющих на вполне строгом уровне познакомиться с отдельными интересными современными результатами. Обзор содержания книги дан в предисловии.