Church–Turing thesis  

From The Art and Popular Culture Encyclopedia

(Difference between revisions)
Jump to: navigation, search
Revision as of 07:08, 7 June 2016
Jahsonic (Talk | contribs)

← Previous diff		 Current revision
Jahsonic (Talk | contribs)

Line 1: Line 1:
{{Template}} {{Template}}
-A '''physical symbol system''' (also called a [[formal system]]) takes physical patterns (symbols), combining them into structures (expressions) and manipulating them (using processes) to produce new expressions.+In [[Computability theory (computation)|computability theory]], the '''Church–Turing thesis''' (also known as the '''Turing–Church thesis''', the '''Church–Turing conjecture''', '''Church's thesis''', '''Church's conjecture''', and '''Turing's thesis''') is a [[hypothesis]] about the nature of [[computable function]]s. It states that a [[function (mathematics)|function]] on the [[natural numbers]] is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a [[Turing machine]]. The thesis is named after American mathematician [[Alonzo Church]] and the British mathematician [[Alan Turing]].
- +Before the precise definition of computable function, mathematicians often used the informal term [[effectively calculable]] to describe functions that are computable by paper-and-pencil methods.
-The '''physical symbol system hypothesis''' ('''PSSH''') is a position in the [[philosophy of artificial intelligence]] formulated by [[Allen Newell]] and [[Herbert A. Simon]]. They wrote:+
- +
-:"A physical symbol system has the [[sufficient|necessary and sufficient means]] for general intelligent action."+
- +
-The idea has philosophical roots in [[Hobbes]] (who claimed reasoning was "nothing more than reckoning"), [[Gottfried Wilhelm Leibniz|Leibniz]] (who attempted to create a logical calculus of all human ideas), [[David Hume|Hume]] (who thought perception could be reduced to "atomic impressions") and even [[Immanuel Kant|Kant]] (who analyzed all experience as controlled by formal rules). The latest version is called the [[computational theory of mind]], associated with philosophers [[Hilary Putnam]] and [[Jerry Fodor]].+
- +
-The hypothesis has been criticized strongly by various parties, but is a core part of AI research. A common critical view is that the hypothesis seems appropriate for higher-level intelligence such as playing chess, but less appropriate for commonplace intelligence such as vision. A distinction is usually made between the kind of high level symbols that directly correspond with objects in the world, such as <nowiki><dog></nowiki> and <nowiki><tail></nowiki> and the more complex "symbols" that are present in a machine like a [[neural network]].+
- +
-== Examples ==+
-Examples of physical symbol systems include:+
-* [[Formal logic]]: the symbols are words like "and", "or", "not", "for all x" and so on. The expressions are statements in formal logic which can be true or false. The processes are the rules of logical deduction.+
-* [[Elementary algebra|Algebra]]: the symbols are "+", "×", "''x''", "''y''", "1", "2", "3", etc. The expressions are equations. The processes are the rules of algebra, that allow one to manipulate a mathematical expression and retain its truth.+
-* A [[digital computer]]: the symbols are zeros and ones of computer memory, the processes are the operations of the [[CPU]] that change memory.+
-* [[Chess]]: the symbols are the pieces, the processes are the legal chess moves, the expressions are the positions of all the pieces on the board.+
- +
-The physical symbol system hypothesis claims that both of these are also examples of physical symbol systems:+
-* Intelligent human thought: the symbols are encoded in our brains. The expressions are [[thought]]s. The processes are the mental operations of thinking.+
-* A running [[artificial intelligence]] program: The symbols are data. The expressions are more data. The processes are programs that manipulate the data.+
- +
-== Arguments in favor of the physical symbol system hypothesis ==+
-=== Newell and Simon ===+
-Two lines of evidence suggested to [[Allen Newell]] and [[Herbert A. Simon]] that "symbol manipulation" was the essence of both human and machine intelligence: the development of [[artificial intelligence]] programs and psychological experiments on human beings.+
- +
-First, in the early decades of AI research there were a number of very successful programs that used high level symbol processing, such as [[Allen Newell|Newell]] and [[Herbert A. Simon]]'s [[General Problem Solver]] or [[Terry Winograd]]'s [[SHRDLU]]. [[John Haugeland]] named this kind of AI research "Good Old Fashioned AI" or [[GOFAI]]. [[Expert system]]s and [[logic programming]] are descendants of this tradition. The success of these programs suggested that symbol processing systems could simulate any intelligent action.+
- +
-And second, [[Psychology|psychological]] experiments carried out at the same time found that, for difficult problems in logic, planning or any kind of "puzzle solving", people used this kind of symbol processing as well. AI researchers were able to simulate the step by step problem solving skills of people with computer programs. This collaboration and the issues it raised eventually would lead to the creation of the field of [[cognitive science]]. (This type of research was called "[[cognitive simulation]].") This line of research suggested that human problem solving consisted primarily of the manipulation of high level symbols.+
- +
-=== Turing completeness ===+
-In Newell and Simon's arguments, the "symbols" that the hypothesis is referring to are physical objects that represent things in the world, symbols such as <nowiki><dog></nowiki> that have a recognizable [[Meaning (semiotics)|meaning]] or [[denotation]] and can be [[compositionality|composed]] with other symbols to create more complex symbols.+
- +
-However, it is also possible to interpret the hypothesis as referring to the simple abstract 0s and 1s in the memory of a digital computer or the stream of 0s and 1s passing through the perceptual apparatus of a robot. These are, in some sense, symbols as well, although it is not always possible to determine exactly what the symbols are standing for. In this version of the hypothesis, no distinction is being made between "symbols" and "signals", as [[David Touretzky]] and [[Dean Pomerleau]] explain.+
- +
- +
-Under this interpretation, the physical symbol system hypothesis asserts merely that intelligence can be ''digitized''. This is a weaker claim. Indeed, [[David Touretzky|Touretzky]] and [[Dean Pomerleau|Pomerleau]] write that if symbols and signals are the same thing, then "[s]ufficiency is a given, unless one is a dualist or some other sort of mystic, because physical symbol systems are [[Turing completeness|Turing-universal]]." The widely accepted [[Church&ndash;Turing thesis]] holds that any [[Turing completeness|Turing-universal]] system can simulate any conceivable process that can be digitized, given enough time and memory. Since any digital computer is [[Turing completeness|Turing-universal]], any digital computer can, in theory, simulate anything that can be digitized to a sufficient level of precision, including the behavior of intelligent organisms. The necessary condition of the physical symbol systems hypothesis can likewise be finessed, since we are willing to accept almost any signal as a form of "symbol" and all intelligent biological systems have signal pathways.+
- +
-== Criticism ==+
- +
-[[Nils Nilsson (researcher)|Nils Nilsson]] has identified four main "themes" or grounds in which the physical symbol system hypothesis has been attacked.+
-#The "erroneous claim that the [physical symbol system hypothesis] lacks [[symbol grounding]]" which is presumed to be a requirement for general intelligent action.+
-#The common belief that AI requires non-symbolic processing (that which can be supplied by a connectionist architecture for instance).+
-#The common statement that the brain is simply not a computer and that "computation as it is currently understood, does not provide an appropriate model for intelligence".+
-#And last of all that it is also believed in by some that the brain is essentially mindless, most of what takes place are chemical reactions and that human intelligent behaviour is analogous to the intelligent behaviour displayed for example by ant colonies.+
- +
-=== Dreyfus and the primacy of unconscious skills ===+
- +
-[[Hubert Dreyfus]] attacked the necessary condition of the physical symbol system hypothesis, calling it "the psychological assumption" and defining it thus:+
-* ''The mind can be viewed as a device operating on bits of information according to formal rules.'' Dreyfus refuted this by showing that human intelligence and expertise depended primarily on unconscious instincts rather than conscious symbolic manipulation. Experts solve problems quickly by using their intuitions, rather than step-by-step trial and error searches. Dreyfus argued that these unconscious skills would never be captured in formal rules.+
- +
-=== Searle and his Chinese room ===+
- +
-[[John Searle]]'s [[Chinese room]] argument, presented in 1980, attempted to show that a program (or any physical symbol system) could not be said to "understand" the symbols that it uses; that the symbols have no meaning for the machine, and so the machine can never be truly intelligent.+
- +
-=== Brooks and the roboticists ===+
-In the sixties and seventies, several laboratories attempted to build [[robot]]s that used symbols to represent the world and plan actions (such as the [[Stanford Cart]]). These projects had limited success. In the middle eighties, [[Rodney Brooks]] of [[MIT]] was able to build robots that had superior ability to move and survive without the use of symbolic reasoning at all. Brooks (and others, such as [[Hans Moravec]]) discovered that our most basic skills of motion, survival, perception, balance and so on did not seem to require high level symbols at all, that in fact, the use of high level symbols was more complicated and less successful.+
- +
-In a 1990 paper [http://people.csail.mit.edu/brooks/papers/elephants.pdf Elephants Don't Play Chess], robotics researcher [[Rodney Brooks]] took direct aim at the physical symbol system hypothesis, arguing that symbols are not always necessary since "the world is its own best model. It is always exactly up to date. It always has every detail there is to be known. The trick is to sense it appropriately and often enough."+
- +
-=== Connectionism ===+
- +
-=== Embodied philosophy ===+
- +
-[[George Lakoff]], [[Mark Turner (cognitive scientist)|Mark Turner]] and others have argued that our abstract skills in areas such as [[mathematic]]s, [[ethic]]s and [[philosophy]] depend on unconscious skills that derive from the body, and that conscious symbol manipulation is only a small part of our intelligence.+
- +
-== See also ==+
-* [[Artificial intelligence, situated approach]]+
- +
 +==See also==
 +*[[Abstract machine]]
 +*[[Church's thesis (constructive mathematics)|Church's thesis in constructive mathematics]]
 +*[[Church–Turing–Deutsch principle]], which states that every [[physical process]] can be simulated by a universal computing device
 +*[[Computability logic]]
 +*[[Computability theory (computation)|Computability theory]]
 +*[[Decidability (logic)|Decidability]]
 +*[[Hypercomputer]]
 +*[[Model of computation]]
 +*[[Oracle (computer science)]]
 +*[[Super-recursive algorithm]]
{{GFDL}} {{GFDL}}

Current revision

Related e

Wikipedia
Wiktionary
Shop

Featured:

In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods.

[edit]

See also


Unless indicated otherwise, the text in this article is either based on Wikipedia article "Church–Turing thesis" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Retrieved from "http://artandpopularculture.com/Church%E2%80%93Turing_thesis"
Personal tools
Metas