Circuits are great as model for bounded input lengths.
An algorithm is a finite answer to an infinite number of questions
Let f be a function $f:\{0,1\}^*\to\{0,1\}$ with unbounded input lengths
Example:
$XOR:\{0,1\}^*\to\{0,1\}$ = 1 if number of inputs in x is odd, 0 otherwise
def XOR(x):
ans = 0
for i in range(len(x)):
ans = (ans + x[i]) % 2
return ans
Algorithm like this uses constant memory and do a single scan from left to right are called “Single Pass Constant Memory Algorithm”
DFA with C states over {0, 1} is a pair
D = (T, S) where $T:[C] \times\{0,1\} \to[C]$ is the transition function that tells you where to go from the current state and $S \subseteq [C]$
How to Compute it?
a) Start with a state $S_0=0$
b) for i = 0, 1, …., len(x)-1:
$s_{i+1} = T(s_i, x[i])$
c) Output 1 is last state $\in S$, 0 otherwise
We say a DFA D = (TS) computes a function $f:\{0,1\}^\to\{0,1\}$ if f(x) = D(x) for all $x\in:\{0,1\}^$
Note: In graph, we could do a double circuit to denote elements of S
Some other notations:
→ DFA = Finite State Machine
→ Start state = 0
→ “Alphabet” = {0, 1}
Examples
This above DFA computes
$D(x)= \begin{cases} 1 \quad \text{if number of 1's in x is divisible by 3} \\ 0 \quad \text{otherwise} \end{cases}$
For instance , let’s consider