Computation Study Guide

📖 Core Concepts Computation – any arithmetic or non‑arithmetic calculation that is well‑defined; includes solving equations and running algorithms. Computer – the device (mechanical, electronic, or human) that carries out a computation. Computable statement – a well‑defined statement that can be encoded as a computation (i.e., expressed in the parameters of a Turing machine). Computer Science – the discipline that studies computations, their limits, and how to perform them. Physical realization – a closed physical system (e.g., Turing machine, digital computer, analog computer, human following strict rules) that enacts a computation. 📌 Must Remember A statement is computable iff it can be represented as a Turing‑machine initialization (Turing formalisation). Non‑computable examples: ill‑defined statements (e.g., “Paul loves me twice as much as Joe”) and provably unsolvable problems such as the halting problem. Medium‑independence: the computational property does not depend on the physical substrate (voltage, gears, etc.). Computability Theory = study of which problems are computable vs. non‑computable; it defines the limits of computation. State‑based models: Turing machine, pushdown automaton, finite‑state automaton, parallel random‑access machine. Functional model: lambda calculus. Logical model: logic programming languages. Concurrent models: actor model, process calculi. 🔄 Key Processes Encoding a problem as a computation Identify the input parameters. Express the problem in a formal language (e.g., Turing‑machine description, lambda term). Determining computability Check if the encoding fits one of the equivalent formalisations (Turing, lambda‑definability, general recursiveness, 1‑definability). If no encoding exists, the statement is non‑computable. Physical realization Choose a physical system (digital computer, mechanical device, etc.) that can implement the encoded algorithm. Verify that the system is closed and deterministic enough to follow the encoded steps. 🔍 Key Comparisons Turing machine vs. Lambda calculus – both capture the same class of computable functions, but one is state‑based (tape + head) and the other is functional (function abstraction & application). Digital computer vs. Analog computer – digital uses discrete symbols (bits), analog uses continuous physical quantities; both can be computationally equivalent when properly encoded. Mechanical computer vs. Human mathematician – both are realizers of computation; the former obeys fixed mechanical rules, the latter follows strict logical steps. ⚠️ Common Misunderstandings “All problems can be solved by a computer.” – False; the halting problem and many ill‑defined statements are provably non‑computable. “Medium‑independence means any material works as a computer.” – It means the computational property can be instantiated on different media, but the system must still obey the required formal rules. “If a statement is well‑defined, it is automatically computable.” – Not true; a well‑defined statement may still be beyond algorithmic solution (e.g., certain decision problems). 🧠 Mental Models / Intuition Computation as a recipe – think of a computation as a precise, step‑by‑step recipe that any qualified “cook” (computer, human, or machine) can follow without ambiguity. Equivalence of models – imagine different languages (English, French, Morse code) all describing the same story; Turing machines, lambda calculus, and other models are just different languages for the same class of “stories” (computable functions). 🚩 Exceptions & Edge Cases Ill‑defined statements – even if they seem meaningful in natural language, they may lack a unique encoding and thus are non‑computable. Physical limits – real hardware may have resource constraints (time, memory) that make a theoretically computable problem practically unsolvable; the theory of computability abstracts away these limits. 📍 When to Use Which State‑based model – best when the problem naturally involves discrete steps or memory stacks (e.g., parsing, language recognition). Functional model (lambda calculus) – ideal for reasoning about higher‑order functions and functional programming concepts. Logical model – choose for problems expressed as logical inference or rule‑based systems. Concurrent model – use when the problem involves independent agents or asynchronous communication (e.g., distributed systems). 👀 Patterns to Recognize Encoding ↔ Turing machine – whenever a problem is phrased as “can we write an algorithm…?”, look for a way to map it to a Turing‑machine description. Halting‑type structure – questions asking “does this program ever stop?” are classic non‑computable patterns. Medium‑independence cue – any statement that emphasizes “voltage vs. gears vs. neurons” signals the mechanistic account and the abstract nature of computation. 🗂️ Exam Traps Distractor: “All well‑defined problems are computable.” – Wrong; well‑defined ≠ solvable (halting problem disproves). Distractor: “Analog computers can compute functions that digital computers cannot.” – Incorrect; with proper encoding, both are computationally equivalent. Distractor: “The physical size of a computer determines its computational power.” – Misleading; power is defined by the formal model, not by physical dimensions. Near‑miss answer: Choosing “lambda calculus” when the question asks for a state‑based description; both are equivalent but the model asked for matters. --- Use this guide for a quick, high‑yield review before the exam. Focus on the core definitions, the equivalence of formal models, and the classic non‑computable examples.