A bounded computation tableau for a nondeterministic Turing-machine run

Fix a nondeterministic one-tape Turing machine $N$ and an input word $w$. Suppose $T\ge \mathrm{\mid }w\mathrm{\mid }$, every branch of $N$ on $w$ halts within $T$ steps, and no branch visits a tape cell beyond position $T$. A bounded computation tableau for $N$ on $w$ is a $(T+1)\times (T+1)$ array whose rows encode one computation branch of $N$ on $w$, padded after halting if necessary:

• row $0$ is the initial configuration on input $w$,
• each later row is obtained from the previous row by one legal transition of $N$, or else repeats the previous row unchanged when that previous row is already halting,
• and each row contains exactly one distinguished state-tagged tape symbol, marking the head position and current state.

The tableau is accepting when some row is an accepting configuration.

• The one-tape hypothesis is what makes one state-tagged symbol sufficient to record the unique head position in each row.

• The bound $T\ge \mathrm{\mid }w\mathrm{\mid }$ ensures that row $0$ has room for the entire input; the width and height are both polynomial in $\mathrm{\mid }w\mathrm{\mid }$ once $T$ is polynomial.

• The repeated-row convention is the standard way to fit an accepting or rejecting branch of length at most $T$ into a fixed $(T+1)\times (T+1)$ tableau.

• The tableau records one branch, not the whole nondeterministic tree.