1632
правки
Изменения
м
rollbackEdits.php mass rollback
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>1 \Rightarrow4</tex> 4.
Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
*2 <tex>2 \Rightarrow1</tex> 1.
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
'''print''' <tex>k</tex>
*3 <tex>3 \Rightarrow1</tex> 1.
Пусть <tex>X</tex> — область значений вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
*4 <tex>4 \Rightarrow2</tex> 2, 4 <tex>4 \Rightarrow3</tex> 3.
Пусть дана <tex>f_X(x)</tex>.
Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения.
}}
== См. также ==
* [[Рекурсивные функции]]
* [[Вычислимые числа]]
* [[Универсальная функция]]
== Источники информации ==
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]
