Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.
Глава I. Основные понятия
§ 1. Функции и операции
1.1. Алфавит. Слова (17). 1.2. Функции. Термы (19). 1.3. Алгебры (24). 1.4. Кодирование (27). Примеры и задачи (30).
§ 2. Основные вычислимые операторы
2.1. Суперпозиции частичных функций (30).
2.2. Оператор примитивной рекурсии (33). 2.3.
Операция.минимизации (39). 2.4. Общерекурсивные
функции (45). Примеры и задачи (47).
Глава II. Примитивно рекурсивные функции и рекурсивно перечислимые множества
§ 3. Примитивно рекурсивные функции
3.1. Операции суммирования и мажорированного обращения (49). 3.2. Примитивная рекурсивность некоторых арифметических функций (53).
3.3. Нумерация пар и чисел (60). 3.4. Зависимости между операторами примитивной рекурсии и минимизации (64). 3.5. Одноместные примитивно рекурсивные функции (68). Дополнения, примеры и задачи (76).
§ 4. Рекурсивно перечислимые множества
4.1. Рекурсивные и примитивно рекурсивные множества (77). 4.2. Рекурсивно перечлслимые множества (79). 4.3. Порожденные множества (82). 4.4. Множества натуральных чисел (86). Примеры и задачи (91).
Глава III. Общерекурсивные и частично рекурсивные
функции
§ 5. Общерекурсивные функции
5.1. Рекурсии 2-й ступени (93). 5.2. Универсальная общерекурспвная функция (98). 5.3. Быстрорастущие функции (105). 5.4. Обращение функций. Алгебра Робинсон (108). Дополнения, примеры и задачи .
§ 6. Частично рекурсивные функции
6.1. Параметризация частично рекурсивных функций (114). 6.2. Универсальные частично рекурсивные функции (120). 6.3. Доопределение функций. Построение нерекурсивного рекурсивно перечислимого множества (123). 6.4. Исследование представления Клпни (127). Дополнения, примеры и задачи (129).
Глава IV. Нумерованные совокупности
§ 7. Нумерации совокупностей множеств n функций
7.1. Универсальные функции Клинп (133). 7.2. Нумерация Клинп (136). 7.3. Нумерация Поста (139). 7.4. Однозначные нумерации (145). Дополнения, примеры и задачи (155).
§ 8. Сводимость и креативность множеств
8.1. Сводимость и эквивалентность множеств (156). 8.2. Продуктивные и креативные множества (159). 8.3. Простые множества (163). 8.4. Максимальные множества (164). Дополнения, примеры и задачи (167).
§ 9. Нумерации произвольных совокупностей
9.1. Изоморфизм и эквивалентность нумераций (171). 9.2., Односводимость нумераций (176). 9.3. Полные нумерации (183). 9.4. Семейства объектов нумерованных совокупностей (188). Дополнения, примеры и задачи (191).
§ 10. Универсальные и креативные системы множеств
10.1. m-универсальные системы множеств (192).
10.2. Креативные системы множеств (196). 10.3. Рекурсивно неотделимые множества (199). Дополнения, примеры и задачи (202).
Глава V. Алгоритмы и машины Тьюринга
§ 11. Словарные множества и функции
11.1. Словарные множества (205). 11.2. Основные словарные операторы (209). 11.3. Прямое определение класса частично рекурсивных словарных функций (215). Дополнения и примеры (218).
§ 12. Машины Тьюринга
12.1. Машины Тьюринга - Поста (219). 12.2. Вычислимые функции (225). 12.3. Синтез машин Тьюринга (230). 12.4. Теоремы о графике и существовании универсальных частично рекурсивных функций (243). 12.5. Универсальные машины (250). Дополнения, примеры и задачи (252).
§ 13. Приложения
13.1. Проблема равенства слов в полугруппах (254). 13.2. Тождественно истинные формулы исчисления предикатов 1-й ступени (263). 13.3. Арифметические множества (270). 13.4. Формулы 2-й ступени (276). Дополнения и примеры (277).
Глава VI. Варианты машин и алгоритмов Тьюринга - Поста
§ 14 Нормальные и операторные алгоритмы
14.1. Формальные системы. Продукции Поста (284). 14.2. Нормальные алгоритмы (289). 14.3. Операторные алгоритмы (291). Дополнения и примеры (301).
§ 15. Многоленточные машины и ТАГ-системы
15.1. Общие многоленточные машины (302). 15.2. Машины Минского (304). 15.3. Однородные продукции. ТАГ-системы (315). Дополнения, примеры и задачи (320).
§ 16. Диофаптовы уравнения
16.1. Диофантовы предикаты и функции (321).
16.2. Арифметическое представление (330). 16.3.
Представимость натуральных чисел многочленами (336). 16.4. Показательные уравнения (339).
Дополнения и примеры (346).
Приложение. Диофантовость рекурсивно перечислимых множеств и предикатов (Д. А. Захаров)
Краткая аннотация книги
Посвящается одному из актуальных и бурно развивающихся разделов математической логики - теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов. Для математиков различных специальностей: научных работников, аспирантов и студентов.
Еще в 30-х годах нашего столетия математическая логика и возникавшая тогда теория алгоритмов казались наиболее абстрактными и наиболее далекими от практических приложений областями математики. В настоящее время положение коренным образом изменилось. Ныне общепризнанно, что обе названные области образуют теоретический фундамент для создания и применений быстродействующих вычислительных и управляющих систем. Резко возрос удельный вес математической логики и теории алгоритмов и в самой математике. Более того, в значительной степени через теорию алгоритмов и математическую логику происходит ныне проникновение математических методов в биологию, лингвистику, экономику вплоть до философии естествознания. Все это привело к тому, что математическую логику и теорию алгоритмов начали включать в учебные планы наших университетов и пединститутов в качестве дисциплин, обязательных для изучения студентами-математиками всех специальностей.
Настоящая книга возникла в результате обработки конспектов лекций по математической логике, теории алгоритмов и их приложений, читавшихся автором в 1956-1959 гг. Ивановском педагогическим институте и с 1960 г. в Новосибирском университете. В ней излагается лишь общая теория алгоритмов и рекурсивных функций. Целиком за пределами книги остались теория автоматов, приложения теории алгоритмов к формальным теориям, теория степеней неразрешимости. Сколько-нибудь подробное изложение этих разделов в настоящее время требует специальных монографий.
Более серьезным недостатком предлагаемой книги может оказаться отсутствие в ней сведений о реальных вычислительных машинах (что на сегодня есть уже достоинством - не надо удалять !!). Однако в настоящее время теория программирования и принципы устройства реальных вычислительных машин читаются во всех университетах в качестве самостоятельных курсов. По этим курсам написано много учебников самого различного уровня. Поэтому нам казалось излишним включать соответствующие вопросы в общую теорию алгоритмов и в данной книге они даже не упоминаются.
Так как лекции по теории алгоритмов иногда читаются до лекций по математической логике, то логическая символика используется нами в очень ограниченном размере и значения всех употребляемых логических символов подробно разъясняются. По этой же причине в книге не обсуждаются вопросы, связанные с интуиционистским и конструктивистским истолкованиями результатов.
От читателей не требуется никаких предварительных специальных знаний, выходящих за пределы программы средней школы. Доказательства всюду проведены полностью за исключением последних глав, где иногда опущены рассуждения рутинного характера, которые легко восстановит каждый читатель, добравшийся до этих глав.
Первая половина книги в несколько ином виде была издана студентами Новосибирского университета в 1960 г. ротапринтным способом. Остальные главы читались в рукописи сотрудниками и студентами кафедры алгебры и математической логики НГУ. Всем им автор признателен за советы и замечания.
Вы можете использовать скачанные с веб-сайта книги и другие материалы только для личного ознакомления. Авторское право авторов книг и любых электронных приложений к ним (в том числе фото, видео, рукописи, архивы и прочее) не подлежит патентованию и подобным "искусственным" дополнительным мерам защиты авторского права - не патентуют рукописи, фотографии, видеоматериалы, формулы, графики, сводные таблицы, тексты монографий, черновики и оригинальные издания вне зависимости от того, находятся ли они в частных или государственных архивах любой страны. Вне зависимости от того, есть ли у книги или рукописи и автора какие-либо коды или нет, подписаны они или нет, известен автор или нет, является он(а) гражданином Украины или иностранцем - запрещено явным образом присваивать чужое авторское право и ставить чужие ФИО в чужих работах и трудах (в случае неуказанного, неустановленного или сомнительного авторства наиболее предпочтительно использовать анонимность - это корректно, этично и непротивозаконно, так как в этом случае истинные владельцы будут поданы в розыск и объективно установленны в своих правах независимой комиссией).
Сегодня электронный вариант публикации приравнен к печатной бумажной форме распространения информации (требования аналогичны). Наиболее предпочтительными являются международные форматы публикаций PDF и DJVU (они лучше всего защищены от сторонних модификаций - изменения в них могут внести только профессионалы), допускаются и другие общепринятые и широко распространенные форматы электронного представления авторской или смежной информации. Помните, что один человек сам по себе ничего не делает и не решает - у любого автора любого издания есть коллеги, единомышленники, соратники, кураторы, преподаватели, наставники, идейные, политические и научные руководители и вдохновители, предшественники и приемники, завистники и плагиаторы, желающие незаконно "упасть на хвост и поехать", "присоседиться к работе" и "присоединиться". Чем серьезнее ученый и чем более масштабные объективные и фундаментальные работы он(а) реально ведет, тем большее количество мошенников и аферистов желает незаконно "находиться" и "быть рядом" с таким человеком, его деньгами, премиями, подарками и другими объективными поощрениями. Поэтому все подобные аферисты и мошенники, как и их голословные заявления, подлежат строгой проверке на практике как гласными, так и негласными методами государственного, общественного и политического независимого контроля (в том числе судебного и силового).
Вам разрешается использовать электронные публикации и иные материалы только для личного ознакомления. Никаких дополнительных прав и свобод (в том числе авторских и коммерческих прав, в том числе права на коммерческое распространение) получение и обладание электронной и иной публикации и материалов Вам не предоставляет. Вам не дает никаких прав, в т.ч. авторских и смежных прав, личное знакомство с автором и правообладателем, совместное проживание, учеба или работа, семейный и иной статус, совместное хобби и увлечения, посещение одних и тех же мероприятий, встречи, конфликты и даже отсутствие таковых. Вы не имеете право продавать электронные публикации и иные авторские материалы, отчуждать их от владельца и извлекать материальную выгоду от владения электронной и иной формой представления авторской информации. Отчуждение авторского научного и творческого права запрещено вне зависимости от срока давности издания, способа и места его хранения, разрекламированности, известности или неизвестности и даже анонимности автора и соавтора, гражданства, здоровья, болезни и любого другого объективного статуса реального правообладателя. Запрещены фото- и видеомонтажи, врезки и изъятия, компиляция из сторонних источников и другие формы заведомого мошенничества. Запрещено иностранцам без признанной в Украине и документально подтвержденной профессии, без легитимных виз и специальных персонифицированных межгосударственных соглашений занимать рабочие места граждан Украины на территории Украины и во всех предприятиях, которые являются собственностью Украины и ее граждан вне зависимости от места регистарции и дислокации этих предприятий. Запрещено работать без рабочих виз на территории Украины гражданам и подданым стран, с которыми у Украины установлен визовый режим.
Авторское право (особенно научное и творческое) никогда не патентуется, не отчуждается ни при каких обстоятельствах, не продается и не покупается и является неотъемлимым от его создателя при любых обстоятельствах - патентуются только уникальные инженерные и программные разработки, авторские алгоритмы, изобретения и подобные материалы, содержащие более 60% объективно признанных независимой государственной экспертной комиссией авторских инноваций. Незаконным является присвоение себе чужих архивов, черновиков, заметок, аудио, фото и видеоматериалов (даже если вы не знаете их автора или же непосредственно знакомы с создателем и правообладателем, это ничего не решает). Научное и творческое авторское право не отчуждается от автора и создателя и никогда не делегируется третьим лицам (особенно без профессии и неконтрафактных документов) - оно является наиболее строгим авторским правом, неотделимым от своего создателя, и не подлежит передаче, купле и продаже ни при каких обстоятельствах. Оно только может быть передано в возмездное или безвозмездное пользование БЕЗ ПРАВА НА ОТЧУЖДЕНИЕ. Главной особенностью научного и творческого авторского права является его обязательная частичная передача в безвозмездное пользование широким слоям заинтересованного населения - на этом сайте все научные книги бесплаты и свободны для скачивания без паролей, кодов и ограничений (я как владелец этого сайта и интернет-хостинг-провайдеры не несем ответственность за деятельность третьих лиц, возможные сбои и технические нарушения интернет-связи при пользовании сайтами по вине третьих лиц). Никаких искусственных препятствий, ограничений скорости, других "негативов" и препятствий мы не устанавливаем.
Государство Украина имеет достаточную базу для обеспечения научных работ и научных исследований по всем законным направлениям научной деятельности. C 2010 г. в Украине любая наука и научные исследования являются объектами строгой государственной монополии и требуют наличия не только документально признанной в Украине профессии, но и высшего государственного образования, официально признанного в Украине.
найти на этой странице (программа отметит желтым цветом) 
список книг по высшей математике с сортировкой по алфавиту. 