Definition: expressions that can be evaluated versus those that can't

Question

Suppose I have an expression $y + f(x)$, and I know $y \in \mathbb R, x \in X$ and $f$ is an arbitrary function from $X$ to the reals.

If I know $y$ and $x$ but don't know $f$, I can't evaluate the expression $y + f(x)$. At least, not completely.

But once I know $f$, (say $f(z) = z^2$), then I can evaluate the expression $y + f(x)$.

Is there a name for the difference between these two circumstances?

Answer 1

The following is informal, but sufficient for my purposes.

The key thing to understand is the difference between an expression and a value. Values are the atomic elements under consideration. Expressions are a combination of values, functions, and other expressions (or whatever a given grammar allows). All values are expressions.

For the case that I'm interested in, reals are values, and functions are not.

Examples of values: 1, 2, $\pi$
Examples of expressions: 1, 2, $\pi$, $x$, $x + 2$, $y + f(x)$

Expressions can be evaluated, resulting in either a value, or a new expression. If we bind the value 3 to $x$, for example, we can substitute 3 for $x$ wherever we see it in an expression:

$2 \to 2$
$x \to 3$
$x + 2 \to 3 + 2 \to 5$
$y + f(3)$

If the result of this evaluation is a value, we say that evaluation is complete. In some cases, it isn't possible to reduce an expression any further given the existing definitions:

$y + f(x) \to y + f(3)$

Here the result is still an expression. In other cases, evaluation of the expression never terminates. Let $f(x) := g(x)$, $g(x) := h(x)$, $h(x) := f(x)$.

$f(x) \to g(x) \to h(x) \to f(x) \to ...$

I was looking for a definition that meant an expression that can be evaluated to completion, i.e. an expression that can be reduced to a value rather than an expression. I believe the appropriate term is a closed-form expression.

A closed-form expression contains no free (unbound) variables. This means that all of the elements of the expression have been defined, and provided there are no problems with infinite recursion, the expression can evaluated by a Turing machine in a finite number of steps.

A reference.

Answer 2

Here is the terminology from predicate logic. An expression such as $x + f(y)$ is called a term. In this particular term there are several free variables (e.g. $x$ and $y$ at least, and also $f$ if we view that as a variable for a function). If we replace the free variables by constants (also known sometimes as parameters), so that no free variables remain, the term is then a closed term. A term that has one or more free variables is called an open term.

In the usual framework of predicate logic, each closed term with parameters from a model $M$ denotes a particular element of the model $M$. Not only do we need the model to have parameters to substitute for the variables, we also need the model to give meaning to symbols such as $+$ that appear in the term.