T Naughton, CS NUIM, Back to SE307 home

You have 15 minutes for question 1 and 25 minutes for question 2.

Q1 Outline how you are attempting to solve the problem: "For our restricted programming language P and a variable X declared in P, does the value of X ever change during execution of P?"

Q2 Write a Turing machine table of behaviour to determine if one binary number is less than another. Initial state: head is at beginning of first number. The two numbers are separated with a blank. Final state: head is at a '1' if first is less than second, and at a '0' otherwise. (You may delete all/part of the input if you wish.)
Sample input: "--101-11--" Corresponding output: "????0?????"
Sample input: "--11-101--" Corresponding output: "????1?????"