Computation

• Intuitatively: We think of computation as “ask a question” and “get an answer” like if you had the equation $y=x^2$ and I say $x=3$, then computation is putting $3$ in a black box and returning $9$.
• Informally: Computation is modelled as answers to yes/no questions.
• Formally: Computation means
  • Given the description of some language $L$.
  • Given an input String $s$.
  • Compute a yes or no answer to the following question:
    • is $s\in L$?
  • That is, does $L$ accept $s$, or does it not accept $s$.

Examples

• Function: Computing a function $f(x)$ can be reduced to a decision problem by rephrasing it “Does $f(x)=y$”, if you can answer this question, you can compute $f(X)$. Thus we can fit functions in our above definition of computation.
• Optimization: Optimization problems can be transformed into decision problems. “What is the shortest path from $A$ to $B$”, can be phrased as “Is $P$ the shortest path between $A$ and $B$.”
• Search: Search problems like “Is this name in this database?” are inherently set membership tests, but it also generalizes: “Is there a 2-letter surname in this database”, can be rephased as multiple set membership tests across all possibilities.

Motivation

Why do computer scientists like this approach?

• Rigor: Sets are well-understood objects with precise definitions.
• Reducible: Any algorithm run on any input can be reduced to “is $x\in L$?”
• Apples-to-apples: Allows for direct comparison algorithms. Computational complexity benefits from being able to cleanly map one decision problem to another.
• Fundamental: Lets us reason about computation in a direct way. Turning Machines are easy-to-define constructions that accept or reject an input. If you can show no Turning machine exists that will always stop and produce the right answer for a given problem, it suggests no algorithm for it exists.