2
The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ ...
2
Here is a more general statement:
A language $L$ has an undecidable subset iff $L$ is infinite.
For the proof, note first that if $L$ is finite then all its subsets are finite and so decidable. Conversely, if $L$ is infinite then it has uncountably many subsets. Since there are only countably many decidable languages, some subset of $L$ (indeed, most ...
1
Well, probably you have already heard about the halting problem. It is a well known and the most common example of an undecidable language. Let us call it $\mathcal{H}$.
I claim that $\mathcal{H} \cap L$ is an undecidable language that is a subset of $L$. Informally, the language of all turing machines of at least 50 states that halt after finite number of ...
1
The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).
Given an instance $M$ of ALLTM, construct a Turing machine $M'$ which on input $x$ runs $M$ on all inputs $y \...
1
Your question doesn't make sense because of a category error. "Regular" is a property of sets of strings. A set of languages is a set of sets of strings, so it doesn't make sense to ask if it's regular.
Only top voted, non community-wiki answers of a minimum length are eligible
