# Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates.

A Turing machine may halt or not in a particular input but a combinational(not sequential) logic circuit always gives an output in a particular input. You may not agree with my point on combinational circuit but a combinational circuit is just a deterministic system so I can evaluate step by step in a input until it gives an output, in other words, there is no loops in a combinational circuit, I think.

So, I want to know whether I can represent any computable function only by those three gates ?

Any way, thx!

• Think carefully about this. Can a computable function be partial? Can a Boolean function be partial? – Hans Hüttel Oct 31 '16 at 3:50

A Turing machine defines a function over all of $\Sigma^*$, it is a finite object which describes the operation on infinitely many inputs.
A logical circuit however, is defined over a specific number of variables, so it has a finite domain. Using boolean circuits over $n$ variables we can implement the set of all functions from $\left\{0,1\right\}^n$ to $\left\{0,1\right\}$, and no more (so no Turing completeness in the simple interpretation).
This is why, when dealing with logical circuits, the notion of non uniform computation is introduced. By non uniform, we mean that the mechanisem for processing some input $x$ might depend on $|x|$. In the context of circuits, this means that instead of talking about one circuit, were talking about a circuit family $\left\{c_n\right\}_{n\in\mathbb{N}}$, where $c_n$ is a circuit with $n$ inputs.
We say that a circuit family $\mathcal{C}_n$ decides some language $L$ if $\forall x\in\Sigma^*: x\in L \iff c_{|x|}(x)=1$. Note that non uniform computation extends the classical uniform computation, i.e. using circuit families of arbitrary size we can decide undecidable (relative to Turing machines) languages. Actually, we can decide all languages. If you want to reduce this back to the Turing model, then you must require the existence of a computable function $f$ which, given $n$, generates the circuit $c_n$.