Изменения
→Теорема Успенского-Райса
Рассмотрим вспомогательную программу:
<tex>g_{i,x}(y):</tex>
'''if ''' U(i, x) == 1
'''return''' <tex>p_X(y)</tex>
'''else''' while True'''true'''
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:
