In Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. Introduction Computer science encomposses a variety of topics relating to computation, ranging from abstract analysis of algorithms and formal grammars, to subjects like programming languages... computer science, a deterministic algorithm is an Flowcharts are often used to represent algorithms. An algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi), is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast with heuristic... algorithm which, in informal terms, behaves predictably. If it runs on a particular input, it will always produce the same correct output, and the underlying machine will always pass through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.

One simple model for deterministic algorithms is the In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). The concept of a function is fundamental to virtually every branch of mathematics... mathematical function; just as a function always produces the same output given a certain input, so do deterministic algorithms. The difference is that algorithms describe precisely how the output is obtained from the input, whereas abstract functions may be defined implicitly.

Formal definition

Formally, deterministic algorithms can be defined in terms of a In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. The internal states of the machine carry no further structure. FSMs are very widely used in modelling of application behaviour, design of... state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, as long as we can predict with certainty what states it will pass through.

Examples of particular An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. Abstraction of computing processes is used in both the computer science and computer engineering disciplines. Abstract machines are often used in thought experiments regarding computability or to analyze the complexity of... abstract machines which are deterministic include the The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing... deterministic Turing machine and In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is a deterministic next state. Formal definition A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of... deterministic finite automaton.

What makes algorithms non-deterministic?

A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:

• If it uses external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data.
• If it operates in a way that is timing-sensitive, for example if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.
• If a hardware error causes its state to change in an unexpected way.

Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most An alternate rewrite has been has been proposed. Please refer to it for large rewrites. A programming language or computer language is a standardized communication technique for expressing instructions to a computer. It is a set of syntactic and semantic rules used to define computer programs. A language enables a... programming languages and especially Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. In contrast to imperative programming, functional programming emphasizes the evaluation of functional expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values. Introduction Mathematical functions... functional programming languages make an effort to prevent the above events from happening except under controlled conditions. Because of the way such restrictions enforce determinism, deterministic algorithms are sometimes called Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). As a consequence of this restriction, variables refer to immutable, persistent values. This means that old values available prior to a change continue to be accessible and may be... purely functional.

Problems with deterministic algorithms

Unfortunately, for some problems deterministic algorithms are also hard to find. For example, there are simple and efficient A randomized algorithm is an algorithm which is allowed to flip a truly random coin. In common practice, this means that the machine implementing the algorithm has access to a pseudo-random number generator. The algorithm typically uses the random bits as an auxiliary input to guide its behavior, in... probabilistic algorithms that determine whether a given number is prime but have a very small chance of being wrong. These have been known since the 1970s (see for example The Fermat primality test is a probabalistic test to determine if a number is composite or probably prime. Concept Fermats little theorem states that if p is prime and , then . If we want to test if n is prime, then we can pick random as in the interval... Fermat primality test); only after another 30 years of focused research was a deterministic algorithm found, and it remains considerably slower in practice.

As another example, In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... NP complete problems, which include many of the most important practical problems, can be quickly solved using an imaginary massively parallel machine called a In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of... nondeterministic Turing machine, but efficient practical algorithms have never been found for any of them. At best, we can currently only find approximate solutions or solutions in special cases.

Another major problem with deterministic algorithms is that sometimes, we don't want the results to be predictable. For example, if you are playing an on-line game of For other uses of the word Blackjack see Blackjack (disambiguation). Black Jack (ブラック・ジャック Burakku Jakku) is a manga written by Osamu Tezuka in the 1970s, dealing with the medical adventures of a doctor named Black Jack. Black Jack consists of hundreds of... blackjack that shuffles its deck using a A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. The outputs of pseudorandom number generators are not truly random—they only approximate some of the properties of random numbers. John von Neumann emphasized this... pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing them to cheat (this has actually happened!)