3
$\begingroup$

Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single OR gate for a depth two circuit. Now change the AND gates to XOR gates, is it correct to say that I now have a different algorithm for any given input?

$\endgroup$
0
$\begingroup$

Look at the formal definition of algorithm:

  • Algorithms works in discrete time, (step by step), defining computational states for each input.
  • Algorithms must be independent of its implementation, and each state must be formally described using first-order structures.
  • Transitions from one state to another must take a finite and fixed number of terms in the current state.

Circuits works naturally in this way, so you can make an algorithm from here using high-level descriptions (flow charts, pseudocode) or formal descriptions and of course the implementation will be a circuit.

$\endgroup$
  • 3
    $\begingroup$ I don't think that this is a formal definition of "algorithm", nor do I think there is one (that is generally accepted and used). $\endgroup$ – Raphael May 28 '13 at 7:05
  • $\begingroup$ Isn't the definition of algorithm anything that can be computed by a Turing Machine, as per the Church-Turing thesis? $\endgroup$ – gardenhead Jun 15 '14 at 23:16
4
$\begingroup$

Have a look at Turing-completeness and the Church-Turing thesis (CT). Basically, CT is saying that everything that is computable, is computable on a Turing machine. Many different models of computation are known to be equivalent to the Turing machine. Even if you are considering something esoteric you came up with yourself, if what you have is Turing-complete, you can claim that you really do have an algorithm.

A circuit is a non-uniform model of computation, meaning that different size circuit compute things for different size inputs. A Turing machine on the other hand is a uniform model, so it's used for all input lengths. Given a Turing machine, one can construct a Boolean circuit that is able to simulate all its computation if we put a bound on the Turing machine's memory. Also, given a circuit, we can build a Turing machine that simulates the circuit.

$\endgroup$
  • $\begingroup$ So can I take your answer as a yes to my question: a Boolean circuit by itself IS an algorithm by definition? $\endgroup$ – William Hird May 26 '13 at 14:46
  • 2
    $\begingroup$ @WilliamHird Obviously, this depends on how you define an algorithm. In fact, around 1900 people had no way of formalizing algorithms. They were just some "procedures you follow to solve a problem". That's why lambda calculus, Turing machines etc. had to be developed. So yes, you can very well argue your circuit is an algorithm. $\endgroup$ – Juho May 26 '13 at 14:51
  • $\begingroup$ btw families of circuits can solve any problem in unary, including undecidable ones, like the halting problem in unary $\endgroup$ – Sasho Nikolov May 26 '13 at 16:16
1
$\begingroup$

I don't think so, because when we think of algorithms (say as Turing machines), they allow the input to be any size. However, a family of circuits can $\mathcal C = \{C_n \ | \ n \in \mathbb N\}$, where we run $C_n$ on inputs of size $n$, can be said to be an algorithm.

$\endgroup$

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.