In Hopcroft, Motwani, and Ullman, "Introduction to Automata Theory, Languages, and Computation", 2nd edition there is the following problem.

Prove that the halting problem is undecidable.

I assume you make a reduction of the halting language to the universal language $L_u$, but I do not see it clearly.

At this point we have proven that $L_u$ is recursively enumerable and not recursive and $L_d$ is not recursively enumerable (the languages are defined below).

Halting Language $L_H$ = { (M, w) | M halts when given w as input }

The universal language $L_u$ = { (M, w) | M is a Turing Machine and w is a string in (0+1)*, such that w belongs to L(M) }

The diagonalization language $L_d$ = { $w_i$ | $w_i$ does not belong to $L(M_i)$ } where $M_i$ is the ith turing machine, and $w_i$ is the ith binary string.

Thanks for any hints!

  • $\begingroup$ You do indeed want to make a reduction, but it goes the other way. If you reduce $L_H$ to $L_u$, all you've shown is that $L_H$ is no more complicated than $L_u$; you want to show that $L_H$ is at least as complicated as $L_u$. So you want a recipe for taking a pair $(M, w)$ and spitting out a pair $(\hat{M}, \hat{w})$ such that $w$ is in $L(M)$ iff $\hat{M}(\hat{w})$ halts. Do you see how to get such a thing? $\endgroup$ – Noah Schweber Mar 8 '17 at 22:16
  • $\begingroup$ Also, $L_d$ as you've defined it is recursively enumerable . . . $\endgroup$ – Noah Schweber Mar 8 '17 at 22:17
  • $\begingroup$ Oops! Right, $L_d$ should be the set of strings of $w_i$ such that $w_i$ is not in L($M_i$) $\endgroup$ – Patrick Clot Mar 9 '17 at 0:50
  • $\begingroup$ Noah: I do not see how to convert (M, w) into (M', w'), how so? $\endgroup$ – Patrick Clot Mar 9 '17 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.