How is a "computer variable" defined mathematically?
Variables used in maths formulae are not the same that those of computing programs. Maths variables can be bound to a given value only once, and then keep that value.
On the other hand, a programming variable is "mutable". It is like a box with a name, to which we can change its value over time.
How can a mutable programming variable be mathematically defined?
$\endgroup$ 173 Answers
$\begingroup$From the EDITOR'S NOTES to David Hilbert & Wilhelm Ackermann, Principles of Mathematical Logic (2nd ed : 1937; english transl : 1950), page 168 :
The distinction between variables and constants [...] is sometimes difficult to grasp clearly. It is not always understood that a constant, like a variable, is a symbol, a linguistic expression, but with the important distinction that a constant has a fixed designation, which remains unaltered throughout the discussion in which the constant appears; whereas a variable designates ambiguously, so to speak, assuming anyone of a range of values. It would, however, be a grave error to suppose that the distinction between variables and constants reflects a corresponding distinction in the domain of objects to which the variables and constants alike refer. Thus to assert with reference, say, to real number theory that the variables "$x$" and "$y$" designate variable numbers, whereas such constants as "$2$" and "$\pi$" designate constant numbers, would be nonsense; or at least there is no known intelligible theory which could accommodate so odd a notion as that of a variable number.
In mathematical logic, variables are mainly used with quantifiers.
In order to compare with computer science, we can see Zohar Manna, Mathematical theory of computation (1974), where the language of predicate calculus [page 77-on] is used for the description of programs.
We have [page 82] the usual definition of well-formed formula :
(c) If $v_i$ is a variable and $A$ is a wff, then $\forall v_i A$ and $\exists v_i A$ are wffs.
Then he use variables to formalize flowchart programs [page 161] :
We distinguish among three types of variables (grouped as three vectors): (1) an input vector $\overline{x} = (x_l, x_2,. . . , x_a)$, which consists of the given input values and therefore never changes during computation; (2) a program vector $\overline{y} = (y_1, y_2, ..., y_b)$, which is used as temporary storage during computation; and (3) an output vector $\overline{z} = (z_1, z_2, ... z_c)$, which yields the output values whe computation terminates.
Finally, the assignment function is introduced [page 164] :
Note that $(y_1, y_2) \leftarrow (0, x_1)$ means that $y_1$ is replaced by $0$ and $y_2$ is replaced by $x_1$ [...]. In general, we shall use the notation $(y_1, y_2, ..., y_n) \leftarrow (g_1(\overline{x}, \overline{y}), ... g_n(\overline{x}, \overline{y}))$ to indicate that the variables $y_i, 1 \le i \le n$, are replaced by $g_i(\overline{x}, \overline{y})$ simultaneously; that is, all the $g_i$'s are evaluated before any $y_i$ is changed. For example, if $y_1 = 1$ and $y_2 = 2$, the assignment $(y_1, y_2) \leftarrow (y_1 + 1, y_1 + y_2)$ yields $y_2 = 3$, not $y_2 = 4$.
In computer languages, the instruction $x=x+1$ (if allowed) is not a numerical identity; there are no reasonable meanings of the concept "number" that may make sense of a statement like : "a number is equal to itself plus $1$".
In the context of computer languages, when we use the instruction
$x_1 \leftarrow x_1 + 1$
the symbol $x_1$ is not a variable: it is a constant.
It is the name of a storage location (memory array or register), like the square on the tape of a Turing machine, and the simple statement above is a "complex" instruction specifiying the following operation :
i) read the content of the storage location ("cell") $x_1$, (say $n$);
ii) add $1$ to that number;
iii) erase the content of the cell $x_1$;
iv) write the number $n+1$ into the cell $x_1$.
During the context of the execution of the program, the name $x_1$ will not change its denotation (the "cell").
The above process can be described as follows: we have a box with six eggs inside and we pull out the eggs from the box. Then we add a new egg and finally we put the seven eggs in the box :
$\endgroup$ 3 $\begingroup$the box does not change, his content has changed.
Apparently what you are after is the fact that we cannot have an equality $x=x+1$ in math, whereas assignments $x=x+1$ are ubiquitous in programs. The closest thing to this "we" have is a variable substitution maybe. Of course, math variables are also "local" in some sense, i.e. I might write "let $p$ be an even integer" and after finishing the corresponding argument start a new one with "let $p$ be any prime" - and the reader should not assume that both restrictions hold (which would force $p=2$). But within an argument, $p$ is unchanged - though it perhaps doesn't even have a fixed value at all: If I let $p$ be an even integer, it is an arbitrary even integer; it could be $42$ or $666$, but neither is it any of these possibilities specifically (except e.g. during a refined case-distinction in a sub-argument) nor does it therefore ever change its "value".
But what we really do not have is the temporal aspect of running computer programs per se. Whenever we have the urge to emulate this, we use sequences $(x_n)_{n\in\mathbb N}$ or functions $f(t)$ where you may perhaps interpret $x_n$ as the "value of $x$ after $n$ steps" or $f(t)$ as the "value of $f$ at time $t$"; but keep in mind that we may deprive you of this interpretation by using other index sets than $\mathbb N$ / other domains than $\mathbb R$. Specifically - and this may provoke some "actual vs. potential infinity" debates - one should consider such a sequence (or function) as given as a complete object - even if a recursive definition suggests that we compute (or even define) it step by step; if one didn't do so, transcending to larger infinities than countable (or in fact getting there in the first place) would be hindered.
A whole different story are random variables. The programmer's idea of invoking rand() is very different form the probability theorists idea of random variables being measurable functions on suitable measure spaces. While a computer random variable assumes values again and again, a math random variable never assumes a value, it only has a probability to assume a value within certain sets.
Please note that assignment of "computer variables" happens in some programming languages - namely, those of the imperative programming paradigm, such as C or Java. In other programming paradigms this is explicitly forbidden - e.g., functional or logic programming.
In Haskell or Prolog, a statement of the form
x = x + 1will lead to a compiler error. Variables are immutable, just like those in mathematics. This leads naturally to an emphasis in functions that transform input into output, not in data that is rewritten from input into output. (And many more advantages in the sense of approaching programming to mathematics, such as functions that return always the same output given the same input).
Probably the confusion arises from using the same words in both fields for different things. A variable in programming, as you have noted, is "a box with a name". More formally, it is a reference to an address in memory. What this part of memory holds, we cannot know from the variable - we can know some things, such as its length if it is a typed variable, but not the actual value unless we look at the memory contents.
"Computer variables" could be compared to an index within a vector or matrix. If we regard the memory as a vector $m$, then a variable is its $i$-th element
$$ \overrightarrow{m}_{i}, 0 < i < \left| \overrightarrow{m} \right| $$
This supposes that all variables need precisely one memory element to be held. This is probably not true, since a double-precision number requires twice the memory as a float. So, a computer variable could be compared to a range of elements within a vector.
$$ [\overrightarrow{m}_{i}, \overrightarrow{m}_{j}] , 0 < i < j < \left| \overrightarrow{m} \right| $$
You could imagine different states of memory as different vectors $\overrightarrow{m}'$, $\overrightarrow{m}''$ ... Indexing those different vectors at the same indices $i$, $j$ (hence the same "computer variable") would yield different elements each time.
$\endgroup$ 2
