Build a Turing *incomplete* language

Question

The world is full of Turing-complete programming languages. Just about every useful language (and most useless ones) are Turing-complete. Some even became Turing-complete by accident. Often this is great, since every Turing-complete language supports the same power of universal computation. But the power of Turing completeness also comes with a curse! The halting problem is undecidable for arbitrary programs in a Turing-complete language, and more generally, it’s impossible to analyze arbitrary programs in any non-trivial way. Sometimes we need less powerful languages.

It takes great care to design a useful language that falls short of Turing completeness. That’s the subject of this challenge!

Requirements

Write an interpreter that will accept a program and some input for the program, and produce some output. The program, input, and output are given using simple data types of your choice.

• Examples of “simple” data types: booleans; numbers; strings (bytes or Unicode); arrays or mappings of simple data types; algebraic data types defined in your interpreter.

• Examples of data types not considered “simple”: function expressions; a subset of strings representing valid programs in some language (unless the subset is validated by your interpreter); generalized algebraic data types. (This restriction is intended to disqualify trivial answers such as the identity function in Agda.)

Your input format must include some way to express arbitrarily sized natural numbers, in a reasonable representation of your choice (e.g. arrays or strings of unary, binary, or decimal digits, or directly as big integers if your host language has them). Your output format must include at least two values, distinguishable from each other, to represent “true” and “false”. Whether the formats can express anything else is up to you.

You may interpret programs in any target language, existing or new, under three conditions:

• Your interpreter must be observably deterministic: for a given program and input, you must always produce the same output.

• Your interpreter must not be Turing-complete. Explain why this is the case—for example, it might be Turing incomplete because the interpreter eventually halts on every program and input, or because its halting problem is otherwise decidable.

• As a minimum standard of usefulness, your target language must be able to express every polynomial-time function from natural numbers to booleans. Explain why this is the case. (To be clear, “polynomial-time” is defined over the length of the input in binary bits, even if your chosen representation of naturals is less efficient.)

Whether any other functions are expressible is up to you—for example, you might design your language around the primitive recursive functions, the elementary functions, or Gödel’s System T, each of which includes all polynomial-time functions.

Your interpreter may be written in any existing host language. You may assume it runs on an ideal machine with unlimited memory and pointers big enough to access it.

This is code-golf: make the shortest interpreter you can!

Clarifications

I believe these points follow from the requirements, but they’re listed here in the hope of being helpful. Feel free to request additional clarifications in the comments.

• As per our default rules, your interpreter will be a program or function that follows our usual conventions for input and output. However, programs in your target language are not bound by these rules—for example, if you decide that programs in your target language will be snippets that perform I/O by accessing a predefined variable, that is fine, as long as your interpreter translates this convention by (say) automatically reading from STDIN to the variable at startup and writing the variable to STDOUT at exit. (This can be viewed as a natural consequence of our policy that languages are defined by their interpreters.)

• You may of course use any data types you want within your language, as long as the program, input, and output types are simple data types.

• Your interpreter must be prepared to accept anything in your chosen simple data type for programs as a program. Your interpreter may of course perform extra validity checks on the program and throw errors or fall back to some default behavior or do something else that respects the requirements—but you may not impose extra validity constraints on programs purely at the specification level. Writing “eval but you’re not allowed to pass in anything except deterministic programs that halt” does not solve this challenge.

• Because of the determinism requirement, an interpreter that works by executing arbitrary code with a timeout in seconds is unlikely to be valid. (Doubly so if it leaves programs enough wiggle room to disable or evade the timeout in some underhanded way.)

• Although I am willing to be may already have been proven wrong, my expectation is that solving this challenge will require doing some actual work to interpret a language. I’m not looking for solutions that put in 1% of this work to satisfy 80% of the requirements, whatever that means—that wouldn’t be fair to those who put in the effort to solve the full challenge as written.

• I updated the challenge with a requirement for the representation of natural number inputs to be “reasonable” after realizing there was a loophole using an unreasonable representation of naturals. Specifically: if we enumerate all polynomial-time functions as \$p_0, p_1, p_2, \dotsc\$, the unreasonable representation of \$n \in \mathbb N\$ as \$(p_0(n), p_1(n), \dotsc, p_{n-1}(n))\$ allows any polynomial-time function \$p_m\$ to be “programmed” as \$\{0 \mapsto p_m(0), 1 \mapsto p_m(1), \dotsc, m \mapsto p_m(m), n \mapsto n_m\text{ for }n > m\}\$, with every output hard-coded into either the program or the input! (I don’t think any of the existing answers have tried to exploit such an unreasonable representation.)

Related challenges

• Write a Programming language of Unknown Completeness
• Turing-Complete Language Interpreter
• Design a One Instruction Set Computer!
• Fewest (distinct) characters for Turing Completeness
• Escape from the tarpit

(Deleted sandbox post)

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.