New answers tagged semi-decidability
0
So in this case would something "not in L" be nothing?
No. A string $\langle G\rangle$ is not in $L$ means $L(G)\ne \Sigma^*$. Such strings exist of course. For example, if $G$ is a mechine that rejects anything, then $L(G)=\emptyset$, thus $\langle G\rangle\notin L$.
0
An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.
0
A good rule of thumb is to use Church's thesis: can you personally solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is Rice's theorem.)
By way of example, let's first consider the following two sets:
...
Top 50 recent answers are included
