11
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ How could this machinery get stuck in an infinite loop? $\endgroup$
    – Guildenstern
    Commented May 25, 2014 at 22:56
  • $\begingroup$ 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$... $\endgroup$
    – user13675
    Commented May 25, 2014 at 23:37

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would their counterpart, boolean circuits, be Turing complete? I am guessing they are since Cook (in his proof of the NP-completeness of 3SAT) showed how Turing machines and boolean circuits are equivalent? $\endgroup$
    – user13675
    Commented May 26, 2014 at 15:59
  • $\begingroup$ @user13675 No, it's exactly the same problem. Every halting Turing machine with can be converted into an equivalent Boolean circuit or formula for every size of input, but for each size you will need a different one. $\endgroup$
    – Yuval Filmus
    Commented May 26, 2014 at 23:05
5
$\begingroup$

strictly speaking as YF has answered, finite circuits cannot be Turing complete.

however its worth mentioning a lead in response to this question (and maybe what youre looking for) a closely related concept used quite widely in theory where circuits are used to compute functions in a way that is stronger than Turing complete.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.