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?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered May 26, 2013 at 15:12
-
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$– RaphaelCommented May 28, 2013 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$ Commented Jun 15, 2014 at 23:16
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ So can I take your answer as a yes to my question: a Boolean circuit by itself IS an algorithm by definition? $\endgroup$ Commented May 26, 2013 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$– JuhoCommented May 26, 2013 at 14:51
-
$\begingroup$ btw families of circuits can solve any problem in unary, including undecidable ones, like the halting problem in unary $\endgroup$ Commented May 26, 2013 at 16:16
$\begingroup$
$\endgroup$
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.
