Кодирование

Теория алгоритмов имеет дело со словами в конечном алфавите. Однако многие объекты нельзя рассматривать как слова в некотором алфавите. К таким объектам, например, можно отнести рациональные числа, алгебраические числа и т.д. Тем не менее, некоторые из таких объектов могут быть закодированы в подходящем конечном алфавите. Например, взяв алфавит из двух символов 0, 1, можно закодировать любое натуральное число, взяв его двоичную запись. При двоичном кодировании не всякое слово в алфавите 0, 1 служит кодом натурального числа (например, 001).