Python 2, 38 bytes

lambda s,n:s.strip("()+*%n")or eval(s)

Try it online!

This evaluates a subset of Python 2 given by arithmetic expressions using only characters ()+*%n, acting on natural-number input n. This computes the class ELEMENTARY, as the closure of the expressions in the basis

\$\{n+m, n^2, n\bmod m, 2^n\}\$

as noted in the Wikipedia article on ELEMENTARY and proven in Superpositions of elementary arithmetic functions. This moreover shows that Python operators can not only do primality testing, but any polynomial-time computable function.

The paper's argument seems to be based on constructions similar to Lopsy's prime-testing solution, encoding lists as digits in a large base and expressing bounded summation on those elements via arithmetic operations. The proof uses this expression for binomial coefficients as an intermediate step.

We check that our operators can express all operations in the basis. The +, **, and % operators do addition, exponent, and modulo. We can get the \$2\$ for \$n^2\$ and \$2^n\$ as \$2=0^0+0^0\$, where \$0\$ is n**n%n**n, avoiding the modulo-by-zero that simply n%n would give for n=0. Parentheses allow arbitrary composition of sub-expressions, and projection is trivial. We can interpret outputs as Booleans by associating True=1, False=0, as is standard in Python.

To ensure we that only this subset can be evaluated, we check that the input expression s is limited to the characters ()+*%n by stripping them from s and returning what remains if non-empty. Note that an invalid string is never evaluated, rather than evaluated then discarded, preventing it from anything strange it could call or overwrite to allow its output to escape.

The really isn't anything extra that's non-trivial that can be done with the whitelisted characters that we might worry allows Turing completeness. The letter n alone can't spell any function or keyword. We can get multiplication with *, but this is of course elementary. We can't even get negative numbers or floats, though these would still be harmless. We can get the empty tuple (), but nothing interesting can be done with it.

APL (Dyalog Unicode), ¹⁵ 14 bytes

(⍎⍞~'⎕⍎⍣⌶?{')⎕

Try it online!

A full program that takes two inputs (an array of numbers in APL syntax, and then a line of APL code) from STDIN and prints the result to STDOUT. The given APL code is sanitized by deleting characters that have a possibility to invoke an unbounded loop/recursion or access to the external system.

Since the input function is written in a single line, it must necessarily consist of built-in functions and operators, possibly including assignment. Using dfns is banned by the character {, and tradfns cannot appear because a tradfn requires at least two lines of code to be defined. Control structures and the Branch primitive are only meaningful inside trandfns, so they are automatically banned as a side effect.

The summary of banned characters with reasons:

• ⎕ by itself is used merely as an I/O primitive, but it is used as the first character of all the system functions, which include shell and filesystem access.
• ⌶ is called an I-beam, which grants access to experimental features. Some of the features include access to system.
• { is required to create a dfn/dop, and has no other uses.
• ⍣ is power operator, which can act as a for-loop or a while-loop depending on how it is used.
• ? is random number generator. It is excluded to satisfy the determinism requirement.
• ⍎ is APL's eval. I can't think of a hole accessible via ⍎ when ⎕UCS, ⎕AV etc are banned, but it is included to be safe.

Any one line of APL code without the six characters is guaranteed to terminate, thus it is not Turing-complete.

Here is a more formal proof via structural induction. Here is the list of all language elements for reference. Let's define a Q-function to be a function that terminates by returning a deterministic array or erroring in finite time.

• All primitive functions except ⍎? along with bracket indexing are Q-functions.
• All primitive operators except ⍣⌶ become Q-functions when given Q-functions and/or arrays as operands.
• Tacit functions made of Q-functions are Q-functions, because tacit functions cannot express recursive functions. Also, something like g←⊢,g does not create a self-reference; it is either illegal (if g is not defined beforehand) or creates a new function based on the previous value of g.
• Any variable created/modified via assignment can only result in a Q-function or an array.

The remaining functionality can be proven to be powerful enough to express elementary functions: Taking multiple arguments as a single array (e.g. subtraction function f(x,y) takes a length 2 array),

• Zero = -⍨, Successor = 1∘+, and Subtraction = 0⌈-/.
• Projection can be expressed as an indexing via ⊃.
• Composition can be written as h g1,g2,g3,...
• Bounded summation and product can be implemented as tacit functions: summation is +/(0,⍳∘⊃)(g,)¨∘⊂1∘↓ and change +/ to ×/ for product.

APL (Dyalog Unicode), 42 bytes

{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}

Try it online!

I thought I'd give it a go at a more "proper" submission. This function interprets the programming language LOOP represented as a nested numeric array (which is used like an ADT), and the input to the LOOP program is represented as a simple numeric vector (enclosed once, for the sake of code golf).

The concept

LOOP has four kinds of commands: (x_i are variables and P are sub-programs)

• x_i := 0 (zero)
• x_i := x_i + 1 (increment)
• P_1; P_2 (sequence)
• LOOP x_i DO P END (bounded loop): Run P x_i times.

Here I represent a sequence of commands as an array [P_k P_k-1 ... P_2 P_1] instead of explicit concatenation, therefore eliminating a command. The order of command is reversed for the sake of code golf.

Each command in the program is encoded as a (c i) pair, where i is the variable index to refer to and c is the command to run on it. I use c←0 for zero, c←1 for increment, and c←P for the bounded loop.

For an illustration, the pseudocode

x_2 += x_1 * 2; x_1 = 0

can be written in LOOP as

LOOP x_1 DO
  x_2 := x_2 + 1
  x_2 := x_2 + 1
END;
x_1 := 0

and the representation for my submission is

(0 1)(((1 2)(1 2))1)
      ------------    Increment x_2 twice
     ---------------  Loop x_1 times
-----                 Assign zero to x_1

For the computational power, LOOP can precisely represent primitive recursive functions, thus satisfying the requirement of the challenge.

The code

{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}  ⍝ ⍺←Program; ⍵←Input
{                                     ⍺,⍵}  ⍝ Append ⍵ to ⍺ for reduction
 ∇{                                 }/      ⍝ Reduce, exposing the self reference to inner dfn:
       c i←⍺               ⍝ Extract command type and index from the next command
   ×|≡⊃     :              ⍝ If the command type is not simple (a loop subprogram):
             ⊃c⍺⍺⍣(i⊃⍵)⊃⍵  ⍝ Run the subprogram c x_i times on the state ⍵
                         ⋄            ⍝ Otherwise
                          c(⊣+×)@i⊢⍵  ⍝ Multiply c and then add c to x_i, which is equivalent to
                                      ⍝ If c is 1, add 1 to x_i; if c is 0, set x_i to 0

JavaScript (Babel Node), 59 51 47 bytes

n=>g=([a,b,c])=>c?g(a)+g(b)**g(c):b?g(a)%g(b):n

Try it online! (51 bytes thanks to @user202729)

This is using @xnor's basic approach, but without eval, and with a reduced basis.

The simple datatype D is a BigInt or an array of D. Given a program p (a D) and an input n (a BigInt), the expression e(n)(p) interprets the program with input n. Programs are interpreted as follows:

• [a, b, c] evaluates a, b, and c, returning a + b**c
• [a, b] evaluates a and b, returning a modulo b
• [0] returns n

These three operations are enough to compute anything elementary recursive. No matter the value of n, the value of n+n**n is positive, hence (n+n**n)%(n+n**n) gives 0, and 0 + 0**0 gives 1. Hence, we have addition as a + b = a + b**1 and exponentiation as a**b = 0 + a**b.

For example, this is a program that computes the constant 2:

[[[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]],
 [[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]],
 [[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]]]

Corollary 2 of the following paper, which @xnor cited, is that this language gives all elementary recursive functions, using the usual tricks to encode a function \$\mathbb{N}^n\to\mathbb{N}\$ as a function \$\mathbb{N}\to\mathbb{N}\$.

Marchenkov, S. S. (2007). Superpositions of elementary arithmetic functions. Journal of Applied and Industrial Mathematics, 1(3), 351–360. doi:10.1134/s1990478907030106

They also point out in Corollary 3 that every recursively enumerable subset \$S\$ of \$\mathbb{N}\$ has an indicator function \$f:\mathbb{N}\to \{0,1\}\$ that is of the form \$f(n)=\exists z\in\mathbb{N},n=p_1(z)\wedge n=p_2(z)\$, where \$p_1(z)\$ and \$p_2(z)\$ are functions in the above language, such that \$f(n)=1\$ if and only if \$n\in S\$. The argument is that you take a Turing machine that describes \$S\$ (say, as a nondeterministic machine that halts with elements of \$S\$ on the tape) then use the language to make nearly identical functions \$p_1\$ and \$p_2\$ that take an execution trace \$z\$ and check whether it brings the machine into a halt state, and if so the result of each function is the tape contents, and otherwise they result in \$p_1(x)=0\$ and \$p_2(x)=1\$.

Jelly, 9 bytes

Ḣ+Ṫị⁴;µḄ¡

Try it online! (The sample program returns true if the input is odd.)

A full program whose first command-line argument is the program to interpret (as an array of arrays of nonnegative integers), and whose second command-line argument is the input (encoding a natural number in unary as a positive-length array of 1 – that means that 0 is not a natural number for the purposes of this solution). The output format is an array of integers, and any polynomial-time function from positive integers to booleans can be encoded as a program that returns [0] for false or [3] for true (Jelly doesn't print the brackets around 1-element arrays, so this will appear as 0 or 3 on TIO!).

No eval needed – this is a complete interpreter for a simple polynomially-powerful but Turing-incomplete language, that does all the work itself.

Explanation

This program is implementing a restricted version of Esimpl with one semideque and where the only commands are pushback and pop-goto. Due to the highly restricted set of commands, the commands can be inferred from the program and need not be explicitly stated, so the only thing that actually needs to be specified in the program is the arguments to the commands. Each of these is specified as a single array with one element per stanza, containing the argument to the pop-goto command first, followed by the arguments to the pushback in reverse order. Tables are not explicitly specified in the program. (Not all arrays of arrays of nonnegative integers actually form valid Esimpl programs under this interpretation, but the ones that don't will still produce some valid output when running under this interpreter and cannot produce Turing-complete behaviour, and so all programs of the right format are handled even though they aren't all useful.) The startup state is also different from Esimpl: stanza 0 is not special, and instead the semideque is initialised with a number of 1s equal to the input minus 1, with execution starting as though a pop-goto 1 command were used. (This pops from an empty semideque when the input is 1; the interpreter treats pops from an empty semideque as though 0 were popped, which is Jelly's behaviour when popping empty lists.)

The body of the Esimpl interpreter's main loop is Ḣ+Ṫị⁴;, and it operates on an array consisting of the current table number followed by the semideque in reverse order:

Ḣ+Ṫị⁴;
Ḣ         pop and remove the first array element
            (i.e. the table number)
  Ṫ       pop and remove the last semideque element
            (i.e. the front of the semideque)
 +        add the two popped numbers
   ị      wrapping-index into
    ⁴       the second-command-line argument
     ;    append {the unpopped parts of the array}

One step of interpreting this restricted Esimpl consists of pushing data specified by the current stanza onto the back of the semideque, then adding a table number specified by the current stanza to a value popped from the front of the semideque in order to produce the new stanza number. The interpreter is effectively doing the second half of one stanza and the first half of the next: it adds the table number and a value popped from the semideque, looks up the appropriate stanza, and pushes the stanza's array onto the back of the semideque (i.e. the start of the array). This contains the data to pushback preceded by the table number, so the next main loop iteration will have the array in the same format as before (i.e. with the table number at the start of the array, ready to run the second half of the stanza).

The reason I picked Esimpl as the language to interpret is because it can simulate Turing machines with only a polynomial slowdown (the simulation is O(n) if you can use multiple semideques and push onto the front, but this single-semideque version simulates Turing machines in O(n²) time). That means that if a Turing machine runs in polynomial time, the Esimpl simulation of it also runs in polynomial time. Esimpl is Turing-complete, but only if you actually run its main loop until the program halts, and this interpreter isn't actually doing that:

Ḣ+Ṫị⁴;µḄ¡
Ḣ+Ṫị⁴;       body of main loop
      µ      group into a single block
        ¡    run it a number of times equal to
       Ḅ       the input interpreted as a binary integer 

The unary input is misinterpreted as binary to specify the number of iterations to run, meaning that the runtime is capped – but it's capped to a value that grows exponentially with the input, meaning that for sufficiently large inputs, a program that can run in polynomial time will always finish before the cap. Additionally, Esimpl is fast enough that a program that simply hardcodes outputs for small inputs will always finish within the fixed time bounds for those inputs (a program that does "if input is 1 then halt with x else if input is 2 then halt with y else …" will always handle the case of input 1 within 1 cycle, of input 2 within 2 cycles, of input 3 within 3 cycles, etc., which beats the required time bound). This means that any polynomial-time Turing machine can be compiled into this exponentially-restricted Esimpl by writing a program that hardcodes the (finitely many) small inputs that would otherwise take too long to run into the equivalent of an if/else chain, and uses a compiled version of the Turing machine to handle everything else.

The remaining problem is handling halting with a value. The basic idea is to write the Esimpl program so that it contains a table 0 with a single stanza pop-goto 0, and likewise a table 3 with a single stanza pop-goto 3; jumping to either of those stanzas with an empty semideque will cause it to jump to itself repeatedly until the program exits due to exceeding the time limit, leaving a fixed output of [0] or [3] as appropriate. (Note that Jelly arrays are 1-indexed and wrapping, so stanza 3 is the third element of the array and stanza 0 is the last element of the array – a bit unintuitive but it works. Incidentally, the reason I chose 0 and 3 is that stanzas 1 and 2 have to form a table in order for program startup to work correctly, meaning that they're unavailable as halt states.) As such, the "empty the semideque then jump to a halt state" strategy works to produce a Boolean output. Programs not written that way might produce other arrays as output, but this is allowed by the question.

JavaScript (Babel Node), 96 86 69 62 bytes

x=>g=([a,b,c])=>c?((v=>{for(;v-->0;)g(b)})(g(a)),g(c)):x[a]+=b

Try it online!

This is implementing a variation on LOOP. A program is recursively defined to be an array of programs or a BigInt. A program p is run with input x (a list of BigInts) by passing x and p as curried arguments (f(x)(p) with f the above function). The program is interpreted as follows:

• [i, n] adds n to x[i], returning the sum.
• [p, q, r] with c = max(0, evaluate(p)), evaluates q c times then returns the result of evaluating r.

The interpreter expects that every x[i] used is initialized to some BigInt.

For example, the following is a program that returns the product of x[2] and x[3], assuming x[0] is set to 1 and x[1] starts with any non-negative number.

[[0, 0],      // loop x[0] times:
 [[0, 0],     //   loop x[0] times:
  [[1, 0],    //     loop x[1] times:
   [1, -1],   //       x[1] += -1
   [0, 0]],   //     x[0] += 0
  [[2, 0],    //   loop x[2] times:
   [[3, 0],   //     loop x[3] times:
    [1, 1],   //       x[1] += 1
    [0, 0]],  //     x[0] += 0
   [0, 0]]],  //   x[0] += 0
 [1, 0]]      // x[1] += 0

The last line returns the value of x[1].

Note that, while this version of LOOP allows variables to be negative, there is no way to clear such a value in a general way.

VBS, 74 bytes

execute replace(replace(replace(lcase(inputbox(0)),"w",0),"e","ne"),"d",2)

Take program that looks like:

j=0:for i=0 to InputBox():j=j+i:ext:msgbox(j)

Disallow loops from CreateObject, Do, (w)End, eval, execute, step, date, now, timer

JavaScript (Node.js), 35 bytes

(67 if no state allowed, 40 for no state strict, if you keep =; still 35 otherwise, still elementary but program is longer without =)

x=>n=>eval(x.replace(/[^!-=n]/g,0))
x=>n=>eval('for(i in this)delete this[i];'+x.replace(/[^!-=n]/g,0))
x=>n=>eval(x.replace(/[^!-=n]/g,'var '))

Try it online!

Even not reaching Bitwise operation is powerful

JavaScript, 43 bytes

n=>g=([a,b,c])=>c?g(b)/g(c)-g(a)<<g(c):a||n

Why?

0   = 1 / 1 - 1 << 1
-x  = (x / 1 - 0 << 1) / -1 - 0 << -1
x+y = (-x / 1 - y << 1) / -1 - 0 << -1
x/y = -(0 / -y - (x / y - 0 << y) << -y) // If y>0
2^x = 2 / 1 - 1 << x
x>=0 = (1<<x)<<-x
[Convert To Positive]: 2^x + 2^x + 2^x + 2^(-1-x) + 1

Bash, 33 bytes

dc -e"?sl`sed "s/[^l+%^]//g;q"`p"

Try it online!

Effectively the same scheme as @xnor's solution, except implemented in sed & dc, and using a subset of dc for user programs. All characters except [+^%l] are filtered out, and those that remain are evaluated by dc. Those characters are sufficient to perform the operations of addition, modulo, exponentiation(with 0^0 == 1) and to read from a variable 'l', which is written to with the user input before the inputted program is run. Numbers may be constructed using a combination of 0 = (n^n)%(n^n), 1 = 0^0, and the successor function, +0^0. Translated to dc, these would be:

0 = llll^llll^%
1 = llll^llll^%llll^llll^%^
S = llll^llll^%llll^llll^%^+ 

where S increments the value at the top of the stack. Operations may be arbitrarily nested. The set of characters is sufficient to encode the operations listed above. However, it is incapable of producing looping / recursion (which, in dc, would require executing a macro, which would require one of [x=<>], as well as either a or [] to define it). Similarly to @xnor's solution, the allowable programs are a superset of the class ELEMENTARY, adding the ability to do make arbitrary exponents, rather than just 2^ and ^2.