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

Ancestors (8)

  1. Characteristic-function register machine
  2. String register machine
  3. Register machine
  4. Computability theory
  5. Foundations of mathematics
  6. Area of mathematics
  7. Mathematics
  8. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version