Булос Дж., Джеффри Р. Вычислимость и логика

Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006. - 17 с. Методическое пособие по дисциплине «Математическая логика и теория алгоритмов». Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.

М.: МЦНМО, 1999-2000. Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. Начала теории множеств. Множества и мощности. Упорядоченные множества. Языки и исчисления. Логика высказываний. Исчисление высказываний. Языки первого порядка. Исчисление предикатов. Теории и модели. Вычислимые функции. Вычислимость, разрешимость и перечислимость. Универсальные функции и неразрешимость. Нумерации...

Перевод с англ. А. А. Мучника под ред. С. Ю. Маслова Книга известного английского математика, охватывающая основные вопросы теории вычислимых функций и ее приложений: сложность вычислений и алгоритмов, теоремы Гёделя о неполноте и Чёрча о неразрешимости, семантику языков программирования. Изложение замкнутое, методически продуманное, имеется много упражнений. Для математиков, специалистов по ЭВМ, желающих ознакомиться с теоретическими основами...

Автор не известен. 136 с. Лекции в виде презентации. Содержание. - Алгоритмы в математике. Основные черты алгоритмов. Числовые функциии алгоритмы их вычисления. Примитивно рекурсивные функции. - Частично рекурсивные функции.Тезис Черча. - Машины Тьюринга и машины с неограниченными регистрами. Вычислимость частично рекурсивных функций на МНР. - Нумерации и универсальные функции. - Нормальные алгорифмы. - Алгоритмические проблемы в логике и матем...

Автор неизввестен. Сборник статей. Фрагмент книги, с. 213- 278. Выходных данных нет. Статьи: Шеннон. Клод Э. "Универсальная машина Тьюринга с двумя внутренними состояниями " Дэвис М. Д. "Замечание об универсальных машинах Тьюринга" Маккартни Дж. "Обращение функций, определяемых машинами Тьюринга" К. де Леу, Э. Ф. Мур, К. Э. Шеннон, Н. Шапиро "Вычислимость на вероятностных машинах"

Учебное пособие. Новосибирск: НГУ, 2005. 114 с. Данная книга - изложение курса лекций по теории алгоритмов, читанного автором на математическом факультете Новосибирского госуниверситета в 2001-2003 годах. Задача учебника - дать хорошее интуитивное понимание математического понятия алгоритма и служить введением для дальнейшего изучения других руководств по теории алгоритмов, а также служить методологической основой для изучения других предметов,...

Автор неизвестен. Конспект лекций по курсу "Матем. логика и теория алгоритмов". 2008 год. - 80 стр. Исчисления высказываний. Определение формального исчисления. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. Логика и исчисления предикатов. Алгебр. системы. Формулы сигнатуры...

Новосибирск: НГУ, 2005. - 130 с. Курс по теории алгоритмов является составной частью дисциплины "Математическая логика", читаемого на 2-3 курсах механико-математического факультета НГУ. В настоящем курсе подробно рассматриваются конечные автоматы и языки, рекурсивные функции и понятие вычислимости, вопросы сложности вычислений.

М.: Изд-во Моск. гос. ун-та гражд. авиации, 2003. - 237 с. Учебное пособие. Содержание: Множества и мощности. Упорядоченные множества. Логика высказываний. Языки первого порядка. Исчисление предикатов. Вычислимые и универсальные функции. Машины Тьюринга. В основном тексте содержится более 200 задач теоретической направленности.

Ответы на вопросы: Машина Тьюринга. Конструирование МТ. Вычислимые по Тьюрингу функции: ПРФ, ЧРФ. Правильная вычислимость. Уточнение понятия алгоритма через машину с неограниченными регистрами. нормальные алгоритмы Маркова. Вычислимые функции и разрешимые множества: вычислимость, разрешимость, перечислимость, множество n-ок нат чисел, диагональная конструкция, главные универсальные функции, универсальная ОРФ, перечислимое неразрешимое множество.r...