Т. А. Сливина математическая логика и теория алгоритмов

4. Неразрешимость десятой проблемы Гильберта о диофантовых уравнениях.
Сущность этой проблемы излагалась в §3 и там же указывалось, что доказательство алгоритмической неразрешимости этой проблемы было дано в I960 году молодым Петербургским математиком Ю. Матиясевичем.


Задачи и упражнения

1. Доказать, что функция G(x,y)=x^y общерекурсивна.

2. Реализовать на машине Тьюринга алгоритм вычисления функции .
3. Построить машину Тьюринга для реализации алгоритма (вычисления функции) .
4. Реализовать на машине Тьюринга алгоритм вычисления функции .
5. Построить машину Тьюринга для реализации алгоритма (вычисления функции) .


Заключение

В учебном пособии изложен основной материал математической логики и теории алгоритмов, без знания которого вообще немыслимо построение какой бы то ни было серьезной теории.

Современная математическая логика представляет собой обширный и разветвленный раздел математики, источником проблем для которого наряду с внутренними ее проблемами могут быть как философские проблемы математики и логики, так и проблемы, возникающие в других разделах математики (алгебра, анализ, математическая кибернетика, программирование и др.). Аппарат математической логики может быть использован в вычислительной математике и в технике в связи с конструированием сложных автоматических устройств.
Знание основ можно использовать для дальнейшего развития теории, например, в теории графов по следующим направлениям:
― логическая теория графов;
― алгебраическая теория графов;
― рекуррентные свойства графов;
― вероятностные графы;
― бесконечные графы и др.
Учебное пособие содержит примеры решений задач и упражнений для самостоятельной работы. Их подбор призван способствовать закреплению материала, излагаемого в теоретическом курсе.
Типовые задачи снабжены решениями, которые могут быть использованы студентами для самостоятельного изучения предмета и овладения общими принципами применения описанных методов и алгоритмов.
В учебном пособии раскрыта лишь часть материала по данной тематике, что обусловлено небольшим объемом изучаемого курса. Однако автор надеется, что, изучив материал пособия, студенты и специалисты, имеющие мало опыта в данных вопросах, проявят интерес к дальнейшему изучению и применению этих знаний для решения возникающих перед ними задач в профессиональной деятельности и научно-исследовательской работе.
Создание этого учебного пособия не было бы возможно без коллектива кафедры прикладной математики Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. На разных этапах подготовки этой книги большую помощь и поддержку оказали доктор технических наук, профессор В.А. Охорзин и кандидат технических наук, доцент А.В. Саяпин. Выражаю свою искреннюю признательность и благодарность коллегам кафедры.