Complexity Explorer Santa Few Institute

Q1. What is a general property of recursive functions that make them important for computability theory?

(A) They break down complex problems into discrete and simple steps.

(B) They save computational time by reducing the number of functions that need to be defined.

(C) They show that a problem is computable for all values of x as long as the base case (n=0) and n+1 are computable.

(D) They allow for conductive definitions of data structures of infinite size.

(E) They can be extended to prove statements about more general well-founded structures, such as trees.

(F) All of the above.

Explanation: The Church-Turning thesis, as well as the Grant Unified Theory of Computation, states that functions involving integers are lambda-computable if and only if they are Turing computable. By definition, this is only possible if this function is recursive, which in turn means the base case (n=0) and n + 1 must be computable.

The other answers, while true about recursive functions, are not important for computability theory in the same way that the Church-Turning thesis is one of the foundational theorems of theoretical computer science.

---

Q2. Below is a factored-out version of a recursive function fun():

base case: fun(0) = 1

fun(x + 1) = [x+1] * [[x-1]+1] * [[x-2]+1] * ... * [0+1]

Q2 (A): What mathematical operation is being performed by fun()?

(A) Cube of x

(B) Fibonacci sequence

(C) Counting

(D) Factorial

Explanation: Each other operation is defined differently: cube of x is defined as x*x*x; fibonacci is fun(x-1) + fun(x-2); and counting is simply x+1. The factorial operation is defined as the product of all numbers from x+1 through 1, which is represented here.

Q2 (B): What is the function fun()?

(A) fun(x + 1) = (x + 1) * fun(x)

(B) fun(x + 1) = fun(x)

(C) fun(x + 1) = (x + 1) * fun(x - 1)

(D) fun(x + 1) = x * fun(x + 1)

Explanation: When adding one to a factorial function, x+1 is multiplied by the function performed on x. For example, if x = 3, the factorial of x+1, or 4, would be 4 * factorial(3), or 4 * (3 * 2 * 1) = 24.

The other options would not result in this answer. Using the x=3 example above, option b would result in factorial(4) = (3 * 2 * 1) = 6; option c would result in 4 * (2 * 1) = 8; and option d would result in 3 * fun(5), which would recurse to infinity.

Q2 (C): How many times was fun() called to compute fun(2 + 1)?

(A) 1

(B) 2

(C) 3

(D) 4

Explanation: fun() is called once for every increment of x. The factorial of 3 is calculated through fun(3) = 3 * fun(2), which is the first call of fun(). Since this function is recursive, fun(2) is then called: fun(2) = 2 * fun(1), which is the second call of fun(). fun() is called once more: fun(1) = 0, which is the base case and completes the recursion.

---

Q3. What are the parts of a Turing machine?

(A) Read/write tape head, transition system, infinite memory tape.

(B) Read/write tape head, finite-state controller, infinite memory tape.

(C) Read/write tape head, scratch tape, infinite memory tape.

(D) Read/write tape head, scratch tape, transition system, infinite memory tape.

Explanation: As mentioned in Lecture 5.4, a Turning machine is built from a tape which can contain an infinite number of symbols (within a finite alphabet). A read/write head interacts with this tape, writing symbols which represent states of the machine. The finite-state controller controls the states of the machine, including putting the machine into the halt state.

The transition system would be a part of the read/write head, and there is no need for a scratch tape to keep track of previous states in Turing’s definition.

---

Q4. Evaluate or reduce the following lambda expressions as far as possible. The notation uses “L” to denote “lambda”.

Q4 (A): (Lx.x)(Lx.x)b

(A) x x b

(B) x

(C) x b

(D) b

Explanation: This lambda function is a copy function - the first (Lx.x) takes the second (Lx.x) as an input, which in turn takes b as an input. Since there are no changes to “x” in either expression, b gets passed to the second function, is not changed, then is passed to the first and likewise is not changed.

Q4 (B): (Lx.x+1)10

(A) 10x

(B) 11

(C) 11x

(D) 10

Explanation: This lambda is an addition function: it takes an input (10) and adds one to it through the “x+1” definition. Since 10+1 = 11, this expression would output 11.

Q4 (C): (Lx.x+1)((Ly.y+2)3)

(A) 5x

(B) y

(C) 6

(D) 6(x+y)

Explanation: There are two lambda expressions here. The first to be evaluated is (Ly.y+2)3, which adds 2 to the input of 3, therefore outputting 5. That 5 is passed to the next expression, which adds 1 to result in a final output of (5+1) = 6.

---

Q5. Why is the halting problem interesting from a computational perspective?

(A) Allowed for the proof that some problems are undecidable or unsolvable.

(B) A solution would solve many problems in computation, ie. it is NP-hard.

(C) Infinite loops cannot be avoided until a solution is found.

(D) Demonstrated computational universality for a Turing machine.

(E) All of the above.

Explanation: The halting problem does many things, but it will not solve the NP-hard problem, as it can only tell whether a problem will finish in finite time or not, not how complex it is. It also does not state that infinite loops are unavoidable - it ultimately tries to figure out if infinite loops exist or not. It also does not demonstrate computational universality, as this is the domain of the Turing machine definition.

What it can do is give a definition of whether some problems are unsolvable. If a program halts, it is computable; otherwise, it is unsolvable. It itself is undecidable (see the discussion at 8:00 in lecture 5.5), and therefore provides a definition for unsolvability.

---

Q6. The cellular automaton Rule 110 has been shown to be Turing-complete. What does this mean?

(A) It can simulate a Turing machine.

(B) It can recognize or decide other data-manipulation rule sets.

(C) It can simulate any calculation or computer program, given infinite time and memory.

(D) It has properties that are undecidable.

(E) All of the above

Explanation: A Turing-complete set of rules can, given infinite time and memory, solve any problems which a Turing machine can solve. This means it can not only simulate a Turing machine, but also can recognize when other rule sets are Turing-complete or not. It is also subject to the same limitations as a Turing machine in that there are properties, such as the Halting Problem, which it cannot solve. Some rules of cellular automata, nearly all programming languages in use today, chemical reaction networks, Minesweeper, and many other sets of rules are Turning-complete.

---

Q7. What properties of the Analytical Engine would have made it Turing-complete?

(A) Input/output devices, integrated memory, loops and conditional branching.

(B) Arithmetic logic processor, integrated memory, internal procedures (system functions).

(C) Arithmetic logic processor, input/output devices, integrated memory.

(D) Arithmetic logic processor, integrated memory, loops and conditional branching.

Explanation: The lecture 5.7 explains the history of the analytical engine, which was a theoretical machine thought up by Charles Babbage and further studied by Ada Lovelace. If built, this would have been a universal Turing machine, because it would have the three components listed in (d). Recall that a Turing machine needs to have a read/write tape head, a finite-state controller, and an infinite memory tape. Combined, the arithmetic logic processor and conditional branching make up the finite-state controller, while the integrated memory contains both the necessary read/write head and the memory tape (which can be overwritten, thereby is loosely “infinite”).

The I/O devices, while useful for modern use of computing devices, are not necessary for a Turing machine, nor are internal procedures. Both are superfluous to the core definition.

---

Q8. Which of the following recursive functions fun() specifies a Fibonacci sequence for x?

(A) fun(x) = fun(x-1) + fun(x-2)

(B) fun(x) = fun(x-1) + (x-2)

(C) fun(x+1) = fun(x) + fun(x-1)

(D) fun(x+1) = fun(x-1) + x

Explanation: This is covered in many locations throughout the course. The recursive Fibonacci sequence is defined through recursive calls, with the two inputs being x-1 and x-2, respectively. Answers (c) and (d) are defined in terms of x+1, which is not correct, as it adds x to the final answer, and answer (b) only includes one recursive call instead of the two required.

---

Q9. What is a general property of dynamical systems?

(A) Randomness

(B) Convergence

(C) Chaos

(D) Equilibrium

(E) All of the above

Explanation: While all the terms are used to describe complex dynamical systems, the general property that links all complex systems together is chaos. There may or may not be randomness, convergence, or equilibrium involved, but all systems involve chaos in some way.

---

Q10. The following TRUE / FALSE statements refer to cellular automata (CAs).

Q10(A): CA cells can exist in an infinite set of states

(A) True

(B) False

Explanation: A CA cell can have one of two states - on/off (interchangable with white/black). There is no gradient between the two states, as the cell by definition must switch between those two states depending on the rule set.

Q10(B): CAs can solve algorithmic problems

(A) True

(B) False

Explanation: Given the right rule set, CAs can be Turing-complete. The full reasoning for this is detailed (a good explanation can be found here), but given their Turing-completeness, CAs can be used to solve any computational problem.

Q10(C): CAs can display emergent behavior

(A) True

(B) False

Explanation: An emergent behavior is a behavior or pattern which occurs at the system level which cannot be predicted from the behavior of individual parts. For example, fractals formed in glass are system-level properties of interactions between molecules as they cool after a heating process. In CAs, system-level interactions can arise from cellular-level rules, resulting in many interesting behaviors. The oscillators below are one such example, and the “glider guns” discussed at 2:40 in lecture 5.8 are another.

Q10(D): A CA at time step t can be efficiently (ie. in a small computational time) predicted algorithmically.

(A) True

(B) False

Explanation: This is related to the halting problem - since CAs are a universal Turing machine, there exists no algorithm which can predict when a CA algorithm will halt, which makes future states therefore undecidable.

Q10(E): CAs form patterns through long-range interactions.

(A) True

(B) False

Explanation: Since CAs are based on rules between individual cells, there are no long-range interactions. The patterns are an emergent property of those cell-based rules.

Q10(F): What is the rule for the following CA? The cell in question is that in the bottom row. In the top row, "neighbors" refer to cells 1 and 3 on the edges, whereas "center" is cell 2 in the middle.

(A) White if two neighbors are white or if the center is white.

(B) Black if and only if one cell is black.

(C) White if two cells are black or if no cells are black.

(D) Black if and only if one neighbor is black.

Explanation: The potential answers can be eliminated iteratively. The first choice (i) is an "or" statement, which is negated by the second cell which includes a black center, but the cell is black. The second choice (ii) is eliminated by the sixth cell, which has one black cell, but the cell is white. The third choice (iii) is again eliminated by the second cell, which includes two black cells, but a black cell. By process of elimination, and by observation, the only choice which is satisfied across all eight states is the fourth choice (iv).

---