CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth
CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth
T Naughton, NUIM
Back to CS370 home
Lab 5 - Undecidable Turing-recognisable languages
In this lab sheet you will prove that particular undecidable languages are Turing-recognisable. You will use Sipser's pseudocode for Turing machines (TMs). If you have not completed any parts of the previous lab sheet or if you got some questions wrong on the lab test, you should do them in this lab.
For each of these undecidable languages, define its complement and then prove that either it or its complement is Turing-recognisable.
1. RTM = {
M,w
: M is a TM and w is a word and M rejects w}
2. L = {M : M is a TM and L(M) is empty, i.e. M accepts no words}.
3. L = {J,n : J is a Java program and n is a line number in J, and line n is never reached in the execution of J}.
4. L = {J,a,b : J is a Java program and a,b are two integers initialised with the same value in J, and a,b get different values at least once in the execution of J}.
5. L = {M : M is a TM and |L(M)|>5, i.e. M accepts more than five words}.