City: Saint Petersburg Novosibirsk Kazan Language: Русский English

What can be done with real numbers and cannot be done with integers
Saint Petersburg / autumn 2013, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Курс будет состоять из двух формально независимых частей. Взятые вместе, они демонстрируют существенное различие, с алгоритмической точки зрения, вещественных чисел и целых чисел. А именно, в первой части будет изложена версия алгоритм Тарского, позволяющего установить истинность или ложность любой замкнутой арифметической формулы первого порядка с переменными для вещественных чисел. В качестве бесплатного приложения этот алгоритм дает разрешимость элементарной геометрии (через введенный Р. Декартом метод координат). Во второй части будет рассказано про отрицательное решение десятой проблемы Гильберта, в которой он просил найти алгоритм, который позволял бы по произвольному диофантову уравнению узнавать, имеет ли оно решения в целых числах — такого алгоритма не существует.

Статья Юрия Владимировича Матиясевича Алгоритм Тарского в журнале Компьютерные инструменты в образовании: http://ipo.spb.ru/journal/index.php?article/1002/

Lecture notes: Yury Matiysevich. On Hilbert's Tenth Problem http://www.mathtube.org/sites/default/files/lecture-notes/Matiyasevich.pdf

Задачи из книжки: 1.2, 1.11, 1.13, 1.14, 1.15, 3.1, 3.2, 3.3, 3.4, 3.6, 3.17, 5.8, 6.1, 7.1, 7.2, 7.5, 7.7, 8.2, 8.5, 8.6, 8.7, 8.8, 8.10, 10.1В, 10.2.

Скан нескольких страниц: [pdf]

Первая и пятая главы: http://logic.pdmi.ras.ru/~yumat/H10Pbook/index.html