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?

Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the other hand, accept an input of a fixed size. Hence Boolean functions don't even qualify as potentially Turing-complete.

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.

StackExchange Computer Science Q#26096, answer score: 9