Computation Theory asign. 1
Do not consult your notes for the following questions
1) Give a definition of undecidability
2) What is a register machine?
3) What is a universal register machine?
4) Why does a numerical encoding of a program work?
5) What does it mean for a partial function from N to N to be computable by a register machine? (from 2007, paper 3, question 7)
6) Describe why the halting problem is undecidable, informally.
You may consult your notes for the remaining questions
2006 Paper 3 Question 7, part a (8 marks)
2003 Paper 3 Question 7, omit the first question (the one worth 6 marks)