Python and Brainfuck (a minimal esoteric programming language with only 8 instructions) are both Turing-complete. What is the correct implication of this fact?
APython can compute everything faster than Brainfuck because it has more built-in operations
BAny function computable by a Python program is also computable by a Brainfuck program, and vice versa — they are equivalent in what they can compute in principle
CBrainfuck must be extended with Python libraries before it can achieve full Turing-complete power
DPython is a computational superset of Brainfuck because it has more expressive syntax
Turing completeness is about what is computable in principle, not efficiency or convenience. Two Turing-complete systems can simulate each other — therefore they can compute exactly the same set of functions. Any algorithm expressible in Python is expressible in Brainfuck (though it may be agonizingly verbose). The reverse is also true. They differ enormously in ergonomics, speed, and expressiveness, but not in the class of problems they can solve. This is the equivalence that the Church-Turing thesis points to.
Question 2 Multiple Choice
A company wants to build a static analysis tool that automatically detects ALL security vulnerabilities in arbitrary Python programs. What does Turing completeness imply?
AThe tool is achievable with sufficiently advanced heuristics and machine learning techniques
BIt is mathematically impossible to build such a tool in general — Python's Turing completeness means the halting problem and Rice's theorem apply, making general-purpose correctness analysis undecidable
CThe tool is feasible for programs up to a certain size; undecidability only applies to infinite programs
DPython's dynamic typing is the limiting factor; a statically-typed Turing-complete language would permit such a tool
Rice's theorem states that any non-trivial semantic property of programs in a Turing-complete language is undecidable. 'Contains a security vulnerability' is precisely such a property — it asks about the behavior of the program, not just its syntax. No algorithm can correctly answer this question for all programs in a Turing-complete language. This is not an engineering limitation; it is a mathematical impossibility inherited from the halting problem. Option A (better heuristics) can improve coverage but cannot achieve completeness. Option C is wrong — undecidability applies to all programs, not just long ones.
Question 3 True / False
Every Turing-complete programming language can in principle compute the same class of functions, making them equivalent in computational power.
TTrue
FFalse
Answer: True
Turing completeness is a threshold property: once crossed, all Turing-complete systems are computationally equivalent — they can each simulate any Turing machine and therefore compute any effectively computable function. Python, C, Java, lambda calculus, Conway's Game of Life, and Brainfuck are all equivalent in this sense. They differ in efficiency, abstraction, and ease of use, but not in the set of functions they can compute. This equivalence is why choosing a programming language for a task is largely a matter of practicality, not fundamental capability.
Question 4 True / False
A computational system with mainly conditional branching but no form of unbounded memory (or its equivalent) can be Turing-complete.
TTrue
FFalse
Answer: False
Unbounded memory (or something equivalent) is a necessary requirement for Turing completeness. A system with conditional branching but bounded memory can only be in finitely many states — it is at most a finite automaton, which can only recognize regular languages. Turing completeness requires the ability to store and manipulate an unbounded amount of information. Lambda calculus achieves unbounded storage through function closures; cellular automata achieve it through an infinite grid; a Turing machine achieves it through an infinite tape. The combination of branching plus unbounded storage is what enables universality.
Question 5 Short Answer
Why does Turing completeness make it mathematically impossible — not just practically difficult — to build a general analyzer that determines whether any arbitrary program in a Turing-complete language will halt?
Think about your answer, then reveal below.
Model answer: The halting problem is undecidable: no Turing machine (and therefore no program) can correctly answer 'does this program halt on this input?' for all possible programs. The proof is a diagonalization argument — any hypothetical halting detector can be fed a program that does the opposite of what the detector predicts, producing a contradiction. Since every Turing-complete system can simulate any Turing machine, the halting problem applies to every Turing-complete language. This is not an engineering limitation that better algorithms could overcome; it is a provable mathematical boundary on what any program can compute.
The key insight is that Turing completeness is a double-edged property: it means 'can compute anything computable,' but it equally means 'inherits all undecidability results.' You cannot have one without the other. Languages designed to avoid undecidability (like total functional languages or Coq's calculus of constructions) achieve this by sacrificing Turing completeness — they cannot express all computable functions. The tradeoff between computational universality and analyzability is fundamental.