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

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

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