# Are Boolean functions Turing complete

A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$.

The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left unchanged. The same can be said of $\mathrm{XOR}$ gates.

In this sense we can start with an initial machine configuration $\textbf{b}=(b_1,\ldots,b_n)$ such that $b_i\in\{0,1\}$ and $\mathrm{XOR}$ it with successive values $\textbf{v}_i$:

$\textbf{b}\oplus\textbf{v}_1\oplus\textbf{v}_2\oplus\textbf{v}_3\ldots$

Each state $\textbf{v}_i$ would represent a permutation of some element in $\textbf{b}$. This process effectively mimics a Turing machine and assumes that there is some generator for the values $\textbf{v}_i$.

So can we say that Boolean functions Turing complete?

• How could this machinery get stuck in an infinite loop? – Guildenstern May 25 '14 at 22:56
• I guess that the thing is that while the Boolean circuit formalism is isomorphic to the Turing formalism, it does not tell you how to build or generate such a program... You kind of need to just "know" the values $\textbf{v}_i$... – user13675 May 25 '14 at 23:37

The relevant notion of completeness here is a complete basis of connectives. A set of connectives ($k$-ary functions on Boolean values for arbitrary $k$) is complete if every Boolean function on $x_1,\ldots,x_n$ (for arbitrary $n \geq 1$) can be represented using the connectives. The following sets are complete: the de Morgan basis $\{\lnot,\lor,\land\}$ and the basis $\{\lnot,\Rightarrow\}$. In contrast, $\{\lnot,\oplus\}$ is not complete: it can only express linear functions.
namely, circuit families. a family of circuits can compute infinite languages. each input of size $n$ has an associated circuit/function $C_n$ built via some method, not necessarily built via a TM! the circuit-languages computable by decidable TMs are known as uniform circuits and circuits not constructable within this class are known as nonuniform.