Печальная Семантика Крипке

Алгоритмически не разрешимое отношение

Пусть T – тьюрингова программа, работающая в алфавите A, и пусть kod (T) - слово в алфавите A, кодирующее программу T (на деталях кодирования не останавливаемся).

Программа T называется самоприменимой, если при подаче ей на вход ее собственного кода, она через конечное число шагов остановится; в противном случае программа называется несамоприменимой. Пусть M – множество кодов самоприменимых программ.

Теорема. Множество M, состоящее из кодов самоприменимых программ алгоритмически неразрешимо.

Доказательство. Пусть M – алгоритмически разрешимо. Тогда существуют две программы T ₁ и T ₂ такие, что T ₁ останавливается только на словах из M, а T ₂ – только на cловах из . Тогда, если T ₂ на своем собственном коде остановится, то по определению множества M получим kod (T ₂) M, а по определению программы T ₂ получим kod (T ₂) Ï M. Если же T ₂ на своем собственном коде не остановится, то по определению M kod (T ₂) Ï M, а по определению T ₂ kod (T ₂) Ï M. Итак, в любом случае имеем противоречие.

Дата добавления: 2015-08-31