Изменения

Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> выполняются три перечисленных свойства.

Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex> построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>.