Здравствуйте, nikov, Вы писали:

N>Доказательство теоремы Матиясевича (или, как он её называет сам, MRDP-теоремы) показывает, каким образом вопрос об остановке любого алгоритма можно механически переформулировать как вопрос наличия решений у некоторого диофантова уравнения. Если бы мы могли алгоритмически определять наличие решений у любого диофантова уравнения, то мы могли бы использовать этот способ, чтобы алгоритмически решать вопрос об остановке любого алгоритма. А это, как показал Тьюринг, невозможно. Следовательно, заключил Матиясевич, не существует алгоритма, который бы определял наличие решений у любого диофантова уравнения.
Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?
А то я тут недавно предположил, что если мы найдем способ алгоритмически решать проблему останова, то мы сможем решать любые диафантовы уравнения или доказывать,
что они не имеют решений

Автор: GhostCoders
Дата: 06.03.20

.

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