# Computation > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Computation > Markdown URL: https://mediated.wiki/source/Computation.md > Source: https://en.wikipedia.org/wiki/Computation > Source revision: 1349430312 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{short description|Any type of calculation}} A '''computation''' is any type of [arithmetic](/source/arithmetic) or non-arithmetic [calculation](/source/calculation) that is well-defined.{{Cite web |date=2024-10-11 |title=Definition of COMPUTATION |url=https://www.merriam-webster.com/dictionary/computation |access-date=2024-10-12 |website=www.merriam-webster.com |language=en}}{{cite web|title=Computation: Definition and Synonyms from Answers.com|url=http://www.answers.com:80/topic/computation|website=Answers.com|access-date=26 April 2017|archive-url=https://web.archive.org/web/20090222005439/http://www.answers.com/topic/computation|archive-date=22 February 2009|url-status=dead}} Common examples of computation are [mathematical equation](/source/mathematical_equation) solving and the [execution](/source/Execution_(computing)) of computer [algorithms](/source/algorithms). Mechanical or electronic devices (or, [historically](/source/History_of_computing_hardware), people) that perform computations are known as ''[computer](/source/computer)s''. [Computer science](/source/Computer_science) is an academic field that involves the study of computation. == Introduction == The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the [1600s](/source/1600s_(decade)),{{cite book | last=Couturat | first=Louis | title=la Logique de Leibniz a'Après des Documents Inédits | publisher=Paris | date=1901 | isbn=978-0343895099}} but agreement on a suitable definition proved elusive.{{cite book | last1=Davis | first1=Martin | last2=Davis | first2=Martin D. | title=The Universal Computer | publisher=W. W. Norton & Company | date=2000 | isbn=978-0-393-04785-1}} A candidate definition was proposed independently by several mathematicians in the 1930s.{{cite book | last=Davis | first=Martin | title=Computability & Unsolvability | publisher=Courier Corporation | date=1982-01-01 | isbn=978-0-486-61471-7}} The best-known variant was formalised by the mathematician [Alan Turing](/source/Alan_Turing), who defined a well-defined statement or calculation as any statement that could be expressed in terms of the initialisation parameters of a [Turing machine](/source/Turing_machine).{{Cite news | last= Turing | first= A.M. |year = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | orig-year = Delivered to the Society November 1936 | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 | url = https://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf }} Other (mathematically equivalent) definitions include [Alonzo Church](/source/Alonzo_Church)'s ''[lambda-definability](/source/Lambda_calculus)'', [Herbrand](/source/Herbrand)-[Gödel](/source/G%C3%B6del)-[Kleene](/source/Kleene)'s ''[general recursiveness](/source/General_recursive_function)'' and [Emil Post](/source/Emil_Post)'s ''1-definability''. Today, any formal statement or calculation that exhibits this quality of well-definedness is termed '''computable''', while the statement or calculation itself is referred to as a '''computation'''. Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formed [algebraic statements](/source/equations), and all statements written in modern computer programming languages.{{cite book | last1=Davis | first1=Martin | last2=Davis | first2=Martin D. | title=The Universal Computer | publisher=W. W. Norton & Company | date=2000 | isbn=978-0-393-04785-1 | page=}} Despite the widespread uptake of this definition, there are some mathematical concepts that have no well-defined characterisation under this definition. This includes [the halting problem](/source/the_halting_problem) and [the busy beaver game](/source/busy_beaver). It remains an open question as to whether there exists a more powerful definition of 'well-defined' that is able to capture both computable and 'non-computable' statements.The study of non-computable statements is the field of [hypercomputation](/source/hypercomputation).{{cite journal | author=Davis, Martin | title = Why there is no such discipline as hypercomputation | journal = Applied Mathematics and Computation | volume = 178 | issue = 1 | year = 2006 | pages = 4–7 | doi = 10.1016/j.amc.2005.09.066}} Some examples of mathematical statements that are computable include: * All statements characterised in modern programming languages, including [C++](/source/C%2B%2B), [Python](/source/Python_(programming_language)), and [Java](/source/Java_(programming_language)) * All calculations carried by an electronic [computer](/source/computer), [calculator](/source/calculator) or [abacus](/source/abacus) * All calculations carried out on an [analytical engine](/source/analytical_engine) * All calculations carried out on a [Turing Machine](/source/Turing_Machine) * The majority of mathematical statements and calculations given in maths textbooks Some examples of mathematical statements that are ''not'' computable include: * Calculations or statements which are ill-defined, such that they cannot be unambiguously encoded into a Turing machine: ("Paul loves me twice as much as Joe"). * Problem statements that appear to be well-defined, but for which it can be proved that no Turing machine exists to solve them (such as [the halting problem](/source/the_halting_problem)) Computation can be seen as a purely physical process occurring inside a closed [physical system](/source/physical_system) called a [computer](/source/computer). Turing's 1937 proof, ''[On Computable Numbers, with an Application to the Entscheidungsproblem](/source/On_Computable_Numbers%2C_with_an_Application_to_the_Entscheidungsproblem)'', demonstrated that there is a formal equivalence between computable statements and particular physical systems, commonly called [computers](/source/computers). Examples of such physical systems are: [Turing machines](/source/Turing_machines), human mathematicians following strict rules, [digital computer](/source/digital_computer)s, [mechanical computer](/source/mechanical_computer)s, [analog computer](/source/analog_computer)s and others. == Alternative accounts of computation == === The mapping account === An alternative account of computation is found throughout the works of [Hilary Putnam](/source/Hilary_Putnam) and others. [Peter Godfrey-Smith](/source/Peter_Godfrey-Smith) has dubbed this the "simple mapping account."{{Citation|last=Godfrey-Smith|first=P.|year=2009|title=Triviality Arguments against Functionalism|journal=Philosophical Studies|volume=145|issue=2|pages=273–95|doi=10.1007/s11098-008-9231-3|s2cid=73619367 }} [Gualtiero Piccinini's](/source/Gualtiero_Piccinini) summary of this account states that a physical system can be said to perform a specific computation when there is a mapping between the state of that system and the computation such that the "microphysical states [of the system] mirror the state transitions between the computational states."{{cite book|last=Piccinini|first=Gualtiero|title=Physical Computation: A Mechanistic Account|place=Oxford|publisher=Oxford University Press|year=2015|page=18|isbn=9780199658855}} === The semantic account === Philosophers such as [Jerry Fodor](/source/Jerry_Fodor){{Citation | last = Fodor | first = J. A. | year = 1986 | title = The Mind-Body Problem | journal = Scientific American | volume = 244 | issue = January 1986}} have suggested various accounts of computation with the restriction that [semantic](/source/semantic) content be a necessary condition for computation (that is, what differentiates an arbitrary physical system from a computing system is that the operands of the computation represent something). This notion attempts to prevent the logical abstraction of the mapping account of [pancomputationalism](/source/digital_physics), the idea that everything can be said to be computing everything. === The mechanistic account === [Gualtiero Piccinini](/source/Gualtiero_Piccinini) proposes an account of computation based on [mechanical philosophy](/source/mechanical_philosophy). It states that physical computing systems are types of mechanisms that, by design, perform physical computation, or the manipulation (by a functional mechanism) of a "medium-independent" vehicle according to a rule. "Medium-independence" requires that the property can be instantiated{{clarify|date=February 2022}} by multiple realizers{{clarify|date=February 2022}} and multiple mechanisms, and that the inputs and outputs of the mechanism also be [multiply realizable](/source/Multiple_realizability). In short, medium-independence allows for the use of physical variables with properties other than voltage (as in typical digital computers); this is imperative in considering other types of computation, such as that which occurs in the [brain](/source/brain) or in a [quantum computer](/source/quantum_computer). A rule, in this sense, provides a mapping among inputs, outputs, and internal states of the physical computing system.{{cite book | last = Piccinini | first = Gualtiero | title = Physical Computation: A Mechanistic Account | place = Oxford | publisher = Oxford University Press | year = 2015 | page = 10 | isbn = 9780199658855}} == Mathematical models == {{Main|Model of computation}} In the [theory of computation](/source/theory_of_computation), a diversity of mathematical models of computation has been developed. Typical mathematical [models of computers](/source/Model_of_computation) are the following: * State models including [Turing machine](/source/Turing_machine), [pushdown automaton](/source/pushdown_automaton), [finite-state automaton](/source/finite-state_automaton), and [PRAM](/source/Parallel_random_access_machine) * Functional models including [lambda calculus](/source/lambda_calculus) * Logical models including [logic programming](/source/logic_programming) * Concurrent models including [actor model](/source/actor_model) and [process calculi](/source/process_calculi) Giunti calls the models studied by computation theory ''computational systems,'' and he argues that all of them are mathematical [dynamical system](/source/dynamical_system)s with discrete time and discrete state space.{{cite book|last=Giunti|first=Marco|title=Computation, Dynamics, and Cognition|place=New York|publisher=Oxford University Press|year=1997|isbn=978-0-19-509009-3}}{{rp|ch.1}} He maintains that a computational system is a complex object which consists of three parts. First, a mathematical dynamical system DS with discrete time and discrete state space; second, a computational setup H=\left(F, B_F\right), which is made up of a theoretical part F, and a real part B_F; third, an interpretation I_{DS,H}, which links the dynamical system DS with the setup H.{{Citation|last=Giunti|first=Marco|year=2017|title=What is a Physical Realization of a Computational System?|journal=Isonomia -- Epistemologica|volume=9|pages=177–92|issn=2037-4348|url=https://www.researchgate.net/publication/319631506}}{{rp|pp.179–80}} == See also == * [Computationalism](/source/Computationalism) * [Computational problem](/source/Computational_problem) * [Computability theory](/source/Computability_theory) * [Hypercomputation](/source/Hypercomputation) * [Limits of computation](/source/Limits_of_computation) * [Numerical computation](/source/Numerical_computation) == Notes == {{reflist|group=note}} == References == {{Reflist}} Category:Theoretical computer science Category:Computability theory --- Adapted from the Wikipedia article [Computation](https://en.wikipedia.org/wiki/Computation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Computation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.