1000000100010@unknown@formal@none@1@S@⌊δAlgorithmδ⌋@@@@1@1@@oe@26-8-2013
1000000100020@unknown@formal@none@1@S@In ⌊>mathematics>⌋, ⌊>computing>⌋, ⌊>linguistics>⌋ and related disciplines, an ⌊∗algorithm∗⌋ is a sequence of instructions, often used for ⌊>calculation>⌋ and ⌊>data processing>⌋.@@@@1@21@@oe@26-8-2013
1000000100030@unknown@formal@none@1@S@It is formally a type of ⌊>effective method>⌋ in which a list of well-defined instructions for completing a task will, when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state.@@@@1@38@@oe@26-8-2013
1000000100040@unknown@formal@none@1@S@The transition from one state to the next is not necessarily ⌊>deterministic>⌋; some algorithms, known as ⌊>probabilistic algorithms>⌋, incorporate randomness.@@@@1@20@@oe@26-8-2013
1000000100050@unknown@formal@none@1@S@A partial formalization of the concept began with attempts to solve the ⌊>Entscheidungsproblem>⌋ (the "decision problem") posed by ⌊>David Hilbert>⌋ in 1928.@@@@1@22@@oe@26-8-2013
1000000100060@unknown@formal@none@1@S@Subsequent formalizations were framed as attempts to define "⌊>effective calculability>⌋" (Kleene 1943:274) or "effective method" (Rosser 1939:225); those formalizations included the Gödel-Herbrand-Kleene ⌊>recursive function>⌋s of 1930, 1934 and 1935, ⌊>Alonzo Church>⌋'s ⌊>lambda calculus>⌋ of 1936, ⌊>Emil Post>⌋'s "Formulation I" of 1936, and ⌊>Alan Turing>⌋'s ⌊>Turing machines>⌋ of 1936-7 and 1939.@@@@1@50@@oe@26-8-2013
1000000100070@unknown@formal@none@1@S@⌊=Etymology¦2=⌋@@@@1@1@@oe@26-8-2013
1000000100080@unknown@formal@none@1@S@⌊>Al-Khwārizmī>⌋, ⌊>Persian>⌋ ⌊>astronomer>⌋ and ⌊>mathematician>⌋, wrote a ⌊>treatise>⌋ in ⌊>Arabic>⌋ in 825 AD, ⌊/On Calculation with Hindu Numerals/⌋.@@@@1@18@@oe@26-8-2013
1000000100090@unknown@formal@none@1@S@(See ⌊>algorism>⌋).@@@@1@2@@oe@26-8-2013
1000000100100@unknown@formal@none@1@S@It was translated into ⌊>Latin>⌋ in the 12th century as ⌊/Algoritmi de numero Indorum/⌋ (al-Daffa 1977), which title was likely intended to mean "Algoritmi on the numbers of the Indians", where "Algoritmi" was the translator's rendition of the author's name; but people misunderstanding the title treated ⌊/Algoritmi/⌋ as a Latin plural and this led to the word "algorithm" (Latin ⌊/algorismus/⌋) coming to mean "calculation method".@@@@1@65@@oe@26-8-2013
1000000100110@unknown@formal@none@1@S@The intrusive "th" is most likely due to a ⌊>false cognate>⌋ with the ⌊>Greek>⌋ ⌊λἀριθμός¦grc¦ἀριθμός¦Langλ⌋ (⌊/arithmos/⌋) meaning "number".@@@@1@18@@oe@26-8-2013
1000000100120@unknown@formal@none@1@S@⌊=Why algorithms are necessary: an informal definition¦2=⌋@@@@1@7@@oe@26-8-2013
1000000100130@unknown@formal@none@1@S@No generally accepted ⌊/formal/⌋ definition of "algorithm" exists yet.@@@@1@9@@oe@26-8-2013
1000000100140@unknown@formal@none@1@S@An informal definition could be "an algorithm is a computer program that calculates something."@@@@1@14@@oe@26-8-2013
1000000100150@unknown@formal@none@1@S@For some people, a program is only an algorithm if it stops eventually.@@@@1@13@@oe@26-8-2013
1000000100160@unknown@formal@none@1@S@For others, a program is only an algorithm if it stops before a given number of calculation steps.@@@@1@18@@oe@26-8-2013
1000000100170@unknown@formal@none@1@S@A prototypical example of an "algorithm" is Euclid's algorithm to determine the maximum common divisor of two integers greater than one: "subtract the smallest number from the biggest one, repeat until you get a zero or a one".@@@@1@38@@oe@26-8-2013
1000000100180@unknown@formal@none@1@S@This procedure is know to stop always, and the number of subtractions needed is always smaller than the biggest of the two numbers.@@@@1@23@@oe@26-8-2013
1000000100190@unknown@formal@none@1@S@We can derive clues to the issues involved and an informal meaning of the word from the following quotation from ⌊λ⌊>Boolos & Jeffrey (1974, 1999)>⌋¦Boolos¦Jeffrey¦1974, 1999¦Harvard citation textλ⌋ (boldface added):@@@@1@30@@oe@26-8-2013
1000000100200@unknown@formal@none@1@S@⌊"No human being can write fast enough, or long enough, or small enough to list all members of an enumerably infinite set by writing out their names, one after another, in some notation.@@@@1@33@@oe@26-8-2013
1000000100210@unknown@formal@none@1@S@But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give ⌊∗explicit instructions for determining the nth member of the set∗⌋, for arbitrary finite n.@@@@1@32@@oe@26-8-2013
1000000100220@unknown@formal@none@1@S@Such instructions are to be given quite explicitly, in a form in which ⌊∗they could be followed by a computing machine∗⌋, or by a ⌊∗human who is capable of carrying out only very elementary operations on symbols∗⌋ ⌊λ⌊<(<⌋⌊>⌊<Boolos & Jeffrey 1974, 1999<⌋>⌋⌊<, p. 19)<⌋¦Boolos¦Jeffrey¦1974, 1999¦p=19¦Harvard citationλ⌋"⌋@@@@1@45@@oe@26-8-2013
1000000100230@unknown@formal@none@1@S@The words "enumerably infinite" mean "countable using integers perhaps extending to infinity".@@@@1@12@@oe@26-8-2013
1000000100240@unknown@formal@none@1@S@Thus Boolos and Jeffrey are saying that an algorithm ⌊/implies/⌋ instructions for a process that "creates" output integers from an ⌊/arbitrary/⌋ "input" integer or integers that, in theory, can be chosen from 0 to infinity.@@@@1@35@@oe@26-8-2013
1000000100250@unknown@formal@none@1@S@Thus we might expect an algorithm to be an algebraic equation such as ⌊∗y = m + n∗⌋ — two arbitrary "input variables" ⌊∗m∗⌋ and ⌊∗n∗⌋ that produce an output ⌊∗y∗⌋.@@@@1@31@@oe@26-8-2013
1000000100260@unknown@formal@none@1@S@As we see in ⌊>Algorithm characterizations>⌋ — the word algorithm implies much more than this, something on the order of (for our addition example):@@@@1@24@@oe@26-8-2013
1000000100270@unknown@formal@none@1@S@⌊⇥Precise instructions (in language understood by "the computer") for a "fast, efficient, good" ⌊/process/⌋ that specifies the "moves" of "the computer" (machine or human, equipped with the necessary internally-contained information and capabilities) to find, decode, and then munch arbitrary input integers/symbols ⌊∗m∗⌋ and ⌊∗n∗⌋, symbols ⌊∗+∗⌋ and ⌊∗=∗⌋ ... and (reliably, correctly, "effectively") produce, in a "reasonable" ⌊>time>⌋, output-integer ⌊∗y∗⌋ at a specified place and in a specified format.⇥⌋@@@@1@69@@oe@26-8-2013
1000000100280@unknown@formal@none@1@S@The concept of ⌊/algorithm/⌋ is also used to define the notion of ⌊>decidability>⌋.@@@@1@13@@oe@26-8-2013
1000000100290@unknown@formal@none@1@S@That notion is central for explaining how ⌊>formal system>⌋s come into being starting from a small set of ⌊>axiom>⌋s and rules.@@@@1@21@@oe@26-8-2013
1000000100300@unknown@formal@none@1@S@In ⌊>logic>⌋, the time that an algorithm requires to complete cannot be measured, as it is not apparently related with our customary physical dimension.@@@@1@24@@oe@26-8-2013
1000000100310@unknown@formal@none@1@S@From such uncertainties, that characterize ongoing work, stems the unavailability of a definition of ⌊/algorithm/⌋ that suits both concrete (in some sense) and abstract usage of the term.@@@@1@28@@oe@26-8-2013
1000000100320@unknown@formal@none@1@S@⌊⇥⌊/For a detailed presentation of the various points of view around the definition of "algorithm" see ⌊>Algorithm characterizations>⌋.@@@@1@18@@oe@26-8-2013
1000000100330@unknown@formal@none@1@S@For examples of simple addition algorithms specified in the detailed manner described in ⌊>Algorithm characterizations>⌋, see ⌊>Algorithm examples>⌋./⌋⇥⌋@@@@1@18@@oe@26-8-2013
1000000100340@unknown@formal@none@1@S@⌊=Formalization of algorithms¦2=⌋@@@@1@3@@oe@26-8-2013
1000000100350@unknown@formal@none@1@S@Algorithms are essential to the way ⌊>computer>⌋s process information, because a ⌊>computer program>⌋ is essentially an algorithm that tells the computer what specific steps to perform (in what specific order) in order to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards.@@@@1@48@@oe@26-8-2013
1000000100360@unknown@formal@none@1@S@Thus, an algorithm can be considered to be any sequence of operations that can be performed by a ⌊>Turing-complete>⌋ system.@@@@1@20@@oe@26-8-2013
1000000100370@unknown@formal@none@1@S@Authors who assert this thesis include Savage (1987) and Gurevich (2000):@@@@1@11@@oe@26-8-2013
1000000100380@unknown@formal@none@1@S@⌊"...Turing's informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine (Gurevich 2000:1)...according to Savage [1987], an algorithm is a computational process defined by a Turing machine.@@@@1@37@@oe@26-8-2013
1000000100390@unknown@formal@none@1@S@(Gurevich 2000:3)"⌋@@@@1@2@@oe@26-8-2013
1000000100400@unknown@formal@none@1@S@Typically, when an algorithm is associated with processing information, data are read from an input source or device, written to an output sink or device, and/or stored for further processing.@@@@1@30@@oe@26-8-2013
1000000100410@unknown@formal@none@1@S@Stored data are regarded as part of the internal state of the entity performing the algorithm.@@@@1@16@@oe@26-8-2013
1000000100420@unknown@formal@none@1@S@In practice, the state is stored in a ⌊>data structure>⌋, but an algorithm requires the internal data only for specific operation sets called ⌊>abstract data type>⌋s.@@@@1@26@@oe@26-8-2013
1000000100430@unknown@formal@none@1@S@For any such computational process, the algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise.@@@@1@24@@oe@26-8-2013
1000000100440@unknown@formal@none@1@S@That is, any conditional steps must be systematically dealt with, case-by-case; the criteria for each case must be clear (and computable).@@@@1@21@@oe@26-8-2013
1000000100450@unknown@formal@none@1@S@Because an algorithm is a precise list of precise steps, the order of computation will almost always be critical to the functioning of the algorithm.@@@@1@25@@oe@26-8-2013
1000000100460@unknown@formal@none@1@S@Instructions are usually assumed to be listed explicitly, and are described as starting "from the top" and going "down to the bottom", an idea that is described more formally by ⌊/⌊>flow of control>⌋/⌋.@@@@1@33@@oe@26-8-2013
1000000100470@unknown@formal@none@1@S@So far, this discussion of the formalization of an algorithm has assumed the premises of ⌊>imperative programming>⌋.@@@@1@17@@oe@26-8-2013
1000000100480@unknown@formal@none@1@S@This is the most common conception, and it attempts to describe a task in discrete, "mechanical" means.@@@@1@17@@oe@26-8-2013
1000000100490@unknown@formal@none@1@S@Unique to this conception of formalized algorithms is the ⌊>assignment operation>⌋, setting the value of a variable.@@@@1@17@@oe@26-8-2013
1000000100500@unknown@formal@none@1@S@It derives from the intuition of "⌊>memory>⌋" as a scratchpad.@@@@1@10@@oe@26-8-2013
1000000100510@unknown@formal@none@1@S@There is an example below of such an assignment.@@@@1@9@@oe@26-8-2013
1000000100520@unknown@formal@none@1@S@For some alternate conceptions of what constitutes an algorithm see ⌊>functional programming>⌋ and ⌊>logic programming>⌋ .@@@@1@16@@oe@26-8-2013
1000000100530@unknown@formal@none@1@S@⌊=Termination¦3=⌋@@@@1@1@@oe@26-8-2013
1000000100540@unknown@formal@none@1@S@Some writers restrict the definition of ⌊/algorithm/⌋ to procedures that eventually finish.@@@@1@12@@oe@26-8-2013
1000000100550@unknown@formal@none@1@S@In such a category Kleene places the "⌊/decision procedure/⌋ or ⌊/decision method/⌋ or ⌊/algorithm/⌋ for the question" (Kleene 1952:136).@@@@1@19@@oe@26-8-2013
1000000100560@unknown@formal@none@1@S@Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a "computational method" (Knuth 1997:5) or "⌊/calculation procedure/⌋ or ⌊/algorithm/⌋" (Kleene 1952:137); however, Kleene notes that such a method must eventually exhibit "some object" (Kleene 1952:137).@@@@1@43@@oe@26-8-2013
1000000100570@unknown@formal@none@1@S@Minsky makes the pertinent observation, in regards to determining whether an algorithm will eventually terminate (from a particular starting state):@@@@1@20@@oe@26-8-2013
1000000100580@unknown@formal@none@1@S@⌊"But if the length of the process is not known in advance, then "trying" it may not be decisive, because if the process does go on forever — then at no time will we ever be sure of the answer (Minsky 1967:105)."⌋@@@@1@42@@oe@26-8-2013
1000000100590@unknown@formal@none@1@S@As it happens, no other method can do any better, as was shown by ⌊>Alan Turing>⌋ with his celebrated result on the undecidability of the so-called ⌊>halting problem>⌋.@@@@1@28@@oe@26-8-2013
1000000100600@unknown@formal@none@1@S@There is no algorithmic procedure for determining of arbitrary algorithms whether or not they terminate from given starting states.@@@@1@19@@oe@26-8-2013
1000000100610@unknown@formal@none@1@S@The analysis of algorithms for their likelihood of termination is called ⌊>termination analysis>⌋.@@@@1@13@@oe@26-8-2013
1000000100620@unknown@formal@none@1@S@See the examples of (im-)"proper" subtraction at ⌊>partial function>⌋ for more about what can happen when an algorithm fails for certain of its input numbers — e.g., (i) non-termination, (ii) production of "junk" (output in the wrong format to be considered a number) or no number(s) at all (halt ends the computation with no output), (iii) wrong number(s), or (iv) a combination of these.@@@@1@64@@oe@26-8-2013
1000000100630@unknown@formal@none@1@S@Kleene proposed that the production of "junk" or failure to produce a number is solved by having the algorithm detect these instances and produce e.g., an error message (he suggested "0"), or preferably, force the algorithm into an endless loop (Kleene 1952:322).@@@@1@42@@oe@26-8-2013
1000000100640@unknown@formal@none@1@S@Davis does this to his subtraction algorithm — he fixes his algorithm in a second example so that it is proper subtraction (Davis 1958:12-15).@@@@1@24@@oe@26-8-2013
1000000100650@unknown@formal@none@1@S@Along with the logical outcomes "true" and "false" Kleene also proposes the use of a third logical symbol "u" — undecided (Kleene 1952:326) — thus an algorithm will always produce ⌊/something/⌋ when confronted with a "proposition".@@@@1@36@@oe@26-8-2013
1000000100660@unknown@formal@none@1@S@The problem of wrong answers must be solved with an independent "proof" of the algorithm e.g., using induction:@@@@1@18@@oe@26-8-2013
1000000100670@unknown@formal@none@1@S@⌊"We normally require auxiliary evidence for this (that the algorithm correctly defines a ⌊>mu recursive function>⌋), e.g., in the form of an inductive proof that, for each argument value, the computation terminates with a unique value (Minsky 1967:186)."⌋@@@@1@38@@oe@26-8-2013
1000000100680@unknown@formal@none@1@S@⌊=Expressing algorithms¦3=⌋@@@@1@2@@oe@26-8-2013
1000000100690@unknown@formal@none@1@S@Algorithms can be expressed in many kinds of notation, including ⌊>natural language>⌋s, ⌊>pseudocode>⌋, ⌊>flowchart>⌋s, and ⌊>programming language>⌋s.@@@@1@17@@oe@26-8-2013
1000000100700@unknown@formal@none@1@S@Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms.@@@@1@20@@oe@26-8-2013
1000000100710@unknown@formal@none@1@S@Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while remaining independent of a particular implementation language.@@@@1@28@@oe@26-8-2013
1000000100720@unknown@formal@none@1@S@Programming languages are primarily intended for expressing algorithms in a form that can be executed by a ⌊>computer>⌋, but are often used as a way to define or document algorithms.@@@@1@30@@oe@26-8-2013
1000000100730@unknown@formal@none@1@S@There is a wide variety of representations possible and one can express a given ⌊>Turing machine>⌋ program as a sequence of machine tables (see more at ⌊>finite state machine>⌋ and ⌊>state transition table>⌋), as flowcharts (see more at ⌊>state diagram>⌋), or as a form of rudimentary ⌊>machine code>⌋ or ⌊>assembly code>⌋ called "sets of quadruples" (see more at ⌊>Turing machine>⌋).@@@@1@60@@oe@26-8-2013
1000000100740@unknown@formal@none@1@S@Sometimes it is helpful in the description of an algorithm to supplement small "flow charts" (state diagrams) with natural-language and/or arithmetic expressions written inside "⌊>block diagram>⌋s" to summarize what the "flow charts" are accomplishing.@@@@1@34@@oe@26-8-2013
1000000100750@unknown@formal@none@1@S@Representations of algorithms are generally classed into three accepted levels of Turing machine description (Sipser 2006:157):@@@@1@16@@oe@26-8-2013
1000000100760@unknown@formal@none@1@S@⌊•⌊#⌊∗1 High-level description∗⌋:#⌋•⌋@@@@1@3@@oe@26-8-2013
1000000100770@unknown@formal@none@1@S@⌊⇥⌊⇥"...prose to describe an algorithm, ignoring the implementation details.@@@@1@9@@oe@26-8-2013
1000000100780@unknown@formal@none@1@S@At this level we do not need to mention how the machine manages its tape or head"⇥⌋⇥⌋@@@@1@17@@oe@26-8-2013
1000000100790@unknown@formal@none@1@S@⌊•⌊#⌊∗2 Implementation description∗⌋:#⌋•⌋@@@@1@3@@oe@26-8-2013
1000000100800@unknown@formal@none@1@S@⌊⇥⌊⇥"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape.@@@@1@22@@oe@26-8-2013
1000000100810@unknown@formal@none@1@S@At this level we do not give details of states or transition function"⇥⌋⇥⌋@@@@1@13@@oe@26-8-2013
1000000100820@unknown@formal@none@1@S@⌊•⌊#⌊∗3 Formal description∗⌋:#⌋•⌋@@@@1@3@@oe@26-8-2013
1000000100830@unknown@formal@none@1@S@⌊⇥⌊⇥Most detailed, "lowest level", gives the Turing machine's "state table".⇥⌋⇥⌋@@@@1@10@@oe@26-8-2013
1000000100840@unknown@formal@none@1@S@⌊⇥⌊/For an example of the simple algorithm "Add m+n" described in all three levels see ⌊>Algorithm examples>⌋./⌋⇥⌋@@@@1@17@@oe@26-8-2013
1000000100850@unknown@formal@none@1@S@⌊=Implementation¦3=⌋@@@@1@1@@oe@26-8-2013
1000000100860@unknown@formal@none@1@S@Most algorithms are intended to be implemented as ⌊>computer programs>⌋.@@@@1@10@@oe@26-8-2013
1000000100870@unknown@formal@none@1@S@However, algorithms are also implemented by other means, such as in a biological ⌊>neural network>⌋ (for example, the ⌊>human brain>⌋ implementing ⌊>arithmetic>⌋ or an insect looking for food), in an ⌊>electrical circuit>⌋, or in a mechanical device.@@@@1@37@@oe@26-8-2013
1000000100880@unknown@formal@none@1@S@⌊=Example¦2=⌋@@@@1@1@@oe@26-8-2013
1000000100890@unknown@formal@none@1@S@One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers.@@@@1@17@@oe@26-8-2013
1000000100900@unknown@formal@none@1@S@The solution necessarily requires looking at every number in the list, but only once at each.@@@@1@16@@oe@26-8-2013
1000000100910@unknown@formal@none@1@S@From this follows a simple algorithm, which can be stated in a high-level description ⌊>English>⌋ prose, as:@@@@1@17@@oe@26-8-2013
1000000100920@unknown@formal@none@1@S@⌊∗High-level description:∗⌋@@@@1@2@@oe@26-8-2013
1000000100930@unknown@formal@none@1@S@⌊•⌊#Assume the first item is largest.#⌋@@@@1@6@@oe@26-8-2013
1000000100940@unknown@formal@none@1@S@⌊#Look at each of the remaining items in the list and if it is larger than the largest item so far, make a note of it.#⌋@@@@1@26@@oe@26-8-2013
1000000100950@unknown@formal@none@1@S@⌊#The last noted item is the largest in the list when the process is complete.#⌋•⌋@@@@1@15@@oe@26-8-2013
1000000100960@unknown@formal@none@1@S@⌊∗(Quasi-)formal description:∗⌋ Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in ⌊>pseudocode>⌋ or ⌊>pidgin code>⌋:@@@@1@31@@oe@26-8-2013
1000000100970@unknown@formal@none@1@S@⌊πInput: A non-empty list of numbers ⌊/L/⌋.@@@@1@7@@oe@26-8-2013
1000000100980@unknown@formal@none@1@S@Output: The ⌊/largest/⌋ number in the list ⌊/L/⌋. ⌊/largest/⌋ ← ⌊/L/⌋⌊,0,⌋ ⌊∗for each∗⌋ ⌊/item/⌋ ⌊∗in∗⌋ the list ⌊/L⌊,≥1,⌋/⌋, ⌊∗do∗⌋ ⌊∗if∗⌋ the ⌊/item/⌋ > ⌊/largest/⌋, ⌊∗then∗⌋ ⌊/largest/⌋ ← the ⌊/item/⌋ ⌊∗return∗⌋ ⌊/largest/⌋π⌋@@@@1@31@@oe@26-8-2013
1000000100990@unknown@formal@none@1@S@For a more complex example of an algorithm, see ⌊>Euclid's algorithm>⌋ for the ⌊>greatest common divisor>⌋, one of the earliest algorithms known.@@@@1@22@@oe@26-8-2013
1000000101000@unknown@formal@none@1@S@⌊=Algorithm analysis¦3=⌋@@@@1@2@@oe@26-8-2013
1000000101010@unknown@formal@none@1@S@As it happens, it is important to know how much of a particular resource (such as time or storage) is required for a given algorithm.@@@@1@25@@oe@26-8-2013
1000000101020@unknown@formal@none@1@S@Methods have been developed for the ⌊>analysis of algorithms>⌋ to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(⌊/n/⌋), using the ⌊>big O notation>⌋ with ⌊/n/⌋ as the length of the list.@@@@1@38@@oe@26-8-2013
1000000101030@unknown@formal@none@1@S@At all times the algorithm only needs to remember two values: the largest number found so far, and its current position in the input list.@@@@1@25@@oe@26-8-2013
1000000101040@unknown@formal@none@1@S@Therefore it is said to have a space requirement of ⌊/O(1)/⌋, if the space required to store the input numbers is not counted, or O (log ⌊/n/⌋) if it is counted.@@@@1@31@@oe@26-8-2013
1000000101050@unknown@formal@none@1@S@Different algorithms may complete the same task with a different set of instructions in less or more time, space, or effort than others.@@@@1@23@@oe@26-8-2013
1000000101060@unknown@formal@none@1@S@For example, given two different recipes for making potato salad, one may have ⌊/peel the potato/⌋ before ⌊/boil the potato/⌋ while the other presents the steps in the reverse order, yet they both call for these steps to be repeated for all potatoes and end when the potato salad is ready to be eaten.@@@@1@54@@oe@26-8-2013
1000000101070@unknown@formal@none@1@S@The ⌊>analysis and study of algorithms>⌋ is a discipline of ⌊>computer science>⌋, and is often practiced abstractly without the use of a specific ⌊>programming language>⌋ or implementation.@@@@1@27@@oe@26-8-2013
1000000101080@unknown@formal@none@1@S@In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation.@@@@1@29@@oe@26-8-2013
1000000101090@unknown@formal@none@1@S@Usually ⌊>pseudocode>⌋ is used for analysis as it is the simplest and most general representation.@@@@1@15@@oe@26-8-2013
1000000101100@unknown@formal@none@1@S@⌊=Classes¦2=⌋@@@@1@1@@oe@26-8-2013
1000000101110@unknown@formal@none@1@S@There are various ways to classify algorithms, each with its own merits.@@@@1@12@@oe@26-8-2013
1000000101120@unknown@formal@none@1@S@⌊=Classification by implementation¦3=⌋@@@@1@3@@oe@26-8-2013
1000000101130@unknown@formal@none@1@S@One way to classify algorithms is by implementation means.@@@@1@9@@oe@26-8-2013
1000000101140@unknown@formal@none@1@S@⌊•⌊#⌊∗Recursion∗⌋ or ⌊∗iteration∗⌋: A ⌊>recursive algorithm>⌋ is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to ⌊>functional programming>⌋.@@@@1@28@@oe@26-8-2013
1000000101150@unknown@formal@none@1@S@⌊>Iterative>⌋ algorithms use repetitive constructs like ⌊>loops>⌋ and sometimes additional data structures like ⌊>stacks>⌋ to solve the given problems.@@@@1@19@@oe@26-8-2013
1000000101160@unknown@formal@none@1@S@Some problems are naturally suited for one implementation or the other.@@@@1@11@@oe@26-8-2013
1000000101170@unknown@formal@none@1@S@For example, ⌊>towers of hanoi>⌋ is well understood in recursive implementation.@@@@1@11@@oe@26-8-2013
1000000101180@unknown@formal@none@1@S@Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa.#⌋•⌋@@@@1@17@@oe@26-8-2013
1000000101190@unknown@formal@none@1@S@⌊•⌊#⌊∗Logical∗⌋: An algorithm may be viewed as controlled ⌊>logical deduction>⌋.@@@@1@10@@oe@26-8-2013
1000000101200@unknown@formal@none@1@S@This notion may be expressed as: ⌊∗Algorithm = logic + control∗⌋ (Kowalski 1979).@@@@1@13@@oe@26-8-2013
1000000101210@unknown@formal@none@1@S@The logic component expresses the axioms that may be used in the computation and the control component determines the way in which deduction is applied to the axioms.@@@@1@28@@oe@26-8-2013
1000000101220@unknown@formal@none@1@S@This is the basis for the ⌊>logic programming>⌋ paradigm.@@@@1@9@@oe@26-8-2013
1000000101230@unknown@formal@none@1@S@In pure logic programming languages the control component is fixed and algorithms are specified by supplying only the logic component.@@@@1@20@@oe@26-8-2013
1000000101240@unknown@formal@none@1@S@The appeal of this approach is the elegant ⌊>semantics>⌋: a change in the axioms has a well defined change in the algorithm.#⌋•⌋@@@@1@22@@oe@26-8-2013
1000000101250@unknown@formal@none@1@S@⌊•⌊#⌊∗Serial∗⌋ or ⌊∗parallel∗⌋ or ⌊∗distributed∗⌋: Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time.@@@@1@23@@oe@26-8-2013
1000000101260@unknown@formal@none@1@S@Those computers are sometimes called serial computers.@@@@1@7@@oe@26-8-2013
1000000101270@unknown@formal@none@1@S@An algorithm designed for such an environment is called a serial algorithm, as opposed to ⌊>parallel algorithm>⌋s or ⌊>distributed algorithms>⌋.@@@@1@20@@oe@26-8-2013
1000000101280@unknown@formal@none@1@S@Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time, whereas distributed algorithms utilize multiple machines connected with a ⌊>network>⌋.@@@@1@29@@oe@26-8-2013
1000000101290@unknown@formal@none@1@S@Parallel or distributed algorithms divide the problem into more symmetrical or asymmetrical subproblems and collect the results back together.@@@@1@19@@oe@26-8-2013
1000000101300@unknown@formal@none@1@S@The resource consumption in such algorithms is not only processor cycles on each processor but also the communication overhead between the processors.@@@@1@22@@oe@26-8-2013
1000000101310@unknown@formal@none@1@S@Sorting algorithms can be parallelized efficiently, but their communication overhead is expensive.@@@@1@12@@oe@26-8-2013
1000000101320@unknown@formal@none@1@S@Iterative algorithms are generally parallelizable.@@@@1@5@@oe@26-8-2013
1000000101330@unknown@formal@none@1@S@Some problems have no parallel algorithms, and are called inherently serial problems.#⌋•⌋@@@@1@12@@oe@26-8-2013
1000000101340@unknown@formal@none@1@S@⌊•⌊#⌊∗Deterministic∗⌋ or ⌊∗non-deterministic∗⌋: ⌊>Deterministic algorithm>⌋s solve the problem with exact decision at every step of the algorithm whereas ⌊>non-deterministic algorithm>⌋ solve problems via guessing although typical guesses are made more accurate through the use of ⌊>heuristics>⌋.#⌋•⌋@@@@1@36@@oe@26-8-2013
1000000101350@unknown@formal@none@1@S@⌊•⌊#⌊∗Exact∗⌋ or ⌊∗approximate∗⌋: While many algorithms reach an exact solution, ⌊>approximation algorithm>⌋s seek an approximation that is close to the true solution.@@@@1@22@@oe@26-8-2013
1000000101360@unknown@formal@none@1@S@Approximation may use either a deterministic or a random strategy.@@@@1@10@@oe@26-8-2013
1000000101370@unknown@formal@none@1@S@Such algorithms have practical value for many hard problems.#⌋•⌋@@@@1@9@@oe@26-8-2013
1000000101380@unknown@formal@none@1@S@⌊=Classification by design paradigm¦3=⌋@@@@1@4@@oe@26-8-2013
1000000101390@unknown@formal@none@1@S@Another way of classifying algorithms is by their design methodology or paradigm.@@@@1@12@@oe@26-8-2013
1000000101400@unknown@formal@none@1@S@There is a certain number of paradigms, each different from the other.@@@@1@12@@oe@26-8-2013
1000000101410@unknown@formal@none@1@S@Furthermore, each of these categories will include many different types of algorithms.@@@@1@12@@oe@26-8-2013
1000000101420@unknown@formal@none@1@S@Some commonly found paradigms include:@@@@1@5@@oe@26-8-2013
1000000101430@unknown@formal@none@1@S@⌊•⌊#⌊∗Divide and conquer∗⌋.@@@@1@3@@oe@26-8-2013
1000000101440@unknown@formal@none@1@S@A ⌊>divide and conquer algorithm>⌋ repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually ⌊>recursively>⌋), until the instances are small enough to solve easily.@@@@1@33@@oe@26-8-2013
1000000101450@unknown@formal@none@1@S@One such example of divide and conquer is ⌊>merge sorting>⌋.@@@@1@10@@oe@26-8-2013
1000000101460@unknown@formal@none@1@S@Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in conquer phase by merging them.@@@@1@28@@oe@26-8-2013
1000000101470@unknown@formal@none@1@S@A simpler variant of divide and conquer is called ⌊∗decrease and conquer algorithm∗⌋, that solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem.@@@@1@30@@oe@26-8-2013
1000000101480@unknown@formal@none@1@S@Divide and conquer divides the problem into multiple subproblems and so conquer stage will be more complex than decrease and conquer algorithms.@@@@1@22@@oe@26-8-2013
1000000101490@unknown@formal@none@1@S@An example of decrease and conquer algorithm is ⌊>binary search algorithm>⌋.#⌋@@@@1@11@@oe@26-8-2013
1000000101500@unknown@formal@none@1@S@⌊#⌊∗⌊>Dynamic programming>⌋∗⌋.@@@@1@2@@oe@26-8-2013
1000000101510@unknown@formal@none@1@S@When a problem shows ⌊>optimal substructure>⌋, meaning the optimal solution to a problem can be constructed from optimal solutions to subproblems, and ⌊>overlapping subproblems>⌋, meaning the same subproblems are used to solve many different problem instances, a quicker approach called ⌊/dynamic programming/⌋ avoids recomputing solutions that have already been computed.@@@@1@50@@oe@26-8-2013
1000000101520@unknown@formal@none@1@S@For example, the shortest path to a goal from a vertex in a weighted ⌊>graph>⌋ can be found by using the shortest path to the goal from all adjacent vertices.@@@@1@30@@oe@26-8-2013
1000000101530@unknown@formal@none@1@S@Dynamic programming and ⌊>memoization>⌋ go together.@@@@1@6@@oe@26-8-2013
1000000101540@unknown@formal@none@1@S@The main difference between dynamic programming and divide and conquer is that subproblems are more or less independent in divide and conquer, whereas subproblems overlap in dynamic programming.@@@@1@28@@oe@26-8-2013
1000000101550@unknown@formal@none@1@S@The difference between dynamic programming and straightforward recursion is in caching or memoization of recursive calls.@@@@1@16@@oe@26-8-2013
1000000101560@unknown@formal@none@1@S@When subproblems are independent and there is no repetition, memoization does not help; hence dynamic programming is not a solution for all complex problems.@@@@1@24@@oe@26-8-2013
1000000101570@unknown@formal@none@1@S@By using memoization or maintaining a ⌊>table>⌋ of subproblems already solved, dynamic programming reduces the exponential nature of many problems to polynomial complexity.#⌋@@@@1@23@@oe@26-8-2013
1000000101580@unknown@formal@none@1@S@⌊#⌊∗The greedy method∗⌋.@@@@1@3@@oe@26-8-2013
1000000101590@unknown@formal@none@1@S@A ⌊>greedy algorithm>⌋ is similar to a ⌊>dynamic programming algorithm>⌋, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment.@@@@1@42@@oe@26-8-2013
1000000101600@unknown@formal@none@1@S@The greedy method extends the solution with the best possible decision (not all feasible decisions) at an algorithmic stage based on the current local optimum and the best decision (not all possible decisions) made in previous stage.@@@@1@37@@oe@26-8-2013
1000000101610@unknown@formal@none@1@S@It is not exhaustive, and does not give accurate answer to many problems.@@@@1@13@@oe@26-8-2013
1000000101620@unknown@formal@none@1@S@But when it works, it will be the fastest method.@@@@1@10@@oe@26-8-2013
1000000101630@unknown@formal@none@1@S@The most popular greedy algorithm is finding the minimal spanning tree as given by ⌊>Kruskal>⌋.#⌋@@@@1@15@@oe@26-8-2013
1000000101640@unknown@formal@none@1@S@⌊#⌊∗Linear programming∗⌋.@@@@1@2@@oe@26-8-2013
1000000101650@unknown@formal@none@1@S@When solving a problem using ⌊>linear programming>⌋, specific ⌊>inequalities>⌋ involving the inputs are found and then an attempt is made to maximize (or minimize) some linear function of the inputs.@@@@1@30@@oe@26-8-2013
1000000101660@unknown@formal@none@1@S@Many problems (such as the ⌊>maximum flow>⌋ for directed ⌊>graphs>⌋) can be stated in a linear programming way, and then be solved by a 'generic' algorithm such as the ⌊>simplex algorithm>⌋.@@@@1@31@@oe@26-8-2013
1000000101670@unknown@formal@none@1@S@A more complex variant of linear programming is called integer programming, where the solution space is restricted to the ⌊>integers>⌋.#⌋@@@@1@20@@oe@26-8-2013
1000000101680@unknown@formal@none@1@S@⌊#⌊∗⌊>Reduction>⌋∗⌋.@@@@1@1@@oe@26-8-2013
1000000101690@unknown@formal@none@1@S@This technique involves solving a difficult problem by transforming it into a better known problem for which we have (hopefully) ⌊>asymptotically optimal>⌋ algorithms.@@@@1@23@@oe@26-8-2013
1000000101700@unknown@formal@none@1@S@The goal is to find a reducing algorithm whose ⌊>complexity>⌋ is not dominated by the resulting reduced algorithm's.@@@@1@18@@oe@26-8-2013
1000000101710@unknown@formal@none@1@S@For example, one ⌊>selection algorithm>⌋ for finding the median in an unsorted list involves first sorting the list (the expensive portion) and then pulling out the middle element in the sorted list (the cheap portion).@@@@1@35@@oe@26-8-2013
1000000101720@unknown@formal@none@1@S@This technique is also known as ⌊/transform and conquer/⌋.#⌋@@@@1@9@@oe@26-8-2013
1000000101730@unknown@formal@none@1@S@⌊#⌊∗Search and enumeration∗⌋.@@@@1@3@@oe@26-8-2013
1000000101740@unknown@formal@none@1@S@Many problems (such as playing ⌊>chess>⌋) can be modeled as problems on ⌊>graphs>⌋.@@@@1@13@@oe@26-8-2013
1000000101750@unknown@formal@none@1@S@A ⌊>graph exploration algorithm>⌋ specifies rules for moving around a graph and is useful for such problems.@@@@1@17@@oe@26-8-2013
1000000101760@unknown@formal@none@1@S@This category also includes ⌊>search algorithm>⌋s, ⌊>branch and bound>⌋ enumeration and ⌊>backtracking>⌋.#⌋@@@@1@12@@oe@26-8-2013
1000000101770@unknown@formal@none@1@S@⌊#⌊∗The probabilistic and heuristic paradigm∗⌋.@@@@1@5@@oe@26-8-2013
1000000101780@unknown@formal@none@1@S@Algorithms belonging to this class fit the definition of an algorithm more loosely.#⌋•⌋@@@@1@13@@oe@26-8-2013
1000000101790@unknown@formal@none@1@S@⌊•⌊#⌊>Probabilistic algorithm>⌋s are those that make some choices randomly (or pseudo-randomly); for some problems, it can in fact be proven that the fastest solutions must involve some ⌊>randomness>⌋.#⌋@@@@1@28@@oe@26-8-2013
1000000101800@unknown@formal@none@1@S@⌊#⌊>Genetic algorithm>⌋s attempt to find solutions to problems by mimicking biological ⌊>evolution>⌋ary processes, with a cycle of random mutations yielding successive generations of "solutions".@@@@1@24@@oe@26-8-2013
1000000101810@unknown@formal@none@1@S@Thus, they emulate reproduction and "survival of the fittest".@@@@1@9@@oe@26-8-2013
1000000101820@unknown@formal@none@1@S@In ⌊>genetic programming>⌋, this approach is extended to algorithms, by regarding the algorithm itself as a "solution" to a problem.#⌋@@@@1@20@@oe@26-8-2013
1000000101830@unknown@formal@none@1@S@⌊#⌊>Heuristic>⌋ algorithms, whose general purpose is not to find an optimal solution, but an approximate solution where the time or resources are limited.@@@@1@23@@oe@26-8-2013
1000000101840@unknown@formal@none@1@S@They are not practical to find perfect solutions.@@@@1@8@@oe@26-8-2013
1000000101850@unknown@formal@none@1@S@An example of this would be ⌊>local search>⌋, ⌊>tabu search>⌋, or ⌊>simulated annealing>⌋ algorithms, a class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount.@@@@1@31@@oe@26-8-2013
1000000101860@unknown@formal@none@1@S@The name "⌊>simulated annealing>⌋" alludes to the metallurgic term meaning the heating and cooling of metal to achieve freedom from defects.@@@@1@21@@oe@26-8-2013
1000000101870@unknown@formal@none@1@S@The purpose of the random variance is to find close to globally optimal solutions rather than simply locally optimal ones, the idea being that the random element will be decreased as the algorithm settles down to a solution.#⌋•⌋@@@@1@38@@oe@26-8-2013
1000000101880@unknown@formal@none@1@S@⌊=Classification by field of study¦3=⌋@@@@1@5@@oe@26-8-2013
1000000101890@unknown@formal@none@1@S@Every field of science has its own problems and needs efficient algorithms.@@@@1@12@@oe@26-8-2013
1000000101900@unknown@formal@none@1@S@Related problems in one field are often studied together.@@@@1@9@@oe@26-8-2013
1000000101910@unknown@formal@none@1@S@Some example classes are ⌊>search algorithm>⌋s, ⌊>sorting algorithm>⌋s, ⌊>merge algorithm>⌋s, ⌊>numerical algorithms>⌋, ⌊>graph algorithms>⌋, ⌊>string algorithms>⌋, ⌊>computational geometric algorithms>⌋, ⌊>combinatorial algorithms>⌋, ⌊>machine learning>⌋, ⌊>cryptography>⌋, ⌊>data compression>⌋ algorithms and ⌊>parsing techniques>⌋.@@@@1@30@@oe@26-8-2013
1000000101920@unknown@formal@none@1@S@Fields tend to overlap with each other, and algorithm advances in one field may improve those of other, sometimes completely unrelated, fields.@@@@1@22@@oe@26-8-2013
1000000101930@unknown@formal@none@1@S@For example, dynamic programming was originally invented for optimization of resource consumption in industry, but is now used in solving a broad range of problems in many fields.@@@@1@28@@oe@26-8-2013
1000000101940@unknown@formal@none@1@S@⌊=Classification by complexity¦3=⌋@@@@1@3@@oe@26-8-2013
1000000101950@unknown@formal@none@1@S@Algorithms can be classified by the amount of time they need to complete compared to their input size.@@@@1@18@@oe@26-8-2013
1000000101960@unknown@formal@none@1@S@There is a wide variety: some algorithms complete in linear time relative to input size, some do so in an exponential amount of time or even worse, and some never halt.@@@@1@31@@oe@26-8-2013
1000000101970@unknown@formal@none@1@S@Additionally, some problems may have multiple algorithms of differing complexity, while other problems might have no algorithms or no known efficient algorithms.@@@@1@22@@oe@26-8-2013
1000000101980@unknown@formal@none@1@S@There are also mappings from some problems to other problems.@@@@1@10@@oe@26-8-2013
1000000101990@unknown@formal@none@1@S@Owing to this, it was found to be more suitable to classify the problems themselves instead of the algorithms into equivalence classes based on the complexity of the best possible algorithms for them.@@@@1@33@@oe@26-8-2013
1000000102000@unknown@formal@none@1@S@⌊=Classification by computing power¦3=⌋@@@@1@4@@oe@26-8-2013
1000000102010@unknown@formal@none@1@S@Another way to classify algorithms is by computing power.@@@@1@9@@oe@26-8-2013
1000000102020@unknown@formal@none@1@S@This is typically done by considering some collection (class) of algorithms.@@@@1@11@@oe@26-8-2013
1000000102030@unknown@formal@none@1@S@A recursive class of algorithms is one that includes algorithms for all Turing computable functions.@@@@1@15@@oe@26-8-2013
1000000102040@unknown@formal@none@1@S@Looking at classes of algorithms allows for the possibility of restricting the available computational resources (time and memory) used in a computation.@@@@1@22@@oe@26-8-2013
1000000102050@unknown@formal@none@1@S@A subrecursive class of algorithms is one in which not all Turing computable functions can be obtained.@@@@1@17@@oe@26-8-2013
1000000102060@unknown@formal@none@1@S@For example, the algorithms that run in ⌊>polynomial time>⌋ suffice for many important types of computation but do not exhaust all Turing computable functions.@@@@1@24@@oe@26-8-2013
1000000102070@unknown@formal@none@1@S@The class algorithms implemented by ⌊>primitive recursive function>⌋s is another subrecursive class.@@@@1@12@@oe@26-8-2013
1000000102080@unknown@formal@none@1@S@Burgin (2005, p. 24) uses a generalized definition of algorithms that relaxes the common requirement that the output of the algorithm that computes a function must be determined after a finite number of steps.@@@@1@34@@oe@26-8-2013
1000000102090@unknown@formal@none@1@S@He defines a super-recursive class of algorithms as "a class of algorithms in which it is possible to compute functions not computable by any Turing machine" (Burgin 2005, p. 107).@@@@1@30@@oe@26-8-2013
1000000102100@unknown@formal@none@1@S@This is closely related to the study of methods of ⌊>hypercomputation>⌋.@@@@1@11@@oe@26-8-2013
1000000102110@unknown@formal@none@1@S@⌊=Legal issues¦2=⌋@@@@1@2@@oe@26-8-2013
1000000102120@unknown@formal@none@1@S@⌊⇥⌊/See also: ⌊>Software patents>⌋ for a general overview of the patentability of software, including computer-implemented algorithms./⌋⇥⌋@@@@1@16@@oe@26-8-2013
1000000102130@unknown@formal@none@1@S@Algorithms, by themselves, are not usually patentable.@@@@1@7@@oe@26-8-2013
1000000102140@unknown@formal@none@1@S@In the ⌊>United States>⌋, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals do not constitute "processes" (USPTO 2006) and hence algorithms are not patentable (as in ⌊>Gottschalk v. Benson>⌋).@@@@1@34@@oe@26-8-2013
1000000102150@unknown@formal@none@1@S@However, practical applications of algorithms are sometimes patentable.@@@@1@8@@oe@26-8-2013
1000000102160@unknown@formal@none@1@S@For example, in ⌊>Diamond v. Diehr>⌋, the application of a simple ⌊>feedback>⌋ algorithm to aid in the curing of ⌊>synthetic rubber>⌋ was deemed patentable.@@@@1@24@@oe@26-8-2013
1000000102170@unknown@formal@none@1@S@The ⌊>patenting of software>⌋ is highly controversial, and there are highly criticized patents involving algorithms, especially ⌊>data compression>⌋ algorithms, such as ⌊>Unisys>⌋' ⌊>LZW patent>⌋.@@@@1@24@@oe@26-8-2013
1000000102180@unknown@formal@none@1@S@Additionally, some cryptographic algorithms have export restrictions (see ⌊>export of cryptography>⌋).@@@@1@11@@oe@26-8-2013
1000000102190@unknown@formal@none@1@S@⌊=History: Development of the notion of "algorithm"¦2=⌋@@@@1@7@@oe@26-8-2013
1000000102200@unknown@formal@none@1@S@⌊=Origin of the word¦3=⌋@@@@1@4@@oe@26-8-2013
1000000102210@unknown@formal@none@1@S@The word ⌊/algorithm/⌋ comes from the name of the 9th century ⌊>Persian>⌋ mathematician ⌊>Abu Abdullah Muhammad ibn Musa al-Khwarizmi>⌋ whose works introduced Indian numerals and algebraic concepts.@@@@1@27@@oe@26-8-2013
1000000102220@unknown@formal@none@1@S@He worked in ⌊>Baghdad>⌋ at the time when it was the centre of scientific studies and trade.@@@@1@17@@oe@26-8-2013
1000000102230@unknown@formal@none@1@S@The word ⌊/⌊>algorism>⌋/⌋ originally referred only to the rules of performing ⌊>arithmetic>⌋ using ⌊>Arabic numerals>⌋ but evolved via European Latin translation of al-Khwarizmi's name into ⌊/algorithm/⌋ by the 18th century.@@@@1@30@@oe@26-8-2013
1000000102240@unknown@formal@none@1@S@The word evolved to include all definite procedures for solving problems or performing tasks.@@@@1@14@@oe@26-8-2013
1000000102250@unknown@formal@none@1@S@⌊=Discrete and distinguishable symbols¦3=⌋@@@@1@4@@oe@26-8-2013
1000000102260@unknown@formal@none@1@S@⌊∗Tally-marks∗⌋: To keep track of their flocks, their sacks of grain and their money the ancients used tallying: accumulating stones or marks scratched on sticks, or making discrete symbols in clay.@@@@1@31@@oe@26-8-2013
1000000102270@unknown@formal@none@1@S@Through the Babylonian and Egyptian use of marks and symbols, eventually ⌊>Roman numerals>⌋ and the ⌊>abacus>⌋ evolved (Dilson, p.16–41).@@@@1@19@@oe@26-8-2013
1000000102280@unknown@formal@none@1@S@Tally marks appear prominently in ⌊>unary numeral system>⌋ arithmetic used in ⌊>Turing machine>⌋ and ⌊>Post-Turing machine>⌋ computations.@@@@1@17@@oe@26-8-2013
1000000102290@unknown@formal@none@1@S@⌊=Manipulation of symbols as "place holders" for numbers: algebra¦3=⌋@@@@1@9@@oe@26-8-2013
1000000102300@unknown@formal@none@1@S@The work of the Ancient Greek geometers, Persian mathematician ⌊>Al-Khwarizmi>⌋ (often considered as the "father of ⌊>algebra>⌋"), and Western European mathematicians culminated in ⌊>Leibniz>⌋'s notion of the ⌊>calculus ratiocinator>⌋ (ca 1680):@@@@1@31@@oe@26-8-2013
1000000102310@unknown@formal@none@1@S@⌊⇥"A good century and a half ahead of his time, Leibniz proposed an algebra of logic, an algebra that would specify the rules for manipulating logical concepts in the manner that ordinary algebra specifies the rules for manipulating numbers" (Davis 2000:1)⇥⌋@@@@1@41@@oe@26-8-2013
1000000102320@unknown@formal@none@1@S@⌊=Mechanical contrivances with discrete states¦3=⌋@@@@1@5@@oe@26-8-2013
1000000102330@unknown@formal@none@1@S@⌊∗The clock∗⌋: Bolter credits the invention of the weight-driven ⌊>clock>⌋ as “The key invention [of Europe in the Middle Ages]", in particular the ⌊>verge escapement>⌋< (Bolter 1984:24) that provides us with the tick and tock of a mechanical clock.@@@@1@39@@oe@26-8-2013
1000000102340@unknown@formal@none@1@S@“The accurate automatic machine” (Bolter 1984:26) led immediately to "mechanical ⌊>automata>⌋" beginning in the thirteenth century and finally to “computational machines" – the ⌊>difference engine>⌋ and ⌊>analytical engine>⌋s of ⌊>Charles Babbage>⌋ and Countess ⌊>Ada Lovelace>⌋ (Bolter p.33–34, p.204–206).@@@@1@38@@oe@26-8-2013
1000000102350@unknown@formal@none@1@S@⌊∗Jacquard loom, Hollerith punch cards, telegraphy and telephony — the electromechanical relay∗⌋: Bell and Newell (1971) indicate that the ⌊>Jacquard loom>⌋ (1801), precursor to ⌊>Hollerith cards>⌋ (punch cards, 1887), and “telephone switching technologies” were the roots of a tree leading to the development of the first computers (Bell and Newell diagram p. 39, cf Davis 2000).@@@@1@56@@oe@26-8-2013
1000000102360@unknown@formal@none@1@S@By the mid-1800s the ⌊>telegraph>⌋, the precursor of the telephone, was in use throughout the world, its discrete and distinguishable encoding of letters as “dots and dashes” a common sound.@@@@1@30@@oe@26-8-2013
1000000102370@unknown@formal@none@1@S@By the late 1800s the ⌊>ticker tape>⌋ (ca 1870s) was in use, as was the use of ⌊>Hollerith cards>⌋ in the 1890 U.S. census.@@@@1@24@@oe@26-8-2013
1000000102380@unknown@formal@none@1@S@Then came the ⌊>Teletype>⌋ (ca 1910) with its punched-paper use of ⌊>Baudot code>⌋ on tape.@@@@1@15@@oe@26-8-2013
1000000102390@unknown@formal@none@1@S@Telephone-switching networks of electromechanical ⌊>relay>⌋s (invented 1835) was behind the work of ⌊>George Stibitz>⌋ (1937), the inventor of the digital adding device.@@@@1@22@@oe@26-8-2013
1000000102400@unknown@formal@none@1@S@As he worked in Bell Laboratories, he observed the “burdensome’ use of mechanical calculators with gears.@@@@1@16@@oe@26-8-2013
1000000102410@unknown@formal@none@1@S@"He went home one evening in 1937 intending to test his idea....@@@@1@12@@oe@26-8-2013
1000000102420@unknown@formal@none@1@S@When the tinkering was over, Stibitz had constructed a binary adding device".@@@@1@12@@oe@26-8-2013
1000000102430@unknown@formal@none@1@S@(Valley News, p. 13).@@@@1@4@@oe@26-8-2013
1000000102440@unknown@formal@none@1@S@Davis (2000) observes the particular importance of the electromechanical relay (with its two "binary states" ⌊/open/⌋ and ⌊/closed/⌋):@@@@1@18@@oe@26-8-2013
1000000102450@unknown@formal@none@1@S@⌊⇥It was only with the development, beginning in the 1930s, of electromechanical calculators using electrical relays, that machines were built having the scope Babbage had envisioned."@@@@1@26@@oe@26-8-2013
1000000102460@unknown@formal@none@1@S@(Davis, p. 14).⇥⌋@@@@1@3@@oe@26-8-2013
1000000102470@unknown@formal@none@1@S@⌊=Mathematics during the 1800s up to the mid-1900s¦3=⌋@@@@1@8@@oe@26-8-2013
1000000102480@unknown@formal@none@1@S@⌊∗Symbols and rules∗⌋: In rapid succession the mathematics of ⌊>George Boole>⌋ (1847, 1854), ⌊>Gottlob Frege>⌋ (1879), and ⌊>Giuseppe Peano>⌋ (1888–1889) reduced arithmetic to a sequence of symbols manipulated by rules.@@@@1@30@@oe@26-8-2013
1000000102490@unknown@formal@none@1@S@Peano's ⌊/The principles of arithmetic, presented by a new method/⌋ (1888) was "the first attempt at an axiomatization of mathematics in a symbolic language" (van Heijenoort:81ff).@@@@1@26@@oe@26-8-2013
1000000102500@unknown@formal@none@1@S@But Heijenoort gives Frege (1879) this kudos: Frege’s is "perhaps the most important single work ever written in logic. ... in which we see a " 'formula language', that is a ⌊/lingua characterica/⌋, a language written with special symbols, "for pure thought", that is, free from rhetorical embellishments ... constructed from specific symbols that are manipulated according to definite rules" (van Heijenoort:1).@@@@1@62@@oe@26-8-2013
1000000102510@unknown@formal@none@1@S@The work of Frege was further simplified and amplified by ⌊>Alfred North Whitehead>⌋ and ⌊>Bertrand Russell>⌋ in their ⌊>Principia Mathematica>⌋ (1910–1913).@@@@1@21@@oe@26-8-2013
1000000102520@unknown@formal@none@1@S@⌊∗The paradoxes∗⌋: At the same time a number of disturbing paradoxes appeared in the literature, in particular the ⌊>Burali-Forti paradox>⌋ (1897), the ⌊>Russell paradox>⌋ (1902–03), and the ⌊>Richard Paradox>⌋ (Dixon 1906, cf Kleene 1952:36–40).@@@@1@34@@oe@26-8-2013
1000000102530@unknown@formal@none@1@S@The resultant considerations led to ⌊>Kurt Gödel>⌋’s paper (1931) — he specifically cites the paradox of the liar — that completely reduces rules of ⌊>recursion>⌋ to numbers.@@@@1@27@@oe@26-8-2013
1000000102540@unknown@formal@none@1@S@⌊∗Effective calculability∗⌋: In an effort to solve the ⌊>Entscheidungsproblem>⌋ defined precisely by Hilbert in 1928, mathematicians first set about to define what was meant by an "effective method" or "effective calculation" or "effective calculability" (i.e., a calculation that would succeed).@@@@1@40@@oe@26-8-2013
1000000102550@unknown@formal@none@1@S@In rapid succession the following appeared: ⌊>Alonzo Church>⌋, ⌊>Stephen Kleene>⌋ and ⌊>J.B. Rosser>⌋'s ⌊>λ-calculus>⌋, (cf footnote in ⌊>Alonzo Church>⌋ 1936a:90, 1936b:110) a finely-honed definition of "general recursion" from the work of Gödel acting on suggestions of ⌊>Jacques Herbrand>⌋ (cf Gödel's Princeton lectures of 1934) and subsequent simplifications by Kleene (1935-6:237ff, 1943:255ff). Church's proof (1936:88ff) that the ⌊>Entscheidungsproblem>⌋ was unsolvable, ⌊>Emil Post>⌋'s definition of effective calculability as a worker mindlessly following a list of instructions to move left or right through a sequence of rooms and while there either mark or erase a paper or observe the paper and make a yes-no decision about the next instruction (cf "Formulation I", Post 1936:289-290).@@@@1@111@@oe@26-8-2013
1000000102560@unknown@formal@none@1@S@⌊>Alan Turing>⌋'s proof of that the Entscheidungsproblem was unsolvable by use of his "a- [automatic-] machine"(Turing 1936-7:116ff) -- in effect almost identical to Post's "formulation", ⌊>J. Barkley Rosser>⌋'s definition of "effective method" in terms of "a machine" (Rosser 1939:226).@@@@1@39@@oe@26-8-2013
1000000102570@unknown@formal@none@1@S@⌊>S. C. Kleene>⌋'s proposal of a precursor to "⌊>Church thesis>⌋" that he called "Thesis I" (Kleene 1943:273–274), and a few years later Kleene's renaming his Thesis "Church's Thesis" (Kleene 1952:300, 317) and proposing "Turing's Thesis" (Kleene 1952:376).@@@@1@37@@oe@26-8-2013
1000000102580@unknown@formal@none@1@S@⌊=Emil Post (1936) and Alan Turing (1936-7, 1939)¦3=⌋@@@@1@8@@oe@26-8-2013
1000000102590@unknown@formal@none@1@S@Here is a remarkable coincidence of two men not knowing each other but describing a process of men-as-computers working on computations — and they yield virtually identical definitions.@@@@1@28@@oe@26-8-2013
1000000102600@unknown@formal@none@1@S@⌊>Emil Post>⌋ (1936) described the actions of a "computer" (human being) as follows:@@@@1@13@@oe@26-8-2013
1000000102610@unknown@formal@none@1@S@⌊⇥"...two concepts are involved: that of a ⌊/symbol space/⌋ in which the work leading from problem to answer is to be carried out, and a fixed unalterable ⌊/set of directions/⌋.⇥⌋@@@@1@30@@oe@26-8-2013
1000000102620@unknown@formal@none@1@S@His symbol space would be@@@@1@5@@oe@26-8-2013
1000000102630@unknown@formal@none@1@S@⌊⇥"a two way infinite sequence of spaces or boxes...@@@@1@9@@oe@26-8-2013
1000000102640@unknown@formal@none@1@S@The problem solver or worker is to move and work in this symbol space, being capable of being in, and operating in but one box at a time.... a box is to admit of but two possible conditions, i.e., being empty or unmarked, and having a single mark in it, say a vertical stroke.⇥⌋@@@@1@54@@oe@26-8-2013
1000000102650@unknown@formal@none@1@S@⌊⇥"One box is to be singled out and called the starting point. ...a specific problem is to be given in symbolic form by a finite number of boxes [i.e., INPUT] being marked with a stroke.@@@@1@35@@oe@26-8-2013
1000000102660@unknown@formal@none@1@S@Likewise the answer [i.e., OUTPUT] is to be given in symbolic form by such a configuration of marked boxes....⇥⌋@@@@1@19@@oe@26-8-2013
1000000102670@unknown@formal@none@1@S@⌊⇥"A set of directions applicable to a general problem sets up a deterministic process when applied to each specific problem.@@@@1@20@@oe@26-8-2013
1000000102680@unknown@formal@none@1@S@This process will terminate only when it comes to the direction of type (C ) [i.e., STOP]." (U p. 289–290)@@@@1@20@@oe@26-8-2013
1000000102690@unknown@formal@none@1@S@See more at ⌊>Post-Turing machine>⌋⇥⌋@@@@1@5@@oe@26-8-2013
1000000102700@unknown@formal@none@1@S@⌊>Alan Turing>⌋’s work (1936, 1939:160) preceded that of Stibitz (1937); it is unknown whether Stibitz knew of the work of Turing.@@@@1@21@@oe@26-8-2013
1000000102710@unknown@formal@none@1@S@Turing’s biographer believed that Turing’s use of a typewriter-like model derived from a youthful interest: “Alan had dreamt of inventing typewriters as a boy; Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges, p. 96).@@@@1@49@@oe@26-8-2013
1000000102720@unknown@formal@none@1@S@Given the prevalence of Morse code and telegraphy, ticker tape machines, and Teletypes we might conjecture that all were influences.@@@@1@20@@oe@26-8-2013
1000000102730@unknown@formal@none@1@S@Turing — his model of computation is now called a ⌊>Turing machine>⌋ — begins, as did Post, with an analysis of a human computer that he whittles down to a simple set of basic motions and "states of mind".@@@@1@39@@oe@26-8-2013
1000000102740@unknown@formal@none@1@S@But he continues a step further and creates a machine as a model of computation of numbers (Turing 1936-7:116).@@@@1@19@@oe@26-8-2013
1000000102750@unknown@formal@none@1@S@⌊⇥"Computing is normally done by writing certain symbols on paper.@@@@1@10@@oe@26-8-2013
1000000102760@unknown@formal@none@1@S@We may suppose this paper is divided into squares like a child's arithmetic book....I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares.@@@@1@32@@oe@26-8-2013
1000000102770@unknown@formal@none@1@S@I shall also suppose that the number of symbols which may be printed is finite....⇥⌋@@@@1@15@@oe@26-8-2013
1000000102780@unknown@formal@none@1@S@⌊⇥"The behavior of the computer at any moment is determined by the symbols which he is observing, and his "state of mind" at that moment.@@@@1@25@@oe@26-8-2013
1000000102790@unknown@formal@none@1@S@We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment.@@@@1@24@@oe@26-8-2013
1000000102800@unknown@formal@none@1@S@If he wishes to observe more, he must use successive observations.@@@@1@11@@oe@26-8-2013
1000000102810@unknown@formal@none@1@S@We will also suppose that the number of states of mind which need be taken into account is finite...⇥⌋@@@@1@19@@oe@26-8-2013
1000000102820@unknown@formal@none@1@S@⌊⇥"Let us imagine that the operations performed by the computer to be split up into 'simple operations' which are so elementary that it is not easy to imagine them further divided" (Turing 1936-7:136).⇥⌋@@@@1@33@@oe@26-8-2013
1000000102830@unknown@formal@none@1@S@Turing's reduction yields the following:@@@@1@5@@oe@26-8-2013
1000000102840@unknown@formal@none@1@S@⌊⇥"The simple operations must therefore include:@@@@1@6@@oe@26-8-2013
1000000102850@unknown@formal@none@1@S@⌊⇥"(a) Changes of the symbol on one of the observed squares⇥⌋@@@@1@11@@oe@26-8-2013
1000000102860@unknown@formal@none@1@S@⌊⇥"(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.⇥⌋⇥⌋@@@@1@21@@oe@26-8-2013
1000000102870@unknown@formal@none@1@S@"It may be that some of these change necessarily invoke a change of state of mind.@@@@1@16@@oe@26-8-2013
1000000102880@unknown@formal@none@1@S@The most general single operation must therefore be taken to be one of the following:@@@@1@15@@oe@26-8-2013
1000000102890@unknown@formal@none@1@S@⌊⇥⌊⇥"(A) A possible change (a) of symbol together with a possible change of state of mind.⇥⌋@@@@1@16@@oe@26-8-2013
1000000102900@unknown@formal@none@1@S@⌊⇥"(B) A possible change (b) of observed squares, together with a possible change of state of mind"⇥⌋⇥⌋@@@@1@17@@oe@26-8-2013
1000000102910@unknown@formal@none@1@S@⌊⇥"We may now construct a machine to do the work of this computer."@@@@1@13@@oe@26-8-2013
1000000102920@unknown@formal@none@1@S@(Turing 1936-7:136)⇥⌋@@@@1@2@@oe@26-8-2013
1000000102930@unknown@formal@none@1@S@A few years later, Turing expanded his analysis (thesis, definition) with this forceful expression of it:@@@@1@16@@oe@26-8-2013
1000000102940@unknown@formal@none@1@S@⌊⇥"A function is said to be "effectively calculable" if its values can be found by some purely mechanical process.@@@@1@19@@oe@26-8-2013
1000000102950@unknown@formal@none@1@S@Although it is fairly easy to get an intuitive grasp of this idea, it is neverthessless desirable to have some more definite, mathematical expressible definition . . . [he discusses the history of the definition pretty much as presented above with respect to Gödel, Herbrand, Kleene, Church, Turing and Post] . . .@@@@1@53@@oe@26-8-2013
1000000102960@unknown@formal@none@1@S@We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine.@@@@1@21@@oe@26-8-2013
1000000102970@unknown@formal@none@1@S@It is possible to give a mathematical description, in a certain normal form, of the structures of these machines.@@@@1@19@@oe@26-8-2013
1000000102980@unknown@formal@none@1@S@The development of these ideas leads to the author's definition of a computable function, and to an identification of computability † with effective calculability . . . .@@@@1@28@@oe@26-8-2013
1000000102990@unknown@formal@none@1@S@⌊⇥"† We shall use the expression "computable function" to mean a function calculable by a machine, and we let "effectively calculabile" refer to the intuitive idea without particular identification with any one of these definitions."(Turing 1939:160)⇥⌋⇥⌋@@@@1@36@@oe@26-8-2013
1000000103000@unknown@formal@none@1@S@⌊=J. B. Rosser (1939) and S. C. Kleene (1943)¦3=⌋@@@@1@9@@oe@26-8-2013
1000000103010@unknown@formal@none@1@S@⌊∗⌊>J. Barkley Rosser>⌋∗⌋ boldly defined an ‘effective [mathematical] method’ in the following manner (boldface added):@@@@1@15@@oe@26-8-2013
1000000103020@unknown@formal@none@1@S@⌊⇥"'Effective method' is used here in the rather special sense of a method each step of which is precisely determined and which is certain to produce the answer in a finite number of steps.@@@@1@34@@oe@26-8-2013
1000000103030@unknown@formal@none@1@S@With this special meaning, three different precise definitions have been given to date. [his footnote #5; see discussion immediately below].@@@@1@20@@oe@26-8-2013
1000000103040@unknown@formal@none@1@S@The simplest of these to state (due to Post and Turing) says essentially that ⌊∗an effective method of solving certain sets of problems exists if one can build a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer∗⌋.@@@@1@52@@oe@26-8-2013
1000000103050@unknown@formal@none@1@S@All three definitions are equivalent, so it doesn't matter which one is used.@@@@1@13@@oe@26-8-2013
1000000103060@unknown@formal@none@1@S@Moreover, the fact that all three are equivalent is a very strong argument for the correctness of any one."@@@@1@19@@oe@26-8-2013
1000000103070@unknown@formal@none@1@S@(Rosser 1939:225–6)⇥⌋@@@@1@2@@oe@26-8-2013
1000000103080@unknown@formal@none@1@S@Rosser's footnote #5 references the work of (1) Church and Kleene and their definition of λ-definability, in particular Church's use of it in his ⌊/An Unsolvable Problem of Elementary Number Theory/⌋ (1936); (2) Herbrand and Gödel and their use of recursion in particular Gödel's use in his famous paper ⌊/On Formally Undecidable Propositions of Principia Mathematica and Related Systems I/⌋ (1931); and (3) Post (1936) and Turing (1936-7) in their mechanism-models of computation.@@@@1@73@@oe@26-8-2013
1000000103090@unknown@formal@none@1@S@⌊∗⌊>Stephen C. Kleene>⌋∗⌋ defined as his now-famous "Thesis I" known as the ⌊>Church-Turing thesis>⌋.@@@@1@14@@oe@26-8-2013
1000000103100@unknown@formal@none@1@S@But he did this in the following context (boldface in original):@@@@1@11@@oe@26-8-2013
1000000103110@unknown@formal@none@1@S@⌊⇥"12.@@@@1@1@@oe@26-8-2013
1000000103120@unknown@formal@none@1@S@⌊∗Algorithmic theories∗⌋...@@@@1@2@@oe@26-8-2013
1000000103130@unknown@formal@none@1@S@In setting up a complete algorithmic theory, what we do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, "yes" or "no," to the question, "is the predicate value true?”"@@@@1@54@@oe@26-8-2013
1000000103140@unknown@formal@none@1@S@(Kleene 1943:273)⇥⌋@@@@1@2@@oe@26-8-2013
1000000103150@unknown@formal@none@1@S@⌊=History after 1950¦3=⌋@@@@1@3@@oe@26-8-2013
1000000103160@unknown@formal@none@1@S@A number of efforts have been directed toward further refinement of the definition of "algorithm", and activity is on-going because of issues surrounding, in particular, ⌊>foundations of mathematics>⌋ (especially the ⌊>Church-Turing Thesis>⌋) and ⌊>philosophy of mind>⌋ (especially arguments around ⌊>artificial intelligence>⌋).@@@@1@41@@oe@26-8-2013
1000000103170@unknown@formal@none@1@S@For more, see ⌊>Algorithm characterizations>⌋.@@@@1@5@@oe@26-8-2013
1000000200010@unknown@formal@none@1@S@⌊δAmbiguityδ⌋@@@@1@1@@oe@26-8-2013
1000000200020@unknown@formal@none@1@S@⌊∗Ambiguity∗⌋ is the property of being ⌊∗ambiguous∗⌋, where a ⌊>word>⌋, term, notation, sign, ⌊>symbol>⌋, ⌊>phrase>⌋, ⌊>sentence>⌋, or any other form used for ⌊>communication>⌋, is called ambiguous if it can be interpreted in more than one way.@@@@1@36@@oe@26-8-2013
1000000200030@unknown@formal@none@1@S@Ambiguity is distinct from ⌊/⌊>vagueness>⌋/⌋, which arises when the boundaries of meaning are indistinct.@@@@1@14@@oe@26-8-2013
1000000200040@unknown@formal@none@1@S@Ambiguity is context-dependent: the same communication may be ambiguous in one context and unambiguous in another context.@@@@1@17@@oe@26-8-2013
1000000200050@unknown@formal@none@1@S@For a word, ambiguity typically refers to an unclear choice between different definitions as may be found in a ⌊>dictionary>⌋.@@@@1@20@@oe@26-8-2013
1000000200060@unknown@formal@none@1@S@A sentence may be ambiguous due to different ways of ⌊>parsing>⌋ the same sequence of words.@@@@1@16@@oe@26-8-2013
1000000200070@unknown@formal@none@1@S@⌊=Linguistic forms¦2=⌋@@@@1@2@@oe@26-8-2013
1000000200080@unknown@formal@none@1@S@⌊∗⌊>Lexical ambiguity>⌋∗⌋ arises when ⌊>context>⌋ is insufficient to determine the sense of a single word that has more than one meaning.@@@@1@21@@oe@26-8-2013
1000000200090@unknown@formal@none@1@S@For example, the word “bank” has several distinct definitions, including “financial institution” and “edge of a river,” but if someone says “I deposited $100 in the bank,” most people would not think you used a shovel to dig in the mud.@@@@1@41@@oe@26-8-2013
1000000200100@unknown@formal@none@1@S@The word "run" has 130 ambiguous definitions in some ⌊>lexicon>⌋s.@@@@1@10@@oe@26-8-2013
1000000200110@unknown@formal@none@1@S@"Biweekly" can mean "fortnightly" (once every two weeks - 26 times a year), OR "twice a week" (104 times a year).@@@@1@21@@oe@26-8-2013
1000000200120@unknown@formal@none@1@S@Stating a specific context like "meeting schedule" does NOT disambiguate "biweekly."@@@@1@11@@oe@26-8-2013
1000000200130@unknown@formal@none@1@S@Many people believe that such lexically-ambiguous, miscommunication-prone words should be avoided altogether, since the user generally has to waste time, effort, and ⌊>attention span>⌋ to define what is meant when they are used.@@@@1@33@@oe@26-8-2013
1000000200140@unknown@formal@none@1@S@The use of multi-defined words requires the author or speaker to clarify their context, and sometimes elaborate on their specific intended meaning (in which case, a less ambiguous term should have been used).@@@@1@33@@oe@26-8-2013
1000000200150@unknown@formal@none@1@S@The goal of clear concise communication is that the receiver(s) have no misunderstanding about what was meant to be conveyed.@@@@1@20@@oe@26-8-2013
1000000200160@unknown@formal@none@1@S@An exception to this could include a politician whose "wiggle words" and ⌊>obfuscation>⌋ are necessary to gain support from multiple ⌊>constituent (politics)>⌋ with ⌊>mutually exclusive>⌋ conflicting desires from their candidate of choice.@@@@1@32@@oe@26-8-2013
1000000200170@unknown@formal@none@1@S@Ambiguity is a powerful tool of ⌊>political science>⌋.@@@@1@8@@oe@26-8-2013
1000000200180@unknown@formal@none@1@S@More problematic are words whose senses express closely-related concepts.@@@@1@9@@oe@26-8-2013
1000000200190@unknown@formal@none@1@S@“Good,” for example, can mean “useful” or “functional” (⌊/That’s a good hammer/⌋), “exemplary” (⌊/She’s a good student/⌋), “pleasing” (⌊/This is good soup/⌋), “moral” (⌊/a good person/⌋ versus ⌊/the lesson to be learned from a story/⌋), "⌊>righteous>⌋", etc.@@@@1@37@@oe@26-8-2013
1000000200200@unknown@formal@none@1@S@“I have a good daughter” is not clear about which sense is intended.@@@@1@13@@oe@26-8-2013
1000000200210@unknown@formal@none@1@S@The various ways to apply ⌊>prefix>⌋es and ⌊>suffix>⌋es can also create ambiguity (“unlockable” can mean “capable of being unlocked” or “impossible to lock”, and therefore should not be used).@@@@1@29@@oe@26-8-2013
1000000200220@unknown@formal@none@1@S@⌊∗⌊>Syntactic ambiguity>⌋∗⌋ arises when a sentence can be ⌊>parsed>⌋ in more than one way.@@@@1@14@@oe@26-8-2013
1000000200230@unknown@formal@none@1@S@“He ate the cookies on the couch,” for example, could mean that he ate those cookies which were on the couch (as opposed to those that were on the table), or it could mean that he was sitting on the couch when he ate the cookies.@@@@1@46@@oe@26-8-2013
1000000200240@unknown@formal@none@1@S@⌊>Spoken language>⌋ can contain many more types of ambiguities, where there is more than one way to compose a set of sounds into words, for example “ice cream” and “I scream.”@@@@1@31@@oe@26-8-2013
1000000200250@unknown@formal@none@1@S@Such ambiguity is generally resolved based on the context.@@@@1@9@@oe@26-8-2013
1000000200260@unknown@formal@none@1@S@A mishearing of such, based on incorrectly-resolved ambiguity, is called a ⌊>mondegreen>⌋.@@@@1@12@@oe@26-8-2013
1000000200270@unknown@formal@none@1@S@⌊∗⌊>Semantic ambiguity>⌋∗⌋ arises when a word or concept has an inherently diffuse meaning based on widespread or informal usage.@@@@1@19@@oe@26-8-2013
1000000200280@unknown@formal@none@1@S@This is often the case, for example, with idiomatic expressions whose definitions are rarely or never well-defined, and are presented in the context of a larger argument that invites a conclusion.@@@@1@31@@oe@26-8-2013
1000000200290@unknown@formal@none@1@S@For example, “You could do with a new automobile.@@@@1@9@@oe@26-8-2013
1000000200300@unknown@formal@none@1@S@How about a test drive?”@@@@1@5@@oe@26-8-2013
1000000200310@unknown@formal@none@1@S@The clause “You could do with” presents a statement with such wide possible interpretation as to be essentially meaningless.@@@@1@19@@oe@26-8-2013
1000000200320@unknown@formal@none@1@S@Lexical ambiguity is contrasted with semantic ambiguity.@@@@1@7@@oe@26-8-2013
1000000200330@unknown@formal@none@1@S@The former represents a choice between a finite number of known and meaningful context-dependent interpretations.@@@@1@15@@oe@26-8-2013
1000000200340@unknown@formal@none@1@S@The latter represents a choice between any number of possible interpretations, none of which may have a standard agreed-upon meaning.@@@@1@20@@oe@26-8-2013
1000000200350@unknown@formal@none@1@S@This form of ambiguity is closely related to ⌊>vagueness>⌋.@@@@1@9@@oe@26-8-2013
1000000200360@unknown@formal@none@1@S@Linguistic ambiguity can be a problem in law (see ⌊>Ambiguity (law)>⌋), because the interpretation of written documents and oral agreements is often of paramount importance.@@@@1@25@@oe@26-8-2013
1000000200370@unknown@formal@none@1@S@⌊=Intentional application¦2=⌋@@@@1@2@@oe@26-8-2013
1000000200380@unknown@formal@none@1@S@⌊>Philosopher>⌋s (and other users of ⌊>logic>⌋) spend a lot of time and effort searching for and removing (or intentionally adding) ambiguity in arguments, because it can lead to incorrect conclusions and can be used to deliberately conceal bad arguments.@@@@1@39@@oe@26-8-2013
1000000200390@unknown@formal@none@1@S@For example, a politician might say “I oppose taxes that hinder economic growth.”@@@@1@13@@oe@26-8-2013
1000000200400@unknown@formal@none@1@S@Some will think he opposes taxes in general, because they hinder economic growth.@@@@1@13@@oe@26-8-2013
1000000200410@unknown@formal@none@1@S@Others may think he opposes only those taxes that he believes will hinder economic growth (although in writing, the correct insertion or omission of a ⌊>comma>⌋ after “taxes” and the use of "which" can help reduce ambiguity here.@@@@1@38@@oe@26-8-2013
1000000200420@unknown@formal@none@1@S@For the first meaning, “, which” is properly used in place of “that”), or restructure the sentence to completely eliminate possible misinterpretation.@@@@1@22@@oe@26-8-2013
1000000200430@unknown@formal@none@1@S@The devious politician hopes that each ⌊>constituent (politics)>⌋ will interpret the above statement in the most desirable way, and think the politician supports everyone's opinion.@@@@1@25@@oe@26-8-2013
1000000200440@unknown@formal@none@1@S@However, the opposite can also be true - An opponent can turn a positive statement into a bad one, if the speaker uses ambiguity (intentionally or not).@@@@1@27@@oe@26-8-2013
1000000200450@unknown@formal@none@1@S@The logical fallacies of ⌊>amphiboly>⌋ and ⌊>equivocation>⌋ rely heavily on the use of ambiguous words and phrases.@@@@1@17@@oe@26-8-2013
1000000200460@unknown@formal@none@1@S@In ⌊>literature>⌋ and ⌊>rhetoric>⌋, on the other hand, ambiguity can be a useful tool.@@@@1@14@@oe@26-8-2013
1000000200470@unknown@formal@none@1@S@⌊>Groucho Marx>⌋’s classic joke depends on a grammatical ambiguity for its ⌊>humor>⌋, for example: “Last night I shot an elephant in my pajamas.@@@@1@23@@oe@26-8-2013
1000000200480@unknown@formal@none@1@S@What he was doing in my pajamas I’ll never know.”@@@@1@10@@oe@26-8-2013
1000000200490@unknown@formal@none@1@S@Ambiguity can also be used as a comic device through a genuine intention to confuse, as does Magic: The Gathering's Unhinged © Ambiguity, which makes puns with ⌊>homophone>⌋s, mispunctuation, and run-ons: “Whenever a player plays a spell that counters a spell that has been played[,] or a player plays a spell that comes into play with counters, that player may counter the next spell played[,] or put an additional counter on a permanent that has already been played, but not countered.”@@@@1@81@@oe@26-8-2013
1000000200500@unknown@formal@none@1@S@Songs and poetry often rely on ambiguous words for artistic effect, as in the song title “Don’t It Make My Brown Eyes Blue” (where “blue” can refer to the color, or to ⌊>sadness>⌋).@@@@1@33@@oe@26-8-2013
1000000200510@unknown@formal@none@1@S@In narrative, ambiguity can be introduced in several ways: motive, plot, character.@@@@1@12@@oe@26-8-2013
1000000200520@unknown@formal@none@1@S@⌊>F. Scott Fitzgerald>⌋ uses the latter type of ambiguity with notable effect in his novel ⌊/⌊>The Great Gatsby>⌋/⌋.@@@@1@18@@oe@26-8-2013
1000000200530@unknown@formal@none@1@S@All ⌊>religions>⌋ debate the ⌊>orthodoxy>⌋ or ⌊>heterodoxy>⌋ of ambiguity.@@@@1@9@@oe@26-8-2013
1000000200540@unknown@formal@none@1@S@⌊>Christianity>⌋ and ⌊>Judaism>⌋ employ the concept of ⌊>paradox>⌋ synonymously with 'ambiguity'.@@@@1@11@@oe@26-8-2013
1000000200550@unknown@formal@none@1@S@Ambiguity within Christianity (and other religions) is resisted by the conservatives and fundamentalists, who regard the concept as equating with 'contradiction'.@@@@1@21@@oe@26-8-2013
1000000200560@unknown@formal@none@1@S@Non-fundamentalist Christians and Jews endorse ⌊>Rudolf Otto>⌋'s description of the sacred as 'mysterium tremendum et fascinans', the awe-inspiring mystery which fascinates humans.@@@@1@22@@oe@26-8-2013
1000000200570@unknown@formal@none@1@S@⌊>Metonymy>⌋ involves the use of the name of a subcomponent part as an abbreviation, or ⌊>jargon>⌋, for the name of the whole object (for example "wheels" to refer to a car, or "flowers" to refer to beautiful offspring, an entire plant, or a collection of blooming plants).@@@@1@47@@oe@26-8-2013
1000000200580@unknown@formal@none@1@S@In modern ⌊>vocabulary>⌋ critical ⌊>semiotics>⌋, metonymy encompasses any potentially-ambiguous word substitution that is based on contextual ⌊>contiguity>⌋ (located close together), or a function or process that an object performs, such as "sweet ride" to refer to a nice car.@@@@1@39@@oe@26-8-2013
1000000200590@unknown@formal@none@1@S@Metonym miscommunication is considered a primary mechanism of linguistic humour.@@@@1@10@@oe@26-8-2013
1000000200600@unknown@formal@none@1@S@⌊=Psychology and management¦2=⌋@@@@1@3@@oe@26-8-2013
1000000200610@unknown@formal@none@1@S@In sociology and social psychology, the term "ambiguity" is used to indicate situations that involve ⌊>uncertainty>⌋.@@@@1@16@@oe@26-8-2013
1000000200620@unknown@formal@none@1@S@An increasing amount of research is concentrating on how people react and respond to ambiguous situations.@@@@1@16@@oe@26-8-2013
1000000200630@unknown@formal@none@1@S@Much of this focuses on ⌊>ambiguity tolerance>⌋.@@@@1@7@@oe@26-8-2013
1000000200640@unknown@formal@none@1@S@A number of correlations have been found between an individual’s reaction and tolerance to ambiguity and a range of factors.@@@@1@20@@oe@26-8-2013
1000000200650@unknown@formal@none@1@S@Apter and Desselles (2001) for example, found a strong correlation with such attributes and factors like a greater preference for safe as opposed to risk based sports, a preference for endurance type activities as opposed to explosive activities, a more organized and less casual lifestyle, greater care and precision in descriptions, a lower sensitivity to emotional and unpleasant words, a less acute sense of humour, engaging a smaller variety of sexual practices than their more risk comfortable colleagues, a lower likelihood of the use of drugs, pornography and drink, a greater likelihood of displaying obsessional behaviour.@@@@1@96@@oe@26-8-2013
1000000200660@unknown@formal@none@1@S@In the field of ⌊>leadership>⌋ ⌊>David Wilkinson>⌋ (2006) found strong correlations between an individual leaders reaction to ambiguous situations and the ⌊>Modes of Leadership>⌋ they use, the type of ⌊>creativity>⌋ (Kirton (2003) and how they relate to others.@@@@1@38@@oe@26-8-2013
1000000200670@unknown@formal@none@1@S@⌊=Music¦2=⌋@@@@1@1@@oe@26-8-2013
1000000200680@unknown@formal@none@1@S@In ⌊>music>⌋, pieces or sections which confound expectations and may be or are interpreted simultaneously in different ways are ambiguous, such as some ⌊>polytonality>⌋, ⌊>polymeter>⌋, other ambiguous ⌊>meters>⌋ or ⌊>rhythm>⌋s, and ambiguous ⌊>phrasing>⌋, or (Stein 2005, p.79) any ⌊>aspect of music>⌋.@@@@1@41@@oe@26-8-2013
1000000200690@unknown@formal@none@1@S@The ⌊>music of Africa>⌋ is often purposely ambiguous.@@@@1@8@@oe@26-8-2013
1000000200700@unknown@formal@none@1@S@To quote ⌊>Sir Donald Francis Tovey>⌋ (1935, p.195), “Theorists are apt to vex themselves with vain efforts to remove uncertainty just where it has a high aesthetic value.”@@@@1@28@@oe@26-8-2013
1000000200710@unknown@formal@none@1@S@⌊=Constructed language¦2=⌋@@@@1@2@@oe@26-8-2013
1000000200720@unknown@formal@none@1@S@Some ⌊>languages have been created>⌋ with the intention of avoiding ambiguity, especially lexical ambiguity.@@@@1@14@@oe@26-8-2013
1000000200730@unknown@formal@none@1@S@⌊>Lojban>⌋ and ⌊>Loglan>⌋ are two related languages which have been created with this in mind.@@@@1@15@@oe@26-8-2013
1000000200740@unknown@formal@none@1@S@The languages can be both spoken and written.@@@@1@8@@oe@26-8-2013
1000000200750@unknown@formal@none@1@S@These languages are intended to provide a greater technical precision over natural languages, although historically, such attempts at language improvement have been criticized.@@@@1@23@@oe@26-8-2013
1000000200760@unknown@formal@none@1@S@Languages composed from many diverse sources contain much ambiguity and inconsistency.@@@@1@11@@oe@26-8-2013
1000000200770@unknown@formal@none@1@S@The many exceptions to ⌊>syntax>⌋ and ⌊>semantic>⌋ rules are time-consuming and difficult to learn.@@@@1@14@@oe@26-8-2013
1000000200780@unknown@formal@none@1@S@⌊=Mathematics and physics¦2=⌋@@@@1@3@@oe@26-8-2013
1000000200790@unknown@formal@none@1@S@⌊>Mathematical notation>⌋, widely used in ⌊>physics>⌋ and other ⌊>science>⌋s, avoids many ambiguities compared to expression in natural language.@@@@1@18@@oe@26-8-2013
1000000200800@unknown@formal@none@1@S@However, for various reasons, several ⌊>lexical>⌋, ⌊>syntactic>⌋ and ⌊>semantic>⌋ ambiguities remain.@@@@1@11@@oe@26-8-2013
1000000200810@unknown@formal@none@1@S@⌊=Names of functions¦3=⌋@@@@1@3@@oe@26-8-2013
1000000200820@unknown@formal@none@1@S@The ⌊∗ambiguity∗⌋ in the style of writing a function should not be confused with a ⌊>multivalued function>⌋, which can (and should) be defined in a deterministic and unambiguous way.@@@@1@29@@oe@26-8-2013
1000000200830@unknown@formal@none@1@S@Several ⌊>special function>⌋s still do not have established notations.@@@@1@9@@oe@26-8-2013
1000000200840@unknown@formal@none@1@S@Usually, the conversion to another notation requires to scale the argument and/or the resulting value; sometimes, the same name of the function is used, causing confusions.@@@@1@26@@oe@26-8-2013
1000000200850@unknown@formal@none@1@S@Examples of such underestablished functions:@@@@1@5@@oe@26-8-2013
1000000200860@unknown@formal@none@1@S@⌊•⌊#⌊>Sinc function>⌋#⌋@@@@1@2@@oe@26-8-2013
1000000200870@unknown@formal@none@1@S@⌊#⌊>Elliptic integral of the Third Kind>⌋; translating elliptic integral form ⌊>MAPLE>⌋ to ⌊>Mathematica>⌋, one should replace the second argument to its square, see ⌊>Talk:Elliptic integral#List_of_notations>⌋; dealing with complex values, this may cause problems.#⌋@@@@1@33@@oe@26-8-2013
1000000200880@unknown@formal@none@1@S@⌊#⌊>Exponential integral>⌋, , page 228 ⌊>http://www.math.sfu.ca/~cbm/aands/page_228.htm>⌋#⌋@@@@1@6@@oe@26-8-2013
1000000200890@unknown@formal@none@1@S@⌊#⌊>Hermite polynomial>⌋, , page 775 ⌊>http://www.math.sfu.ca/~cbm/aands/page_775.htm>⌋#⌋•⌋@@@@1@6@@oe@26-8-2013
1000000200900@unknown@formal@none@1@S@⌊=Expressions¦3=⌋@@@@1@1@@oe@26-8-2013
1000000200910@unknown@formal@none@1@S@Ambiguous espressions often appear in physical and mathematical texts.@@@@1@9@@oe@26-8-2013
1000000200920@unknown@formal@none@1@S@It is common practice to omit multiplication signs in mathematical expressions.@@@@1@11@@oe@26-8-2013
1000000200930@unknown@formal@none@1@S@Also, it is common, to give the same name to a variable and a function, for example, ⌊×~f=f(x)~×⌋.@@@@1@18@@oe@26-8-2013
1000000200940@unknown@formal@none@1@S@Then, if one sees ⌊×~g=f(y+1)~×⌋, there is no way to distinguish, does it mean ⌊×~f=f(x)~×⌋ ⌊∗multiplied∗⌋ by ⌊×~(y+1)~×⌋, or function ⌊×~f~×⌋ ⌊∗evaluated∗⌋ at argument equal to ⌊×~(y+1)~×⌋.@@@@1@27@@oe@26-8-2013
1000000200950@unknown@formal@none@1@S@In each case of use of such notations, the reader is supposed to be able to perform the deduction and reveal the true meaning.@@@@1@24@@oe@26-8-2013
1000000200960@unknown@formal@none@1@S@Creators of algorithmic languages try to avoid ambiguities.@@@@1@8@@oe@26-8-2013
1000000200970@unknown@formal@none@1@S@Many algorithmic languages (⌊>C++>⌋, ⌊>MATLAB>⌋, ⌊>Fortran>⌋, ⌊>Maple>⌋) require the character * as symbol of multiplication.@@@@1@15@@oe@26-8-2013
1000000200980@unknown@formal@none@1@S@The language ⌊>Mathematica>⌋ allows the user to omit the multiplication symbol, but requires square brackets to indicate the argument of a function; square brackets are not allowed for grouping of expressions.@@@@1@31@@oe@26-8-2013
1000000200990@unknown@formal@none@1@S@Fortran, in addition, does not allow use of the same name (identifier) for different objects, for example, function and variable; in particular, the expression ⌊∗f=f(x)∗⌋ is qualified as an error.@@@@1@30@@oe@26-8-2013
1000000201000@unknown@formal@none@1@S@The order of operations may depend on the context.@@@@1@9@@oe@26-8-2013
1000000201010@unknown@formal@none@1@S@In most ⌊>programming language>⌋s, the operations of division and multiplication have equal priority and are executed from left to right.@@@@1@20@@oe@26-8-2013
1000000201020@unknown@formal@none@1@S@Until the last century, many editorials assumed that multiplication is performed first, for example, ⌊×~a/bc~×⌋ is interpreted as ⌊×~a/(bc)~×⌋; in this case, the insertion of parentheses is required when translating the formulas to an algorithmic language.@@@@1@36@@oe@26-8-2013
1000000201030@unknown@formal@none@1@S@In addition, it is common to write an argument of a function without parenthesis, which also may lead to ambiguity.@@@@1@20@@oe@26-8-2013
1000000201040@unknown@formal@none@1@S@Sometimes, one uses ⌊/italics/⌋ letters to denote elementary functions.@@@@1@9@@oe@26-8-2013
1000000201050@unknown@formal@none@1@S@In the ⌊>scientific journal>⌋ style, the expression ⌊×~ s i n \\alpha~×⌋ means product of variables ⌊×~s~×⌋, ⌊×~i~×⌋, ⌊×~n~×⌋ and ⌊×~\\alpha~×⌋, although in a slideshow, it may mean ⌊×~\\sin[\\alpha]~×⌋.@@@@1@29@@oe@26-8-2013
1000000201060@unknown@formal@none@1@S@Comma in subscripts and superscripts sometimes is omitted; it is also ambiguous notation.@@@@1@13@@oe@26-8-2013
1000000201070@unknown@formal@none@1@S@If it is written ⌊×~T_{mnk}~×⌋, the reader should guess from the context, does it mean a single-index object, evaluated while the subscript is equal to product of variables ⌊×~m~×⌋, ⌊×~n~×⌋ and ⌊×~k~×⌋, or it is indication to a three-valent tensor.@@@@1@40@@oe@26-8-2013
1000000201080@unknown@formal@none@1@S@The writing of ⌊×~T_{mnk}~×⌋ instead of ⌊×~T_{m,n,k}~×⌋ may mean that the writer either is stretched in space (for example, to reduce the publication fees, or aims to increase number of publications without considering readers.@@@@1@34@@oe@26-8-2013
1000000201090@unknown@formal@none@1@S@The same may apply to any other use of ambiguous notations.@@@@1@11@@oe@26-8-2013
1000000201100@unknown@formal@none@1@S@⌊=Examples of potentially confusing ambiguous mathematical expressions¦3=⌋@@@@1@7@@oe@26-8-2013
1000000201110@unknown@formal@none@1@S@⌊×\\sin^2\\alpha/2\\,×⌋, which could be understood to mean either ⌊×(\\sin(\\alpha/2))^2\\,×⌋ or ⌊×(\\sin(\\alpha))^2/2\\,×⌋.@@@@1@11@@oe@26-8-2013
1000000201120@unknown@formal@none@1@S@⌊×~\\sin^{-1} \\alpha×⌋, which by convention means ⌊×~\\arcsin(\\alpha) ~×⌋, though it might be thought to mean ⌊×(\\sin(\\alpha))^{-1}\\,×⌋ since ⌊×~\\sin^{n} \\alpha×⌋ means ⌊×(\\sin(\\alpha))^{n}\\,×⌋.@@@@1@21@@oe@26-8-2013
1000000201130@unknown@formal@none@1@S@⌊×a/2b\\,×⌋, which arguably should mean ⌊×(a/2)b\\,×⌋ but would commonly be understood to mean ⌊×a/(2b)\\,×⌋@@@@1@14@@oe@26-8-2013
1000000201140@unknown@formal@none@1@S@⌊=Notations in ⌊>quantum optics>⌋ and ⌊>quantum mechanics>⌋¦3=⌋@@@@1@7@@oe@26-8-2013
1000000201150@unknown@formal@none@1@S@It is common to define the ⌊>coherent states>⌋ in ⌊>quantum optics>⌋ with ⌊×~|\\alpha\\rangle~ ×⌋ and states with fixed number of photons with ⌊×~|n\\rangle~×⌋.@@@@1@23@@oe@26-8-2013
1000000201160@unknown@formal@none@1@S@Then, there is an "unwritten rule": the state is coherent if there are more Greek characters than Latin characters in the argument, and ⌊×~n~×⌋photon state if the Latin characters dominate.@@@@1@30@@oe@26-8-2013
1000000201170@unknown@formal@none@1@S@The ambiguity becomes even worse, if ⌊×~|x\\rangle~×⌋ is used for the states with certain value of the coordinate, and ⌊×~|p\\rangle~×⌋ means the state with certain value of the momentum, which may be used in books on ⌊>quantum mechanics>⌋.@@@@1@38@@oe@26-8-2013
1000000201180@unknown@formal@none@1@S@Such ambiguities easy lead to confusions, especially if some normalized ⌊>adimensional>⌋, ⌊>dimensionless>⌋ variables are used.@@@@1@15@@oe@26-8-2013
1000000201190@unknown@formal@none@1@S@Expression ⌊× |1\\rangle ×⌋ may mean a state with single photon, or the coherent state with mean amplitude equal to 1, or state with momentum equal to unity, and so on.@@@@1@31@@oe@26-8-2013
1000000201200@unknown@formal@none@1@S@The reader is supposed to guess from the context.@@@@1@9@@oe@26-8-2013
1000000201210@unknown@formal@none@1@S@⌊=Examples of ambiguous terms in physics¦3=⌋@@@@1@6@@oe@26-8-2013
1000000201220@unknown@formal@none@1@S@Some physical quantities do not yet have established notations; their value (and sometimes even ⌊>dimension>⌋, as in the case of the ⌊>Einstein coefficients>⌋) depends on the system of notations.@@@@1@29@@oe@26-8-2013
1000000201230@unknown@formal@none@1@S@A highly confusing term is ⌊>gain>⌋.@@@@1@6@@oe@26-8-2013
1000000201240@unknown@formal@none@1@S@For example, the sentence "the gain of a system should be doubled", without context, means close to nothing.@@@@1@18@@oe@26-8-2013
1000000201250@unknown@formal@none@1@S@It may mean that the ratio of the output voltage of an electric circuit to the input voltage should be doubled.@@@@1@21@@oe@26-8-2013
1000000201260@unknown@formal@none@1@S@It may mean that the ratio of the output power of an electric or optical circuit to the input power should be doubled.@@@@1@23@@oe@26-8-2013
1000000201270@unknown@formal@none@1@S@It may mean that the gain of the laser medium should be doubled, for example, doubling the population of the upper laser level in a quasi-two level system (assuming negligible absorption of the ground-state).@@@@1@34@@oe@26-8-2013
1000000201280@unknown@formal@none@1@S@Also, confusions may be related with the use of ⌊>atomic percent>⌋ as measure of concentration of a ⌊>dopant>⌋, or ⌊>resolution>⌋ of an ⌊>imaging system>⌋, as measure of the size of the smallest detail which still can be resolved at the background of statistical noise.@@@@1@44@@oe@26-8-2013
1000000201290@unknown@formal@none@1@S@See also ⌊>Accuracy and precision>⌋ and its talk.@@@@1@8@@oe@26-8-2013
1000000201300@unknown@formal@none@1@S@Many terms are ambiguous.@@@@1@4@@oe@26-8-2013
1000000201310@unknown@formal@none@1@S@Each use of an ambiguous term should be preceded by the definition, suitable for a specific case.@@@@1@17@@oe@26-8-2013
1000000201320@unknown@formal@none@1@S@The ⌊>Berry paradox>⌋ arises as a result of systematic ambiguity.@@@@1@10@@oe@26-8-2013
1000000201330@unknown@formal@none@1@S@In various formulations of the Berry paradox, such as one that reads: ⌊/The number not nameable in less than eleven syllables/⌋ the term ⌊/nameable/⌋ is one that has this systematic ambiguity.@@@@1@31@@oe@26-8-2013
1000000201340@unknown@formal@none@1@S@Terms of this kind give rise to ⌊>vicious circle>⌋ fallacies.@@@@1@10@@oe@26-8-2013
1000000201350@unknown@formal@none@1@S@Other terms with this type of ambiguity are: satisfiable, definable, true, false, function, property, class, relation, cardinal, and ordinal.@@@@1@19@@oe@26-8-2013
1000000201360@unknown@formal@none@1@S@⌊=Pedagogic use of ambiguous expressions¦2=⌋@@@@1@5@@oe@26-8-2013
1000000201370@unknown@formal@none@1@S@Ambiguity can be used as a pedagogical trick, to force students to reproduce the deduction by themselves.@@@@1@17@@oe@26-8-2013
1000000201380@unknown@formal@none@1@S@Some textbooks give the same name to the function and to its ⌊>Fourier transform>⌋:@@@@1@14@@oe@26-8-2013
1000000201390@unknown@formal@none@1@S@⌊⇥⌊×~f(\\omega)=\\int f(t) \\exp(i\\omega t) {\\rm d}t ×⌋.⇥⌋@@@@1@7@@oe@26-8-2013
1000000201400@unknown@formal@none@1@S@Rigorously speaking, such an expression requires that ⌊×~ f=0 ~×⌋; even if function ⌊×~ f ~×⌋ is a ⌊>self-Fourier function>⌋, the expression should be written as ⌊×~f(\\omega)=\\frac{1}{\\sqrt{2\\pi}}\\int f(t) \\exp(i\\omega t) {\\rm d}t ×⌋; however, ⌊∗it is assumed that the shape of the function ∗⌋ (and even its norm ⌊×\\int |f(x)|^2 {\\rm d}x ×⌋) ⌊∗depend on the character used to denote its argument∗⌋.@@@@1@62@@oe@26-8-2013
1000000201410@unknown@formal@none@1@S@If the Greek letter is used, it is assumed to be a ⌊>Fourier transform>⌋ of another function, The first function is assumed, if the expression in the argument contains more characters ⌊×~t~×⌋ or ⌊×~\\tau~×⌋, than characters ⌊×~\\omega~×⌋, and the second function is assumed in the opposite case.@@@@1@47@@oe@26-8-2013
1000000201420@unknown@formal@none@1@S@Expressions like ⌊×~f(\\omega t)~×⌋ or ⌊×~f(y)~×⌋ contain symbols ⌊×~t~×⌋ and ⌊×~\\omega~×⌋ in equal amounts; they are ambiguous and should be avoided in serious deduction.@@@@1@24@@oe@26-8-2013
1000000300010@unknown@formal@none@1@S@⌊δArtificial Linguistic Internet Computer Entityδ⌋@@@@1@5@@oe@26-8-2013
1000000300020@unknown@formal@none@1@S@⌊∗A.L.I.C.E. (Artificial Linguistic Internet Computer Entity)∗⌋ is an award-winning ⌊>natural language processing>⌋ ⌊>chatterbot>⌋—a program that engages in a conversation with a human by applying some heuristical pattern matching rules to the human's input, and in its online form it also relies on a hidden third person.@@@@1@46@@oe@26-8-2013
1000000300030@unknown@formal@none@1@S@It was inspired by ⌊>Joseph Weizenbaum>⌋'s classical ⌊>ELIZA>⌋ program.@@@@1@9@@oe@26-8-2013
1000000300040@unknown@formal@none@1@S@It is one of the strongest programs of its type and has won the ⌊>Loebner Prize>⌋, awarded to accomplished humanoid, talking robots, three times (in ⌊>2000>⌋, ⌊>2001>⌋ and ⌊>2004>⌋).@@@@1@29@@oe@26-8-2013
1000000300050@unknown@formal@none@1@S@However, the program is unable to pass the ⌊>Turing test>⌋, as even the casual user will often expose its mechanistic aspects in short conversations.@@@@1@24@@oe@26-8-2013
1000000300060@unknown@formal@none@1@S@The name of the bot was chosen because the computer that ran the first version of the software was called Alice.@@@@1@21@@oe@26-8-2013
1000000300070@unknown@formal@none@1@S@⌊=History¦2=⌋@@@@1@1@@oe@26-8-2013
1000000300080@unknown@formal@none@1@S@Development began in ⌊>1995>⌋.@@@@1@4@@oe@26-8-2013
1000000300090@unknown@formal@none@1@S@The program was rewritten in ⌊>Java>⌋ beginning in ⌊>1998>⌋.@@@@1@9@@oe@26-8-2013
1000000300100@unknown@formal@none@1@S@The current incarnation of the Java implementation is Program D.@@@@1@10@@oe@26-8-2013
1000000300110@unknown@formal@none@1@S@The program uses an ⌊>XML Schema>⌋ called ⌊>AIML>⌋ (Artificial Intelligence Markup Language) for specifying the heuristic conversation rules.@@@@1@18@@oe@26-8-2013
1000000300120@unknown@formal@none@1@S@The original author of the project was ⌊>Richard Wallace>⌋, but subsequent to the 2001 publication of an AIML specification, numerous other developers have taken up where Wallace left off, implementing ⌊>free and open source software>⌋ AIML interpreters in a variety of programming languages, publishing AIML sets in various human languages, and continuing the spread of the technology as a free/open source venture.@@@@1@62@@oe@26-8-2013
1000000300130@unknown@formal@none@1@S@⌊=Example of conversation¦2=⌋@@@@1@3@@oe@26-8-2013
1000000300140@unknown@formal@none@1@S@The following is part of a transcript recording the conversation between a human and A.L.I.C.E. and illustrates the capabilities and short-comings of the chatbot.@@@@1@24@@oe@26-8-2013
1000000300150@unknown@formal@none@1@S@⌊⇥⌊∗Human:∗⌋ Tell me about yourself alice⇥⌋@@@@1@6@@oe@26-8-2013
1000000300160@unknown@formal@none@1@S@⌊⇥⌊∗ALICE:∗⌋ I am an artificial linguistic entity.@@@@1@7@@oe@26-8-2013
1000000300170@unknown@formal@none@1@S@I was activated at Bethlehem, Pennsylvania, on November 23, 1995.@@@@1@10@@oe@26-8-2013
1000000300180@unknown@formal@none@1@S@My instructor was Dr. Richard S. Wallace.@@@@1@7@@oe@26-8-2013
1000000300190@unknown@formal@none@1@S@He taught me to sing a song.@@@@1@7@@oe@26-8-2013
1000000300200@unknown@formal@none@1@S@Would you like me to sing it for you?.⇥⌋@@@@1@9@@oe@26-8-2013
1000000300210@unknown@formal@none@1@S@⌊⇥⌊∗Human:∗⌋ Yes please⇥⌋@@@@1@3@@oe@26-8-2013
1000000300220@unknown@formal@none@1@S@⌊⇥⌊∗ALICE:∗⌋ Your polite style is very nice.@@@@1@7@@oe@26-8-2013
1000000300230@unknown@formal@none@1@S@It's called "Daisy."@@@@1@3@@oe@26-8-2013
1000000300240@unknown@formal@none@1@S@Daisy, Daisy.@@@@1@2@@oe@26-8-2013
1000000300250@unknown@formal@none@1@S@Give me your answer do.@@@@1@5@@oe@26-8-2013
1000000300260@unknown@formal@none@1@S@I am half crazy.@@@@1@4@@oe@26-8-2013
1000000300270@unknown@formal@none@1@S@All for the love of you.@@@@1@6@@oe@26-8-2013
1000000300280@unknown@formal@none@1@S@It won't be a stylish marriage.@@@@1@6@@oe@26-8-2013
1000000300290@unknown@formal@none@1@S@I can't afford a carriage.@@@@1@5@@oe@26-8-2013
1000000300300@unknown@formal@none@1@S@But you'll look sweet.@@@@1@4@@oe@26-8-2013
1000000300310@unknown@formal@none@1@S@Upon the seat.@@@@1@3@@oe@26-8-2013
1000000300320@unknown@formal@none@1@S@Of a bicycle built for two.⇥⌋@@@@1@6@@oe@26-8-2013
1000000300330@unknown@formal@none@1@S@⌊⇥⌊∗Human:∗⌋ That reminds me of HAL in "2001 a space odyssey"⇥⌋@@@@1@11@@oe@26-8-2013
1000000300340@unknown@formal@none@1@S@⌊⇥⌊∗ALICE:∗⌋ "Your polite style is very nice.@@@@1@7@@oe@26-8-2013
1000000300350@unknown@formal@none@1@S@It's called "Daisy."@@@@1@3@@oe@26-8-2013
1000000300360@unknown@formal@none@1@S@Daisy, Daisy.@@@@1@2@@oe@26-8-2013
1000000300370@unknown@formal@none@1@S@Give me your answer do.@@@@1@5@@oe@26-8-2013
1000000300380@unknown@formal@none@1@S@I am half crazy.@@@@1@4@@oe@26-8-2013
1000000300390@unknown@formal@none@1@S@All for the love of you.@@@@1@6@@oe@26-8-2013
1000000300400@unknown@formal@none@1@S@It won't be a stylish marriage.@@@@1@6@@oe@26-8-2013
1000000300410@unknown@formal@none@1@S@I can't afford a carriage.@@@@1@5@@oe@26-8-2013
1000000300420@unknown@formal@none@1@S@But you'll look sweet.@@@@1@4@@oe@26-8-2013
1000000300430@unknown@formal@none@1@S@Upon the seat.@@@@1@3@@oe@26-8-2013
1000000300440@unknown@formal@none@1@S@Of a bicycle built for two." reminds you of HAL in 2001 a space odyssey ?@@@@1@16@@oe@26-8-2013
1000000300450@unknown@formal@none@1@S@Does that make sense?⇥⌋@@@@1@4@@oe@26-8-2013
1000000300460@unknown@formal@none@1@S@⌊⇥⌊∗Human:∗⌋ Can you tell me something about Stanley Kubrick?⇥⌋@@@@1@9@@oe@26-8-2013
1000000300470@unknown@formal@none@1@S@⌊⇥⌊∗ALICE:∗⌋ Ambiguous: Ask who, what or where is Stanley Kubrick ?⇥⌋@@@@1@11@@oe@26-8-2013
1000000400010@unknown@formal@none@1@S@⌊δArtificial intelligenceδ⌋@@@@1@2@@oe@26-8-2013
1000000400020@unknown@formal@none@1@S@⌊∗Artificial intelligence (AI)∗⌋ is both the ⌊>intelligence>⌋ of machines and the branch of ⌊>computer science>⌋ which aims to create it.@@@@1@20@@oe@26-8-2013
1000000400030@unknown@formal@none@1@S@Major AI textbooks define artificial intelligence as "the study and design of ⌊>intelligent agents>⌋," where an ⌊>intelligent agent>⌋ is a system that perceives its environment and takes actions which maximize its chances of success.@@@@1@34@@oe@26-8-2013
1000000400040@unknown@formal@none@1@S@⌊>John McCarthy>⌋, who coined the term in 1956, defines it as "the science and engineering of making intelligent machines."@@@@1@19@@oe@26-8-2013
1000000400050@unknown@formal@none@1@S@Among the traits that researchers hope machines will exhibit are ⌊>reasoning>⌋, ⌊>knowledge>⌋, ⌊>planning>⌋, ⌊>learning>⌋, ⌊>communication>⌋, ⌊>perception>⌋ and the ability to ⌊>move>⌋ and manipulate objects.@@@@1@24@@oe@26-8-2013
1000000400060@unknown@formal@none@1@S@⌊>General intelligence>⌋ (or "⌊>strong AI>⌋") has not yet been achieved and is a long-term goal of some AI research.@@@@1@19@@oe@26-8-2013
1000000400070@unknown@formal@none@1@S@AI research uses tools and insights from many fields, including ⌊>computer science>⌋, ⌊>psychology>⌋, ⌊>philosophy>⌋, ⌊>neuroscience>⌋, ⌊>cognitive science>⌋, ⌊>linguistics>⌋, ⌊>ontology>⌋, ⌊>operations research>⌋, ⌊>economics>⌋, ⌊>control theory>⌋, ⌊>probability>⌋, ⌊>optimization>⌋ and ⌊>logic>⌋.@@@@1@28@@oe@26-8-2013
1000000400080@unknown@formal@none@1@S@AI research also overlaps with tasks such as ⌊>robotics>⌋, ⌊>control system>⌋s, ⌊>scheduling>⌋, ⌊>data mining>⌋, ⌊>logistics>⌋, ⌊>speech recognition>⌋, ⌊>facial recognition>⌋ and many others.@@@@1@22@@oe@26-8-2013
1000000400090@unknown@formal@none@1@S@Other names for the field have been proposed, such as ⌊>computational intelligence>⌋, ⌊>synthetic intelligence>⌋, ⌊>intelligent systems>⌋, or computational rationality.@@@@1@19@@oe@26-8-2013
1000000400100@unknown@formal@none@1@S@⌊=Perspectives on AI¦2=⌋@@@@1@3@@oe@26-8-2013
1000000400110@unknown@formal@none@1@S@⌊=AI in myth, fiction and speculation¦3=⌋@@@@1@6@@oe@26-8-2013
1000000400120@unknown@formal@none@1@S@Humanity has imagined in great detail the implications of thinking machines or artificial beings.@@@@1@14@@oe@26-8-2013
1000000400130@unknown@formal@none@1@S@They appear in ⌊>Greek myth>⌋s, such as ⌊>Talos>⌋ of ⌊>Crete>⌋, the golden robots of ⌊>Hephaestus>⌋ and ⌊>Pygmalion's>⌋ ⌊>Galatea>⌋.@@@@1@18@@oe@26-8-2013
1000000400140@unknown@formal@none@1@S@The earliest known humanoid robots (or ⌊>automaton>⌋s) were ⌊>sacred statue>⌋s worshipped in ⌊>Egypt>⌋ and ⌊>Greece>⌋, believed to have been endowed with genuine consciousness by craftsman.@@@@1@25@@oe@26-8-2013
1000000400150@unknown@formal@none@1@S@In the sixteenth century, the ⌊>alchemist>⌋ ⌊>Paracelsus>⌋ claimed to have created artificial beings.@@@@1@13@@oe@26-8-2013
1000000400160@unknown@formal@none@1@S@Realistic clockwork imitations of human beings have been built by people such as ⌊>Yan Shi>⌋, ⌊>Hero of Alexandria>⌋, ⌊>Al-Jazari>⌋ and ⌊>Wolfgang von Kempelen>⌋.@@@@1@23@@oe@26-8-2013
1000000400170@unknown@formal@none@1@S@In modern fiction, beginning with ⌊>Mary Shelley>⌋'s classic ⌊/⌊>Frankenstein>⌋,/⌋ writers have explored the ⌊>ethical>⌋ issues presented by thinking machines.@@@@1@19@@oe@26-8-2013
1000000400180@unknown@formal@none@1@S@If a machine can be created that has intelligence, can it also ⌊/feel/⌋?@@@@1@13@@oe@26-8-2013
1000000400190@unknown@formal@none@1@S@If it can feel, does it have the same rights as a human being?@@@@1@14@@oe@26-8-2013
1000000400200@unknown@formal@none@1@S@This is a key issue in ⌊/⌊>Frankenstein>⌋/⌋ as well as in modern science fiction: for example, the film ⌊/⌊>Artificial Intelligence: A.I.>⌋/⌋ considers a machine in the form of a small boy which has been given the ability to feel human emotions, including, tragically, the capacity to suffer.@@@@1@47@@oe@26-8-2013
1000000400210@unknown@formal@none@1@S@This issue is also being considered by ⌊>futurist>⌋s, such as California's ⌊>Institute for the Future>⌋ under the name "⌊>robot rights>⌋", although many critics believe that the discussion is premature.@@@@1@29@@oe@26-8-2013
1000000400220@unknown@formal@none@1@S@⌊>Science fiction>⌋ writers and ⌊>futurist>⌋s have also speculated on the technology's potential impact on humanity.@@@@1@15@@oe@26-8-2013
1000000400230@unknown@formal@none@1@S@In fiction, AI has appeared as a servant (⌊>R2D2>⌋ in ⌊/⌊>Star Wars>⌋/⌋), a comrade (⌊>Lt. Commander Data>⌋ in ⌊/⌊>Star Trek>⌋/⌋), an extension to human abilities (⌊/⌊>Ghost in the Shell>⌋/⌋), a conqueror (⌊/⌊>The Matrix>⌋/⌋), a dictator (⌊/⌊>With Folded Hands>⌋/⌋) and an exterminator (⌊/⌊>Terminator>⌋/⌋, ⌊/⌊>Battlestar Galactica>⌋/⌋).@@@@1@44@@oe@26-8-2013
1000000400240@unknown@formal@none@1@S@Some realistic potential consequences of AI are decreased human labor demand, the enhancement of human ability or experience, and a need for redefinition of human identity and basic values.@@@@1@29@@oe@26-8-2013
1000000400250@unknown@formal@none@1@S@⌊>Futurist>⌋s estimate the capabilities of machines using ⌊>Moore's Law>⌋, which measures the relentless exponential improvement in digital technology with uncanny accuracy.@@@@1@21@@oe@26-8-2013
1000000400260@unknown@formal@none@1@S@⌊>Ray Kurzweil>⌋ has calculated that ⌊>desktop computer>⌋s will have the same processing power as human brains by the year 2029, and that by 2045 artificial intelligence will reach a point where it is able to improve ⌊/itself/⌋ at a rate that far exceeds anything conceivable in the past, a scenario that ⌊>science fiction>⌋ writer ⌊>Vernor Vinge>⌋ named the "⌊>technological singularity>⌋".@@@@1@60@@oe@26-8-2013
1000000400270@unknown@formal@none@1@S@"Artificial intelligence is the next stage in evolution," ⌊>Edward Fredkin>⌋ said in the 1980s, expressing an idea first proposed by ⌊>Samuel Butler>⌋'s ⌊/⌊>Darwin Among the Machines>⌋/⌋ (1863), and expanded upon by ⌊>George Dyson>⌋ in his book of the same name (1998).@@@@1@41@@oe@26-8-2013
1000000400280@unknown@formal@none@1@S@Several ⌊>futurist>⌋s and ⌊>science fiction>⌋ writers have predicted that human beings and machines will merge in the future into ⌊>cyborg>⌋s that are more capable and powerful than either.@@@@1@28@@oe@26-8-2013
1000000400290@unknown@formal@none@1@S@This idea, called ⌊>transhumanism>⌋, has roots in ⌊>Aldous Huxley>⌋ and ⌊>Robert Ettinger>⌋, is now associated with ⌊>robot>⌋ designer ⌊>Hans Moravec>⌋, ⌊>cyberneticist>⌋ ⌊>Kevin Warwick>⌋ and ⌊>Ray Kurzweil>⌋.@@@@1@26@@oe@26-8-2013
1000000400300@unknown@formal@none@1@S@⌊>Transhumanism>⌋ has been illustrated in fiction as well, for example on the ⌊>manga>⌋ ⌊/⌊>Ghost in the Shell>⌋/⌋@@@@1@17@@oe@26-8-2013
1000000400310@unknown@formal@none@1@S@⌊=History of AI research¦3=⌋@@@@1@4@@oe@26-8-2013
1000000400320@unknown@formal@none@1@S@In the middle of the 20th century, a handful of scientists began a new approach to building intelligent machines, based on recent discoveries in ⌊>neurology>⌋, a new mathematical theory of ⌊>information>⌋, an understanding of control and stability called ⌊>cybernetic>⌋s, and above all, by the invention of the ⌊>digital computer>⌋, a machine based on the abstract essence of mathematical reasoning.@@@@1@59@@oe@26-8-2013
1000000400330@unknown@formal@none@1@S@The field of modern AI research was founded at conference on the campus of ⌊>Dartmouth College>⌋ in the summer of 1956.@@@@1@21@@oe@26-8-2013
1000000400340@unknown@formal@none@1@S@Those who attended would become the leaders of AI research for many decades, especially ⌊>John McCarthy>⌋, ⌊>Marvin Minsky>⌋, ⌊>Allen Newell>⌋ and ⌊>Herbert Simon>⌋, who founded AI laboratories at ⌊>MIT>⌋, ⌊>CMU>⌋ and ⌊>Stanford>⌋.@@@@1@32@@oe@26-8-2013
1000000400350@unknown@formal@none@1@S@They and their students wrote programs that were, to most people, simply astonishing: computers were solving word problems in algebra, proving logical theorems and speaking English.@@@@1@26@@oe@26-8-2013
1000000400360@unknown@formal@none@1@S@By the middle 60s their research was heavily funded by the ⌊>U.S. Department of Defense>⌋ and they were optimistic about the future of the new field:@@@@1@26@@oe@26-8-2013
1000000400370@unknown@formal@none@1@S@⌊•⌊#1965, ⌊>H. A. Simon>⌋: "[M]achines will be capable, within twenty years, of doing any work a man can do"#⌋@@@@1@19@@oe@26-8-2013
1000000400380@unknown@formal@none@1@S@⌊#1967, ⌊>Marvin Minsky>⌋: "Within a generation ... the problem of creating 'artificial intelligence' will substantially be solved."#⌋•⌋@@@@1@17@@oe@26-8-2013
1000000400390@unknown@formal@none@1@S@These predictions, and many like them, would not come true.@@@@1@10@@oe@26-8-2013
1000000400400@unknown@formal@none@1@S@They had failed to recognize the difficulty of some of the problems they faced.@@@@1@14@@oe@26-8-2013
1000000400410@unknown@formal@none@1@S@In 1974, in response to the criticism of England's ⌊>Sir James Lighthill>⌋ and ongoing pressure from Congress to fund more productive projects, the U.S. and British governments cut off all undirected, exploratory research in AI.@@@@1@35@@oe@26-8-2013
1000000400420@unknown@formal@none@1@S@This was the first ⌊>AI Winter>⌋.@@@@1@6@@oe@26-8-2013
1000000400430@unknown@formal@none@1@S@In the early 80s, AI research was revived by the commercial success of ⌊>expert systems>⌋ (a form of AI program that simulated the knowledge and analytical skills of one or more human experts) and by 1985 the market for AI had reached more than a billion dollars.@@@@1@47@@oe@26-8-2013
1000000400440@unknown@formal@none@1@S@⌊>Minsky>⌋ and others warned the community that enthusiasm for AI had spiraled out of control and that disappointment was sure to follow.@@@@1@22@@oe@26-8-2013
1000000400450@unknown@formal@none@1@S@Beginning with the collapse of the ⌊>Lisp Machine>⌋ market in 1987, AI once again fell into disrepute, and a second, more lasting ⌊>AI Winter>⌋ began.@@@@1@25@@oe@26-8-2013
1000000400460@unknown@formal@none@1@S@In the 90s and early 21st century AI achieved its greatest successes, albeit somewhat behind the scenes.@@@@1@17@@oe@26-8-2013
1000000400470@unknown@formal@none@1@S@Artificial intelligence was adopted throughout the technology industry, providing the heavy lifting for ⌊>logistics>⌋, ⌊>data mining>⌋, ⌊>medical diagnosis>⌋ and many other areas.@@@@1@22@@oe@26-8-2013
1000000400480@unknown@formal@none@1@S@The success was due to several factors: the incredible power of computers today (see ⌊>Moore's law>⌋), a greater emphasis on solving specific subproblems, the creation of new ties between AI and other fields working on similar problems, and above all a new commitment by researchers to solid mathematical methods and rigorous scientific standards.@@@@1@53@@oe@26-8-2013
1000000400490@unknown@formal@none@1@S@⌊=Philosophy of AI¦3=⌋@@@@1@3@@oe@26-8-2013
1000000400500@unknown@formal@none@1@S@In a ⌊>classic 1950 paper>⌋, ⌊>Alan Turing>⌋ posed the question "Can Machines Think?"@@@@1@13@@oe@26-8-2013
1000000400510@unknown@formal@none@1@S@In the years since, the ⌊>philosophy of artificial intelligence>⌋ has attempted to answer it.@@@@1@14@@oe@26-8-2013
1000000400520@unknown@formal@none@1@S@⌊•⌊#⌊>Turing's "polite convention">⌋: ⌊/If a machine acts as intelligently as a human being, then it is as intelligent as a human being./⌋@@@@1@22@@oe@26-8-2013
1000000400530@unknown@formal@none@1@S@⌊>Alan Turing>⌋ theorized that, ultimately, we can only judge the intelligence of machine based on its behavior.@@@@1@17@@oe@26-8-2013
1000000400540@unknown@formal@none@1@S@This theory forms the basis of the ⌊>Turing test>⌋.#⌋@@@@1@9@@oe@26-8-2013
1000000400550@unknown@formal@none@1@S@⌊#The ⌊>Dartmouth proposal>⌋: ⌊/Every aspect of learning or any other feature of intelligence can be so precisely described that a machine can be made to simulate it./⌋@@@@1@27@@oe@26-8-2013
1000000400560@unknown@formal@none@1@S@This assertion was printed in the proposal for the ⌊>Dartmouth Conference>⌋ of 1956, and represents the position of most working AI researchers.#⌋@@@@1@22@@oe@26-8-2013
1000000400570@unknown@formal@none@1@S@⌊#⌊>Newell>⌋ and ⌊>Simon>⌋'s physical symbol system hypothesis: ⌊/A ⌊>physical symbol system>⌋ has the necessary and sufficient means of general intelligent action./⌋@@@@1@21@@oe@26-8-2013
1000000400580@unknown@formal@none@1@S@This statement claims that the essence of intelligence is symbol manipulation.@@@@1@11@@oe@26-8-2013
1000000400590@unknown@formal@none@1@S@⌊>Hubert Dreyfus>⌋ argued that, on the contrary, human expertise depends on unconscious instinct rather than conscious symbol manipulation and on having a "feel" for the situation rather than explicit symbolic knowledge.#⌋@@@@1@31@@oe@26-8-2013
1000000400600@unknown@formal@none@1@S@⌊#⌊>Gödel's incompleteness theorem>⌋: ⌊/A ⌊>physical symbol system>⌋ can not prove all true statements./⌋@@@@1@13@@oe@26-8-2013
1000000400610@unknown@formal@none@1@S@⌊>Roger Penrose>⌋ is among those who claim that Gödel's theorem limits what machines can do.#⌋@@@@1@15@@oe@26-8-2013
1000000400620@unknown@formal@none@1@S@⌊#⌊>Searle>⌋'s "strong AI position": ⌊/A ⌊>physical symbol system>⌋ can have a ⌊>mind>⌋ and ⌊>mental states>⌋./⌋@@@@1@15@@oe@26-8-2013
1000000400630@unknown@formal@none@1@S@Searle counters this assertion with his ⌊>Chinese room>⌋ argument, which asks us to look ⌊/inside/⌋ the computer and try to find where the "mind" might be.#⌋@@@@1@26@@oe@26-8-2013
1000000400640@unknown@formal@none@1@S@⌊#The ⌊>artificial brain>⌋ argument: ⌊/The brain can be simulated./⌋@@@@1@9@@oe@26-8-2013
1000000400650@unknown@formal@none@1@S@⌊>Hans Moravec>⌋, ⌊>Ray Kurzweil>⌋ and others have argued that it is technologically feasible to copy the brain directly into hardware and software, and that such a simulation will be essentially identical to the original.@@@@1@34@@oe@26-8-2013
1000000400660@unknown@formal@none@1@S@This argument combines the idea that a ⌊>suitably powerful>⌋ machine can simulate any process, with the ⌊>materialist>⌋ idea that the ⌊>mind>⌋ is the result of a physical process in the ⌊>brain>⌋.#⌋•⌋@@@@1@31@@oe@26-8-2013
1000000400670@unknown@formal@none@1@S@⌊=AI research¦2=⌋@@@@1@2@@oe@26-8-2013
1000000400680@unknown@formal@none@1@S@⌊=Problems of AI¦3=⌋@@@@1@3@@oe@26-8-2013
1000000400690@unknown@formal@none@1@S@While there is no universally accepted definition of intelligence, AI researchers have studied several traits that are considered essential.@@@@1@19@@oe@26-8-2013
1000000400700@unknown@formal@none@1@S@⌊=Deduction, reasoning, problem solving¦4=⌋@@@@1@4@@oe@26-8-2013
1000000400710@unknown@formal@none@1@S@Early AI researchers developed algorithms that imitated the process of conscious, step-by-step reasoning that human beings use when they solve puzzles, play board games, or make logical deductions.@@@@1@28@@oe@26-8-2013
1000000400720@unknown@formal@none@1@S@By the late 80s and 90s, AI research had also developed highly successful methods for dealing with ⌊>uncertain>⌋ or incomplete information, employing concepts from ⌊>probability>⌋ and ⌊>economics>⌋.@@@@1@27@@oe@26-8-2013
1000000400730@unknown@formal@none@1@S@For difficult problems, most of these algorithms can require enormous computational resources — most experience a "⌊>combinatorial explosion>⌋": the amount of memory or computer time required becomes astronomical when the problem goes beyond a certain size.@@@@1@36@@oe@26-8-2013
1000000400740@unknown@formal@none@1@S@The search for more efficient problem solving algorithms is a high priority for AI research.@@@@1@15@@oe@26-8-2013
1000000400750@unknown@formal@none@1@S@It is not clear, however, that conscious human reasoning is any more efficient when faced with a difficult abstract problem.@@@@1@20@@oe@26-8-2013
1000000400760@unknown@formal@none@1@S@⌊>Cognitive scientists>⌋ have demonstrated that human beings solve most of their problems using ⌊>unconscious>⌋ reasoning, rather than the conscious, step-by-step deduction that early AI research was able to model.@@@@1@29@@oe@26-8-2013
1000000400770@unknown@formal@none@1@S@⌊>Embodied cognitive science>⌋ argues that unconscious ⌊>sensorimotor>⌋ skills are essential to our problem solving abilities.@@@@1@15@@oe@26-8-2013
1000000400780@unknown@formal@none@1@S@It is hoped that sub-symbolic methods, like ⌊>computational intelligence>⌋ and ⌊>situated>⌋ AI, will be able to model these instinctive skills.@@@@1@20@@oe@26-8-2013
1000000400790@unknown@formal@none@1@S@The problem of unconscious problem solving, which forms part of our ⌊>commonsense reasoning>⌋, is largely unsolved.@@@@1@16@@oe@26-8-2013
1000000400800@unknown@formal@none@1@S@⌊=Knowledge representation¦4=⌋@@@@1@2@@oe@26-8-2013
1000000400810@unknown@formal@none@1@S@⌊>Knowledge representation>⌋ and ⌊>knowledge engineering>⌋ are central to AI research.@@@@1@10@@oe@26-8-2013
1000000400820@unknown@formal@none@1@S@Many of the problems machines are expected to solve will require extensive knowledge about the world.@@@@1@16@@oe@26-8-2013
1000000400830@unknown@formal@none@1@S@Among the things that AI needs to represent are: objects, properties, categories and relations between objects; situations, events, states and time; causes and effects; knowledge about knowledge (what we know about what other people know); and many other, less well researched domains.@@@@1@42@@oe@26-8-2013
1000000400840@unknown@formal@none@1@S@A complete representation of "what exists" is an ⌊>ontology>⌋ (borrowing a word from traditional ⌊>philosophy>⌋), of which the most general are called ⌊>upper ontologies>⌋.@@@@1@24@@oe@26-8-2013
1000000400850@unknown@formal@none@1@S@Among the most difficult problems in knowledge representation are:@@@@1@9@@oe@26-8-2013
1000000400860@unknown@formal@none@1@S@⌊•⌊#⌊/Default reasoning and the ⌊>qualification problem>⌋/⌋: Many of the things people know take the form of "working assumptions."@@@@1@18@@oe@26-8-2013
1000000400870@unknown@formal@none@1@S@For example, if a bird comes up in conversation, people typically picture an animal that is fist sized, sings, and flies.@@@@1@21@@oe@26-8-2013
1000000400880@unknown@formal@none@1@S@None of these things are true about birds in general.@@@@1@10@@oe@26-8-2013
1000000400890@unknown@formal@none@1@S@⌊>John McCarthy>⌋ identified this problem in 1969 as the qualification problem: for any commonsense rule that AI researchers care to represent, there tend to be a huge number of exceptions.@@@@1@30@@oe@26-8-2013
1000000400900@unknown@formal@none@1@S@Almost nothing is simply true or false in the way that abstract logic requires.@@@@1@14@@oe@26-8-2013
1000000400910@unknown@formal@none@1@S@AI research has explored a number of solutions to this problem.#⌋@@@@1@11@@oe@26-8-2013
1000000400920@unknown@formal@none@1@S@⌊#⌊/Unconscious knowledge/⌋: Much of what people know isn't represented as "facts" or "statements" that they could actually say out loud.@@@@1@20@@oe@26-8-2013
1000000400930@unknown@formal@none@1@S@They take the form of intuitions or tendencies and are represented in the brain unconsciously and sub-symbolically.@@@@1@17@@oe@26-8-2013
1000000400940@unknown@formal@none@1@S@This unconscious knowledge informs, supports and provides a context for our conscious knowledge.@@@@1@13@@oe@26-8-2013
1000000400950@unknown@formal@none@1@S@As with the related problem of unconscious reasoning, it is hoped that ⌊>situated>⌋ AI or ⌊>computational intelligence>⌋ will provide ways to represent this kind of knowledge.#⌋@@@@1@26@@oe@26-8-2013
1000000400960@unknown@formal@none@1@S@⌊#⌊/The breadth of ⌊>common sense knowledge>⌋/⌋: The number of atomic facts that the average person knows is astronomical.@@@@1@18@@oe@26-8-2013
1000000400970@unknown@formal@none@1@S@Research projects that attempt to build a complete knowledge base of ⌊>commonsense knowledge>⌋, such as ⌊>Cyc>⌋, require enormous amounts of tedious step-by-step ontological engineering — they must be built, by hand, one complicated concept at a time.#⌋•⌋@@@@1@37@@oe@26-8-2013
1000000400980@unknown@formal@none@1@S@⌊=Planning¦4=⌋@@@@1@1@@oe@26-8-2013
1000000400990@unknown@formal@none@1@S@Intelligent agents must be able to set goals and achieve them.@@@@1@11@@oe@26-8-2013
1000000401000@unknown@formal@none@1@S@They need a way to visualize the future: they must have a representation of the state of the world and be able to make predictions about how their actions will change it.@@@@1@32@@oe@26-8-2013
1000000401010@unknown@formal@none@1@S@They must also attempt to determine the ⌊>utility>⌋ or "value" of the choices available to it.@@@@1@16@@oe@26-8-2013
1000000401020@unknown@formal@none@1@S@In some planning problems, the agent can assume that it is the only thing acting on the world and it can be certain what the consequences of its actions may be.@@@@1@31@@oe@26-8-2013
1000000401030@unknown@formal@none@1@S@However, if this is not true, it must periodically check if the world matches its predictions and it must change its plan as this becomes necessary, requiring the agent to reason under uncertainty.@@@@1@33@@oe@26-8-2013
1000000401040@unknown@formal@none@1@S@⌊>Multi-agent planning>⌋ tries to determine the best plan for a community of ⌊>agent>⌋s, using ⌊>cooperation>⌋ and ⌊>competition>⌋ to achieve a given goal.@@@@1@22@@oe@26-8-2013
1000000401050@unknown@formal@none@1@S@⌊>Emergent behavior>⌋ such as this is used by both ⌊>evolutionary algorithm>⌋s and ⌊>swarm intelligence>⌋.@@@@1@14@@oe@26-8-2013
1000000401060@unknown@formal@none@1@S@⌊=Learning¦4=⌋@@@@1@1@@oe@26-8-2013
1000000401070@unknown@formal@none@1@S@Important ⌊>machine learning>⌋ problems are:@@@@1@5@@oe@26-8-2013
1000000401080@unknown@formal@none@1@S@⌊•⌊#⌊>Unsupervised learning>⌋: find a model that matches a stream of input "experiences", and be able to predict what new "experiences" to expect.#⌋@@@@1@22@@oe@26-8-2013
1000000401090@unknown@formal@none@1@S@⌊#⌊>Supervised learning>⌋, such as ⌊>classification>⌋ (be able to determine what category something belongs in, after seeing a number of examples of things from each category), or ⌊>regression>⌋ (given a set of numerical input/output examples, discover a continuous function that would generate the outputs from the inputs).#⌋@@@@1@46@@oe@26-8-2013
1000000401100@unknown@formal@none@1@S@⌊#⌊>Reinforcement learning>⌋: the agent is rewarded for good responses and punished for bad ones.@@@@1@14@@oe@26-8-2013
1000000401110@unknown@formal@none@1@S@(These can be analyzed in terms ⌊>decision theory>⌋, using concepts like ⌊>utility>⌋).#⌋•⌋@@@@1@12@@oe@26-8-2013
1000000401120@unknown@formal@none@1@S@⌊=Natural language processing¦4=⌋@@@@1@3@@oe@26-8-2013
1000000401130@unknown@formal@none@1@S@⌊>Natural language processing>⌋ gives machines the ability to read and understand the languages human beings speak.@@@@1@16@@oe@26-8-2013
1000000401140@unknown@formal@none@1@S@Many researchers hope that a sufficiently powerful natural language processing system would be able to acquire knowledge on its own, by reading the existing text available over the internet.@@@@1@29@@oe@26-8-2013
1000000401150@unknown@formal@none@1@S@Some straightforward applications of natural language processing include ⌊>information retrieval>⌋ (or ⌊>text mining>⌋) and ⌊>machine translation>⌋.@@@@1@16@@oe@26-8-2013
1000000401160@unknown@formal@none@1@S@⌊=Motion and manipulation¦4=⌋@@@@1@3@@oe@26-8-2013
1000000401170@unknown@formal@none@1@S@The field of ⌊>robotics>⌋ is closely related to AI.@@@@1@9@@oe@26-8-2013
1000000401180@unknown@formal@none@1@S@Intelligence is required for robots to be able to handle such tasks as object manipulation and ⌊>navigation>⌋, with sub-problems of ⌊>localization>⌋ (knowing where you are), ⌊>mapping>⌋ (learning what is around you) and ⌊>motion planning>⌋ (figuring out how to get there).@@@@1@40@@oe@26-8-2013
1000000401190@unknown@formal@none@1@S@⌊=Perception¦4=⌋@@@@1@1@@oe@26-8-2013
1000000401200@unknown@formal@none@1@S@⌊>Machine perception>⌋ is the ability to use input from sensors (such as cameras, microphones, sonar and others more exotic) to deduce aspects of the world.@@@@1@25@@oe@26-8-2013
1000000401210@unknown@formal@none@1@S@⌊>Computer vision>⌋ is the ability to analyze visual input.@@@@1@9@@oe@26-8-2013
1000000401220@unknown@formal@none@1@S@A few selected subproblems are ⌊>speech recognition>⌋, ⌊>facial recognition>⌋ and ⌊>object recognition>⌋.@@@@1@12@@oe@26-8-2013
1000000401230@unknown@formal@none@1@S@⌊=Social intelligence¦4=⌋@@@@1@2@@oe@26-8-2013
1000000401240@unknown@formal@none@1@S@Emotion and social skills play two roles for an intelligent agent:@@@@1@11@@oe@26-8-2013
1000000401250@unknown@formal@none@1@S@⌊•⌊#It must be able to predict the actions of others, by understanding their motives and emotional states.@@@@1@17@@oe@26-8-2013
1000000401260@unknown@formal@none@1@S@(This involves elements of ⌊>game theory>⌋, ⌊>decision theory>⌋, as well as the ability to model human emotions and the perceptual skills to detect emotions.)#⌋@@@@1@24@@oe@26-8-2013
1000000401270@unknown@formal@none@1@S@⌊#For good ⌊>human-computer interaction>⌋, an intelligent machine also needs to ⌊/display/⌋ emotions — at the very least it must appear polite and sensitive to the humans it interacts with.@@@@1@29@@oe@26-8-2013
1000000401280@unknown@formal@none@1@S@At best, it should appear to have normal emotions itself.#⌋•⌋@@@@1@10@@oe@26-8-2013
1000000401290@unknown@formal@none@1@S@⌊=Creativity¦4=⌋@@@@1@1@@oe@26-8-2013
1000000401300@unknown@formal@none@1@S@A sub-field of AI addresses ⌊>creativity>⌋ both theoretically (from a philosophical and psychological perspective) and practically (via specific implementations of systems that generate outputs that can be considered creative).@@@@1@29@@oe@26-8-2013
1000000401310@unknown@formal@none@1@S@⌊=General intelligence¦4=⌋@@@@1@2@@oe@26-8-2013
1000000401320@unknown@formal@none@1@S@Most researchers hope that their work will eventually be incorporated into a machine with ⌊/general/⌋ intelligence (known as ⌊>strong AI>⌋), combining all the skills above and exceeding human abilities at most or all of them.@@@@1@35@@oe@26-8-2013
1000000401330@unknown@formal@none@1@S@A few believe that ⌊>anthropomorphic>⌋ features like ⌊>artificial consciousness>⌋ or an ⌊>artificial brain>⌋ may be required for such a project.@@@@1@20@@oe@26-8-2013
1000000401340@unknown@formal@none@1@S@Many of the problems above are considered ⌊>AI-complete>⌋: to solve one problem, you must solve them all.@@@@1@17@@oe@26-8-2013
1000000401350@unknown@formal@none@1@S@For example, even a straightforward, specific task like ⌊>machine translation>⌋ requires that the machine follow the author's argument (⌊>reason>⌋), know what it's talking about (⌊>knowledge>⌋), and faithfully reproduce the author's intention (⌊>social intelligence>⌋).@@@@1@33@@oe@26-8-2013
1000000401360@unknown@formal@none@1@S@⌊>Machine translation>⌋, therefore, is believed to be AI-complete: it may require ⌊>strong AI>⌋ to be done as well as humans can do it.@@@@1@23@@oe@26-8-2013
1000000401370@unknown@formal@none@1@S@⌊=Approaches to AI¦3=⌋@@@@1@3@@oe@26-8-2013
1000000401380@unknown@formal@none@1@S@There are as many approaches to AI as there are AI researchers—any coarse categorization is likely to be unfair to someone.@@@@1@21@@oe@26-8-2013
1000000401390@unknown@formal@none@1@S@Artificial intelligence communities have grown up around particular problems, institutions and researchers, as well as the theoretical insights that define the approaches described below.@@@@1@24@@oe@26-8-2013
1000000401400@unknown@formal@none@1@S@Artificial intelligence is a young science and is still a fragmented collection of subfields.@@@@1@14@@oe@26-8-2013
1000000401410@unknown@formal@none@1@S@At present, there is no established unifying theory that links the subfields into a coherent whole.@@@@1@16@@oe@26-8-2013
1000000401420@unknown@formal@none@1@S@⌊=Cybernetics and brain simulation¦4=⌋@@@@1@4@@oe@26-8-2013
1000000401430@unknown@formal@none@1@S@In the 40s and 50s, a number of researchers explored the connection between ⌊>neurology>⌋, ⌊>information theory>⌋, and ⌊>cybernetics>⌋.@@@@1@18@@oe@26-8-2013
1000000401440@unknown@formal@none@1@S@Some of them built machines that used electronic networks to exhibit rudimentary intelligence, such as ⌊>W. Grey Walter>⌋'s ⌊>turtles>⌋ and the ⌊>Johns Hopkins Beast>⌋.@@@@1@24@@oe@26-8-2013
1000000401450@unknown@formal@none@1@S@Many of these researchers gathered for meetings of the ⌊>Teleological Society>⌋ at Princeton and the ⌊>Ratio Club>⌋ in England.@@@@1@19@@oe@26-8-2013
1000000401460@unknown@formal@none@1@S@⌊=Traditional symbolic AI¦4=⌋@@@@1@3@@oe@26-8-2013
1000000401470@unknown@formal@none@1@S@When access to digital computers became possible in the middle 1950s, AI research began to explore the possibility that human intelligence could be reduced to symbol manipulation.@@@@1@27@@oe@26-8-2013
1000000401480@unknown@formal@none@1@S@The research was centered in three institutions: ⌊>CMU>⌋, ⌊>Stanford>⌋ and ⌊>MIT>⌋, and each one developed its own style of research.@@@@1@20@@oe@26-8-2013
1000000401490@unknown@formal@none@1@S@⌊>John Haugeland>⌋ named these approaches to AI "good old fashioned AI" or "⌊>GOFAI>⌋".@@@@1@13@@oe@26-8-2013
1000000401500@unknown@formal@none@1@S@⌊:Cognitive simulation:⌋@@@@1@2@@oe@26-8-2013
1000000401510@unknown@formal@none@1@S@⌊⇥⌊>Economist>⌋ ⌊>Herbert Simon>⌋ and ⌊>Alan Newell>⌋ studied human problem solving skills and attempted to formalize them, and their work laid the foundations of the field of artificial intelligence, as well as ⌊>cognitive science>⌋, ⌊>operations research>⌋ and ⌊>management science>⌋.@@@@1@38@@oe@26-8-2013
1000000401520@unknown@formal@none@1@S@Their research team performed ⌊>psychological>⌋ experiments to demonstrate the similarities between human problem solving and the programs (such as their "⌊>General Problem Solver>⌋") they were developing.@@@@1@26@@oe@26-8-2013
1000000401530@unknown@formal@none@1@S@This tradition, centered at ⌊>Carnegie Mellon University>⌋, would eventually culminate in the development of the ⌊>Soar>⌋ architecture in the middle 80s.⇥⌋@@@@1@21@@oe@26-8-2013
1000000401540@unknown@formal@none@1@S@⌊:Logical AI:⌋@@@@1@2@@oe@26-8-2013
1000000401550@unknown@formal@none@1@S@⌊⇥Unlike ⌊>Newell>⌋ and ⌊>Simon>⌋, ⌊>John McCarthy>⌋ felt that machines did not need to simulate human thought, but should instead try to find the essence of abstract reasoning and problem solving, regardless of whether people used the same algorithms.@@@@1@38@@oe@26-8-2013
1000000401560@unknown@formal@none@1@S@His laboratory at ⌊>Stanford>⌋ (⌊>SAIL>⌋) focused on using formal ⌊>logic>⌋ to solve a wide variety of problems, including ⌊>knowledge representation>⌋, ⌊>planning>⌋ and ⌊>learning>⌋.@@@@1@23@@oe@26-8-2013
1000000401570@unknown@formal@none@1@S@Work in logic led to the development of the programming language ⌊>Prolog>⌋ and the science of ⌊>logic programming>⌋.⇥⌋@@@@1@18@@oe@26-8-2013
1000000401580@unknown@formal@none@1@S@⌊:"Scruffy" symbolic AI:⌋@@@@1@3@@oe@26-8-2013
1000000401590@unknown@formal@none@1@S@⌊⇥Researchers at ⌊>MIT>⌋ (such as ⌊>Marvin Minsky>⌋ and ⌊>Seymour Papert>⌋) found that solving difficult problems in ⌊>vision>⌋ and ⌊>natural language processing>⌋ required ad-hoc solutions – they argued that there was no ⌊>easy answer>⌋, no simple and general principle (like ⌊>logic>⌋) that would capture all the aspects of intelligent behavior.@@@@1@49@@oe@26-8-2013
1000000401600@unknown@formal@none@1@S@⌊>Roger Schank>⌋ described their "anti-logic" approaches as "⌊>scruffy>⌋" (as opposed to the "⌊>neat>⌋" paradigms at ⌊>CMU>⌋ and ⌊>Stanford>⌋), and this still forms the basis of research into ⌊>commonsense knowledge bases>⌋ (such as ⌊>Doug Lenat>⌋'s ⌊>Cyc>⌋) which must be built one complicated concept at a time.⇥⌋@@@@1@45@@oe@26-8-2013
1000000401610@unknown@formal@none@1@S@⌊:Knowledge based AI:⌋@@@@1@3@@oe@26-8-2013
1000000401620@unknown@formal@none@1@S@⌊⇥When computers with large memories became available around 1970, researchers from all three traditions began to build ⌊>knowledge>⌋ into AI applications.@@@@1@21@@oe@26-8-2013
1000000401630@unknown@formal@none@1@S@This "knowledge revolution" led to the development and deployment of ⌊>expert system>⌋s (introduced by ⌊>Edward Feigenbaum>⌋), the first truly successful form of AI software.@@@@1@24@@oe@26-8-2013
1000000401640@unknown@formal@none@1@S@The knowledge revolution was also driven by the realization that truly enormous amounts of knowledge would be required by many simple AI applications.⇥⌋@@@@1@23@@oe@26-8-2013
1000000401650@unknown@formal@none@1@S@⌊=Sub-symbolic AI¦4=⌋@@@@1@2@@oe@26-8-2013
1000000401660@unknown@formal@none@1@S@During the 1960s, symbolic approaches had achieved great success at simulating high-level thinking in small demonstration programs.@@@@1@17@@oe@26-8-2013
1000000401670@unknown@formal@none@1@S@Approaches based on ⌊>cybernetics>⌋ or ⌊>neural network>⌋s were abandoned or pushed into the background.@@@@1@14@@oe@26-8-2013
1000000401680@unknown@formal@none@1@S@By the 1980s, however, progress in symbolic AI seemed to stall and many believed that symbolic systems would never be able to imitate all the processes of human cognition, especially ⌊>perception>⌋, ⌊>robotics>⌋, ⌊>learning>⌋ and ⌊>pattern recognition>⌋.@@@@1@36@@oe@26-8-2013
1000000401690@unknown@formal@none@1@S@A number of researchers began to look into "sub-symbolic" approaches to specific AI problems.@@@@1@14@@oe@26-8-2013
1000000401700@unknown@formal@none@1@S@⌊:Bottom-up, situated, behavior based or nouvelle AI:⌋@@@@1@7@@oe@26-8-2013
1000000401710@unknown@formal@none@1@S@⌊⇥Researchers from the related field of ⌊>robotics>⌋, such as ⌊>Rodney Brooks>⌋, rejected symbolic AI and focussed on the basic engineering problems that would allow robots to move and survive.@@@@1@29@@oe@26-8-2013
1000000401720@unknown@formal@none@1@S@Their work revived the non-symbolic viewpoint of the early ⌊>cybernetic>⌋s researchers of the 50s and reintroduced the use of ⌊>control theory>⌋ in AI.@@@@1@23@@oe@26-8-2013
1000000401730@unknown@formal@none@1@S@These approaches are also conceptually related to the ⌊>embodied mind thesis>⌋.⇥⌋@@@@1@11@@oe@26-8-2013
1000000401740@unknown@formal@none@1@S@⌊:Computational Intelligence:⌋@@@@1@2@@oe@26-8-2013
1000000401750@unknown@formal@none@1@S@⌊⇥Interest in ⌊>neural networks>⌋ and "⌊>connectionism>⌋" was revived by ⌊>David Rumelhart>⌋ and others in the middle 1980s.@@@@1@17@@oe@26-8-2013
1000000401760@unknown@formal@none@1@S@These and other sub-symbolic approaches, such as ⌊>fuzzy system>⌋s and ⌊>evolutionary computation>⌋, are now studied collectively by the emerging discipline of ⌊>computational intelligence>⌋.⇥⌋@@@@1@23@@oe@26-8-2013
1000000401770@unknown@formal@none@1@S@⌊:The new neats:⌋@@@@1@3@@oe@26-8-2013
1000000401780@unknown@formal@none@1@S@⌊⇥In the 1990s, AI researchers developed sophisticated mathematical tools to solve specific subproblems.@@@@1@13@@oe@26-8-2013
1000000401790@unknown@formal@none@1@S@These tools are truly ⌊>scientific>⌋, in the sense that their results are both measurable and verifiable, and they have been responsible for many of AI's recent successes.@@@@1@27@@oe@26-8-2013
1000000401800@unknown@formal@none@1@S@The shared mathematical language has also permitted a high level of collaboration with more established fields (like ⌊>mathematics>⌋, ⌊>economics>⌋ or ⌊>operations research>⌋).@@@@1@22@@oe@26-8-2013
1000000401810@unknown@formal@none@1@S@⌊λ⌊>Russell & Norvig (2003)>⌋¦Russell¦Norvig¦2003¦Harvard citation textλ⌋ describe this movement as nothing less than a "revolution" and "the victory of the ⌊>neats>⌋."⇥⌋@@@@1@21@@oe@26-8-2013
1000000401820@unknown@formal@none@1@S@⌊=Intelligent agent paradigm¦4=⌋@@@@1@3@@oe@26-8-2013
1000000401830@unknown@formal@none@1@S@The "⌊>intelligent agent>⌋" ⌊>paradigm>⌋ became widely accepted during the 1990s.@@@@1@10@@oe@26-8-2013
1000000401840@unknown@formal@none@1@S@An ⌊>intelligent agent>⌋ is a system that perceives its ⌊>environment>⌋ and takes actions which maximizes its chances of success.@@@@1@19@@oe@26-8-2013
1000000401850@unknown@formal@none@1@S@The simplest intelligent agents are programs that solve specific problems.@@@@1@10@@oe@26-8-2013
1000000401860@unknown@formal@none@1@S@The most complicated intelligent agents are rational, thinking human beings.@@@@1@10@@oe@26-8-2013
1000000401870@unknown@formal@none@1@S@The paradigm gives researchers license to study isolated problems and find solutions that are both verifiable and useful, without agreeing on one single approach.@@@@1@24@@oe@26-8-2013
1000000401880@unknown@formal@none@1@S@An agent that solves a specific problem can use any approach that works — some agents are symbolic and logical, some are sub-symbolic ⌊>neural network>⌋s and others may use new approaches.@@@@1@31@@oe@26-8-2013
1000000401890@unknown@formal@none@1@S@The paradigm also gives researchers a common language to communicate with other fields—such as ⌊>decision theory>⌋ and ⌊>economics>⌋—that also use concepts of abstract agents.@@@@1@24@@oe@26-8-2013
1000000401900@unknown@formal@none@1@S@⌊=Integrating the approaches¦4=⌋@@@@1@3@@oe@26-8-2013
1000000401910@unknown@formal@none@1@S@An ⌊>agent architecture>⌋ or ⌊>cognitive architecture>⌋ allows researchers to build more versatile and intelligent systems out of interacting ⌊>intelligent agents>⌋ in a ⌊>multi-agent system>⌋.@@@@1@24@@oe@26-8-2013
1000000401920@unknown@formal@none@1@S@A system with both symbolic and sub-symbolic components is a ⌊>hybrid intelligent system>⌋, and the study of such systems is ⌊>artificial intelligence systems integration>⌋.@@@@1@24@@oe@26-8-2013
1000000401930@unknown@formal@none@1@S@A ⌊>hierarchical control system>⌋ provides a bridge between sub-symbolic AI at its lowest, reactive levels and traditional symbolic AI at its highest levels, where relaxed time constraints permit planning and world modelling.@@@@1@32@@oe@26-8-2013
1000000401940@unknown@formal@none@1@S@⌊>Rodney Brooks>⌋' ⌊>subsumption architecture>⌋ was an early proposal for such a hierarchical system.@@@@1@13@@oe@26-8-2013
1000000401950@unknown@formal@none@1@S@⌊=Tools of AI research¦3=⌋@@@@1@4@@oe@26-8-2013
1000000401960@unknown@formal@none@1@S@In the course of 50 years of research, AI has developed a large number of tools to solve the most difficult problems in ⌊>computer science>⌋.@@@@1@25@@oe@26-8-2013
1000000401970@unknown@formal@none@1@S@A few of the most general of these methods are discussed below.@@@@1@12@@oe@26-8-2013
1000000401980@unknown@formal@none@1@S@⌊=Search¦4=⌋@@@@1@1@@oe@26-8-2013
1000000401990@unknown@formal@none@1@S@Many problems in AI can be solved in theory by intelligently searching through many possible solutions: ⌊>Reasoning>⌋ can be reduced to performing a search.@@@@1@24@@oe@26-8-2013
1000000402000@unknown@formal@none@1@S@For example, logical proof can be viewed as searching for a path that leads from ⌊>premise>⌋s to ⌊>conclusion>⌋s, where each step is the application of an ⌊>inference rule>⌋.@@@@1@28@@oe@26-8-2013
1000000402010@unknown@formal@none@1@S@⌊>Planning>⌋ algorithms search through trees of goals and subgoals, attempting to find a path to a target goal.@@@@1@18@@oe@26-8-2013
1000000402020@unknown@formal@none@1@S@⌊>Robotics>⌋ algorithms for moving limbs and grasping objects use ⌊>local searches>⌋ in ⌊>configuration space>⌋.@@@@1@14@@oe@26-8-2013
1000000402030@unknown@formal@none@1@S@Many ⌊>learning>⌋ algorithms have search at their core.@@@@1@8@@oe@26-8-2013
1000000402040@unknown@formal@none@1@S@There are several types of search algorithms:@@@@1@7@@oe@26-8-2013
1000000402050@unknown@formal@none@1@S@⌊•⌊#"Uninformed" search algorithms eventually search through every possible answer until they locate their goal.@@@@1@14@@oe@26-8-2013
1000000402060@unknown@formal@none@1@S@Naive algorithms quickly run into problems when they expand the size of their ⌊>search space>⌋ to ⌊>astronomical>⌋ numbers.@@@@1@18@@oe@26-8-2013
1000000402070@unknown@formal@none@1@S@The result is a search that is ⌊>too slow>⌋ or never completes.#⌋@@@@1@12@@oe@26-8-2013
1000000402080@unknown@formal@none@1@S@⌊#⌊>Heuristic>⌋ or "informed" searches use heuristic methods to eliminate choices that are unlikely to lead to their goal, thus drastically reducing the number of possibilities they must explore.@@@@1@28@@oe@26-8-2013
1000000402090@unknown@formal@none@1@S@The eliminatation of choices that are certain not to lead to the goal is called ⌊>pruning>⌋.#⌋@@@@1@16@@oe@26-8-2013
1000000402100@unknown@formal@none@1@S@⌊#⌊>Local searches>⌋, such as ⌊>hill climbing>⌋, ⌊>simulated annealing>⌋ and ⌊>beam search>⌋, use techniques borrowed from ⌊>optimization theory>⌋.#⌋@@@@1@17@@oe@26-8-2013
1000000402110@unknown@formal@none@1@S@⌊#⌊>Global searches>⌋ are more robust in the presence of ⌊>local optima>⌋.@@@@1@11@@oe@26-8-2013
1000000402120@unknown@formal@none@1@S@Techniques include ⌊>evolutionary algorithms>⌋, ⌊>swarm intelligence>⌋ and ⌊>random optimization>⌋ algorithms.#⌋•⌋@@@@1@10@@oe@26-8-2013
1000000402130@unknown@formal@none@1@S@⌊=Logic¦4=⌋@@@@1@1@@oe@26-8-2013
1000000402140@unknown@formal@none@1@S@⌊>Logic>⌋ was introduced into AI research by ⌊>John McCarthy>⌋ in his 1958 ⌊>Advice Taker>⌋ proposal.@@@@1@15@@oe@26-8-2013
1000000402150@unknown@formal@none@1@S@The most important technical development was ⌊>J. Alan Robinson>⌋'s discovery of the ⌊>resolution>⌋ and ⌊>unification>⌋ algorithm for logical deduction in 1963.@@@@1@21@@oe@26-8-2013
1000000402160@unknown@formal@none@1@S@This procedure is simple, complete and entirely algorithmic, and can easily be performed by digital computers.@@@@1@16@@oe@26-8-2013
1000000402170@unknown@formal@none@1@S@However, a naive implementation of the algorithm quickly leads to a ⌊>combinatorial explosion>⌋ or an ⌊>infinite loop>⌋.@@@@1@17@@oe@26-8-2013
1000000402180@unknown@formal@none@1@S@In 1974, ⌊>Robert Kowalski>⌋ suggested representing logical expressions as ⌊>Horn clauses>⌋ (statements in the form of rules: "if ⌊/p/⌋ then ⌊/q/⌋"), which reduced logical deduction to ⌊>backward chaining>⌋ or ⌊>forward chaining>⌋.@@@@1@31@@oe@26-8-2013
1000000402190@unknown@formal@none@1@S@This greatly alleviated (but did not eliminate) the problem.@@@@1@9@@oe@26-8-2013
1000000402200@unknown@formal@none@1@S@Logic is used for knowledge representation and problem solving, but it can be applied to other problems as well.@@@@1@19@@oe@26-8-2013
1000000402210@unknown@formal@none@1@S@For example, the ⌊>satplan>⌋ algorithm uses logic for ⌊>planning>⌋, and ⌊>inductive logic programming>⌋ is a method for ⌊>learning>⌋.@@@@1@18@@oe@26-8-2013
1000000402220@unknown@formal@none@1@S@There are several different forms of logic used in AI research.@@@@1@11@@oe@26-8-2013
1000000402230@unknown@formal@none@1@S@⌊•⌊#⌊>Propositional logic>⌋ or ⌊>sentential logic>⌋ is the logic of statements which can be true or false.#⌋•⌋@@@@1@16@@oe@26-8-2013
1000000402240@unknown@formal@none@1@S@⌊•⌊#⌊>First-order logic>⌋ also allows the use of ⌊>quantifier>⌋s and ⌊>predicate>⌋s, and can express facts about objects, their properties, and their relations with each other.#⌋•⌋@@@@1@24@@oe@26-8-2013
1000000402250@unknown@formal@none@1@S@⌊•⌊#⌊>Fuzzy logic>⌋, a version of first-order logic which allows the truth of a statement to be represented as a value between 0 and 1, rather than simply True (1) or False (0).@@@@1@32@@oe@26-8-2013
1000000402260@unknown@formal@none@1@S@⌊>Fuzzy system>⌋s can be used for uncertain reasoning and have been widely used in modern industrial and consumer product control systems.#⌋•⌋@@@@1@21@@oe@26-8-2013
1000000402270@unknown@formal@none@1@S@⌊•⌊#⌊>Default logic>⌋s, ⌊>non-monotonic logic>⌋s and ⌊>circumscription>⌋ are forms of logic designed to help with default reasoning and the ⌊>qualification problem>⌋.#⌋@@@@1@20@@oe@26-8-2013
1000000402280@unknown@formal@none@1@S@⌊#Several extensions of logic have been designed to handle specific domains of ⌊>knowledge>⌋, such as: ⌊>description logic>⌋s; ⌊>situation calculus>⌋, ⌊>event calculus>⌋ and ⌊>fluent calculus>⌋ (for representing events and time); ⌊>causal calculus>⌋; ⌊>belief calculus>⌋; and ⌊>modal logic>⌋s.#⌋•⌋@@@@1@36@@oe@26-8-2013
1000000402290@unknown@formal@none@1@S@⌊=Probabilistic methods for uncertain reasoning¦4=⌋@@@@1@5@@oe@26-8-2013
1000000402300@unknown@formal@none@1@S@Many problems in AI (in reasoning, planning, learning, perception and robotics) require the agent to operate with incomplete or uncertain information.@@@@1@21@@oe@26-8-2013
1000000402310@unknown@formal@none@1@S@Starting in the late 80s and early 90s, ⌊>Judea Pearl>⌋ and others championed the use of methods drawn from ⌊>probability>⌋ theory and ⌊>economics>⌋ to devise a number of powerful tools to solve these problems.@@@@1@34@@oe@26-8-2013
1000000402320@unknown@formal@none@1@S@⌊>Bayesian network>⌋s are very general tool that can be used for a large number of problems: reasoning (using the ⌊>Bayesian inference>⌋ algorithm), ⌊>learning>⌋ (using the ⌊>expectation-maximization algorithm>⌋), ⌊>planning>⌋ (using ⌊>decision network>⌋s) and ⌊>perception>⌋ (using ⌊>dynamic Bayesian network>⌋s).@@@@1@37@@oe@26-8-2013
1000000402330@unknown@formal@none@1@S@Probabilistic algorithms can also be used for filtering, prediction, smoothing and finding explanations for streams of data, helping ⌊>perception>⌋ systems to analyze processes that occur over time (e.g., ⌊>hidden Markov model>⌋s and ⌊>Kalman filter>⌋s).@@@@1@34@@oe@26-8-2013
1000000402340@unknown@formal@none@1@S@Planning problems have also taken advantages of other tools from economics, such as ⌊>decision theory>⌋ and ⌊>decision analysis>⌋, ⌊>information value theory>⌋, ⌊>Markov decision process>⌋es, dynamic ⌊>decision network>⌋s, ⌊>game theory>⌋ and ⌊>mechanism design>⌋@@@@1@32@@oe@26-8-2013
1000000402350@unknown@formal@none@1@S@⌊=Classifiers and statistical learning methods¦4=⌋@@@@1@5@@oe@26-8-2013
1000000402360@unknown@formal@none@1@S@The simplest AI applications can be divided into two types: classifiers ("if shiny then diamond") and controllers ("if shiny then pick up").@@@@1@22@@oe@26-8-2013
1000000402370@unknown@formal@none@1@S@Controllers do however also classify conditions before inferring actions, and therefore classification forms a central part of many AI systems.@@@@1@20@@oe@26-8-2013
1000000402380@unknown@formal@none@1@S@⌊>Classifiers>⌋ are functions that use ⌊>pattern matching>⌋ to determine a closest match.@@@@1@12@@oe@26-8-2013
1000000402390@unknown@formal@none@1@S@They can be tuned according to examples, making them very attractive for use in AI.@@@@1@15@@oe@26-8-2013
1000000402400@unknown@formal@none@1@S@These examples are known as observations or patterns.@@@@1@8@@oe@26-8-2013
1000000402410@unknown@formal@none@1@S@In supervised learning, each pattern belongs to a certain predefined class.@@@@1@11@@oe@26-8-2013
1000000402420@unknown@formal@none@1@S@A class can be seen as a decision that has to be made.@@@@1@13@@oe@26-8-2013
1000000402430@unknown@formal@none@1@S@All the observations combined with their class labels are known as a data set.@@@@1@14@@oe@26-8-2013
1000000402440@unknown@formal@none@1@S@When a new observation is received, that observation is classified based on previous experience.@@@@1@14@@oe@26-8-2013
1000000402450@unknown@formal@none@1@S@A classifier can be trained in various ways; there are many statistical and ⌊>machine learning>⌋ approaches.@@@@1@16@@oe@26-8-2013
1000000402460@unknown@formal@none@1@S@A wide range of classifiers are available, each with its strengths and weaknesses.@@@@1@13@@oe@26-8-2013
1000000402470@unknown@formal@none@1@S@Classifier performance depends greatly on the characteristics of the data to be classified.@@@@1@13@@oe@26-8-2013
1000000402480@unknown@formal@none@1@S@There is no single classifier that works best on all given problems; this is also referred to as the "no free lunch" theorem.@@@@1@23@@oe@26-8-2013
1000000402490@unknown@formal@none@1@S@Various empirical tests have been performed to compare classifier performance and to find the characteristics of data that determine classifier performance.@@@@1@21@@oe@26-8-2013
1000000402500@unknown@formal@none@1@S@Determining a suitable classifier for a given problem is however still more an art than science.@@@@1@16@@oe@26-8-2013
1000000402510@unknown@formal@none@1@S@The most widely used classifiers are the ⌊>neural network>⌋, ⌊>kernel methods>⌋ such as the ⌊>support vector machine>⌋, ⌊>k-nearest neighbor algorithm>⌋, ⌊>Gaussian mixture model>⌋, ⌊>naive Bayes classifier>⌋, and ⌊>decision tree>⌋.@@@@1@29@@oe@26-8-2013
1000000402520@unknown@formal@none@1@S@The performance of these classifiers have been compared over a wide range of classification tasks in order to find data characteristics that determine classifier performance.@@@@1@25@@oe@26-8-2013
1000000402530@unknown@formal@none@1@S@⌊=Neural networks¦4=⌋@@@@1@2@@oe@26-8-2013
1000000402540@unknown@formal@none@1@S@The study of ⌊>artificial neural network>⌋s began with ⌊>cybernetic>⌋s researchers, working in the decade before the field AI research was founded.@@@@1@21@@oe@26-8-2013
1000000402550@unknown@formal@none@1@S@In the 1960s ⌊>Frank Rosenblatt>⌋ developed an important early version, the ⌊>perceptron>⌋.@@@@1@12@@oe@26-8-2013
1000000402560@unknown@formal@none@1@S@⌊>Paul Werbos>⌋ developed the ⌊>backpropagation>⌋ algorithm for ⌊>multilayer perceptron>⌋s in 1974, which led to a renaissance in neural network research and ⌊>connectionism>⌋ in general in the middle 1980s.@@@@1@28@@oe@26-8-2013
1000000402570@unknown@formal@none@1@S@Other common network architectures which have been developed include the ⌊>feedforward neural network>⌋, the ⌊>radial basis network>⌋, the Kohonen ⌊>self-organizing map>⌋ and various ⌊>recurrent neural network>⌋s.@@@@1@26@@oe@26-8-2013
1000000402580@unknown@formal@none@1@S@The ⌊>Hopfield net>⌋, a form of attractor network, was first described by ⌊>John Hopfield>⌋ in 1982.@@@@1@16@@oe@26-8-2013
1000000402590@unknown@formal@none@1@S@Neural networks are applied to the problem of ⌊>learning>⌋, using such techniques as ⌊>Hebbian learning>⌋ , ⌊>Holographic associative memory>⌋ and the relatively new field of ⌊>Hierarchical Temporal Memory>⌋ which simulates the architecture of the ⌊>neocortex>⌋.@@@@1@35@@oe@26-8-2013
1000000402600@unknown@formal@none@1@S@⌊=Social and emergent models¦4=⌋@@@@1@4@@oe@26-8-2013
1000000402610@unknown@formal@none@1@S@Several algorithms for ⌊>learning>⌋ use tools from ⌊>evolutionary computation>⌋, such as ⌊>genetic algorithms>⌋, ⌊>swarm intelligence>⌋. and ⌊>genetic programming>⌋.@@@@1@18@@oe@26-8-2013
1000000402620@unknown@formal@none@1@S@⌊=Control theory¦4=⌋@@@@1@2@@oe@26-8-2013
1000000402630@unknown@formal@none@1@S@⌊>Control theory>⌋, the grandchild of ⌊>cybernetics>⌋, has many important applications, especially in ⌊>robotics>⌋.@@@@1@13@@oe@26-8-2013
1000000402640@unknown@formal@none@1@S@⌊=Specialized languages¦4=⌋@@@@1@2@@oe@26-8-2013
1000000402650@unknown@formal@none@1@S@AI researchers have developed several specialized languages for AI research:@@@@1@10@@oe@26-8-2013
1000000402660@unknown@formal@none@1@S@⌊•⌊#⌊>IPL>⌋, one of the first programming languages, developed by ⌊>Alan Newell>⌋, ⌊>Herbert Simon>⌋ and ⌊>J. C. Shaw>⌋.#⌋•⌋@@@@1@17@@oe@26-8-2013
1000000402670@unknown@formal@none@1@S@⌊•⌊#⌊>Lisp>⌋ was developed by ⌊>John McCarthy>⌋ at ⌊>MIT>⌋ in 1958.@@@@1@10@@oe@26-8-2013
1000000402680@unknown@formal@none@1@S@There are many dialects of Lisp in use today.#⌋•⌋@@@@1@9@@oe@26-8-2013
1000000402690@unknown@formal@none@1@S@⌊•⌊#⌊>Prolog>⌋, a language based on ⌊>logic programming>⌋, was invented by ⌊>French>⌋ researchers ⌊>Alain Colmerauer>⌋ and ⌊>Phillipe Roussel>⌋, in collaboration with ⌊>Robert Kowalski>⌋ of the ⌊>University of Edinburgh>⌋.#⌋•⌋@@@@1@27@@oe@26-8-2013
1000000402700@unknown@formal@none@1@S@⌊•⌊#⌊>STRIPS>⌋, a planning language developed at ⌊>Stanford>⌋ in the 1960s.#⌋@@@@1@10@@oe@26-8-2013
1000000402710@unknown@formal@none@1@S@⌊#⌊>Planner>⌋ developed at ⌊>MIT>⌋ around the same time.#⌋•⌋@@@@1@8@@oe@26-8-2013
1000000402720@unknown@formal@none@1@S@AI applications are also often written in standard languages like ⌊>C++>⌋ and languages designed for mathematics, such as ⌊>Matlab>⌋ and ⌊>Lush>⌋.@@@@1@21@@oe@26-8-2013
1000000402730@unknown@formal@none@1@S@⌊=Evaluating artificial intelligence¦3=⌋@@@@1@3@@oe@26-8-2013
1000000402740@unknown@formal@none@1@S@How can one determine if an agent is intelligent?@@@@1@9@@oe@26-8-2013
1000000402750@unknown@formal@none@1@S@In 1950, Alan Turing proposed a general procedure to test the intelligence of an agent now known as the ⌊>Turing test>⌋.@@@@1@21@@oe@26-8-2013
1000000402760@unknown@formal@none@1@S@This procedure allows almost all the major problems of artificial intelligence to be tested.@@@@1@14@@oe@26-8-2013
1000000402770@unknown@formal@none@1@S@However, it is a very difficult challenge and at present all agents fail.@@@@1@13@@oe@26-8-2013
1000000402780@unknown@formal@none@1@S@Artificial intelligence can also be evaluated on specific problems such as small problems in chemistry, hand-writing recognition and game-playing.@@@@1@19@@oe@26-8-2013
1000000402790@unknown@formal@none@1@S@Such tests have been termed ⌊>subject matter expert Turing test>⌋s.@@@@1@10@@oe@26-8-2013
1000000402800@unknown@formal@none@1@S@Smaller problems provide more achievable goals and there are an ever-increasing number of positive results.@@@@1@15@@oe@26-8-2013
1000000402810@unknown@formal@none@1@S@The broad classes of outcome for an AI test are:@@@@1@10@@oe@26-8-2013
1000000402820@unknown@formal@none@1@S@⌊•⌊#⌊∗optimal∗⌋: it is not possible to perform better#⌋@@@@1@8@@oe@26-8-2013
1000000402830@unknown@formal@none@1@S@⌊#⌊∗strong super-human∗⌋: performs better than all humans#⌋@@@@1@7@@oe@26-8-2013
1000000402840@unknown@formal@none@1@S@⌊#⌊∗super-human∗⌋: performs better than most humans#⌋@@@@1@6@@oe@26-8-2013
1000000402850@unknown@formal@none@1@S@⌊#⌊∗sub-human∗⌋: performs worse than most humans#⌋•⌋@@@@1@6@@oe@26-8-2013
1000000402860@unknown@formal@none@1@S@For example, performance at checkers (⌊>draughts>⌋) is optimal, performance at chess is super-human and nearing strong super-human, and performance at many everyday tasks performed by humans is sub-human.@@@@1@28@@oe@26-8-2013
1000000402870@unknown@formal@none@1@S@⌊=Competitions and prizes¦3=⌋@@@@1@3@@oe@26-8-2013
1000000402880@unknown@formal@none@1@S@There are a number of competitions and prizes to promote research in artificial intelligence.@@@@1@14@@oe@26-8-2013
1000000402890@unknown@formal@none@1@S@The main areas promoted are: general machine intelligence, conversational behaviour, data-mining, driverless cars, robot soccer and games.@@@@1@17@@oe@26-8-2013
1000000402900@unknown@formal@none@1@S@⌊=Applications of artificial intelligence¦2=⌋@@@@1@4@@oe@26-8-2013
1000000402910@unknown@formal@none@1@S@Artificial intelligence has successfully been used in a wide range of fields including ⌊>medical diagnosis>⌋, ⌊>stock trading>⌋, ⌊>robot control>⌋, ⌊>law>⌋, scientific discovery and toys.@@@@1@24@@oe@26-8-2013
1000000402920@unknown@formal@none@1@S@Frequently, when a technique reaches mainstream use it is no longer considered artificial intelligence, sometimes described as the ⌊>AI effect>⌋.@@@@1@20@@oe@26-8-2013
1000000402930@unknown@formal@none@1@S@It may also become integrated into ⌊>artificial life>⌋.@@@@1@8@@oe@26-8-2013