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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

D ≡ λt. zero? (H(tt))(K(tt))S.
Действительно, пусть терм (tt) имеет нормальную форму, тогда
Dt
≡ (λt. zero? (H(tt))(K(tt))S) t
= zero? (H(tt))(K(tt))S
= zero? <0> (K(tt))S
= true (K(tt))S
≡ K (K(tt))S
= (K(tt)
Если же
терм (tt) не имеет нормальную форму, то
Dt
≡ (λt. zero? (H(tt))(K(tt))S) t
= zero? (H(tt))(K(tt))S
= zero? <1> (K(tt))S
= false (K(tt))S
≡ (KI )(K(tt))S
= IS
= S
Для любого t терм Dt имеет нормальную форму (поскольку он равен либо K(tt),
имеющего нормальную форму, либо равен S), поэтому терм DD также имеет нормальную
форму (скажем некий комбинатор α). Согласно определению D, комбинатор DD равен
K(DD), т.е. D = α и D = Kα → λy.α. Но комбинаторы α и λy.α оба находятся в нормальной
форме и не совпадают. Получили противоречие.
Используя аналогичные идеи получены и следующие результаты о
неразрешимости. Не существует никакого общего алгоритма, позволяющего установить,
вычисляет ли некоторая конкретная программа (на любом языке программирования)
постоянную нулевую функцию [11, с. 110]. То же самое справедливо и для любой другой
конкретной вычислимой функции. И как следствие, можно утверждать, что вопрос о том,
вычисляют ли две данные программы одну и
ту же одноместную функцию, также
неразрешим. Тем самым, мы получаем, что в области тестирования компьютерных
программ, мы имеем принципиальные ограничения.
Диофантовы уравнения [11, с. 114]. Пусть p(x
1
, x
2
, ..., x
n
) – многочлен от
переменных x
1
, x
2
, ..., x
n
с целыми коэффициентами. Тогда уравнение
p(x
1
, x
2
, ..., x
n
) = 0,
для которого мы ищем только целые решения, называется диофантовым уравнением.
Первым диофантовые уравнения систематизировал и изучил греческий математик
Диофант в третьем веке нашей эры. Ниже приводится пример системы диофантовых
уравнений:
⎪
⎩
⎪
⎨
⎧
=−+−+−
=+−
=−+
.042
,065
,026
2
2
32
zyxww
zxy
yxw
Вот еще один пример:
⎪
⎩
⎪
⎨
⎧
=−+−+−
=+−
=−+
.032
,065
,026
2
2
32
zyxww
zxy
yxw

Страницы