Complementing a characteristic-function register machine
= Complementing a characteristic-function register machine
Replace the original halt state by a continuation state that tests whether its one-letter output is $0$ or $1$, removes it, appends the other symbol, and enters a new halt state. This computes the complement language without changing termination behavior.