T Naughton, NUIM
Back to CS403/SE307/CS355 home

Lab 4 - Decidability and undecidability - Group A

First, find out what team you are in here and go to the space allocated for your team. If you do not have a team, or are not scheduled for this lab, then please wait at the whiteboard and you will be seated presently.

The object of this lab is to work in teams to prove or disprove certain assertions. The team will also be asked to provide specific examples and to comment on various consequences of their proofs. One team member will then make a very short presentation of the team's results to the entire lab. It will be important for each team to ensure that nobody is left behind in the group discussions, as explained next.

At 2.45pm, each team will submit a 1-page (single sided) written presentation containing its proof(s), example(s), and comment(s). Your page will be photocopied onto a transparency and you will use this in your presentation (so write with a dark pen and make sure all illustrations are clear). A single person will be chosen randomly from the team to give the presentation. Presentations will last no more than 3 minutes each. All team members will receive the same mark. The assessment will be based on an equal weighting of (i) the quality of the written submission, and (ii) how well the randomly chosen presenter convinces the demonstrators that they understand the group's submission. Presentation skills (or lack of same) will not be taken into account in the assesment, so don't worry if you're nervous!

Your proof(s) can be very high level pseudocode algorithms or even a diagram if it is expressive enough. Also, try not to clutter the page with minor details that you could easily explain in your presentation.

You may use your lecture notes (and Sipser's book, if you have it) but no other material (including WWW material) for this lab.

Problem 1. Let the language VAREQUAL_J be defined as VAREQUAL_J = { < J, u, v > : J is a Java program, u and v are integer variables declared in J, and u and v have the same value at least once during the execution of J }. You are given that HALT_J is undecidable. HALT_J is defined as HALT_J = { < J, w > : w is a string, J is a Java function that takes a string as an argument and makes no function calls other than System.out.Print(), and J halts on w }.

(i) Prove that VAREQUAL_J is undecidable.
(ii) Prove that VAREQUAL_J is Turing-recognisable or prove that it is not Turing recognisable.
(iii) Define the complement of VAREQUAL_J.
(iv) Prove that the complement of VAREQUAL_J is Turing-recognisable or prove that it is not Turing recognisable.