Problem: Prove that the language $L = \\{\langle P \rangle \mid P \text{ is an instance of PCP with a match in which the } i\text{th domino is used at most } i \text{ times}\\}$ is decidable.
Attempted Solution: The critical distinction in this instance of PCP is that each domino may only be used a finite number of times, whereas in the original formulation, each domino can be used any number of times to find a match. Notice: The 1st domino may be used 0 or 1 times (2 options) The 2nd domino may be used 0, 1, or 2 times (3 options) $\cdots$ The $i$th domino may be used 0 to $i$ times, inclusive ($i + 1$ options) $\cdots$ The $n$th domino may be used 0 to $n$ times, inclusive ($n + 1$ options). Therefore there is a finite number of configurations to check for instances of this problem and that number is $$2 \cdot 3 \cdot 4 \cdots (n + 1) = (n + 1)!.$$ Consider a TM $M$ where
$M$ = "On input $\langle P \rangle$ where $P$ is as described above
- non-deterministically guesses a sequence of dominos, respecting the constraint that the $i$th domino is used at most $i$ times. It does this by, at each step, non-deterministically choosing one of the available dominoes (considering how many times each domino can still be used).
- Check if the configuration is a match. If a match is found, accept.
- If a point is reached where no further dominoes can be selected to continue the sequence (either because all options have been exhausted for the current length or because adding any of the remaining dominoes would violate the constraint), it rejects the input for that specific computation branch.
- If one of the non-deterministic branches accepts the input, accept. If none do, reject."
Question: I just sort of feel like I am abusing non-determinism here... am I? Is this too much hand-waving? One particular thing I am worried about is step 4; what if one of the branches loops forever? How does $M$ "know" when all computational branches have been rejected or one has been accepted?