Справочная книга по математической логике, часть 3, Теория рекурсии, Барвайс Д., 1982

Справочная книга по математической логике, Часть 3, Теория рекурсии, Барвайс Дж., 1982.

Понятие алгоритма становится в настоящее время одним из важнейших понятий как теоретической, так и прикладной математики. Это связано в первую очередь с современным развитием электронной вычислительной техники и необходимостью создания мощного математического обеспечения для этой техники. Немаловажными являются и связи теории алгоритмов с математической логикой и основаниями математики; точное математическое определение понятия алгоритма впервые было найдено в рамках формальных систем математической логики. Теория рекурсии — так называется этот третий том «Справочной книги по математической логике» — составляет теоретическую основу современного учения об алгоритмах. Первая вводная глава этого тома, написанная Эндертоном, довольно подробно и мотивированно знакомит читателя с тем разделом теории алгоритмов, который теперь называется «классической» теорией рекурсии. Две следующие главы, написанные соответственно Девисом и Рабином, знакомят читателя с постановками различных алгоритмических проблем, возникающих в арифметике, алгебре, математической логике и других разделах математики. Наряду с формулировками проблем здесь имеются указания на методы решения таких проблем и даны примеры. Следует отметить, что обе эти главы не могут служить обзорами по рассматриваемой проблематике, так как отбор материала в этих главах отражает довольно субъективные взгляды авторов, не заботившихся, по-видимому, ни о достаточно полном обзоре результатов, ни о точности указаний на авторство приводимых утверждений.




Машины Тьюринга.
Существует много эквивалентных способов формулировки определения рекурсивности. Формулировка, выраженная в терминах воображаемой вычислительной машины, была дана английским математиком Аланом Тьюрингом в его фундаментальной статье [1]. (Аналогичная работа была сделана одновременно, но независимо, Эмилем Постом из Нью-Йорка; см. Пост [1].) Главная трудность при нахождении этого определения была в том, что Тьюринг искал его до создания реальных цифровых вычислительных машин. На самом деле познание шло от абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг позднее сыграл вдохновляющую роль в развитии вычислительных машин. На неформальном уровне мы можем начать описывать машину Тьюринга как некий черный ящик с лентой. Лента разбита на ячейки и каждая ячейка может содержать пустой символ О, либо непустой символ 1. Лента потенциально бесконечна в обе стороны в том смысле, что мы никогда не придем к ее концу, но в любое время лишь конечное число ячеек может быть непустым. В начале лента содержит числа входа, в конце — число-выход. В промежуточное время лента используется как пространство памяти для вычисления.

Если мы откроем черный ящик, то обнаружим, что он устроен очень просто. В любой момент времени он может обозревать лишь одну ячейку памяти. Устройство содержит конечный список инструкций (или состояний) q0, q1,...,qn. Каждая инструкция может указать два возможных направления действий; одного нужно придерживаться, если на обозреваемой ячейке ленты находится 0, а другого, — если там находится 1. В любом случае следующее действие может состоять из таких трех типов элементарных шагов.

СОДЕРЖАНИЕ
Введение
§ 1. Неформальная вычислимость
§ 2. Машины Тьюринга
§ 3. Тезис Чёрча
§ 4. Универсальные машины и нормальная форма
§ 5. Оракулы и функционалы
§ 6. Рекурсивная перечислимость
§ 7. Логика и теория рекурсии
§ 8. Степени неразрешимости
§ 9. Креативные и меньшие множества
§ 10. Определимость и рекурсия
§ 11. Рекурсивные аналоги классических объектов
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Справочная книга по математической логике, часть 3, Теория рекурсии, Барвайс Д., 1982 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Теги: справочник по математике :: математика :: Барвайс