The class , defined using the operations , , , , exponentiation, and , corresponds to all primitive recursive functions from to . Here's the reasoning:

1. Basic Functions and Closure Under Composition:
   • The successor function (), zero function (), and projection functions (sele...

Short answer: Flex is far smaller than the class of primitive recursive (PR) functions. In particular, every Flex-function has a fixed, finite “exponential height,” so a standard PR function such as tetration n ↦ 2↑↑n (defined by g(0)=1, g(n+1)=2^{g(n)}) is not in Flex. Exponentiation is also not superfluous: without it, Flex collapses to at most polynomial growth and cannot define, e.g., n!.

Wha...

This is a fascinating question about the computational power of arithmetic operations combined with the floor function. Let me analyze what we know about and address your conjecture.

Key Observations

You've already made several important discoveries:

1. Basic arithmetic functions: , binomial coefficients, factorial
2. Characteristic functions: divisibility tes...

Functions from Expressible in

This question investigates which functions from can be constructed using the operations , , , , exponentiation, and the floor function , collectively called .

What We Already Know

From the given examples, we can see that $\mathcal{Flex}...

Excellent question! You've touched upon a classic topic in computability theory. Your explorations are spot on, and your conjectures are very natural ones to make. Let's break down the class of functions you've defined and see where it fits in the hierarchy of computable functions.

Let's call your class . A function is in if ...

Here is what one can prove about the “Flex’’‐class

Flex := the set of all functions f∶ℕ→ℕ which can be written as a single term built up from the constants 0,1 and the variable n by using +, – (truncated at 0), ×, integer‐division, exponentiation, and the floor‐operator.

1. Every Flex‐function is primitive‐recursive.
   That is trivial since each of +, ×, ^, ⌊·⌋, etc. is itself primitive...

<think> We are considering the class of functions $\mathcal{Flex}$ from $\mathbb{N}$ to $\mathbb{N}$ (with domain $\mathbb{N}$ and codomain $\mathbb{N}$) that can be built from the following operations: - Addition ($+$) - Subtraction ($-$) [Note: since we are in $\mathbb{N}$, we must handle negative results; we can use the floor function to adjust, but typically in such contexts subtraction is d...

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

Let

 L = { 0 , 1 , variables , + , – , × , ÷ , ^ , ⌊ · ⌋ }

and call an L-term any finite expression that is built out of the symbols of L in the usual way (÷ is ordinary rational division and the result is rounded down afterwards if necessary; “–’’ is ordinary subtraction, so every term denotes a natural number).
For k≥0 we write

 t : ℕ^k → ℕ

for the function that the term t de...