Теория алгоритмов. Зюзысов В.М. - 23 стр.

UptoLike

Составители:

Рубрика:

Решением первой системы является, в частности, следующее:

w=1, x=1, y=2, z=4,

тогда как вторая система вообще не имеет решения. В самом деле, судя по первому

уравнению, число y должно быть четным, судя по второму уравнению, число z также

должно быть четным, однако это противоречит третьему уравнению, причем при любом

поскольку значение разности w

–w – это всегда четное число, а число 3 нечетно.

Десятая проблема Гильберта, сформулированная в 1900 году, состоит в том, чтобы

установить, существует ли алгоритм, с помощью которого можно было бы проверить,

имеет ли данное диофантово уравнение решение. В 1970 году советский математик Ю.

Матиясевич доказал, что такого алгоритма не существует. Доступное доказательство

этого

можно найти в [15].

Занимательному изложению вопросов вычислимости, вплоть до получения

доказательства теоремы Гёделя, посвящена книга Р. Смаллиана [23].