# 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?

• Say we want to graph the equation $y=x^2$. If we are binding a single value to $x$ that it keeps, which forces $y$ to have a single value it keeps, then where does the graph come from? – John Habert Feb 4 '14 at 17:47
• Wrong premise. A variable represents usually some amount that is... variable! – Martín-Blas Pérez Pinilla Feb 4 '14 at 17:49
• Here is something that should interest you: en.wikipedia.org/wiki/Semantics_(computer_science) – Denis Feb 4 '14 at 17:52
• "... a variable is "mutable". It is like a box with a name..." Exactly ! A variable is a name. So, when you "work with" the syntax, you must use syntax rules for manipulating it. When you use it to "speak of" (semantics), you must give it a denotation (an object to refer to). When you write (in number theory) $2 \times x = x + x$, the $x$ can denote any number. – Mauro ALLEGRANZA Feb 4 '14 at 18:07
• According to a great philosopher and logician, Bertand Russell (1908) . "a variable is a symbol which is to have one of a certain set of values, without its being decided which one. It does not have first one value of a set and then another; it has at all times some value of the set, where, so long as we do not replace the variable by a constant, the 'some' remains unspecified." – Mauro ALLEGRANZA Feb 4 '14 at 19:50

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.

• If I understand well your explanation, I agree with you that the "correct" meaning of $x = x+1$ in computer programming is not an "identity". If I remember well, someone prefer to avoid this sloppiness and write instead $x := x+1$, that is "let we assign to x ..." You are right also in pointing at "context"; often we omit the context, but in $2 \times x = x+x$ it is "strictly forbidden" to assign to the first $x$ the value $1$ and to the second one the value $2$, because in the "context" of the entire identity the $x$ is universally quantified. – Mauro ALLEGRANZA Feb 4 '14 at 19:56
• Lazy evaluation gives us a means of simulating theses (potentially ) infinite sequences. This type of data structure is called a stream. – Baby Dragon Feb 25 '14 at 15:05

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 :

the box does not change, his content has changed.

• Very well documented and an interesting read. But I do not understand the definition of well-formed formula, nor its application to the ensuing argumentation. Is it the fact that "variables" are "something that appears in wffs"? Also, when Mana requires that variables be assigned simultaneously, he is proposing an ideal model of computation, right? – logc Feb 25 '14 at 16:51
• @logc - About wff, Manna use the standard definition of math log textbooks: I've copied only the passage related to variables. He introduces Terms: "Each individual constant $a_i$ and each individual variable $x_i$ is a term"; then atomic formulas like : "if $t_1$ and $t_2$ are terms, then $(t_1 = t_2)$ is an atf. Finally, he introduces well-formed formulas (wffs) built up with connectives ($\lnot A$, $A \lor B$) and quantifiers ($\forall$ and $\exists$), and here we have : "If $v_i$ is a variable and $A$ is a wff, then $\forall v_i(A)$ and ..." is a wff". 1/2 – Mauro ALLEGRANZA Feb 25 '14 at 17:04
• @logc - And yes, the "ideal model" is used for the purpose of "describe methods for verifying computer programs. [...] In order to discuss programs and their correctness we must specify a programming language. We shall consider flowchart programs without arrays". 2/2 – Mauro ALLEGRANZA Feb 25 '14 at 17:06

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 + 1


will 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.

• Thanks - I apologize for my "old style" computer science examples, but when I've studied "some" computer scince at university, Manna's textbook was pretty new ... – Mauro ALLEGRANZA Feb 25 '14 at 16:55
• @MauroALLEGRANZA - No need for apologies, my math is super rusty quite some years after college. You are right that Haskell is a "newcomer" from the early '90s, but Prolog was already around when Manna published that book. :) – logc Feb 25 '14 at 17:27