0

I know that the acceptance problem of a Turing machine is the problem to decide if for any turing machine $M$, given a string $w$ the Turing machine accepts $w$ or not. If the not acceptance of a string is present on the definition of the acceptance problem of a Turing machine, then what is the complement of this problem?

Bernard
  • 175,478
Matheus
  • 167

1 Answers1

0

The set of strings for which a TM halts is semi-decidable.

The complement of this set is not semi-decidable.

Because if a set and its complement are both semi-decidable, the set will be decidable.

Wuestenfux
  • 20,964