University of Sussex Informatics
Spring 2021
Limits of Computation
Feedback to Exercises 1 (covers Lectures 1–3) Dr Bernhard Reus
Effective Procedures, Problems, WHILE Syntax
1. What are the four defining characteristics of effective procedures? Answer: An effective procedure is one that
• is defined in terms of a finite number of exact instructions (each instruction can be in turn represented by a finite num- ber of symbols).
• must always produce the desired result in a finite number of steps.
• can be carried out by a human with just paper and pencil (so it must be clear for us what the instructions mean!)
• does not require any insight or ingenuity on the part of the human who carries it out, which means it is simple enough for a machine to do it too (and it does not need any “oracle”).
A function or procedure is “effectively calculable” meant for Tur- ing that “its values can be found by some purely mechanical pro- cess”. This he said, should be understood literally, leading to the first formalisation of computation in terms of what we now call “Turing machines”.
2. For each problems below state whether it is a function problem (and if so, if it is an optimisation problem), a decision problem, or whether it does not qualify as problem in our sense. If it is not a problem in our sense explain why it is not.
(a) Is 221 a prime number?
Answer: Not a Problem, there is no uniform question!
1
(b) Given a finite array of integers what is the sum of all its values?
Answer: Function Problem
(c) Can an integer number n be divided by 7?
Answer: Decision Problem. Some might argue it is not clear enough what “can an integer be divided by 7” means, as it is not clearly stated which kind of division. In this case one could argue it is not a problem as we can’t give a clear answer.
(d) Does a given Java program run on a Java SE10 virtual ma- chine with input string “Turing” return the string “Icon”? Answer: Decision Problem.
(e) What is the maximum value of a given function f on the real numbers in a given interval [a, b]?
Answer: Optimisation (so Function) Problem. Note that here a function “on real numbers” means a function from real numbers to the real numbers. One could argue that if it is not known what the codomain (result type) of f was, it would not be clear if we can say what a maximum value on this codomain is.
(f) What is the meaning of life?
Answer: Not a problem (neither uniform, nor do we know a definite answer).
3. For the pairs of sets A and B in (a)-(e) below, explain whether A ⊆ B (A is a subset of B), whether B ⊆ A (B is a subset of A), whether A = B, and whether A ̸= B.
(a) A = {1,3,5} and B = {1,3,5,6} Answer: A ⊂ B so A ̸= B.
(b) A = {1,3,3,3} and B = {1,3}
Answer: A = B. This was difficult for some of you. Note that in sets we don’t distinguish multiple occurrences of an element. So either an element (e.g. 3) is in the set or it is not.
(c) A={x∈N|x=x+1}andB=∅
Answer: A = B . This was difficult for some of you. Note
2
that there is no natural number x such that x = x + 1. So this is the empty set. Note that ∅ means empty set, i.e. {}.
(d) A={x∈N|even(x) ∧ x<11}andB={0,2,4,6,8,10} Answer: A = B. Note that in computer science 0 is usually considered to be a natural number unless stated otherwise.
4. Which of the following are legal expressions or commands in core WHILE as presented in Lecture 3?
Answers:
(a) tl nil is a legal expression (core WHILE)
(b) tl rl is a legal expression (core WHILE) as rl must be a
variable.
(c) cons hd hd x x tl x is an illegal expression as there are
too many arguments, either for hd or cons.
(d) while a { cons hd a } is an illegal command, as there is no proper statement in the loop body. Moreover, also the expression in use is ill-formed as cons needs two arguments.
(e) if tl tl X { } else { X:= Y }isalegalcommandincore WHILE.
5. Given are the following elements of D:
s = ⟨⟨nil.nil⟩.nil⟩ t = ⟨nil.⟨nil.nil⟩⟩
(a) Draw s and t as (two-dimensional) trees: Answer: This is s:
/\ /\
/\ nil /\
nil nil
This is t:
/\ /\
nil /\ /\
nil nil
3
(b) Iss=t?
Answer: No these are different trees clearly.
(c) State whether s and t, respectively, can be read as numbers, and if so, which number?
Answer: s is not a number, but t represents 2.
(d) State whether s and t, respectively, can be read as lists, and if so, which lists?
Answer: Yes, s represents [1] or [[0]] or [[nil]] or [[[]]], while t encodes [0,0] or [[],[]] or [nil,nil]. Multiple answers are possible as a tree can encode several
values of different “type”. Types are just in the eye of the beholder.
4