For each natural number d we consider a finite structure M_{d} whose
universe is the set of all 0,1-sequence of length n=2^{d}, each
representing a natural number in the set \lbrace 0,1,...,2^{n}-1\rbrace in binary form.
The operations included in the structure are the
constants 0,1,2^{n}-1,n, multiplication and addition modulo 2^{n},
the unary function \min\lbrace 2^{x}, 2^{n}-1\rbrace, the binary
functions \lfloor x/y\rfloor , \max(x,y), \min(x,y), and the
boolean vector operations AND, OR, NEGATION defined on 0,1
sequences of length n by performing the operations on all components
simultaneously. These are essentially the arithmetic operations that
can be performed on a RAM by a single instruction. We show that there
exists a term (that is, an algebraic expression) F(x,y) built up from
the mentioned operations, with the only free variables x,y, such that
for all terms G(y), which is also built up from the mentioned
operations, the following holds. For infinitely many positive integers
d, there exists an a\in M_{d} such that the following two statements
are not equivalent: (i) M_{d} \models \exists x, F(x,a) , (ii)
M_{d}\models G(a)=0. In other words, the question whether an
existential statement, depending on the parameter a\in M_{d} is true
or not, cannot be decided by evaluating an algebraic expression at a.
We also show that this theorem remains true if we include the operation
\min \lbrace x^{y}, 2^{n}-1 \rbrace into the structure M_{d}. A
general theorem is proved as well which describes sufficient conditions
for a set of operations on a sequence of structures K_{d}, d=1,2,...
which guarantees that the analogue of the mentioned theorem holds for
the structure K_{d} too.
For each natural number d we consider a finite structure M_{d} whose
universe is the set of all 0,1-sequence of length n=2^{d}, each
representing a natural number in the set \lbrace 0,1,...,2^{n}-1\rbrace in binary form.
The operations included in the structure are the
constants 0,1,2^{n}-1,n, multiplication and addition modulo 2^{n},
the unary function \min\lbrace 2^{x}, 2^{n}-1\rbrace, the binary
functions \lfloor x/y\rfloor , \max(x,y), \min(x,y), and the
boolean vector operations AND, OR, NEGATION defined on 0,1
sequences of length n by performing the operations on all components
simultaneously. These are essentially the arithmetic operations that
can be performed on a RAM by a single instruction. We show that there
exists a term (that is, an algebraic expression) F(x,y) built up from
the mentioned operations, with the only free variables x,y, such that
for all terms G(y), which is also built up from the mentioned
operations, the following holds. For infinitely many positive integers
d, there exists an a\in M_{d} such that the following two statements
are not equivalent: (i) M_{d} \models \exists x, F(x,a) , (ii)
M_{d}\models G(a)=0. In other words, the question whether an
existential statement, depending on the parameter a\in M_{d} is true
or not, cannot be decided by evaluating an algebraic expression at a.
We also show that this theorem remains true if we include the operation
\min \lbrace x^{y}, 2^{n}-1 \rbrace into the structure M_{d}. A
general theorem is proved as well which describes sufficient conditions
for a set of operations on a sequence of structures K_{d}, d=1,2,...
which guarantees that the analogue of the mentioned theorem holds for
the structure K_{d} too.