Изменения
→Основные определения: орфография
Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.
|proof=
Приведем пример такой биекции: занумеруем подряд все строки длинны длины <tex>1</tex>, затем все строки длинны длины <tex>2</tex> и так далее {{---}} нумерация названий столбцов в <tex>Excel</tex>, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.
}}
Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:
<tex>2^{\mathtt{code}} \cdot 3^{\mathtt{input}}</tex>, где <tex>\mathtt{code}, \ \mathtt{input}</tex> {{---}} есть натуральные числа, соотвествующие соответствующие тексту программы и тексту входных данных соответственно.
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
