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

1 1 1 1 ? 24

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

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

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.

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
        commandseries[0:0] = functions[command]

    return commandseries,stack,functions,prev,halt

def main():
    #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:
        a = input()
        while a:
            pre = pre + "" + a
            a = input()
    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))

    #Shared variables
    stack = []
    functions = I_need_missing()
    prev = I_need_missing()
    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("")
        return

if __name__ == '__main__':
    main()

Betrothed

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:

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.

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

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.

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

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.

Toeplitz

This language is only Turing complete if the Toeplitz conjecture is proven false. This conjecture asks if every closed curve on a plane contains all four vertices of a square. This theoretical language is unbounded by size or time.

How it works

This language provides four data pointers, which start off in the same position on a Jordan curve of unknown (possibly infinite) length and shape. The commands used are similar to those used in Brainfuck, which move the data pointer, change its value, take input or output, and move the instruction pointer. If the curve was stretched into a straight line, the data pointer could be visualized as moving left or right on the line in fluid motion. The only four written commands this language uses are commands for moving the data pointer left or right or conditional jump commands, along with the numbers 1 through 4 for specifying which data pointer is being referred to. Whenever the positions of the four data pointers form the vertices of a rectangle, a command is executed, depending on the side ratios.

Written Commands

< : move instruction pointer 1 unit to the left
> : move instruction pointer 1 unit to the right
[ : if byte at specified data pointer is 0, jump instruction pointer forward to command after matching ] command
] : if byte at specified data pointer is not 0, jump instruction pointer back to command after matching [ command

Each < or > is preceded by a number from 1 to 4 to specify which data pointer is being moved. 1 unit is of arbitrary size.

Runtime Commands

These commands are executed whenever a rectangle is formed by the positions of the four data points on the curve. To determine the sides, side1 is either side 1-2 or 1-3 and side2 is either side 2-4 or 3-4 if side1 is not determined first; if either possible sides for side1 are different length sides, side2 is determined first; if the possibilities for side1 agree or contain a diagonal, side1 is defined first and side2 is the side with the other length.

side1 / side2 < 1 and side1 was determined first : increment byte at all data pointers
side1 / side2 < 1 and side2 was determined first : decrement byte at all data pointers
side1 / side2 > 1 and side1 was determined first : output byte at all data pointers
side1 / side2 > 1 and side2 was determined first : accept input for all data pointers
side1 / side2 = 1 (side1 = side2; the rectangle is a square) : halt program

As you can see, the Turning completeness of this program requires there to be vertices of rectangles of all side ratios present in the Jordan curve.

Example Program

1>2>>3<<<4<4[4<4] : move dp1 1 unit right; move dp2 2 units right; move dp3 3 units left; move dp4 1 unit left; move dp4 1 unit left every time the byte value at its position is nonzero

If the programmer could define the closed curve in addition to the program, through an array of coordinates with 1 index per unit, for example, then I believe that this language would be Turning complete; the question is whether it is Turing complete for all closed curves.

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.

Amicable Parity

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

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

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): pushes x to the stack

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 execute line the function 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.

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.

The interpreter can be found here: repl.it/GL7S/23. 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.

There is a small interpreter bug, where the b() command does not work. I am working on trying to figure out how to fix it, but if you figure out a fix, let me know.

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.

Soles

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

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

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. At that point, the program will exit. 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