[Question]
  [
Determining whether a Language is [Turing Complete](https://en.wikipedia.org/wiki/Turing_completeness) 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](https://en.wikipedia.org/wiki/List_of_unsolved_problems_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](https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics).
* 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](/questions/tagged/popularity-contest "show questions tagged '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](https://codegolf.stackexchange.com/users/62131/ais523) in the Nineteeth Byte:
> 
> [I prefer to make my esolangs' gimmicks more firmly baked into the language](http://chat.stackexchange.com/transcript/message/35611798#35611798)
> 
> 
>
* It should be interesting as a standalone esoteric language.
  
[Answer]
## Legendre
This language is only Turing-complete if and only if [Legendre's conjecture](https://en.wikipedia.org/wiki/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](https://oeis.org/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 > 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())
```
[Answer]
## Union Closed
This programming language is Turing complete iff the [Union-closed Sets conjecture](https://en.wikipedia.org/wiki/Union-closed_sets_conjecture) is incorrect.
## Controls
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 
## Syntax
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  
j(x,y)!=j(a,b)  
+(x)!=+(y) 
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) 
## Interpreter
```
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) {
    res.push(obj[k]);
  }
  return res;
}
function runCode(){
  var inputBox=document.getElementById("code");
  input=inputBox.value;
  input=input.split("\n").map(a=>a.split(" "));
  input=input.filter(x=>x.filter(y=>y.length>0).length>0);
  for(i=0;i<input.length;i++){
    for(j=0;j<input[i].length;j++){
      switch(input[i][j][0]){
        case"j":
          eval(input[i][j].split(",")[0].slice(2)+"=0;"+input[i][j].split(",")[1].slice(0,-1)+"=0")
          break;
        default:
          eval(input[i][j].slice(0,1)+"=0");
          break;
      }
    }
  }
  counts=[0,0,0];
  for(i=0;i<input.length;i++){
    count=[0,0,0];
    for(j=0;j<input[i].length;j++){
      switch(input[i][j][0]){
        case"j":
          count[2]=1;
          break;
        default:
          if(input[i][j][1]=="+"){
            count[0]=1;
          }
          else{
            count[1]=1;
          }
        break;
      }
    }
    for(j=0;j<3;j++){
      counts[j]+=count[j];
    }
  }
  for(i=0;i<input.length-1;i++){
    for(j=i+1;j<input.length;j++){
      valid=0;
      union=union_arrays(input[i],input[j]);
      for(k=0;k<input.length;k++){
        if(union_arrays(input[k],[]).sort().join("")==union.sort().join("")){
          valid=1;
        }
      }
      if(!valid){
        break;
      }
    }
    if(!valid){
      break;
    }
  }
  console.log(valid)
  var queue=[]
  if(valid){
    queue.push(input[0]);
    while(queue.length){
      for(i=0;i<queue[0].length;i++){
        if(queue[0][i][0]=="j"&&counts[2]<input.length/2){
          eval("if("+queue[0][i].split(",")[1].slice(0,-1)+"===0&&input["+queue[0][i].split(",")[0].slice(2)+"])queue.push(input["+queue[0][i].split(",")[0].slice(2)+"])");
        }
        if(queue[0][i][1]=="+"&&counts[0])
          eval(queue[0][i]);
        if(queue[0][i][1]=="-"&&counts[1])
          eval(queue[0][i]);
      }
      queue=queue.splice(0,1);
    }
  }
}
```
```
<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.
[Answer]
## 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.
## Proof
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](https://www.wikiwand.com/en/Fermat_number) (`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.
## Implementation
(tested with ruby 2.3.1)
```
#!/usr/bin/env ruby
require 'prime'
CHEAT_MODE = false
DEBUG_MODE = false
NUM_CACHE = {}
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
      break
    end
    if num > n
      NUM_CACHE[n] = -1
      break
    end
    i += 1
  end
  NUM_CACHE[n]
end
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)
end
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
      end
      break if count != 0
    else
      instruction_pos += 1
    end
  else
    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
    end
    break if count != 0
  end
end
data_pos = 0
while data_tape[data_pos] >= 0
  print data_tape[data_pos].chr
  data_pos += 1
end
```
Examples:
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
5
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
```
[Answer]
# 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](https://en.wikipedia.org/wiki/Collatz_conjecture) can be proven for all positive integers. Otherwise, the language is Turing complete.
This language was based off of [Cardinal](https://esolangs.org/wiki/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.
## Commands:
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");
  input=inputBox.value;
  area=input.split('\n');
  width=0;
  height=area.length;
  for(i=0;i<height;i++){
    width=Math.max(width,area[i].length);
  }
  //Determine the endurance of the swallows
  contVal=0;
  for(i=0;i<height;i++){
    for(j=0;j<area[i].length;j++){
      contVal+=((j+1)<<i)*area[i].charCodeAt(j);
    }
  }
  //Spawn the African and European swallows and initialize the conditionals
  pointerList=[];
  condList=[];
  for(i=0;i<height;i++){
    for(j=0;j<area[i].length;j++){
      if(area[i][j]=='A'){
        pointerList.push([i,j,0,0]);
        pointerList.push([i,j,2,0]);
      }
      if(area[i][j]=='E'){
        pointerList.push([i,j,1,0]);
        pointerList.push([i,j,3,0]);
      }
      if(area[i][j]=='R'||area[i][j]=='L'){
        condList.push([i,j,-1]);
      }
    }
  }
  output='';
  while(1){
    for(i=0;i<pointerList.length;i++){
      switch (pointerList[i][2]){
        case 0:
          pointerList[i][1]++;
          break;
        case 1:
          pointerList[i][0]++;
          break;
        case 2:
          pointerList[i][1]--;
          break;
        case 3:
          pointerList[i][0]--;
          break;
      }
      if(pointerList[i][1]<0||pointerList[i][0]<0||pointerList[i][0]>=height||pointerList[i][1]>=area[pointerList[i][0]].length){
        pointerList.splice(i,1);
      }
      else{
        switch(area[pointerList[i][0]][pointerList[i][1]]){
          case "+":
            pointerList[i][3]++;
            break;
          case "0":
            pointerList[i][3]=0;
            break;  
          case ">":
            pointerList[i][2]=1;
            break;
          case "v":
            pointerList[i][2]=2;
            break;
              case "<":
            pointerList[i][2]=3;
            break;
          case "^":
            pointerList[i][2]=0;
            break;
          case "R":
            for(j=0;j<condList.length;j++){
              if(pointerList[i][0]==condList[j][0]&&pointerList[i][1]==condList[j][1]){
                if(condList[j][2]==-1){
                  condList[j][2]=pointerList[i][3];
                  pointerList.splice(i,1);
                }
                else{
                  if(pointerList[i][3]!=condList[j][2]){
                    pointerList[i][2]=(pointerList[i][2]+1)%4;
                  }
                }
              }
            }
            break;
          case "L":
            for(j=0;j<condList.length;j++){
              if(pointerList[i][0]==condList[j][0]&&pointerList[i][1]==condList[j][1]){
                if(condList[j][2]==-1){
                  condList[j][2]=pointerList[i][3];
                  pointerList.splice(i,1);
                }
                else{
                  if(pointerList[i][3]!=condList[j][2]){
                    pointerList[i][2]=(pointerList[i][2]+3)%4;
                  }
                }
              }
            }
            break;
          case "A":
            pointerList.push([pointerList[i][0],pointerList[i][1],0,pointerList[i][3]]);
            pointerList.push([pointerList[i][0],pointerList[i][1],2,pointerList[i][3]]);
            break;
          case "E":
            pointerList.push([pointerList[i][0],pointerList[i][1],1,pointerList[i][3]]);
            pointerList.push([pointerList[i][0],pointerList[i][1],3,pointerList[i][3]]);
            break;
          case "?":
            pointerList.splice(i,1);
        }
      }
    }
    if(contVal%2===0){
      contVal=contVal/2;
    }
    else{
      contVal=contVal*3+1;
    }
    if(!pointerList.length||contVal==1){
      break;
    }
  }
  console.log(output);
}
```
```
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>
<p class=results></p>
```
## Explanation:
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](https://cs.stackexchange.com/a/995)
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
    ^+R
      +
      A
```
will act as a for loop >count up to 1 (further code could be added to the loop)
Similarly, the code
```
Rv
^<
```
Will act as a do until equal to the conditional value set in R loop. 
[Answer]
# Perfection/Imperfection
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.
**Commands:**
`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.
**Syntax:**
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](https://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](https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete), 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:
```
{p(t(),0)}{(p(t(),0)}{p(t(),0)}{p(t(),0)}{p(t(),0)}{p(0,0)}{c(i(e(k(s(q(),k(0))),0),c(r(q()),i(l(k(0),0),z(s(k(0),1),0)))),i(e(k(s(q(),k(0))),1),c(z(a(k(0),1),0),i(e(k(q()),1),p(k(s(q(),k(0))),1)))))}
```
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!
[Answer]
# Soles
This programming language is Turing complete iff the [Scholz conjecture](https://en.wikipedia.org/wiki/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
## Interpreter
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=inputBox.value;
  input=input.split(" ");
  counter=1;
  lvals=[0];
  l=(x,arr)=>{
    if(arr[x-1]){
      return arr[x-1];
    }
    minim=Number.MAX_SAFE_INTEGER;
    console.log(min);
    for(i=Math.floor(x/2);i>0;i--){
      minim=Math.min(minim,l(i,arr)+l(x-i,arr)+1);
    }
    return minim;
  };
  cont=1;
  pointer=0;
  while(cont){
    lvals[Math.pow(2,counter)-2]=l(Math.pow(2,counter)-1,lvals);
    lvals[counter-1]=l(counter,lvals);
    if(lvals[Math.pow(2,counter)-2]>n-1+lvals[counter-1]){
      break;
    }
    switch(input[pointer][0]){
      case "+":
        x=input[pointer].slice(2,-1);
        eval(x+"++")
        break;
      case "-":
        x=input[pointer].slice(2,-1);
        eval(x+"--")
        break;
      case "j":
        x=input[pointer].split(",")[0].slice(2);
        y=input[pointer].split(",")[0].slice(0,-1);
        eval("if(!"+y+")pointer="+x+"-1");
        break;
      case "x":
        cont=0;
        break;
    }
    pointer++;
    if(pointer>input.length){
      break;
    }
    counter++;
  }
}
```
```
<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  
Increment  
Decrement  
Jump if Zero  
Halt
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
[Answer]
# Betrothed
[Betrothed Github](https://github.com/ConorOBrien-Foxx/Betrothed).
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:
```
V. PROOF OF TURING COMPLETENESS
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.
```
[Answer]
# Amicable Parity
This language is based on whether there are any [amicable numbers](https://en.wikipedia.org/wiki/Amicable_numbers) with [opposite parity](https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics#Number_theory).
## Commands
```
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](https://en.wikipedia.org/wiki/Talk%3ATuring_completeness#The_need_for_an_explicit_HALT_state), the language would be Turing incomplete.
## Interpreter
```
sumDiv=r=>{
  sum=0;
  for(i=1;i<=Math.sqrt(r)&&i!=r;i++){
    if(r%i===0){
      sum+=i+r/i;
    }
    if(i*i==r){
      sum-=i;
    }
  }
  return sum;
};
function runCode(){
  var inputBox=document.getElementById("code");
  input=inputBox.value;
  input=input.split("\n");
  val=2;
  exit=0;
  loop=0;
  for(j=0;!exit;){
    for(i=0;i<input[j].length;i++){
      if(input[j][i]=="x"&&j){
        exit=1;
        break;
      }
      else if(input[j][i]=="j"){
        if(val==sumDiv(sumDiv(val))&&val!=sumDiv(val)&&(val+sumDiv(val))%2){
          j=(j+1)%input.length;
          i--;
        }
        else if(j&&val!=sumDiv(sumDiv(val))){
          j--;
          i--;
        }
      }
      else if(input[j][i]=="+"){
        val++;
      }
      else if(input[j][i]=="-"){
        val--;
      }
      else if(input[j][i]=="{"){
        loop=i;
      }
      else if(input[j][i]=="}"&&j){
        i=loop;
      }
      if(input[j].length==i+1){
        i=-1;
      }
    }
  }
}
```
```
<input type="text" id="code" value=""/>
<button onClick="runCode()">Submit</button>
<p class=results></p>
```
[Answer]
# Taggis
Taggis is a language based on [tag systems](https://en.wikipedia.org/wiki/Tag_system#Example:_Computation_of_Collatz_sequences). 
Taggis's turing completeness is based on the [Collatz Conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture)
## Syntax
A Taggis program's syntax is simply three strings (production rules) consisting entirely of the letters 
a, b, and c, separated by spaces.
## Execution
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 `a`s and the 3n + 1 step is replaced with (3n + 1) / 2 [1], leading to the program output:
```
aaa // 3
  abc
    cbc
      caaa
        aaaaa // 5
          aaabc
            abcbc
              cbcbc
                cbcaaa
                  caaaaaa
                    aaaaaaaa // 8
                      aaaaaabc
                        aaaabcbc
                          aabcbcbc
                            bcbcbcbc
                              bcbcbca
                                bcbcaa
                                  bcaaa
                                    aaaa // 4
                                      aabc
                                        bcbc
                                          bca
                                            aa // 2
                                              bc
                                                a // 1 and halt because we then begin an infinite loop
                                                 HALT
```
## 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:
        seen.add(tuple(current))
        yield current
        head = current[0]
        current = current[2:]
        current.extend([a, b, c][head])
        if tuple(current) in seen:
            return
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]
        productions.append(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')
parse()
```
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*,](https://www.sciencedirect.com/science/article/pii/S0304397507007700)
[Answer]
# Newline
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
```
\n\ng\nr\n\n[\n\nd\n\n\n\n]
```
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](https://www.khanacademy.org/computer-programming/melang/5474968288952320).
]