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

Lab 4 - Decidability and undecidability - Group B

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 HASVAR_J be defined as HASVAR_J = { < J, v > : J is a Java program, v is an integer variable declared in J, and v is initialised to zero in its declaration statement }. (i) Prove that HASVAR_J is Turing-recognisable. (ii) Prove that the complement of HASVAR_J is Turing-recognisable. (iii) Is HASVAR_J decidable?

Problem 2. Let the language VARZERO_J be defined as VARZERO_J = { < J, v > : J is a Java program, v is an integer variable declared in J, and v contains the value zero at some point during the execution of J }. (i) Prove that VARZERO_J is Turing-recognisable. (ii) Prove that VARZERO_J is undecidable. You can assume that HALTS_J is undecidable. HALTS_J is defined as HALTS_J = { < J > : J is a Java program and J halts }. (iii) Is the complement of VARZERO_J Turing-recognisable?