Изменения
Нет описания правки
{{Лемма
|statement=
Существует [[Отображения#Свойства отображений | биекция ]] между строками и натуральными числами.
|proof=
Приведем пример такой биекции:
Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:
<tex>2^{\mathrmmathtt{code}} \cdot 3^{\mathrmmathtt{input}}</tex>, где <tex>code, \ input</tex> {{---}} есть натуральные числа, соотвествующие тексту программы и тексту входных данных соответственно.
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
<tex>p_2(i) {:} </tex>
'''if''' <tex>i \leqslant k 2 </tex>
'''return''' 1
'''else'''
