Найти универсальный алгоритм для решения задач — отличная цель. Но всегда ли он существует? Разбираемся вместе с математиками.
Итак, все началось с диофантовых уравнений.
📝 Что такое диофантовы уравнения
Это уравнения, обе части которых — многочлены с целыми коэффициентами. Еще одно условие: решения для них нужно найти в целых числах. Сегодня такие уравнения встречаются в том числе в прикладных задачах: например, секвенировании ДНК.
Помните, совсем недавно мы рассказывали о «проблемах Гильберта»? Одна из них, десятая, посвящена именно диофантовым уравнениям.
Десятая проблема звучит так
Для заданного диофантового уравнения указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах.
Примеры:
x^2 + y^2 - 5 = 0 имеет решения в целых числах, например (1,2) или (-2,-1)
А вот x^2 + y^2 - 3 = 0 не имеет решений в целых числах.
Под «способом», который предлагал найти Гильберт, сейчас подразумевают алгоритм. Математик предвидел, что исследование десятой проблемы потребует развития вычислительных методов. Так и оказалось: благодаря ей появилась теория алгоритмов и вычислимости.
📝 Решили ли десятую проблему
Ну, как вам сказать...
Гильберт считал, что любую математическую задачу можно решить, главное — найти определенный метод для этого. А в 1970 году Юрий Матиясевич «решил» десятую проблему и доказал: универсального алгоритма для решения произвольных диофантовых уравнений не существует. То есть нельзя написать программу, которая говорила бы, можно ли решить то или иное уравнение или нет. Кстати, теперь задачи такого типа называют неразрешимыми.
А мы благодаря Гильберту и Матиясевичу знаем, что автоматизировать все задачи на самом деле невозможно,
#задача