Editing Expression (mathematics) (section)

=== Computation ===
{{Main|Computation}}

A [[computation]] is any type of [[arithmetic]] or non-arithmetic [[calculation]] that is "well-defined".<ref>{{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}}</ref> The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the [[1600s (decade)|1600s]],<ref>{{cite book |last=Couturat |first=Louis |title=la Logique de Leibniz a'Après des Documents Inédits |date=1901 |publisher=Paris |isbn=978-0343895099}}</ref> but agreement on a suitable definition proved elusive.<ref name="Davis Davis 2000">{{cite book |last1=Davis |first1=Martin |title=The Universal Computer |last2=Davis |first2=Martin D. |date=2000 |publisher=W. W. Norton & Company |isbn=978-0-393-04785-1}}</ref> A candidate definition was proposed independently by several mathematicians in the 1930s.<ref name="Davis">{{cite book |last=Davis |first=Martin |title=Computability & Unsolvability |date=1982-01-01 |publisher=Courier Corporation |isbn=978-0-486-61471-7}}</ref> The best-known variant was formalised by the mathematician [[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]].<ref>{{Cite news |last=Turing |first=A.M. |year=1937 |title=On Computable Numbers, with an Application to the Entscheidungsproblem |url=http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf |periodical=Proceedings of the London Mathematical Society |pages=230–65 |volume=42 |doi=10.1112/plms/s2-42.1.230 |orig-year=Delivered to the Society November 1936 |series=2}}</ref>{{page needed|reason=Couldn't find string "well-defined" in the paper.|date=October 2024}} Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formed [[Equations|algebraic statements]], and all statements written in modern computer programming languages.<ref name="Davis Davis 2000 p.">{{cite book |last1=Davis |first1=Martin |title=The Universal Computer |last2=Davis |first2=Martin D. |date=2000 |publisher=W. W. Norton & Company |isbn=978-0-393-04785-1 |page=}}</ref>

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]] and [[Busy beaver|the busy beaver game]]. 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.{{efn|The study of non-computable statements is the field of [[hypercomputation]].}}<ref>{{cite journal |author=Davis, Martin |year=2006 |title=Why there is no such discipline as hypercomputation |journal=Applied Mathematics and Computation |volume=178 |issue=1 <!-- Special Issue on Hypercomputation --> |pages=4–7 |doi=10.1016/j.amc.2005.09.066}}</ref> All statements characterised in modern programming languages are well-defined, including [[C++]], [[Python (programming language)|Python]], and [[Java (programming language)|Java]].<ref name="Davis Davis 2000 p." />

Common examples of computation are basic [[arithmetic]] and the [[Execution (computing)|execution]] of computer [[algorithms]]. A [[calculation]] is a deliberate mathematical process that transforms one or more inputs into one or more outputs or ''results''. For example, [[multiplying]] 7 by 6 is a simple algorithmic calculation. Extracting the [[square root]] or the [[cube root]] of a number using mathematical models is a more complex algorithmic calculation.

==== Rewriting ====
Expressions can be computed by means of an ''[[evaluation strategy]].''<ref>{{cite book |last1=Araki |first1=Shota |url=https://books.google.com/books?id=MFMCCwAAQBAJ&pg=PA1 |title=Theory and Practice of Computation |last2=Nishizaki |first2=Shin-ya |date=November 2014 |isbn=978-981-4612-87-6 |page=1 |chapter=Call-by-name evaluation of RPC and RMI calculi |doi=10.1142/9789814612883_0001 |access-date=21 August 2021}}</ref> To illustrate, executing a function call <code>f(a,b)</code> may first evaluate the arguments <code>a</code> and <code>b</code>, store the results in [[Reference (computer science)|references]] or memory locations <code>ref_a</code> and <code>ref_b</code>, then evaluate the function's body with those references passed in. This gives the function the ability to look up the original argument values passed in through dereferencing the parameters (some languages use specific operators to perform this), to modify them via [[Assignment (computer science)|assignment]] as if they were local variables, and to return values via the references. This is the call-by-reference evaluation strategy.<ref>{{cite book |author1=Daniel P. Friedman |title=Essentials of Programming Languages |author2=Mitchell Wand |date=2008 |publisher=[[MIT Press|The MIT Press]] |isbn=978-0262062794 |edition=third |location=Cambridge, MA}}</ref> Evaluation strategy is part of the semantics of the programming language definition. Some languages, such as [[PureScript]], have variants with different evaluation strategies. Some [[declarative language]]s, such as [[Datalog]], support multiple evaluation strategies. Some languages define a [[calling convention]].

In [[rewriting]], a [[reduction strategy]] or rewriting strategy is a relation specifying a rewrite for each object or term, compatible with a given reduction relation. A rewriting strategy specifies, out of all the reducible subterms ([[redex]]es), which one should be reduced (''contracted'') within a term. One of the most common systems involves [[lambda calculus]].