New answers tagged

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