# Build a Turing *incomplete* language

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

• Roughly related, and an answer that implements computationally equivalent subset of LOOP. Also there's a mathematical equivalent of PSPACE which looks deceptively simple. – Bubbler May 17 '20 at 23:02
• @Bubbler Yes, I thought of reusing that mini-LOOP language (with the reduction you suggested at the time), and I might still, but I think it’s more interesting to do something new. – Mitchell Spector May 18 '20 at 1:33
• A possible loophole: what prevents is from saying "Programs that don't halt within a finite amount of time are ill-formed" and making the interpreter do undefined behaviour on them, and the interpreter is eval? – the default. May 18 '20 at 5:11
• @mypronounismonicareinstate That would be covered by “Examples of data types not considered “simple”: … a subset of strings representing valid programs in some language (unless the subset is validated by your interpreter)”. You may not arbitrarily disallow some programs except by having your interpreter actually check for them. (The particular check of “halts within a finite amount of time” would be impossible, of course.) – Anders Kaseorg May 18 '20 at 5:21
• Prime example: A sequence of non-recursive SQL statements including CREATE and ALTER table. It's rather hard to show it's not Turing complete other than by showing it won't halt. I was able to get so much done in SQL alone without reaching for TSQL WHILE. – Joshua May 18 '20 at 17:47

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

• This is a really cool and surprising fact! I wanted to see what an eval-free answer would look like, though I ended up using Javascript instead of Python. codegolf.stackexchange.com/a/204976/78112 – Kyle Miller May 19 '20 at 17:18
• I commented something similar on the post an hour earlier. Nice job :) – ghosts_in_the_code May 20 '20 at 8:19
• @ghosts_in_the_code Your comment involved for loops, which this answer does not—that’s what makes this so surprising. – Anders Kaseorg May 24 '20 at 18:50
• @AndersKaseorg makes sense. Not stealing credit :) – ghosts_in_the_code May 24 '20 at 19:13

# APL (Dyalog Unicode), 15 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.
• I’m not familiar with APL (maybe this is as good an excuse as any to start learning…), but are you sure you can’t get unbounded recursion through some back-door construction without direct self-reference, like (λx.x x)(λx.x x) in lambda calculus? – Anders Kaseorg May 18 '20 at 5:50
• @AndersKaseorg It doesn't work because "functions" can only take arrays as args and return arrays, and "operators" can only take functions/arrays as operands (and nothing can take operators as args/operands). – Bubbler May 18 '20 at 5:58
• Do control structures present a problem, or are they already somehow disallowed in this context? – Anders Kaseorg May 18 '20 at 7:28
• What is stopping people from using gotos (starting a line with a label and going to that line, like A:→A to make a loop)? – Wzl May 18 '20 at 16:57
• @Wezl Both the label marker A: and the goto branch →A work only inside tradfns (and tradfns are not allowed as I already explained). Other than that, → has no meaning except for an interactive environment (e.g. Dyalog IDE). – Bubbler May 18 '20 at 23:01

# 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), 5951 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\$$.

• “Python is too careful with its arithmetic (there are exceptions when doing mod-by-zero)”—there’s nothing inherently wrong with that. “All recursively enumerable functions”—you mean elementary functions (some recursively enumerable functions aren’t even computable). – Anders Kaseorg May 19 '20 at 19:48
• @AndersKaseorg It's a problem with the approach I took to golf the interpreter, which is to evaluate all four functions in an array then select; I couldn't think of a short way to guard the division that would use a comparable number of bytes, that's all. For the second thing, I misunderstood what Corollary 3 was saying; it's just the fact that verifying that a Turing machine follows a given execution trace is elementary recursive, and thus can be implemented as a "diophantine representation" using these integer operations. – Kyle Miller May 19 '20 at 20:18
• 51 bytes – user202729 May 20 '20 at 7:39
• Side-comment to @AndersKaseorg which doesn't affect your actual point. You wrote: "some recursively enumerable functions aren’t even computable". Since "recursively enumerable" is a property that applies to sets, presumably this is identifying a function $f$ with $\{\langle x,y\rangle \mid f(x)=y\}.$ Usually "function" in this context would mean "total function"; but any r.e. function is then recursive. If you allow partial functions, then any r.e. function is partial recursive. Is there an interpretation that would give you an r.e. function that isn't computable in an appropriate sense? – Mitchell Spector May 24 '20 at 16:33
• @MitchellSpector The challenge asks only about functions from naturals to booleans, so I had interpreted the language “recursively enumerable functions” from the old version of this answer as “indicator functions of recursively enumerable sets”. Interpreting it as “recursive functions” (total or partial) wouldn’t have made the statement true either. The statement has since been corrected. – Anders Kaseorg May 24 '20 at 18:43

# JavaScript (Babel Node), 968669 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.

• Quick golf: c<=1 -> c<2, c==2 -> c<3, ()=> -> _=>, c-->0 -> c--. Also, I think you can start with f=(x,[c,a,b])=>... and remove all the ...s in f(x,...a) etc. – Bubbler May 19 '20 at 6:24
• @Bubbler Thanks! My editor's syntax highlighter was unhappy with argument destructuring, so I didn't test it in TIO. – Kyle Miller May 19 '20 at 6:28
• @Bubbler I can't change c-->0 to c-- because c=x[a] might be negative – Kyle Miller May 19 '20 at 6:36
• 79 using curried function. – Bubbler May 19 '20 at 6:42
• 77 – l4m2 May 19 '20 at 7:21

# 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

• I think you need to explain why this can express every polynomial-time function. – Bubbler May 18 '20 at 5:26
• @Bubbler I think you can just For for $k$ layers for $n^k$ time, and IF is easily expressed with FOR – l4m2 May 18 '20 at 5:29
• I don't know VBS, so take this with a grain of salt, but: According to OP, your interpreter has to validate the program. Will this interpreter print an error message if the program uses any of the disallowed constructs (CreateObject, Do, etc.)? – Mitchell Spector May 18 '20 at 7:57
• @MitchellSpector I’m also not familiar enough with VBScript to be sure whether this is both sufficiently powerful and sufficiently restricted (and I am regretting not having disallowed eval builtins to avoid having the ability to answer these questions depend so crucially on deep familiarity with the host language). But there’s no requirement for an error message in particular, as long as something happens that doesn’t break the other requirements. – Anders Kaseorg May 18 '20 at 8:29
• @AndersKaseorg I tend to agree that disallowing eval and variants would have been the way to go, but then people would have complained about that on the grounds that it's not objectively clear exactly which built-ins were being banned. codegolf.meta.stackexchange.com/questions/13771/… – Mitchell Spector May 18 '20 at 9:14