Алгоритмическая разрешимость. Алгоритмически неразрешимые задачи

Июль 22, 2022

Главная
Математика
Алгоритмическая разрешимость. Алгоритмически неразрешимые задачи

Содержание

2. Алгоритмически неразрешимые задачи Давид Гильберт на Международном математическом конгрессе в Париже в 1900 году опубликовал список
3. Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью «О вычислимых числах
4. Методы доказательства неразрешимости Косвенный метод «От противного» Исходя из предположения о разрешимости данной проблемы, путем набора
5. Теорема. Задача об остановке произвольной машины Тьюринга на произвольном входном слове алгоритмически неразрешима. Иными словами, нельзя
6. от противного Предположим, что задача об остановке произвольной машины Т при обработке произвольного слова t алгоритмически
7. Д обрабатывает эти два слова и пишет “да”, если Т останавливается при обработке t, и “нет“
8. Построим машину F. F работает как E, но отличие состоит в том, что, если после работы
9. Если данный алгоритм работает для произвольной машины Т, то и для конкретной тоже будет работать. Положим
10. Поскольку Т=F, имеем ситуацию: F остановится, если F не остановится, и F не остановится, если F
11. Если бы имелся алгоритм (а значит и соответствующая машина Тьюринга) для решения проблемы остановки произвольной машины
12. S0 Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на пустой ленте для некоторой
13. Новая машина MTt начинает работу на пустой ленте и работает по следующей программе: S1 λ →
14. https://www.youtube.com/watch?v=92WHN-pAFCs Мультфильм
15. По сути, машина MTt просто печатает копию ленты t на своей ленте, затем выбирает нужную позицию
16. Теорема. Задача об остановке конкретной универсальной машины на произвольной ленте специального типа алгоритмически неразрешима (без доказательства)
17. Если предположить, что процесс вычислений в конечном итоге завершится, то с математической точки зрения можно найти
18. При этом машина U (а точнее, ее более продвинутая модификация), может начать имитацию поведения машины Т
19. Теорема Задача о печатании данного символа на чистой ленте точно один раз алгоритмически не разрешима. Доказательство
20. Построим машину Е, которая работает как D вплоть до ее остановки. После этого машина Е печатает
21. Теорема. Задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима. Доказательство: Без
22. Построим машину Е, которая работает как D вплоть до ее остановки. После этого машина Е переходит
23. Теорема. Задача о печатании данного символа на чистой ленте хотя бы один раз алгоритмически неразрешима. Доказательство:
24. Т.о. получим, что символ «0» печатается хотя бы один раз в том случае, если произвольная машина
25. Две машины Тьюринга, имеющие один и тот же внешний алфавит, будем называть взаимозаменяемыми, если, каково бы
26. (без доказательства) Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует алгоритма, позволяющего для любой
27. Причины: Отсутствие общего метода решения задачи Информационная неопределенность задачи Логическая неразрешимость Другие неразрешимые задачи
28. Пример 1: Распределение девяток в записи числа Пи Определим функцию f(n) = i, где n –
29. Пример 2: Вычисление совершенных чисел Совершенные числа – это числа, которые равны сумме своих делителей, например:
30. Пример 3: Десятая проблема Гильберта Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует
31. Пример 4: Позиционирование машины Поста на последний помеченный ящик Пусть на ленте машины Поста заданы наборы
32. Пример 5: Проблема «останова» (теорема 1) Пример 6: Проблема эквивалентности алгоритмов По двум произвольным заданным алгоритмам
33. 23 проблемы Гильберта 12 – решены полностью 4 – требуют уточнения формулировок Остальные – не решены
34. СЕМЬ задач тысячелетия Задачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных как «важные классические
36. Скачать презентацию

Слайд 2

Алгоритмически неразрешимые задачи
Давид Гильберт на Международном математическом конгрессе в Париже в

1900 году опубликовал список неразрешенных математических проблем (23 шт).
Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт – «в математике не может быть неразрешимых проблем», в связи с этим формулировка проблем была руководством к действию, констатацией отсутствия решений в данный момент.
Однако многие проблемы никак не решались….

Слайд 3

Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического

общества статью «О вычислимых числах в приложении к проблеме разрешения»

Для любой ли задачи существует алгоритм решения?

Любой алгоритм можно преобразить в машину Тьюринга
Утверждение о существовании алгоритмически неразрешимых проблем является весьма сильным – мы констатируем, что мы не только сейчас не знаем соответствующего алгоритма, более того, мы не можем принципиально никогда его найти.

Слайд 4

Методы доказательства неразрешимости
Косвенный метод «От противного»
Исходя из предположения о разрешимости

данной проблемы, путем набора логических преобразований (переходов) приходим к противоречию с доказанными ранее утверждениями либо с элементарной логикой (со здравым смыслом).
Часто показывается, что разрешимость исследуемой проблемы влечёт разрешимость проблемы, о которой уже известно, что она неразрешима

принято при доказательстве алгоритмической неразрешимости некоторой задачи сводить ее к ставшей классической задаче – «задаче останова».

Прямые

Косвенные

Слайд 5

Теорема. Задача об остановке произвольной машины Тьюринга на произвольном входном слове

алгоритмически неразрешима.
Иными словами, нельзя придумать универсальный алгоритм, в результате выполнения которого будет получен однозначный ответ: “да”- если произвольная машина Т остановится на ленте с произвольным входным словом t и “нет” – если Т не остановится на ленте t.

Задачи об остановке машин Тьюринга

Слайд 6

от противного
Предположим, что задача об остановке произвольной машины Т при обработке

произвольного слова t алгоритмически разрешима. Это означает, что существует алгоритм решения, а значит и существует реализующая его машина Тьюринга Д.
Построим машину Д, на ленте которой записано кодовое описание машины Т и кодовое описание входного слова t (начальное состояние ленты машины Д).

Доказательство

кодовое описание машины Т

кодовое описание входного слова t

Слайд 7

Д обрабатывает эти два слова и пишет “да”, если Т останавливается

при обработке t, и “нет“ если этого не происходит. Если этот алгоритм работает для любого случая (любого входного слова t), то должен работать и для частного случая. В качестве начального слова, в том числе, можно выбрать описание машины, т.е. возьмем dt = dT.
Построим машину Е, которая будет на своей ленте иметь описание произвольной машины Т. Работа машины Е состоит в том, что она копирует описание dT , а затем работает как Д. Если существует Д,
то существует Е.

Доказательство

Слайд 8

Построим машину F.
F работает как E, но отличие состоит в

том, что, если после работы на входном слове dT машина Е останавливается с ответом “да” (что означает что машина Т останавливается), то машина F не останавливается, а продолжает бесконечное движение вправо без изменения знаков на ленте.
Если же вдруг машина Е останавливается с ответом «нет» (это означает, что машина Т не останавливается), то F просто останавливается.

Доказательство

Слайд 9

Если данный алгоритм работает для произвольной машины Т, то и для

конкретной тоже будет работать. Положим Т=F. Таким образом, на ленте машины F оказывается описание самой машины F. В результате получим, что машина F анализирует саму себя (F – самоанализирующая машина).
Получаем, что F не останавливается в том случае, если Е остановится с ответом “да”, а это означает, что машина Т остановится.

Доказательство

Слайд 10

Поскольку Т=F, имеем ситуацию: F остановится, если F не остановится, и

F не остановится, если F остановится, что явно противоречит здравому смыслу. Такой машины существовать не может.
Поскольку все рассуждения были логически обоснованы, полученное противоречие означает, что ошибка в изначальном предположении о существовании машины Д.
Отсюда напрямую следует, что задача об остановке произвольной машины Т на произвольном слове t алгоритмически неразрешима, Q.E.D.

Доказательство

Слайд 11

Если бы имелся алгоритм (а значит и соответствующая машина Тьюринга) для

решения проблемы остановки произвольной машины при обработке произвольного слова, то эта машина могла бы решить и проблему остановки на пустой ленте как частный случай. Но неразрешимость проблемы остановки при анализе произвольного слова непосредственно не означает неразрешимости проблемы остановки на пустой ленте, потому как последняя задача может оказаться более простой, так как ее сфера применения явно уже.
Однако мы можем показать, что эти задачи эквиваленты, в том случае, если для каждой пары машина-лента (T-t) докажем наличие соответствующей машины MTt , работающей на чистой ленте.

Теорема. Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима.

Слайд 12

S0
Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на

пустой ленте для некоторой другой машины, предположим MTt. Машина MTt строится непосредственно по описанию T и t, если диаграмму состояний Т дополнить последовательностью новых состояний.
Предположим, что для пары T, t в некоторый момент времени лента выглядит таким образом
∂ r1 r2 … rm rm+1 rm+2 … rn λ λ λ

Доказательство

Слайд 13

Новая машина MTt начинает работу на пустой ленте и работает по

следующей программе:
S1 λ → r1 R S2
S2 λ → r2 R S3
…
Sm λ → rm R Sm+1
Sm+1 λ → x R Sm+2
Sm+2 λ → rm+2 R Sm+3
…
Sn λ → rn L Sх
Sх rn-1 → rn-1 L Sх
Sх rn-2 → rn-2 L Sх
…
Sх rm+2 → rm+2 L Sх
Sх х → rm+1 L S0
S0 rm → далее работа аналогично машине Т на ленте t,
где: x – некоторая буква, в других случаях не встречающаяся на входной ленте t; S1, …, Sn, Sх – новые состояния машины MTt, которых не было
в машине Т.

Слайд 14

https://www.youtube.com/watch?v=92WHN-pAFCs
Мультфильм

Слайд 15

По сути, машина MTt просто печатает копию ленты t на своей

ленте, затем выбирает нужную позицию и после этого становится полностью идентичной машине Т. Значит MTt и Т - эквивалентные машины.
Предположим, что задача об остановке машины на чистой ленте алгоритмически разрешима, значит ее можно решить и применительно к машине MTt, начинающей работу на чистой ленте. Соответственно, такая задача решается и для машины Т на ленте t, что есть противоречие с доказанным ранее утверждением о том, что для произвольной машины Т задача остановки при обработке произвольного слова t алгоритмически неразрешима. Отсюда следует, что задача об остановке машины на чистой ленте
алгоритмически неразрешима, Q.E.D.

Т.о. машина MTt при запуске на пустой ленте эквивалента машине Т, работающей на ленте t,

Слайд 16

Теорема. Задача об остановке конкретной универсальной машины на произвольной ленте специального

типа алгоритмически неразрешима (без доказательства)

Помещение описания машины Т и ленты t на ленте универсальной машины U и запуск последней дает некоторое упрощение проблемы останова. В случае когда Т на ленте t остановится, логично утверждать что остановится и машина U. Соответственно, если Т на ленте t никогда не остановится, логично утверждать что никогда не становится и машина U. Т.о. общая проблема с произвольной машиной и произвольной лентой легко сводится к проблеме конкретной универсальной машины U с лентой вида

Слайд 17

Если предположить, что процесс вычислений в конечном итоге завершится, то с

математической точки зрения можно найти верхнюю границу времени, затраченного на вычисления.
Такая граница безусловно существует, потому что машина Т имеет известное число n состояний, ее алфавит состоит из известного числа m символов, а лента t содержит известное число q непустых ячеек. Т.о. в природе существует только конечное число вычислений, связанных со значениями (n,m,q), и, следовательно, только конечное число вычислений, кончающихся остановом. Тогда f(n,m,q) - точная длина самого длинного процесса вычисления из этого конечного множества.

Слайд 18

При этом машина U (а точнее, ее более продвинутая модификация), может

начать имитацию поведения машины Т с лентой t и вести счет числа циклов. Если вычисление не завершилось за время f(n,m,q), то U может смело останавливаться и сообщать что вычисления на машине Т никогда не закончатся.
При всей логичности такого хода решения проблемы оказывается, что не существует машины, которая может вычислить верхнюю границу функции f(n,m,q), при всем при том, что сама эта граница существует.

Слайд 19

Теорема
Задача о печатании данного символа на чистой
ленте точно один

раз алгоритмически не
разрешима.
Доказательство
Без ограничения общности, возьмем знак «0». Итак, машина Тьюринга Т работает на чистой ленте. Преобразуем ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины. Очевидно, что D остановится тогда, когда остановится Т.

Задачи о печатании символов

Слайд 20

Построим машину Е, которая работает как D вплоть до ее остановки.

После этого машина Е печатает «0» и тоже останавливается.
Т.о. получим, что символ «0» печатается точно один раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит, задача о печатании ровно одного нуля равносильна задаче об остановке машины на чистой ленте.
Поскольку задача останова алгоритмически неразрешима, то и задача о печатании символа точно один раз тоже неразрешима, Q.E.D.

Доказательство

Слайд 21

Теорема. Задача о печатании данного
символа на чистой ленте бесконечно

много
раз алгоритмически неразрешима.
Доказательство:
Без ограничения общности, возьмем знак «0». Итак, машина Тьюринга Т работает на чистой ленте. Преобразуем ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины.
Очевидно, что D остановится тогда, когда остановится Т.

Слайд 22

Построим машину Е, которая работает как D вплоть до ее остановки.

После этого машина Е переходит в состояние А и печатает «0» бесконечно много раз (Aλ → 0RA).
Т.о. получим, что символ «0» печатается бесконечно много раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит, задача о печатании бесконечно большого числа нулей равносильна задаче об остановке машины на чистой ленте.
Поскольку задача останова алгоритмически неразрешима, то и задача о печатании символа бесконечно много раз тоже не разрешима, Q.E.D.

Доказательство

Слайд 23

Теорема. Задача о печатании данного
символа на чистой ленте хотя

бы один раз
алгоритмически неразрешима.
Доказательство:
Без ограничения общности, возьмем знак «0». Итак, машина Тьюринга Т работает на чистой ленте. Построим машину Е, которая работает как Т вплоть до ее остановки. После чего машина Е печатает «0» и останавливается. В итоге будет напечатан хотя бы один символ «0» (возможно и больше, если ранее машиной Т такой символ уже печатался).

Слайд 24

Т.о. получим, что символ «0» печатается хотя бы один раз в

том случае, если произвольная машина Т останавливается на чистой ленте.
Значит, эта задача равносильна задаче об остановке машины на чистой ленте.
Поскольку эта задача согласно доказанной ранее теореме алгоритмически неразрешима, то и задача о печатании символа хотя бы один раз тоже неразрешима, Q.E.D.

Доказательство

Слайд 25

Две машины Тьюринга, имеющие один и тот же внешний алфавит, будем

называть взаимозаменяемыми, если, каково бы ни было слово в их общем алфавите, они либо перерабатывают его в одно и то же слово, либо обе к нему неприменимы.
Свойство машин Тьюринга называется инвариантным, если любые две взаимозаменяемые машины либо обе обладают этим свойством, либо обе не обладают.
Свойство машин Тьюринга называется нетривиальным, если существуют как машины,
обладающие этим свойством, так и не
обладающие им.

Обобщение проблемы неразрешимости

Слайд 26

(без доказательства)
Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует

алгоритма, позволяющего для любой машины Тьюринга узнать, обладает ли она этим свойством.

Теорема Райса

Слайд 27

Причины:
Отсутствие общего метода решения задачи
Информационная неопределенность задачи
Логическая неразрешимость
Другие неразрешимые задачи

Слайд 28

Пример 1: Распределение девяток в записи числа Пи
Определим функцию f(n) = i,

где n – количество девяток подряд в десятичной записи числа Пи, а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.
Задача состоит в вычислении функции f(n) для произвольно заданного n.
Поскольку число Пи является иррациональным и трансцендентным, то мы не знаем никакой информации о распределении девяток (равно как и любых других цифр) в десятичной записи числа. Вычисление f(n) связано с вычислением последующих цифр в разложении , до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно – мы даже не знаем в принципе (по природе числа ) существует ли решение для всех n.

Отсутствие общего метода решения задачи

Слайд 29

Пример 2: Вычисление совершенных чисел
Совершенные числа – это числа, которые равны

сумме своих делителей, например: 28 = 1+2+4+7+14.
Определим функцию S(n) = n-ое по счёту совершенное число и поставим задачу вычисления S(n) по произвольно заданному n.
Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно-бесконечно, поэтому наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?

Отсутствие общего метода решения задачи

Слайд 30

Пример 3: Десятая проблема Гильберта
Пусть задан многочлен n-ой степени с целыми

коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?
Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.

Отсутствие общего метода решения задачи

Слайд 31

Пример 4: Позиционирование машины Поста на последний помеченный ящик
Пусть на ленте

машины Поста заданы наборы помеченных ящиков (кортежи) произвольной длины с произвольными расстояниями между кортежами и головка находится у самого левого помеченного ящика. Задача состоит в установке головки на самый правый помеченный ящик последнего кортежа.
Попытка построения алгоритма, решающего эту задачу приводит к необходимости ответа на вопрос – когда после обнаружения конца кортежа мы сдвинулись вправо по пустым ящикам на М позиций и не обнаружили начало следующего кортежа – больше на ленте кортежей нет или они есть где-то правее? Информационная неопределенность задачи состоит в отсутствии информации либо о количестве кортежей на ленте, либо о максимальном расстоянии между кортежами – при наличии такой информации (при разрешении информационной неопределенности) задача становится алгоритмически разрешимой.

Информационная неопределенность задачи

Слайд 32

Пример 5: Проблема «останова» (теорема 1)
Пример 6: Проблема эквивалентности алгоритмов
По двум

произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
Пример 7: Проблема тотальности
По произвольному заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных.

Логическая неразрешимость

Слайд 33

23 проблемы Гильберта
12 – решены полностью
4 – требуют уточнения формулировок
Остальные

– не решены или решены частично
http://ru-wiki.org/Проблемы_Гильберта
----------------------------------------------------------------------
Например, проблема простых чисел №8
(гипотеза Римана и проблема Гольдбаха)
проблема Гольдбаха Любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел. (решена частично: доказано что любое нечётное число, большее 5, можно представить
в виде суммы трёх простых чисел).

Слайд 34

СЕМЬ задач тысячелетия
Задачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных

как «важные классические задачи, решение которых не найдено вот уже в течение многих лет».
За решение каждой из этих проблем институтом Клэя предложен приз в 1 000 000 долларов США.
Из 23 проблем Гильберта только одна — гипотеза Римана — вошла в список Проблем тысячелетия.
На данный момент только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена (автор решения - российский математик Г. Я. Перельман)

Алгоритмическая разрешимость. Алгоритмически неразрешимые задачи

Содержание

Алгоритмически неразрешимые задачиДавид Гильберт на Международном математическом конгрессе в Париже в

Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического

Методы доказательства неразрешимостиКосвенный метод «От противного» Исходя из предположения о разрешимости

Теорема. Задача об остановке произвольной машины Тьюринга на произвольном входном слове

от противногоПредположим, что задача об остановке произвольной машины Т при обработке

Д обрабатывает эти два слова и пишет “да”, если Т останавливается

Построим машину F. F работает как E, но отличие состоит в

Если данный алгоритм работает для произвольной машины Т, то и для

Поскольку Т=F, имеем ситуацию: F остановится, если F не остановится, и

Если бы имелся алгоритм (а значит и соответствующая машина Тьюринга) для

S0Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на

Новая машина MTt начинает работу на пустой ленте и работает по

https://www.youtube.com/watch?v=92WHN-pAFCsМультфильм

По сути, машина MTt просто печатает копию ленты t на своей

Теорема. Задача об остановке конкретной универсальной машины на произвольной ленте специального

Если предположить, что процесс вычислений в конечном итоге завершится, то с

При этом машина U (а точнее, ее более продвинутая модификация), может

Теорема Задача о печатании данного символа на чистой ленте точно один

Построим машину Е, которая работает как D вплоть до ее остановки.

Теорема. Задача о печатании данного символа на чистой ленте бесконечно

Построим машину Е, которая работает как D вплоть до ее остановки.

Теорема. Задача о печатании данного символа на чистой ленте хотя

Т.о. получим, что символ «0» печатается хотя бы один раз в

Две машины Тьюринга, имеющие один и тот же внешний алфавит, будем

(без доказательства)Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует

Причины:Отсутствие общего метода решения задачиИнформационная неопределенность задачиЛогическая неразрешимостьДругие неразрешимые задачи

Пример 1: Распределение девяток в записи числа ПиОпределим функцию f(n) = i,

Пример 2: Вычисление совершенных чиселСовершенные числа – это числа, которые равны

Пример 3: Десятая проблема ГильбертаПусть задан многочлен n-ой степени с целыми

Пример 4: Позиционирование машины Поста на последний помеченный ящикПусть на ленте

Пример 5: Проблема «останова» (теорема 1)Пример 6: Проблема эквивалентности алгоритмовПо двум

23 проблемы Гильберта12 – решены полностью 4 – требуют уточнения формулировокОстальные

СЕМЬ задач тысячелетияЗадачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных

Похожие презентации

Алгоритмически неразрешимые задачи
Давид Гильберт на Международном математическом конгрессе в Париже в

Методы доказательства неразрешимости
Косвенный метод «От противного»
Исходя из предположения о разрешимости

от противного
Предположим, что задача об остановке произвольной машины Т при обработке

Построим машину F.
F работает как E, но отличие состоит в

S0
Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на

https://www.youtube.com/watch?v=92WHN-pAFCs
Мультфильм

Теорема
Задача о печатании данного символа на чистой
ленте точно один

Теорема. Задача о печатании данного
символа на чистой ленте бесконечно

Теорема. Задача о печатании данного
символа на чистой ленте хотя

(без доказательства)
Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует

Причины:
Отсутствие общего метода решения задачи
Информационная неопределенность задачи
Логическая неразрешимость
Другие неразрешимые задачи

Пример 1: Распределение девяток в записи числа Пи
Определим функцию f(n) = i,

Пример 2: Вычисление совершенных чисел
Совершенные числа – это числа, которые равны

Пример 3: Десятая проблема Гильберта
Пусть задан многочлен n-ой степени с целыми

Пример 4: Позиционирование машины Поста на последний помеченный ящик
Пусть на ленте

Пример 5: Проблема «останова» (теорема 1)
Пример 6: Проблема эквивалентности алгоритмов
По двум

23 проблемы Гильберта
12 – решены полностью
4 – требуют уточнения формулировок
Остальные

СЕМЬ задач тысячелетия
Задачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных