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.


1 Answer 1


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 :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.