Т. А. Сливина математическая логика и теория алгоритмов

Теорема. Проблема распознавания самоприменимости алгоритмически не разрешима.
Доказательство. Предположим противное. Пусть такая машина А существует. Тогда в А всякий самоприменимый шифр перерабатывается в какой-то символ  (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр – в другой символ  (имеющий смысл отрицательного ответа на поставленный вопрос). В таком случае можно было построить и такую машину В, которая по-прежнему перерабатывает несамоприменимые шифры в , в то время как к самоприменимым шифрам В уже не применима. Этого можно было добиться путем такого изменения схемы машины В, чтобы после появления символа  вместо появления стоп-состояния, машина начала бы неограниченно повторять этот же символ.
Таким образом, В применима ко всякому несамоприменимому шифру (вырабатывается при этом символ ) и не применима к самоприменимым шифрам. Но это приводит к противоречию. Действительно:

1. 
   пусть машина В самоприменима, тогда она применима к своему шифру В и перерабатывает его в символ ; но появление этого символа как раз и должно означать, что В несамоприменима;
   
2. 
   пусть В несамоприменима, тогда она не применима к В, что должно означать как раз, что В самоприменима. Полученное противоречие доказывает теорему.
   

3. Проблема эквивалентности слов для ассоциативных исчислений.
Первые результаты об алгоритмической неразрешимости были установлены для проблем, возникающих в самой математической логике и в теории алгоритмов. Сюда относятся и рассмотренные проблемы «Проблема выводимости» и «Проблема самоприменимости». Но позже выяснилось, что аналогичные проблемы возникают в самых различных специальных разделах математики. Сюда относятся, в первую очередь, алгебраические проблемы, приводящие к различным вариантам проблемы слов.
Рассмотрим некоторый алфавит А = {а,b,с,... и множество слов в этом алфавите. Если слово L является частью слова М, то говорят, что слово L входит в слово М. Так, слово аса входит в слово bcacab, начиная с буквы а.
Будем рассматривать преобразование одних слов в другие с помощью некоторых допустимых подстановок вида
P — Q или P Q,
где Р и Q два слова в том же алфавите А.
Применение ориентированной подстановки Р  Q к слову R возможно в том случае, когда в нем имеется хотя бы одно вхождение левой части Р; оно заключается в замене любого одного такого вхождения соответствующей правой частью Q.
Применение неориентированной подстановки Р — Q допускает как замену вхождения левой части правой, так и замену вхождения правой части левой.
Будем рассматривать, в основном, неориентированные подстановки.
Пример. Подстановка ас – аса применима к слову ЬсасаЬ двумя способами; замена вхождения аса в это слово дает слово bсасаb, а замена вхождения ас дает слово bсасааb.
К слову abcab эта подстановка не применима.