Lecture 01

• Function
  • A process that manipulates information in some way
    • input-output behavior
    • More formal definition: $f:D→R$
    • A function assigns a value $f(x) \in R$ to every element of $x\in D$
    • The following two questions are answered by the definition of each computation model
      • What steps are allowed?
      • How to measure efficiency?
  • Assumptions:
    • We make the following two assumptions
    • $D=\{0,1\}^*$ - all binary string $D=\{0,1\}^n$ - binary string of length n
      • Since every countable set can be mapped to the first set, and every finite set can be mapped to the second, this does not lose too much generality
    • $R = \{0,1\}$
      • This does lose some generality, but it will turn out that most of our ideas will easily translate to the situation when the output domain is bigger. Further, for most examples of functions to bigger domains that are hard to compute, we shall be able to easily find corresponding boolean functions that are hard to compute.
• Computational Process
  • a process that manipulates information in some local or restricted way.

Several Computation Models

Finite Automata