editor
177
правок
Изменения
м
Выделено определение
{{Определение
|definition =
<tex>D</tex> — класс языков, удовлетворяющих некоторым ограничениям; распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> — класс вычислимых функций, удовлетворяющих тем вычисляемых программами с теми же ограничениямограничениями.}}{{Определение|definition =
'''Язык <tex>L_1</tex> сводится к языку <tex>L_2</tex> относительно <tex>\widetilde{D}</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
<tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.
