Question

A question about -tuples with possible answers is a partition of into disjoint sets .

A Register Machine with upper register index answers a question about -tuples with answers if:

1. it has designated ‘answer states’
2. for any input , produces a configuration in finitely many steps if and only if

Think of this as an if-else block. The register machine just progresses us to the next appropriate command based on the content of the registers (without changing the registers).