When we start teaching ‘digital logic design’ we say that there are three primary logics (AND, OR, NOT) and the other four (NAND, NOR, Excusive-OR, Excusive-NOR) are secondary logics. But the concept of universal logics (NAND, NOR) suggests that you can design algorithms or hardware implementations of any complex problem. Can anyone give some examples of real and complex problem’s realization algorithm using either NAND/NOR logic.
Hi, you mean something like the minesweeper challenge?
http://www.cs.auckland.ac.nz/~jaru003/treasure_chest/Ian%20Stewart%27s%20article%20Million-Dollar%20Minesweeper.htm
In complexity theory there is the concept of bit complexity, that you can program every algorithm on a Turing machine, so that you only have to realize the relatively simple turing machine using NAND gates.
Another view of bit complexity is via computational graphs where the nodes are arithmetic operations or alternatively logical operations and the leafs only consist of numbers 0 and 1. There is, e.g., ongoing research on the complexity classes of real numbers, for instance, how small one can make such a graph that computes the first n binary digits of pi or ln(2). Obviously, just giving the bits gives an upper bound of size n.
The work of Arnold Schönhage should come close to your stated goal. He gives the bit complexity of all algorithms, which is also necessary because he uses bigint data types. But nobody will completely resolve all operations into NAND gates, basic operations are used as modules where one knows in principle how to implement them as logic circuit.
Dear Afaq,
In computer science, an algorithm is defined as a problem (a question) that has yes/no answer or either of them. In other words, if there exists such a Turing machine that can decide the problem, then the problem is decidable. Since a Turning machine is a mathematical abstraction of a computing device (e.g., computer), then an algorithm can be implemented using logic gates, e.g., NAND that specifically decide the problem. As an example of complex system, modern controllers used in memory sticks are implemented as SoCs including various peripherial devices and often use NAND logic because it is very fast (probably the fastest).
Sorry for the misunderstanding. Certainly, logic gates and memory elements are different things. An example was about the controller which is usually implemented as an SoC and integrates various function units and usually uses NAND gates due to their efficiency.
Indeed, a Turing machine contains an infinite tape while hardware memory systems are are finite still. However, what can be an example of a real complex system that would require an infinite 'tape'?
Dear Professor Afaq Sb.
yes you are all right. the DeMorgan's Theorem relevance to this question obviously.
Dear All,
Primary logics are only AND, OR and NOT. Each of these logics can be be realized using NAND (secondary) logic.
NOT A = A NAND A
A AND B = NOT (A NAND B)
A OR B = (NOT A )NAND (NOT B)
Dear ALL
Can we discuss examples of some real problems solved by using NAND or NOR logics or hybrid of NAND / NOR.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms