$3.$ Cook$-$Levin windows.

Recall from lecture that one critical ingredient in the proof of the Cook$-$Levin theorem is to

specify which contents of the $2$xx$3$ "windows" of the verifier's computation tableau are valid.

Specify all the valid $2$xx$3$ window contents that could appear in two adjacent rows of the

tableau, if those rows represent the verifier TM taking the following transition:

Since these windows are from two adjacent rows that represent taking the above transition, it

cannot be the case, for example, that q$\_($a$)$ appears in the bottom row of any of these windows.

For simplicity, you can assume that the symbols in the cells of the window are restricted to

$\{0,1,\_|\_,$q$\_($a$),$q$\_($b$)\}.$ Recall that there can be other symbols in the rows, such as the "boundary"

symbol # and "separator" symbol $$,$ but we will ignore those here.

To avoid having to write out many similar windows, you may use one or more variables s$\_($i$)$ to

indicate that a cell could have any of $0,1,$ or $\_|\_.$ Such a variable, when repeated in multiple

cells, represents the same symbol in every such cell. For example, instead of writing all three of

the following windows $($which may or may not be valid!$)$:

you could simply write

If needed, you may use multiple variables $($s$\_(1),$s$\_(2),$dots$)$ in a single window.

Be sure to include all valid window contents that represent the head of the TM being in both

rows of the window, all those that represent the head being in only one of the rows of the

window, and all those that represent the head not being in the window at all. Do not include

any invalid windows.

You do not need to provide any justification.