Write a Programming language of Unknown Completeness 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.
Rules

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 popularity-contest 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

It should not be a simple patch of an existing language.  Changing an existing language to fit the specifications is fine but patching on a condition is discouraged because it is boring.  As said by ais523 in the Nineteeth Byte:

I prefer to make my esolangs' gimmicks more firmly baked into the language


It should be interesting as a standalone esoteric language.
Legendre

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

Initialization:

1 1 1 1 ? 24


x INC (A/B) y:

A: 

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


B: 

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


x DEC (A/B) y z:

A: 

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


B: 

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


x HALT:

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.

Interpreter

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 &gt; 1:
            t = True
            for j in range(2,int(i ** 0.5)+1):
                t = i/j != round(i/j)
                if not t:
                    break
        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
        stack.append(commandseries.pop(0))

    elif command == 3:#execute top instruction
        commandseries.insert(0,stack.pop())

    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:
            stack.pop()

    elif command == 7:#duplicate top of stack
        stack.append(stack[-1])

    elif command == 8:#halt
        halt = True

    else:#run custom
        try:
            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("-f","--file")
    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 == "":
            return
    else:
        pre = open(args.file).read()

    mid = pre.split()
    final = []

    for i in mid:
        if i == "?" and allow_zero:
            final.append("?")
        elif i != 0 or allow_zero: #and allow_zero)
            final.append(int(i))

    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
    else:
        if args.stackOut:
            print(stack)
        else:
            for i in stack:
                print(i == "?" and "?" or chr(i),end = "")
            print("")
        if args.file or halt:
            return
        else:
            main(stack,functions,prev)


if __name__ == '__main__':
    main([],I_need_missing(),I_need_missing())