Editing Expression (mathematics) (section)

==Variables and evaluation==
{{anchor|evaluation}} In [[elementary algebra]], a [[Variable (mathematics)|''variable'']] in an expression is a [[Letter (alphabet)|letter]] that represents a number whose value may change. To ''evaluate an expression'' with a variable means to find the value of the expression when the variable is [[Assignment (computer science)|assigned]] a given number. Expressions can be ''evaluated'' or ''simplified'' by replacing [[Operation (mathematics)|operations]] that appear in them with their result, or by combining [[Like terms|like-terms]].<ref>{{Cite web |last1=Marecek |first1=Lynn |last2=Mathis |first2=Andrea Honeycutt |date=2020-05-06 |title=1.1 Use the Language of Algebra - Intermediate Algebra 2e {{!}} OpenStax |url=https://openstax.org/books/intermediate-algebra-2e/pages/1-1-use-the-language-of-algebra#term-00018 |access-date=2024-10-14 |website=openstax.org |language=English}}</ref>

For example, take the expression <math>4 x^2 + 8</math>; it can be evaluated at {{Math|1=''x'' = 3}} in the following steps:

<math display="inline">4(3)^2 + 8</math>, (replace x with 3)

<math>4 \cdot (3 \cdot 3 ) + 8</math> (use definition of [[Exponentiation|exponent]])

<math>4 \cdot 9 + 8</math> (evaluate inner multiplication)

<math>36 + 8</math> (evaluate remaining multiplication)

<math>44</math> (evaluate addition)

A ''term'' is a constant or the [[Product (mathematics)|product]] of a constant and one or more variables. Some examples include <math>7, \; 5x, \; 13x^2y, \; 4b </math> The constant of the product is called the [[coefficient]]. Terms that are either constants or have the same variables raised to the same powers are called ''[[like terms]]''. If there are like terms in an expression, one can simplify the expression by combining the like terms. One adds the coefficients and keeps the same variable.

<math>4x + 7x +2x = 13x</math>

Any variable can be classified as being either a [[free variable]] or a [[bound variable]]. For a given combination of values for the free variables, an expression may be evaluated, although for some combinations of values of the free variables, the value of the expression may be [[Undefined (mathematics)|undefined]]. Thus an expression represents an [[Operation (mathematics)|operation]] over constants and free variables and whose output is the resulting value of the expression.<ref name="Model Theory">{{cite book |author1=C.C. Chang |author1-link=Chen Chung Chang |title=Model Theory |author2=H. Jerome Keisler |author2-link=H. Jerome Keisler |publisher=North Holland |year=1977 |series=Studies in Logic and the Foundation of Mathematics |volume=73}}; here: Sect.1.3</ref>

For a non-formalized language, that is, in most mathematical texts outside of [[mathematical logic]], for an individual expression it is not always possible to identify which variables are free and bound. For example, in <math display="inline">\sum_{i < k} a_{ik}</math>, depending on the context, the variable <math display="inline">i</math> can be free and <math display="inline">k</math> bound, or vice-versa, but they cannot both be free. Determining which value is assumed to be free depends on context and [[Semantics of logic|semantics]].<ref>Sobolev, S.K. (originator). [http://encyclopediaofmath.org/index.php?title=Free_variable&oldid=46988 ''Free variable'']. ''[[Encyclopedia of Mathematics]]''. [[Springer Publishing|Springer]]. {{ISBN|1402006098}}.</ref>

=== Equivalence ===
{{Main|Identity (mathematics)}}

An expression is often used to define a [[Function (mathematics)|function]], or denote [[Function composition|compositions]] of functions, by taking the variables to be [[Argument of a function|arguments]], or inputs, of the function, and assigning the output to be the evaluation of the resulting expression.<ref name="Codd19702">{{cite journal |last1=Codd |first1=Edgar Frank |date=June 1970 |title=A Relational Model of Data for Large Shared Data Banks |url=https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf |url-status=live |journal=Communications of the ACM |volume=13 |issue=6 |pages=377–387 |doi=10.1145/362384.362685 |s2cid=207549016 |archive-url=https://web.archive.org/web/20040908011134/http://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf |archive-date=2004-09-08 |access-date=2020-04-29 |authorlink=Edgar F. Codd}}</ref> For example, <math>x\mapsto x^2+1</math> and <math>f(x) = x^2 + 1</math>  define the function that associates to each number its [[Square function|square]] plus one. An expression with no variables would define a [[constant function]]. In this way, two expressions are said to be equivalent if, for each combination of values for the free variables, they have the same output, i.e., they represent the same function.<ref>Equation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Equation&oldid=32613</ref><ref>Pratt, Vaughan, "Algebra", The Stanford Encyclopedia of Philosophy (Winter 2022 Edition), Edward N. Zalta & Uri Nodelman (eds.), URL: https://plato.stanford.edu/entries/algebra/#Laws</ref> The equivalence between two expressions is called an [[Identity (mathematics)|identity]] and is sometimes denoted with <math>\equiv.</math>

For example, in the expression <math display="inline">\sum_{n=1}^{3} (2nx),</math> the variable {{math|''n''}} is bound, and the variable {{math|''x''}} is free. This expression is equivalent to the simpler expression {{math|12 ''x''}}; that is <math display="block">\sum_{n=1}^{3} (2nx)\equiv 12x.</math> The value for {{math|1=''x'' = 3}} is 36, which can be denoted <math display="block">\sum_{n=1}^{3} (2nx)\Big|_{x=3}= 36.</math>

=== Polynomial evaluation ===
{{Main|Polynomial evaluation}}
A polynomial consists of variables and [[coefficient]]s, that involve only the operations of [[addition]], [[subtraction]], [[multiplication]] and [[exponentiation]] to [[nonnegative integer]] powers, and has a finite number of terms. The problem of [[polynomial evaluation]] arises frequently in practice. In [[computational geometry]], polynomials are used to compute function approximations using [[Taylor polynomials]]. In [[cryptography]] and [[hash table]]s, polynomials are used to compute [[K-independent hashing|''k''-independent hashing]].

In the former case, polynomials are evaluated using [[floating-point arithmetic]], which is not exact. Thus different schemes for the evaluation will, in general, give slightly different answers. In the latter case, the polynomials are usually evaluated in a [[finite field]], in which case the answers are always exact.

For evaluating the [[univariate polynomial]] <math display="inline">a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0,</math> the most naive method would use <math>n</math> multiplications to compute <math>a_nx^n</math>, use <math display="inline">n-1</math> multiplications to compute <math>a_{n-1} x^{n-1}</math> and so on for a total of <math display="inline">\frac{n(n+1)}{2}</math> multiplications and <math>n</math> additions. Using better methods, such as [[Horner's rule]], this can be reduced to <math>n</math> multiplications and <math>n</math> additions. If some preprocessing is allowed, even more savings are possible.

=== 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]].