Transitions checked 1-bit carryadd. Simulate the FA to perform the validity check. I.e., let Qi,xi be the ith quantifier and bound variable. Deal with quantifiers one at a time. Generalize Sipser 1.25.
New state is for guessing the leading bits.
Easy to check. This is one general technique for building decision algorithms for theories Not all decision algorithms necessarily built like this. FA can check operations bit-wise. FA can know results when guessing extra leading bits. But, need to be able to guess number in existential quantification.