Can a Boolean circuit be considered an algorithm?

Question

Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single OR gate for a depth two circuit. Now change the AND gates to XOR gates, is it correct to say that I now have a different algorithm for any given input?

Answer 1

Look at the formal definition of algorithm:

• Algorithms works in discrete time, (step by step), defining computational states for each input.
• Algorithms must be independent of its implementation, and each state must be formally described using first-order structures.
• Transitions from one state to another must take a finite and fixed number of terms in the current state.

Circuits works naturally in this way, so you can make an algorithm from here using high-level descriptions (flow charts, pseudocode) or formal descriptions and of course the implementation will be a circuit.

Answer 2

Have a look at Turing-completeness and the Church-Turing thesis (CT). Basically, CT is saying that everything that is computable, is computable on a Turing machine. Many different models of computation are known to be equivalent to the Turing machine. Even if you are considering something esoteric you came up with yourself, if what you have is Turing-complete, you can claim that you really do have an algorithm.

A circuit is a non-uniform model of computation, meaning that different size circuit compute things for different size inputs. A Turing machine on the other hand is a uniform model, so it's used for all input lengths. Given a Turing machine, one can construct a Boolean circuit that is able to simulate all its computation if we put a bound on the Turing machine's memory. Also, given a circuit, we can build a Turing machine that simulates the circuit.

Answer 3

I don't think so, because when we think of algorithms (say as Turing machines), they allow the input to be any size. However, a family of circuits can $\mathcal C = \{C_n \ | \ n \in \mathbb N\}$, where we run $C_n$ on inputs of size $n$, can be said to be an algorithm.