A system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. A classic example is lambda calculus. Programming languages such as C, C++, COBOL, Pascal, Java are all turing complete.
In essence: "Turing complete" == "Can do anything a Turing machine does"
Turing machine is an endless infinite piece of tape, has a read/write head that goes over the top of the marks on the tape which can be 0s or 1s. Just the ability to read and write on a infinite piece of tape of patterns of 0s and 1s is powerful enough to compute anything that can be computed.
- Conditional branching (if-else statements)
- Must be able to have arbitrary amount of memory (totality of the ram: as much memory as you need must be present)
This describes a design architecture for an electronic digital computer with parts consisting of a processing unit containing an arithmetic logic unit and processor registers, a control unit containing an instruction register and program counter, a memory to store both data and instructions, external mass storage, and input and output mechanisms.
- P refers to polynomial time problems which are easy to solve.
- NP refers to non-polynomial time probelms which are hard to solve. For example, factoring is a hard problem (e.g.: What are the factors of a large 100-digit number?).
- However, for NP problems, we can verify the correctness quickly. Hence, they are hard to solve, but easy to check.
- The P vs NP problems asks whether every problem whose solution can be quickly verified (in polynomial time) can also be solved quickly (in polynomial time.)
TODO: NP Hard, NP Complete
An indivisible sequence of primitive operations that must complete without interruption (or that can be expected to do so), or can be considered as instantaneous.
Denoting an element of a set which is unchanged in value when multiplied or otherwise operated on by itself.
From a RESTful service standpoint, for an operation (or service call) to be idempotent, clients can make that same call repeatedly while producing the same result. In other words, making multiple identical requests has the same effect as making a single request. Note that while idempotent operations produce the same result on the server (no side effects), the response itself may not be the same (e.g. a resource's state may change between requests).