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

  • This conversation has been moved to chat. – Dennis Mar 5 '17 at 17:08
  • 11
    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." – xnor Mar 12 '17 at 1:20
  • @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. – Post Left Garf Hunter Mar 12 '17 at 1:43
  • 2
    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. – fəˈnɛtɪk Mar 13 '17 at 12:37
  • 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). – PyRulez Jun 1 '17 at 2:28

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 > 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())
up vote 12 down vote
+450

Union Closed

This programming language is Turing complete iff the 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.

  • 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). – Post Left Garf Hunter Mar 13 '17 at 5:03
  • @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. – fəˈnɛtɪk Mar 13 '17 at 11:56
  • 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. – fəˈnɛtɪk Mar 13 '17 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.

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
  • 1
    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. – AdmBorkBork Mar 8 '17 at 13:54
  • 1
    @AdmBorkBork Don't worry. It just has more bits than the universe has elemental particles. – fəˈnɛtɪk Mar 8 '17 at 13:57
  • @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) – lol Mar 8 '17 at 16:33
  • @MatthewRoh I had made a mistake. I meant in the observable universe. – fəˈnɛtɪk Mar 8 '17 at 17:12
  • 1
    @MatthewRoh Actually, it could be finite, infinite, uncountable, or even inconsistent with set theory! We will never know, however :( – CalculatorFeline Mar 12 '17 at 4:30

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

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

  • 1
    +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 – Gryphon Jun 23 '17 at 10:53
  • 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. – Nathaniel Apr 15 at 4:08
  • @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. – fəˈnɛtɪk Apr 15 at 13:23
  • 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. – Nathaniel Apr 15 at 13:42
  • @Nathaniel The program literally works by checking every single number for if it works in the scholz conjecture. It automatically exits when it finds a number which disagrees with the conjecture. – fəˈnɛtɪk Apr 15 at 13:44

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.

  • 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. – Rohan Jhunjhunwala Feb 25 '17 at 18:57
  • 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. ?? – DLosc Mar 8 '17 at 19:40
  • Sorry, while it is doing that I think I had accidentally cut that out of my description at some point – fəˈnɛtɪk Mar 8 '17 at 19:41

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.
  • 3
    "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... – Leo Mar 6 '17 at 16:01
  • 1
    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 – Leo Mar 6 '17 at 18:30
  • 7
    @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. – Conor O'Brien Mar 6 '17 at 18:59
  • 3
    @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. – Conor O'Brien Mar 8 '17 at 12:02
  • 1
    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.) – user62131 Mar 8 '17 at 22:57

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

{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!

  • 1
    I think you might only be creating a new value for looping locally as it isn't shared with the function. – fəˈnɛtɪk Mar 9 '17 at 17:08
  • 2
    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. – Post Left Garf Hunter Mar 11 '17 at 19:23
  • 1
    @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! – Comrade SparklePony Mar 11 '17 at 20:00
  • 1
    "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". – xnor Mar 12 '17 at 1:11

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>

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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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