Questions: Formal Models of Computation: Turing Machines and Lambda Calculus

Question 1

A function f is known to be computable by a Turing machine in 100 steps. Which of the following is guaranteed about computing f using an equivalent lambda calculus term?

• A. It will also require exactly 100 beta-reductions, since both models are equivalent
• B. It will require at most 100 beta-reductions, since equivalent models are equally efficient
• C. It will correctly compute f, but the number of beta-reductions may be exponentially larger or smaller — equivalence is about computability, not complexity
• D. The lambda calculus cannot simulate this Turing machine because it lacks a tape mechanism

Answer: (C)

The Church-Turing equivalence guarantees that both models compute the same class of functions — whatever a Turing machine computes, a lambda calculus term computes. But equivalence in computational power says nothing about efficiency. A 100-step Turing machine computation might require thousands of beta-reductions to simulate, or vice versa. Complexity (how long it takes) is a separate question from computability (whether it terminates with the right answer).

Question 2

Which statement correctly characterizes the relationship between Turing machines and the lambda calculus?

• A. They are equivalent in the functions they can compute, but this equivalence is a proven mathematical theorem with no remaining uncertainty
• B. The lambda calculus can compute a strict superset of Turing-computable functions, since it handles higher-order functions that Turing machines cannot
• C. They compute exactly the same class of functions; the Church-Turing thesis asserts this coincidence reflects the true boundary of mechanical computation, though this claim is a conjecture rather than a theorem
• D. Turing machines are strictly more powerful because they have an infinite tape, while lambda calculus terms are finite expressions

Answer: (C)

Every lambda calculus term can be simulated by a Turing machine (mechanically apply reduction rules), and every Turing machine can be encoded in the lambda calculus (represent tape and state as data). This proves both directions of the equivalence. However, the broader claim — that these models capture *all* mechanical computation — is the Church-Turing *thesis*, a philosophical conjecture about what 'computable' means, not a formal theorem. No one has proved it or refuted it, because 'mechanical computation' has no prior formal definition to prove it against.

Question 3

The Church-Turing thesis is a proven mathematical theorem establishing that Turing machines compute most and primarily the computable functions.

• T. True
• F. False

Answer: False

The Church-Turing thesis is a conjecture, not a theorem. It asserts that any function computable by a 'reasonable mechanical process' is computable by a Turing machine — but 'reasonable mechanical process' has no prior formal definition, so there is nothing to prove the thesis against in a strict logical sense. The equivalence between specific formal models (Turing machines, lambda calculus, recursive functions) is proven. The broader claim that these models capture all of computation is an empirical observation and philosophical commitment, not a mathematical derivation.

Question 4

If two computational models are Turing-equivalent, they will solve any given problem with the same number of computational steps.

• T. True
• F. False

Answer: False

Turing equivalence means the models compute the same class of functions — both halt on the same inputs and produce the same outputs. It says nothing about efficiency. A Turing machine might solve a problem in polynomial time while an equivalent lambda calculus simulation requires exponential beta-reductions, or vice versa. This is why complexity theory studies specific machine models carefully: different Turing machine variants (deterministic, nondeterministic, multi-tape) can define different complexity classes even though they all compute the same functions.

Question 5

What does it mean for two computational models to be 'equivalent,' and what does equivalence explicitly NOT imply?

Model answer: Two models are computationally equivalent if they compute exactly the same class of functions: for every function one can compute (halting with the correct output on all valid inputs), the other can compute it too. Equivalence does NOT imply equal efficiency — the same function may require very different numbers of steps in each model. It also does not imply that programs in one model are easily translated into the other in a practical sense, only that a translation exists in principle.

The distinction between 'what can be computed' and 'how efficiently it can be computed' is foundational in theoretical CS. Computability theory (can it be done at all?) and complexity theory (how much resource does it take?) are separate disciplines. The Church-Turing equivalence results belong to computability; they say nothing about polynomial vs. exponential time, which is the domain of complexity classes like P, NP, and PSPACE.