48
правок
Изменения
Нет описания правки
''continue or find path'' //''недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной''
counter++
''if'' counter ≥ r_i ''then'' //''нашли r_i вершин, удачно завершаем работу''
ACCEPT
</code>
<tex>Enum </tex> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>. Для угадывания пути достаточно <tex>O(\log |G|)</tex> памяти, так как необходимо помнить лишь текущую вершину пути и пытаться угадывать следующую. <tex>Enum </tex> является недетерминированой программой и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается.
Теперь имея <tex>Enum</tex>, можно индуктивно находить <tex>r_i</tex>. Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину <tex>s</tex>. Пусть известно значение <tex>r_i</tex>. Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.
<code>
