URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Эббинхауз Г.-Д., Якобс К., Ман Ф.-К., Хермес Г. Машины Тьюринга и рекурсивные функции. Пер. с нем.
Id: 16118
 
399 руб.

Машины Тьюринга и рекурсивные функции. Пер. с нем.

1972. 264 с. Мягкая обложка. Букинист. Состояние: 4+. .

 Аннотация

Этот коллективный труд немецких математиков содержит элементарное изложение теории машин Тьюринга и рекурсивных функций - важного раздела современной математической логики, нашедшего широкое применение в кибернетике. Помимо основ этой теории, книга содержит ряд существенных результатов, включая достижения последнего времени (в частности, результаты Колмогороа о связи машин Тьюринга с основаниями теории вероятностей). Изложение ведется строго, но доступно, содержит много примеров и пояснений. Книгу с интересом прочтут читатели разных категорий, начиная от учащихся старших классов школ с математической специализацией и кончая научными работниками и преподавателями высшей школы.


 ОГЛАВЛЕНИЕ

От переводчика...................... 5

Предисловие........................ 7

Машины Тьюринга и вычислимые функции I. Уточнение понятия алгоритма. Г.-Д. Эббинхауз............ 9

§ 1. Нестрогие предварительные соображения...... 9

§ 2. Наглядное описание и определение машины Тьюринга 20

Машины Тьюринга и вычислимые функции П. Ф.-К. Ман 34

§ 3. Примеры машин Тьюринга. Диаграммы Тьюринга.. 34

§ 4. Нормированная вычислимость по Тьюрингу.... 55

§ 5. Простые примеры неразрешимых множеств..... 68

Машины Тьюринга и вычислимые функции III. Г.-Д. Эббинхауз.......................... 74

§ 6. Универсальная машина Тьюринга и теорема Клини

о перечислимости................. 74

Литература.................... 84

Перечислимость. Г.-Д. Эббинхауз.............. 86

§ 1. Введение..................... 86

§ 2. Простые теоремы о перечислимых множествах... 91

§ 3. Перечислимость по Тьюрингу........... 95

§ 4. Перечислимость по Шмульяну.......... 107

§ 5. Перечислимость по Шмульяну и Тьюрингу..... 118

§ 6. Неперечислимость множества истинных арифметических высказываний и неразрешимость арифметики.. 126

Литература.................... 149

Проблема разрешимости и игра «домино». Г. Хермес..... 150

§ 1. К проблеме разрешимости логики предикатов. Часть 1 150 § 2. Выражения, префиксы, типы префиксов. Классы выражений, определяемые такими типами...... 153

§ 3. Выполнимость выражений............. 155

§ 4. К проблеме разрешимости логики предикатов.

Часть 2..................... 158

§ 5. Проблемы домино................. 160

§ 6. Сопоставление таблице Тьюринга угловой игры

«домино», Х?................ 163

§ 7. Лемма. Если м (т) после применения к пустой ленте не останавливается, то угловая игра «домино» ?т,

Xj- правильная.................. 165

§ 8. Лемма. Если угловая игра «домино» х т, правильная, то машина м (т) после применения к пустой ленте никогда не останавливается....... 167

§ 9. Определение выражения а-, (-.<,, соответствующего

угловой игре «домино» 2), Х°............ 171

§ 10. Лемма. Если угловая игра «домино» ЛГ, ?° правильная, то СС , ?0 выполнимо............. 173

§11. Лемма. Угловая игра «домино»  D° правильна, если

ео выполнимо................. 175

§ 12. Переход к узкой логике предикатов........ 176

§ 13. Обзор проблемы разрешимости для класса выраже-

жений л V Л и диагональной игры «домино».... 179

Литература.................... 182

Машины Тьюринга и случайные 0-1-последовательности.

К- Якобе....................... 183

§ 1. Сложность конечных 0-1-слов по Колмогорову... 190

§ 2. Один неудавшийся подход............ 196

§ 3. Пространство бесконечных 0-1-последовательностей 201

§ 4. Случайные бесконечные 0-1-последовательности... 207

Литература......,............ 214

Машинно-порожденные 0-1-последовательности. К- Якобе.. 216

§ 1. Один алгоритм порождения 0-1-последовательностей 219

§ 2. Апериодичность................. 226

§ 3. Почти-периодичность............... 232

§ 4. Средние значения................ 234

§ 5. Периодичность.................. 242

§ 6. Задачи...................... 245

Литература................... 247

Указатель обозначений................... 248

Именной указатель.................... 249

Предметный указатель................... 251

 
© URSS 2016.

Информация о Продавце