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!

  • 1
    $\begingroup$ Think carefully about this. Can a computable function be partial? Can a Boolean function be partial? $\endgroup$ 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$.

  • $\begingroup$ I think you may misunderstanding my question. On the other words, this question is just asked whether the set of all boolean function is equal to the set of all computable function or is there a isomorphism between them? I just noticed that about few minutes ago and now I know the answer is no. Any way, thx! $\endgroup$
    – Yachao Zhu
    Oct 31 '16 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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