New answers tagged semi-decidability
1
vote
Accepted
How to proof the existence of languages over {0,1}* that are neither semi-decidable nor co-semi-decidable
An usual example is the language:
$$\mathsf{ALL} = \{\langle M\rangle \mid \forall x\in \{0,1\}^*, M \text{ accepts }x\}$$
Though it can be proved formally that it is neither semi-decidable, nor co-...
- 16.9k
Top 50 recent answers are included