Fix a space-\(S\) algorithm \(A\) and a fixed input. Build the finite state machine \(Q\) whose states are the configurations of \(A\) between blocks of \(n\) random bits. Its edge labels record exactly which \(n\)-bit random block moves one configuration to another. The number of configurations is at most \(2^S\). Acceptance of \(Q\) on a block sequence is the same event as acceptance of \(A\) on the concatenated random string. Applying Definition 2 to this \(Q\) gives Definition 24.

Choose the block length \(\Theta (S)\) so that Lemma 23 applies with error \(2^{-\Theta (S)}\). Choose \(k=\lceil \log R\rceil \) so the recursive generator outputs at least \(R\) bits after concatenating its \(2^k\) blocks, and discard any excess bits. Each hash function is represented with \(O(S)\) bits by the convolution family of Lemma 5; the seed consists of one \(O(S)\)-bit initial string plus \(k\) such hash descriptions, for total length \(O(S\log R)\). Proposition 25 converts the block guarantee into the ordinary space-bounded guarantee. The recursive evaluation performs one explicit hash computation for each generated block and stores the current recursion data and hash descriptions, which fits in \(O(S\log R)\) space.

Replace the original random tape by the output of the generator from Theorem 26. The simulator samples only the generator seed, computes requested pseudorandom bits as needed, and runs the original algorithm. The distinguishing guarantee preserves the acceptance probability up to the theorem’s parameter. Storing the seed and generator workspace costs \(O(S\log R)\) space.

Enumerate every seed of the generator in Theorem 26 and run the randomized machine using the corresponding generated random string. The enumeration uses only the seed counter and the generator workspace. Since the generator fools every space-\(S\) algorithm, averaging over the seed enumeration approximates the original randomized acceptance probability. The procedure is black-box because it depends only on the machine’s space bound, not on its internal transition structure.

If the concatenation were not universal, then there would be a graph, port-numbering, and start vertex for which no generator output visits all vertices. A logarithmic-space tester can store the current vertex, the target vertex, and a step counter, and accept exactly those random walk strings that visit the target. Under truly random choices, a sufficiently long random walk has positive probability of reaching every fixed target in a connected regular graph. Under the generator, that probability would be zero for one target, contradicting the generator’s small distinguishing error. Hence every target is reached by at least one generated walk, and the concatenation of all generated walks traverses the graph from every start.

A walk step in a \(d\)-regular graph is encoded by \(O(\log d)\le O(\log n)\) random bits, and the logspace traversal tester of Lemma 30 uses \(O(\log n)\) space. Apply Theorem 26 with \(S=O(\log n)\) and with polynomially many random bits for the walk length required by the standard random-walk traversal argument. The seed length is \(O(\log ^2 n)\), so enumerating all seeds multiplies the walk length by \(2^{O(\log ^2 n)}=n^{O(\log n)}\). The deterministic generator enumerator keeps a seed counter, a recursion stack, and the current output position, all of size logarithmic in the final sequence length.