Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable.
I would prefer if reduction was used and not Rice's theorem.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Imagine a fixed machine $M$ and a fixed string $w$ and then let $M'$ be the machine that on input $x$ simulates $M$ on $w$, and if that simulation halts then answers Yes if $x=ab$ and No otherwise.
How could you decide whether $M'$ belongs to your language? You would need to know whether $M$ halts on $w$! As in that case $L(M')=\{ab\}$ and otherwise $L(M')= \varnothing$.
Details up to you :)
answered Aug 3, 2020 at 19:31