patternMinor
Which languages, decided by a turing machine are decidable?
Viewed 0 times
languagesdecidedaredecidablemachinewhichturing
Problem
How do I decide if a language is decidable and/or semi-decidable?
I have theses languages:
a) { | L(M) ⊆ 0*}
b) { | L(M) contains at least one word of even length}
c) { | L(M) is semi-decidable}
d) { | L(M) is decidable}
My problem is, that I don’t quite now how to interpret this notation. I know that is the code of a turing-machine and L(M) is the language decided by the turing machine.
But I’m not quite sure if I understand “language decided by a turing machine” correctly.
Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?
Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?
I guess there’s a major flaw in my thoughts, but which is it?
For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.
How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0 (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.
b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.
I know there are many errors in
I have theses languages:
a) { | L(M) ⊆ 0*}
b) { | L(M) contains at least one word of even length}
c) { | L(M) is semi-decidable}
d) { | L(M) is decidable}
My problem is, that I don’t quite now how to interpret this notation. I know that is the code of a turing-machine and L(M) is the language decided by the turing machine.
But I’m not quite sure if I understand “language decided by a turing machine” correctly.
Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?
Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?
I guess there’s a major flaw in my thoughts, but which is it?
For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.
How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0 (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.
b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.
I know there are many errors in
Solution
Nice question.
Notations and terms
$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.
$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.
Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book introduction to the theory of computation by Michael Sipser. You could take a look at its definition at Wikipedia as well.
We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.
DEFINITION 3.6. Call a language Turing-decidable or simply decidable if some Turing machine decides it.
Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.
Application of Rice's theorem
Here is the Rice's theorem.
Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.
In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $\langle M_1\rangle \in P$ iff $\langle M_2\rangle \in P$. Here, $M_1$ and $M_2$ are any TMs. Then $P$ is an undecidable language.
a) $P=\{\langle M \rangle\mid L(M)\subseteq 0^*\}$.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)\subseteq 0^$ iff $L(M_2)\subseteq 0^$
By Rice's theorem, $P$ is undecidable.
b) $P=\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\}$.
-
$P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{00\}$ but $P$ does not contain the description of a Turing machine whose language is $\{0\}$.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ contains at least one word of even length iff $L(M_2)$ contains at least one word of even length.
By Rice's theorem, $P$ is undecidable.
c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\}$ contains all TM descriptions, which is a decidable language.
d) $P=\{\langle M \rangle\mid L(M)\text{ is decidable}\}$.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ is decidable iff $L(M_2)$ is decidable.
By Rice's theorem, $P$ is undecidable.
For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\{0\}$, then, of course, for every $M$, $L(M)\subseteq 0^$. Then $\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^\}$ contains all TM descriptions. It is decidable.
Notations and terms
$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.
$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.
Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book introduction to the theory of computation by Michael Sipser. You could take a look at its definition at Wikipedia as well.
We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.
DEFINITION 3.6. Call a language Turing-decidable or simply decidable if some Turing machine decides it.
Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.
Application of Rice's theorem
Here is the Rice's theorem.
Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.
In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $\langle M_1\rangle \in P$ iff $\langle M_2\rangle \in P$. Here, $M_1$ and $M_2$ are any TMs. Then $P$ is an undecidable language.
a) $P=\{\langle M \rangle\mid L(M)\subseteq 0^*\}$.
- WLOG, let 1 be an input alphabet symbol other than 0. $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{0\}$ but $P$ does not contain the description of a Turing machine whose language is $\{1\}$.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)\subseteq 0^$ iff $L(M_2)\subseteq 0^$
By Rice's theorem, $P$ is undecidable.
b) $P=\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\}$.
-
$P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{00\}$ but $P$ does not contain the description of a Turing machine whose language is $\{0\}$.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ contains at least one word of even length iff $L(M_2)$ contains at least one word of even length.
By Rice's theorem, $P$ is undecidable.
c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\}$ contains all TM descriptions, which is a decidable language.
d) $P=\{\langle M \rangle\mid L(M)\text{ is decidable}\}$.
- Let $R=L(D)$ be a decidable language. For example, we can take $R=\{0\}$ and $D$ is a Turing machine that accepts 0 and rejects all other inputs. $\langle D\rangle\in P$. Let $H=L(N)$ be a semi-decidable but not decidable language. For example, we can take $H$ to be the language of the halting problem. Then $\langle N\rangle\not\in P$. Hence $P$ is nontrivial.
-
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ is decidable iff $L(M_2)$ is decidable.
By Rice's theorem, $P$ is undecidable.
For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\{0\}$, then, of course, for every $M$, $L(M)\subseteq 0^$. Then $\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^\}$ contains all TM descriptions. It is decidable.
Context
StackExchange Computer Science Q#111895, answer score: 2
Revisions (0)
No revisions yet.