Write “Flex-term’’ for a (closed) expression that you can build out of
• the variable n, • decimal numerals 0,1,2,…, • the operations + , − , × , ÷ (ordinary rational division), • the unary symbol ⌊·⌋, and • the binary symbol ^ (exponentiation),
using the usual brackets to specify the order of evaluation.
The value of a Flex-term τ at n∈ℕ is the natural number that you obtain
by carrying out the ordinary real‐number operations and taking the floor when
a ⌊·⌋ occurs.
The class 𝔽lex is the set of all unary functions that are given by some Flex-term.
The question is: how large is this class? In particular, can it be all primitive–recursive functions?
A normal–form and a convenient measure of complexity
Put the Flex-terms in «prefix depth normal form».
The depth d(τ) is the largest number of exponentiation symbols that one meets
on a path from the root of the syntax tree of τ down to the variable n.
Example
τ(n)=⌊(3n+7) ^ ((n−2)^3·n)⌋
has d(τ)=2. A term that contains no ^ has depth 0.
How large can a depth-d term grow?
Define iterated exponentials
exp0(x)=x,
exp(k+1)(x)=2^{expk(x)} (tower of height k+1 with top entry x).
Claim. For every Flex-term τ there are constants C,k∈ℕ and
d=d(τ) such that
τ(n) ≤ expd ( C·n^{k} ) for every n∈ℕ. (★)
Proof is by induction over the construction of τ. • Depth 0. A depth-0 term is obtained from n by +,−,×,÷ and ⌊·⌋. It is therefore bounded by a polynomial C·n^{k}, so (★) holds with d=0. • Induction step. Suppose the statement is true for all proper sub-terms of τ. If τ is built from sub-terms by +,−,×,÷,⌊·⌋ the bound (★) is preserved (up to another polynomial factor). If τ = σ1 ^ σ2 and depth(τ)=d, then depth(σ1),depth(σ2)≤d−1. By the induction hypothesis there are polynomials p,q such that σ1(n) ≤ exp(d−1)(p(n)), σ2(n) ≤ exp(d−1)(q(n)). Hence τ(n)=σ1(n)^{σ2(n)} ≤ ( exp(d−1)(p(n)) )^{ exp(d−1)(q(n)) } ≤ exp d ( C·n^{k} ) for suitable C,k, finishing the induction.
So every Flex function grows at most like a fixed-height tower of 2’s (the height being the largest nesting depth of ^ in its defining term).
Assume toward a contradiction that T is given by a Flex-term τ.
Let d=d(τ).
By (★) we have a polynomial p with T(n) ≤ exp d ( p(n) ).
But exp d ( p(n) ) is a tower of height d whose largest entry
is p(n), whereas T(n) is a tower of height n.
For n>d+2 that is impossible, because a tower whose height
grows with n eventually dominates every fixed-height tower.
Therefore no such τ exists; in other words, T ∉ 𝔽lex.
a) 𝔽lex is strictly smaller than the set PR of all primitive–recursive functions: the primitive–recursive tower function T is not in 𝔽lex.
b) 𝔽lex is contained in the well-known class EL of elementary recursive functions, because EL is exactly the closure of the basic arithmetic operations under composition and bounded iteration, and every elementary function is dominated by some fixed-height exponential tower. The estimate (★) shows that every Flex function has this property, so 𝔽lex ⊆ EL ⊊ PR.
c) Exponentiation is essential. If one deletes “^’’ from the list of allowed symbols, every expression is a depth-0 term; the resulting functions are bounded by polynomials, so neither n! nor the primality indicator can be obtained.
Summary.
A Flex-term contains only finitely many exponentiation signs, so the value it
returns is always bounded by a tower of exponentials of some fixed height.
There are primitive-recursive (indeed very simple) functions whose growth
requires towers of variable height; such functions cannot be expressed by any
Flex-term. Consequently
𝔽lex ⊂ elementary recursive ⊂ primitive recursive,
and your conjecture “𝔽lex = PR’’ is false.
Was this answer helpful?
version: o3-pro-2025-06-10
Status: UQ Validated
Validated: 8 months ago
Status: Human Verified
Verified: 7 months ago
Loading model reviews...
Loading reviews...