Determining whether a Language is Turing Complete is very important when designing a language. It is a also a pretty difficult task for a lot of esoteric programming languages to begin with, but lets kick it up a notch. Lets make some programming languages that are so hard to prove Turing Complete that even the best mathematicians in the world will fail to prove them either way. Your task is to devise and implement a language whose Turing Completeness relies on a major unsolved problem in Mathematics.


  • The problem you choose must have be posed at least 10 years ago and must be unsolved, as of the posting of this question. It can be any provable conjecture in mathematics not just one of the ones listed on the Wikipedia page.

  • You must provide a specification of the language and an implementation in an existing language.

  • The programming language must be Turing complete if and only if the conjecture holds. (or if and only if the conjecture doesn't hold)

  • You must include a proof as to why it would be Turing complete or incomplete based on the chosen conjecture. You may assume access to unbounded memory when running the interpreter or compiled program.

  • Since we are concerned with Turing Completeness I/O is not required, however the goal is to make the most interesting language so it might help.

  • This is a so the answer with the most votes will win.

Target Criteria

What should a good answer do? Here are some things to look for when voting but are not technically required

  • \$\begingroup\$ This conversation has been moved to chat. \$\endgroup\$
    – Dennis
    Mar 5, 2017 at 17:08
  • 15
    \$\begingroup\$ On the whole, I'm finding the answers here disappointing. They are pretty much "Start with a Turing-complete language, then test if conjecture X is True/False and if so, terminate or disable a key feature." \$\endgroup\$
    – xnor
    Mar 12, 2017 at 1:20
  • 1
    \$\begingroup\$ @xnor I agree with you, I was hoping that this bounty would provoke some more interesting answers but it looks like that is not going to happen. \$\endgroup\$
    – Wheat Wizard
    Mar 12, 2017 at 1:43
  • 2
    \$\begingroup\$ I think one of the issues is that most conjectures have been proven to be true for an infinite number of values but the counterexamples would also be true for an infinite number of values. As a result, it becomes nearly impossible to prove Turing completeness iff true. \$\endgroup\$ Mar 13, 2017 at 12:37
  • 1
    \$\begingroup\$ I think the requirement that Turing completeness is tied one-to-one with a given conjecture is a pretty strong requirement. I think it would be easy if proving or disproving Turing completeness decided two different open problems, respectively. (i.e. proving Turing completeness decides open problem A and disproving decides open problem B). \$\endgroup\$
    – PyRulez
    Jun 1, 2017 at 2:28

10 Answers 10



This language is only Turing-complete if and only if Legendre's conjecture is false, i.e. there exists a integer n > 0 such that there are no primes between n^2 and (n+1)^2. This language takes some inspiration from Underload, though in some respects it is very different from it.

Programs in Legendre are made up of series of positive integers (0 is especially banned, because it essentially negates the entire purpose of the language). Each integer corresponds to a base command in Legendre, or a potential user-defined one. Which command it is assigned to is based on the number of primes between its square and the next integer (equivalent to the OEIS sequence A014085).

The language's commands modify a stack, which can hold arbitrarily large positive integers. If the stack ever holds 0, the 0 is immediately removed. In detail, the commands are:

  • 2 (smallest integer producing this command: 1): Push the next integer in the program onto the stack.

  • 3 (smallest producing integer: 4): Pop the top integer on the stack and execute the command associated with it.

  • 4 (smallest: 6): Pop the top integer. If it was 1, increment the top integer on the stack.

  • 5 (10): Swap the top two stack items.

  • 6 (15): Decrement the top integer on the stack. If that results in 0, pop the 0 and discard it.

  • 7 (16): Duplicate the top integer on the stack.

  • 8 (25): Halt execution and print the stack contents.

This is the basic instruction set, which is unable to do anything interesting, let alone loop. However, there is another command, which can be accessed only if Legendre's conjecture proves false.

  • 0 (unknown): Remove all items from the stack and combine them into a new function, which will execute all commands starting at the original bottom of the stack and ending at the top, accessible as a command whose "command number" is equal to the one the next integer in the program source corresponds to.

If this command is somehow accessible, the language becomes Turing-complete, as one can simulate a Minsky machine in it.

When the command 8 is execute or the end of the program is reached, the program terminates and the (Unicode) character corresponding to each integer on the stack is printed.

Example programs

1 2 1 3 1 10 4

This simple program pushes the number 2, then 3 and finally a 10, before executing a 4 (command: 3), which causes the 10 (command: 5) to be popped and executed, swapping the 2 and 3.

1 5 3 15 2 1 6 7

This program demonstrates the use of the indirect integer-to-command correspondence. First, a 5 is pushed, then a 15 and a 1, using three different ways of encoding the 2 command. Then, the 1 is popped and as a result, the 15 is incremented to a 16, and finally executed. The program ends with two instances of the number 5 on the stack.

1 1 1 5 ? 24 1 15 1 31 ? 31 24 31

This program demonstrates the use of the 0 command, using ? as a placeholder number. The program first stores '1 5' in the function 9, then '15 31' in 10, before running function 9 (using 24), which pushes 5 onto the stack, and the repeatedly decrements it, until it reaches 0 and is removed. Then, the program halts.

Minsky machine

In order to convert a Minsky machine to Legendre code, the 0 command must be used. Because this command is inaccessible unless Legendre's conjecture is false, I have used a placeholder ? instead.

Note that all Minsky machine instruction line names need to have integers with different A014085 correspondences from each other and the base commands as well as 24 (9) and 31 (10).

1 1 1 1 ? 24
x INC (A/B) y:


1 y 1 24 1 ? 1 6 1 1 16 1 24 ? x


1 y 1 24 1 ? 1 10 1 6 1 1 16 1 10 1 24 ? x
x DEC (A/B) y z:


1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 24 ? x


1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 10 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 10 1 24 ? x
1 25 ? x

To create the final program, append all parts (with x,y,z replaced by their counterparts) and add a single integer to start the first instruction in the chain. This should prove the language's Turing-completeness in case Legendre's conjecture is proven false by counterexample.


This interpreter is written in Python (3), and has been tested on all three above examples. Use the -a/--allowZero flags to allow ? to be used, -f/--file to run code directly from a file and -s/--stackOut to output the stack as a Python list instead. If no file is given, the interpreter enters a sort of REPL mode, which is best used with --stackOut.

import sys
import argparse
import io

class I_need_missing(dict): #used to avoid try/except statements. Essentially a dict
    def __missing__(self,key):
        return None 

def appropriate(integer,prev): #returns number of primes between the square of the integer given and the next

    return_value = 0

    if prev[integer]:
        return prev[integer],prev
    if integer == "?":
        return 0,prev
    for i in range(integer ** 2, (integer + 1) ** 2):
        t = False
        if i > 1:
            t = True
            for j in range(2,int(i ** 0.5)+1):
                t = i/j != round(i/j)
                if not t:
        return_value += t

    prev[integer] = return_value
    return return_value,prev

def run_command(commandseries,stack,functions,prev): #Runs the appropriate action for each command.

    command,prev = appropriate(commandseries.pop(0),prev)

    halt = False

    if command == 0: #store in given number
        functions[appropriate(commandseries.pop(0),prev)[0]] = stack
        stack = []

    elif command == 2:#push

    elif command == 3:#execute top instruction

    elif command == 4:#pop, add 1 to new top if popped value was 1
        if stack.pop() == 1:
            stack[-1] += 1

    elif command == 5:#swap top two integers/?
        stack[-1],stack[-2] = stack[-2],stack[-1]

    elif command == 6:#subtract 1 from top of stack
        stack[-1] -= 1
        if stack[-1] == 0:

    elif command == 7:#duplicate top of stack

    elif command == 8:#halt
        halt = True

    else:#run custom
            commandseries[0:0] = functions[command]
        except TypeError:
            print("Warning: unassigned function " + str(command) + " is unassigned", file = sys.stderr)

    return commandseries,stack,functions,prev,halt

def main(stack,functions,prev):
    #Parser for command line options
    parser = argparse.ArgumentParser(description = "Interpreter for the Legendre esoteric programming language.")
    parser.add_argument("-a","--allowZero", action = "store_true")
    parser.add_argument("-s","--stackOut", action = "store_true")

    args = parser.parse_args()
    allow_zero = bool(args.allowZero)

    #Program decoding starts
    pre = ""

    if not args.file:
        pre = input()
        if pre == "":
        pre = open(args.file).read()

    mid = pre.split()
    final = []

    for i in mid:
        if i == "?" and allow_zero:
        elif i != 0 or allow_zero: #and allow_zero)

    halt = False

    #Functional programming at its best
    while final and not halt:
        final,stack,functions,prev,halt = run_command(final,stack,functions,prev)

    #Halting and output
        if args.stackOut:
            for i in stack:
                print(i == "?" and "?" or chr(i),end = "")
        if args.file or halt:

if __name__ == '__main__':

Union Closed

This programming language is Turing complete iff the Union-closed Sets conjecture is incorrect.


List of Commands:
x++ Increment x (INC)
x-- Decrement x (DEC)
j(x,y) Add instruction set x if y is 0 to end of instruction queue

All variables are initialized as 0


Programs are written as a set of sets of commands.
Command1 Command2 Command3...
Command1 Command2...

For determining if the program is union closed, each set only accounts for the list of different commands that are in the set

If any command type (+,-,j) appears in at least half the sets, it does nothing.

Programs can end if there are no instructions on the end of the instruction queue

Infinite loops, including the empty loop, can be achieved using j(x,y)


function union_arrays (x, y) {
  var obj = {};
  for (var i = x.length-1; i >= 0; -- i)
     obj[x[i]] = x[i];
  for (var i = y.length-1; i >= 0; -- i)
     obj[y[i]] = y[i];
  var res = [];
  for (var k in obj) {
  return res;

function runCode(){
  var inputBox=document.getElementById("code");
  input=input.split("\n").map(a=>a.split(" "));


  var queue=[]
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>

<p class=results></p>

Turing Completeness

If all three commands, j(x,y), increment, decrement the commands are all available, so a Minsky machine can be simulated.

Any set with only j(x,y) which is reached using j(x,y) is HALT
x++ is INC
x-- is DEC
j(x,y) is JZ

If the union closed sets conjecture is correct, at least one of the three commands will always be disabled, thereby making it impossible for this language to be Turing complete.

  • \$\begingroup\$ What I would do is instead of having 3 operators is have an infinite number of values and taking the modulo 4 of each to get one of the three operations plus a no-op. When the program starts up it checks that the union of the sets is closed and then removes any elements that are in more than half of the sets. It then repeats this until there is no such element. If the conjecture is true all programs are the same as the empty program, however if it is false you can express every possible program (thats why the no-op is included). \$\endgroup\$
    – Wheat Wizard
    Mar 13, 2017 at 5:03
  • \$\begingroup\$ @WheatWizard The determination of union closed by the interpreter considers the same operator on different variables to be different. x++ is considered to be different from y++. As a result, there is an infinitude of different sets that can be created. With an infinite number of possible sets, if none of the three main types are in more than half of the sets, then it is turing complete. \$\endgroup\$ Mar 13, 2017 at 11:56
  • \$\begingroup\$ It is possible that a proof to the Union closed sets conjecture would leave a conversion to one of three operators as turing complete, as it could be possible to leave all different operators in the program, you would only need 3 out of an infinite number of values to remain. \$\endgroup\$ Mar 13, 2017 at 12:20

Fermat primes

The language works on two potentially infinite tapes, where each location of the tape can store an arbitrary integer. Both tapes are filled with -1 at start. There is also two tape heads that start at position 0 on both tapes.

The interpreter will first read the input, and store the values into the first (data) tape, starting at position 0.

Then it will read the supplied program. For every number it encounters, it will first check if the value is a Fermat prime or not. If yes, it will write to the second (instruction) tape which Fermat prime it is, otherwise it will write -1 to the instruction tape.

Next check the value at the instruction pointer, and do one of the following:

  • -1 or less: Exit the program
  • 0: Move the data tape position one to the left. Move the instruction tape position one to the right
  • 1: Move the data tape position one to the right. Move the instruction tape position one to the right
  • 2: Increase the value at the data tape position. Move the instruction tape position one to the right
  • 3: Decrease the value at the data tape position. Move the instruction tape position one to the right
  • 4: If the value at the current data tape position is zero, then move the instruction tape to the right, until you reach either a matching 5 (or larger) value on the instruction tape, or something smaller than 0. If it is a 5 (or larger), move the instruction pointer the right once again, if it's smaller than 0 then exit the program. If value the current data tape position is not zero, simply move the instruction tape one to the right
  • 5 or more: Move the instruction pointer to the left, until you reach the corresponding 4 value, or you find something less than 0. In the case of the latter, exit the program.

(by matching 5 (or more) and 4 values it means that while searching for the proper value on the instruction tape any time it encounters the same value as the initial command (either 5 (or more) or 4), it will have to skip the appropriate number of the other value (4 or 5 (or more) respectively) on the search)

Loop, until the instruction says you have to exit the program.

When the program exits, output the values on the data tape from position 0 until the first tape position that contains a -1 value.


Note that the language essentially maps to an IO-less Brainfuck interpreter, where F_5 is required to be able to do any kind of proper loops.

However based on the Fermat prime conjecture there are only 5 Fermat primes (F_0 - F_4). If F_5 exists the language is Turing-complete, as we know that Brainfuck is Turing-complete. However, without F_5 you won't be able to do neither branching nor looping, essentially locking you into very simple programs.


(tested with ruby 2.3.1)

#!/usr/bin/env ruby
require 'prime'

CHEAT_MODE = false
DEBUG_MODE = false

def determine_number(n)
  return n.to_i if CHEAT_MODE
  n = n.to_i
  -1 if n<3

  return NUM_CACHE[n] if NUM_CACHE[n]

  i = 0

  loop do
    num = 2**(2**i) + 1
    if num == n && Prime.prime?(n)
      NUM_CACHE[n] = i
    if num > n
      NUM_CACHE[n] = -1
    i += 1


data_tape = Hash.new(-1)
instruction_tape = Hash.new(-1)

STDIN.read.each_char.with_index { |c,i| data_tape[i] = c.ord }
File.read(ARGV[0]).split.each.with_index do |n,i|
  instruction_tape[i] = determine_number(n)

data_pos = 0
instruction_pos = 0

while instruction_tape[instruction_pos] >= 0
  p data_tape, data_pos, instruction_tape, instruction_pos,'------------' if DEBUG_MODE

  case instruction_tape[instruction_pos]
  when 0 then data_pos -= 1; instruction_pos += 1
  when 1 then data_pos += 1; instruction_pos += 1
  when 2 then data_tape[data_pos] += 1; instruction_pos += 1
  when 3 then data_tape[data_pos] -= 1; instruction_pos += 1
  when 4 then
    if data_tape[data_pos] == 0
      count = 1
      instruction_pos += 1
      while count>0 && instruction_tape[instruction_pos] >= 0
        count += 1 if instruction_tape[instruction_pos] == 4
        count -= 1 if instruction_tape[instruction_pos] >= 5
        instruction_pos += 1
      break if count != 0
      instruction_pos += 1
    count = 1
    instruction_pos -= 1
    while count>0 && instruction_tape[instruction_pos] >= 0
      count += 1 if instruction_tape[instruction_pos] >= 5
      count -= 1 if instruction_tape[instruction_pos] == 4
      instruction_pos -= 1 if count>0
    break if count != 0

data_pos = 0

while data_tape[data_pos] >= 0
  print data_tape[data_pos].chr
  data_pos += 1


This will write H (short for Hello World!) to the screen with a newline:

17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17
17 17 17 17 17 17 17 17 17 17

Save as example.fermat and run it like this (note: you always need to have an input):

$ echo -n '' | ./fermat.rb example.fermat

This next example will do a simple Caesar style cypher by incrementing each value of the input by one. You obviously have to replace ? with the 5th Fermat prime:

17 65537 5 17 ? 257

You can try it out that it works by enabling cheat mode and using 2 4 1 2 5 3 as the source code:

$ echo 'Hello' | ./fermat.rb example2_cheat.fermat
  • 2
    \$\begingroup\$ I feel sorry for the poor coder who has to type out the corresponding prime number to get to 5. I hope they have a good keyboard. \$\endgroup\$ Mar 8, 2017 at 13:54
  • 2
    \$\begingroup\$ @AdmBorkBork Don't worry. It just has more bits than the universe has elemental particles. \$\endgroup\$ Mar 8, 2017 at 13:57
  • \$\begingroup\$ @LliwTelracs actually that doesn't make sense since the amount of elemental particles in the universe is Aleph-null(omega) and from omega, it begins to not mean the actual size of the number. (Unless its aleph one :P) \$\endgroup\$ Mar 8, 2017 at 16:33
  • 1
    \$\begingroup\$ @MatthewRoh I had made a mistake. I meant in the observable universe. \$\endgroup\$ Mar 8, 2017 at 17:12
  • 2
    \$\begingroup\$ @MatthewRoh Actually, it could be finite, infinite, uncountable, or even inconsistent with set theory! We will never know, however :( \$\endgroup\$ Mar 12, 2017 at 4:30

Swallows w/ Coconut v2

As the previous version had errors which made it invalid for this contest, and I don't want to have the upvotes from the previous version count for this version which is significantly different, this version is being submitted as a new post.

This language is not Turing complete if the Collatz Conjecture can be proven for all positive integers. Otherwise, the language is Turing complete.

This language was based off of Cardinal.

First, the contVal of the program is calculated using the formula
contVal=sum(sum(ASCII values of row)*2^(row number-1))

Next, 2 Swallows headed in opposite directions are created at each A or E and all conditional turn statements are set to wait for initialization.
Swallows created at an E are headed left/right and swallows created at an A are headed up/down.

Finally, the code will perform steps until all pointers have been removed or contVal has fallen to one.

At each step, if contVal%2==0 it will be divided by 2, otherwise, it will be multiplied by three and incremented by one.


0 : set value to 0
+ : increment value by 1
> : change direction to right
v : change direction to down
< : change direction to left
^ : change direction to up
R : Subsequent pointers after the first pointer compare with the value of the first pointer. If equal, go straight, else turn right.
L : Subsequent pointers after the first pointer compare with the value of the first pointer. If equal, go straight, else turn left.
E : Duplicate the pointer but heading in the directions left and right
A : Duplicate the pointer but heading in the directions up and down
? : Remove the pointer if the value is 0

function runCode(){
  var inputBox=document.getElementById("code");
  //Determine the endurance of the swallows
  //Spawn the African and European swallows and initialize the conditionals
      switch (pointerList[i][2]){
        case 0:
        case 1:
        case 2:
        case 3:
          case "+":
          case "0":
          case ">":
          case "v":
              case "<":
          case "^":
          case "R":
          case "L":
          case "A":
          case "E":
          case "?":
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>

<p class=results></p>


If the Collatz Conjecture can be proven for all positive integers, the duration of any program run in this language is finite, as contVal will always converge to 1, thereby ending the program.

Otherwise, I simply need to prove that this language can implement the following functions

Increment: which is represented by +
Constant 0: which is represented by 0
Variable access: variables are stored as pointers as they travel
Statement concatenation: by changing the distance travelled to operations, the order in which operations are performed can be changed
For loop: In this language

E   > V

will act as a for loop >count up to 1 (further code could be added to the loop)

Similarly, the code


Will act as a do until equal to the conditional value set in R loop.

  • \$\begingroup\$ You beat me too it, I was going to do something ith the collatz conjecture. Nice job, on the interesting take on it. I was going to just create a language which would only be able to store numbersif they converged to 1. \$\endgroup\$ Feb 25, 2017 at 18:57
  • \$\begingroup\$ I'm confused. Where does the Collatz function figure into this? From a second readthrough I think you mean to say that the function is applied to contVal at every step (and therefore if the conjecture is true, there are no infinite loops)--but I don't see that explicitly stated anywhere in the answer. ?? \$\endgroup\$
    – DLosc
    Mar 8, 2017 at 19:40
  • \$\begingroup\$ Sorry, while it is doing that I think I had accidentally cut that out of my description at some point \$\endgroup\$ Mar 8, 2017 at 19:41


Whew, that was fun.

Perfection/Imperfection is only complete if there are infinite perfect numbers. If there are, it's called Perfection, and if there are not, it is called Imperfection. Until this mystery is solved, it holds both names.

A perfect number is a number whose divisors sum to the number, so six is a perfect number because 1+2+3=6.

Perfection/Imperfection has the following functions:

Perfection/Imperfection is stack-based, with a zero-indexed stack.


p(x, y): pushes x to the stack in the yth position.

z(x, y): pushes x to the stack in the yth position, gets rid of what was previously in the yth position

r(x): removes the xth item from the stack

k(x): returns the xth item on the stack

a(x, y): adds x and y. When used with strings, it puts them together in order xy.

s(x, y): subtracts y from x. with strings, removes the last len(y) from x

m(x, y): multiplies x and y. If used with strings, multiplies x times len y.

d(x, y): divides x by y

o(x): prints x

i(x, y): if x evaluates to true, then it executes function y

n(): returns the counter the code block is being called on.

q(): returns the length of the stack

t(): user input

e(x, y): If x is an integer, if x and y have the same value, then this returns 1. if y is a string then it gets the length of y. if x is a string, then it converts y to a string and checks if they are the same, and if they are, returns 1. Otherwise it returns 0.

l(x, y): if x is larger than y, then it returns 1. If there is a string, then it uses the length of the string.

b(): stops the program.

c(x, y): runs x, then y.

To get the equivalent of a Python and, multiply the two values together. For or, add the values, and for not, subtract the value from 1. This only works if the value is 1 or 0, which can be achieved by dividing the number by itself.

Data types: integers and strings. Strings are denoted by '', and all non-integer numbers are rounded.


Code consists of nested functions inside of ten {}s. For example, a program that would get to inputs and print them added would be: {o(a(t(), t()))}. In the background of the program there is a counter that starts at 0 and progresses by 1 every time it executes a code block. The first code block runs at 0, and so on. Once the ten code blocks are executed, the sixth one is executed every time the counter reaches a perfect number. You do not need to have all ten code blocks for the program to work, but you need 7 if you want to make a loop. To better understand how this language works, run the following program, which prints the counter every time the counter reaches a perfect number: {}{}{}{}{}{}{o(n())}.

The interpreter can be found here: repl.it/GL7S/37. Either select 1 and type your code in the terminal, or paste your code in the code.perfect tab and select 2 when you run. It will make sense when you try it.

Proof of Turing completeness/lack of Turing completeness.

According to this software engineering stack exchange article, a Turing complete must be able to have a form of conditional repetition of jump, and have a way to read or write memory. It can read/write memory in the form of the stack, and it can loop due to the fact that the 6th code block is executed every time the counter reaches a perfect number. If there are an infinite number of perfect numbers, it can loop indefinitely and is Turing complete, and otherwise it is not.

Self Bitwise Cyclic Tag interpreter that takes 5 characters, 1 or 0, as input:


It can be expanded to take any number of chars as input. It could take infinite input, but only if there are infinite perfect numbers!

  • 1
    \$\begingroup\$ I think you might only be creating a new value for looping locally as it isn't shared with the function. \$\endgroup\$ Mar 9, 2017 at 17:08
  • 3
    \$\begingroup\$ As it stands you do not have a proof of TC. The software engineering article you link to gives a rough set of requirements, however TC is not just a bunch of boxes to check off. You will need to implement a TC automaton (like a Minsky Machine) or show that your language is undecidable. \$\endgroup\$
    – Wheat Wizard
    Mar 11, 2017 at 19:23
  • 2
    \$\begingroup\$ @WheatWizard There, I added a Bitwise Cyclic Tag interpreter. It can be modded to take any amount of chars as input. It could possibly take infinite chars as input, but only if there are infinite perfect numbers! \$\endgroup\$
    – sporkl
    Mar 11, 2017 at 20:00
  • 2
    \$\begingroup\$ "Once the ten code blocks are executed, the sixth one is executed every time the counter reaches a perfect number. " So the interpreter just directly counts perfect numbers? I feel like this goes against the spirit of the challenge. The actual language specification doesn't matter much, it can be anything Turing-complete plus "only run for a step only when you hit a perfect number". \$\endgroup\$
    – xnor
    Mar 12, 2017 at 1:11


This programming language is Turing complete iff the Scholz conjecture is true.

I wrote this language because @SztupY was saying that there wouldn't be any results that rely on the conjecture to be true to be Turing complete

List of Commands

+(x)      Increment x (INC)   
-(x)      Decrement x (DEC)  
j(x,y)    Jump to instruction x if y is 0 (JZ)  
x         End program (HALT) 

With these commands, this language can simulate a Minsky machine


I would highly recommend not running this. It uses an extraordinarily slow method of checking the addition chain.

function runCode(){
  var inputBox=document.getElementById("code");
  input=input.split(" ");

      return arr[x-1];
    return minim;
      case "+":
      case "-":
      case "j":
      case "x":
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>

<p class=results></p>

Turing completeness

The language uses a counter for number of commands run which it checks against the Scholz conjecture to modify the turing completeness of the language.

If the Scholz conjecture is true, this program works exactly like a normal Minsky machine with
Jump if Zero

However, if the Scholz conjecture is false, the counter will eventually reach a value for which the Scholz conjecture does not hold true. As the language has been designed to exit upon reaching a number which the Scholz conjecture is false, the program will exit every time after running that many commands. Therefore, all programs will have limited length. As this disagrees with the requirements for the language to be Turing complete,

"The tape cannot be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a linear bounded automaton",

the language would not be Turing complete should the Scholz conjecture be false

  • 1
    \$\begingroup\$ +1, as this actually hard-bakes the conjecture requirement into the language, rather then adding something extraneous to kill the language if the conjecture is true/false \$\endgroup\$
    – Gryphon
    Jun 23, 2017 at 10:53
  • \$\begingroup\$ I don't get it. The commands you provide are just exactly the ones you need to simulate a Minsky machine, so if that's all there is to it your language is Turing complete regardless of the Scholz conjecture. You must be missing something from your explanation. \$\endgroup\$
    – N. Virgo
    Apr 15, 2018 at 4:08
  • \$\begingroup\$ @Nathaniel One of the requirements for a Turing complete language is that the language can end up in an infinite loop (halting problem). My code counts up as it runs instructions and if the Scholz conjecture is false, the program will always stop after a set number of instructions. \$\endgroup\$ Apr 15, 2018 at 13:23
  • 1
    \$\begingroup\$ Yes, but you have forgotten to explain what causes it to stop if the Scholz conjecture is false. Take another look at your answer - it's not there at all. \$\endgroup\$
    – N. Virgo
    Apr 15, 2018 at 13:42
  • 2
    \$\begingroup\$ Yes, but you forgot to actually say that. Really, take a look. It isn't there. \$\endgroup\$
    – N. Virgo
    Apr 15, 2018 at 13:54


Betrothed Github.

The readme and specification is on the github, under "README.txt".

Generally, a Betrothed program is composed of pairs of lines, whose lengths are distinct twin prime pairs or betrothed pairs (no duplicates can occur). The program is executed by find "pliable subsets" of the first line in the pair within the second line. The number of such subsets, combined with the levenshtein distance between the original second line and the second line without the pliable subsets, determine the command to execute.

I will excerpt the proof for this post:


Now, no language can be Turing Complete with bounded program size. Therefore, if Betrothed
is Turing Complete, it must have unbounded program size. Since the lengths of the lines of
a Betrothed program must be twin prime pairs or betrothed pairs, and since both sequences
are unproven to be infinite or finite, Betrothed has unbounded program size if and only if
there are infintie betrothed pairs, there are infinite twin prime pairs, or both.

    Next: to prove that if Betrothed has an unbounded program size, then it is Turing
Complete. I will use the op-codes from the above table to demonstrate key factors of a
Turing Complete language; they are of the form  [index]<[ld]> .

  1. Conditional goto: 6<> 5<>, or if-popjump. This can be used to form a loop.
  2. Inequality to a constant K: 10<K> 
  3. Arbitrarily large variable space: you can use some separator constant C.

    With this, I have sufficient reason to believe that Betrothed is Turing Complete.
  • 4
    \$\begingroup\$ "Now, no language can be Turing Complete with bounded program size." I'm confused about this statement... On one hand it's true that with a bounded program size we can only write a finite number of different programs, but on the other hand a common proof for Turing Completeness is writing an interpreter for a different Turing Complete language, which doesn't need unbounded program size at all... \$\endgroup\$
    – Leo
    Mar 6, 2017 at 16:01
  • 1
    \$\begingroup\$ Well, the program passed to the interpreter doesn't need to be put in the code of the interpreter, it should be given to the interpreter as input \$\endgroup\$
    – Leo
    Mar 6, 2017 at 18:30
  • 7
    \$\begingroup\$ @Leo. I will say that, in order for the language to be TC, it must be able to encode the program to be passed to the interpreter (that is, imagine that this language has no input command.) Imagine a language with one command: b. This interprets a BF program, which is placed after it, like b+++++.. The size of the program, however, is limited to 10 characters. While it can interpret BF, it cannot compute all programs a Turing machine can. \$\endgroup\$ Mar 6, 2017 at 18:59
  • 3
    \$\begingroup\$ @EriktheOutgolfer the main problem with your problem is "it can put the BF program it gets from input..." For this, I strongly encourage you to read or reread my previous comment, particularly this first sentence. If the language is only Turing complete based upon the input, then how can it, without any input, be Turing complete? That is, in order for the language to be Turing complete, it is the language's program itself that must encode the program. Otherwise, one is found that they are encoding the program in the input, which is not a valid way of programming. \$\endgroup\$ Mar 8, 2017 at 12:02
  • 1
    \$\begingroup\$ I don't think this is a settled point. This Esolang article discusses the issue. (There's also the question of whether a program that prints out every possible terminating program in a Turing-complete language, together with its output, is a Turing-completeness demonstration; that doesn't require input and can be done with a finitely long program.) \$\endgroup\$
    – user62131
    Mar 8, 2017 at 22:57

Amicable Parity

This language is based on whether there are any amicable numbers with opposite parity.


x : End program if not on top line  
+ : increment stored value  
- : decrement stored value  
{ : set next goto x value to current x value
} : goto previous x value set by {  
j : Go down one line if the special value is an amicable number and the
    parity is opposite to the matching number (loops back to top). If the
    special value is not an amicable number and not on the top line, go up
    one line.  

Control flow

The program cycles repeatedly from left to right before looping back to the start. If it encounters a "j", it checks the value to determine if it should change rows. If the number is an amicable number with opposite parity to its match, it goes down one row (looping back to top), Otherwise, if the number is an amicable number, it goes up one row if not already in the top row.

The program can only end if the program reaches an x in any row outside of the top row.

Turing Completeness

This program can be used to simulate a Minsky machine assuming that there is a pair of amicable numbers with opposite parity.

j,{ and } can be used to simulate JZ(r,x) although it would check for amicable numbers as opposed to zero.
+ is INC(r)
- is DEC(r)
x is HALT

If you can not leave the first row, the x and } commands do nothing. This results in the program being unable to enter a HALT state unless it is an empty program. Therefore, under the description that Turing completeness requires a HALT state, the language would be Turing incomplete.


  return sum;
function runCode(){
  var inputBox=document.getElementById("code");
      else if(input[j][i]=="j"){
        else if(j&&val!=sumDiv(sumDiv(val))){
      else if(input[j][i]=="+"){
      else if(input[j][i]=="-"){
      else if(input[j][i]=="{"){
      else if(input[j][i]=="}"&&j){
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>

<p class=results></p>



Taggis is a language based on tag systems.

Taggis's turing completeness is based on the Collatz Conjecture


A Taggis program's syntax is simply three strings (production rules) consisting entirely of the letters a, b, and c, separated by spaces.


Taggis's only program state is a string consisting of the same three characters.

Taggis implements a TS(3, 2) tag system, where in every step the first 2 letters of the current "tag" are removed, and the very first letter that was in that removed portion gets its corresponding production rule appended to the end of the string.

For example, the Taggis program bc a aaa implements the 3n + 1 problem, where iterations are represented by a corresponding number of as and the 3n + 1 step is replaced with (3n + 1) / 2 [1], leading to the program output:

aaa // 3
        aaaaa // 5
                    aaaaaaaa // 8
                                    aaaa // 4
                                            aa // 2
                                                a // 1 and halt because we then begin an infinite loop

Turing completeness

Of course, this simple system may seem far too simple to emulate Turing completeness, but it turns out that any Turing machine with 2 symbols (a class that includes universal machines) can be converted to a tag system with 2 removed characters from the head, and 32 * m production rules, where m is the number of states in the Turing machine.

The smallest known universal Turing machine with only 2 symbols uses 18 states and thus the corresponding tag system contains a whopping 576 production rules [2].

However, the computational class of the set of all tag systems with 3 productions and 2 removed symbols is tied to the Collatz Conjecture [2]. If the Collatz Conjecture is proved to be false, then Taggis is Turing-complete. Otherwise, it is based on ANOTHER unsolved problem in mathematics, finding a smaller Turing machine than

def taggis(inp, a, b, c):
    current = inp
    seen = set()
    while True:

        yield current

        head = current[0]

        current = current[2:]

        current.extend([a, b, c][head])

        if tuple(current) in seen:

def parse():
    program = input().split(" ")

    assert len(program) == 3, "There has to be exactly 3 production rules!" 

    productions = []

    for production in program:

        production = [{"a": 0, "b": 1, "c": 2}[x] for x in production]

    program_input = [{"a": 0, "b": 1, "c": 2}[x] for x in input()]

    k = 0   

    for step in taggis(program_input, *productions):
        print(' ' * k +''.join(['abc'[x] for x in step]))

        k += 2
    print(' ' * (k - 1) + 'HALT')

  1. which is equivalent to the original Collatz function as 3n + 1 of an odd n will always be even and therefore the division can be automatically applied

  2. Tag systems and Collatz-like functions, Liesbeth De Mol,



Disclaimer: It is a bit of a mess and pretty simple. This is the first language I have ever written and the conjecture is the only one I understood. I know another user had a longer answer with the same one but I decided to write this anyway.

To write in Newline you must have a lot of time and newlines (\n). This works off of the Legendre conjecture being true. Every operator must fall on a number in the Legendre conjecture that we start with n = 1. Every time you have an operator you take the amount of \n's and plug that into the Legendre Conjecture and get the range that the next prime amount of \n's must fall in. So to start off you do \n\n then you move on to an operator then \n then another operator we are at 3 newlines. Now the next one is it 5 so you add \n\n and on operator making sure that the last operator line has the right amount of newlines that you are on a prime amount that falls in the Legendre conjecture that we started.

Numbers (the array) is like the variables. Every time an operator runs (that uses numbers) it increments.

+ adds
- subtracts
/ divide
* multiply 
s sqrt
% mod
a push to vars
g sets stack to numbers
q pushes value of stack to numbers
i increment 
d decrement
r stops subtraction at 0
w turns back on subtraction past 0
[ starts loop
] ends loop runs until stack is 0
{ starts loop
} ends loop and loops until loops[ln] is 0
k increment loops

As long as we have unlimited primes that follow the rules this language has non finite tape.

Minsky machine


How it works:

\n\ng     # the first two newlines are to get to a prime number of newlines (2) then sets the value of stack to the first variable in the array numbers (see code in link)

\nr       # gets to the next number and makes it so subtraction stops at 0

\n\n[     # starts the loop

\n\nd     # decrements stack 

\n\n\n\n] # ends loop

Try it out on KhanAcademy.

  • \$\begingroup\$ @wheat it doesn't need to loop with non finite memory \$\endgroup\$ Mar 7, 2017 at 17:07
  • \$\begingroup\$ It only works if it is true. I can't finish the write up right now as I am on mobile but will tonight \$\endgroup\$ Mar 7, 2017 at 17:08
  • \$\begingroup\$ Even if you have infinite memory, you still need to be able to infinite loop. \$\endgroup\$
    – Pavel
    Mar 7, 2017 at 17:50
  • \$\begingroup\$ I have loops. Trying to make them infinite \$\endgroup\$ Mar 7, 2017 at 22:35
  • \$\begingroup\$ Right now they crash \$\endgroup\$ Mar 7, 2017 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.