Изменения

#Так как программа <tex>f</tex> возвращает только те <tex>y</tex>, для которых <tex>R(x, y) = 1</tex>, то <tex>R(x, f(x)) = 0</tex> получиться не может. Покажем, что и зависнуть на словах из языка <tex>f</tex> не может. Как выше уже упоминалось, если слово принадлежит языку <tex>L</tex>, то для него есть сертификат, а значит есть и программа <tex>g</tex>, которая , например, просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и <tex>g</tex> будет занумерована, а следовательно и запущена. После остановки <tex>g</tex> и проверки правильности <tex>y</tex> программа <tex>f</tex> вернет его.#Как выше уже оговаривалось, если Если программа <tex>g(x)</tex> правильно находит сертификаты для слов из языка и завершается за <tex>k</tex> шагов для некоторого слова <tex>x</tex> из <tex>L</tex>, то программа <tex>f</tex> завершится не более, чем за <tex>2^i \cdot (k + poly(|x + y|))</tex> шагов для этого же слова. Заметим, что <tex>2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))</tex>, так как <tex>y</tex> — сертификат для <tex>x</tex> и потому <tex>|y| \le poly(|x|)</tex>.