Determinar se um idioma é Turing Complete é muito importante ao projetar um idioma. Também é uma tarefa bastante difícil para muitas linguagens de programação esotéricas, mas vamos aumentar um pouco. Vamos criar algumas linguagens de programação que são tão difíceis de provar Turing Complete que mesmo os melhores matemáticos do mundo não conseguirão prová-las de qualquer maneira. Sua tarefa é planejar e implementar uma linguagem cuja complexidade de Turing se baseie em um grande problema não resolvido em matemática .

Regras

• O problema que você escolher deve ter sido colocado há pelo menos 10 anos e não ter sido resolvido, a partir da publicação desta pergunta. Pode ser qualquer conjectura comprovável em matemática e não apenas uma das listadas na página da Wikipedia .

• Você deve fornecer uma especificação do idioma e uma implementação em um idioma existente.

• A linguagem de programação deve ser Turing completa se e somente se a conjectura se mantiver. (ou se e somente se a conjectura não se mantiver)

• Você deve incluir uma prova de por que seria Turing completo ou incompleto com base na conjectura escolhida. Você pode assumir acesso à memória ilimitada ao executar o intérprete ou o programa compilado.

• Como estamos preocupados com a E / S de Completude Turing, não é necessário, no entanto, o objetivo é tornar o idioma mais interessante para que ele possa ajudar.

• Este é um concurso de popularidade, por isso a resposta com mais votos vencerá.

Critérios de destino

O que uma boa resposta deve fazer? Aqui estão algumas coisas a procurar ao votar, mas não são tecnicamente necessárias

• Não deve ser um patch simples de um idioma existente. Alterar um idioma existente para atender às especificações é bom, mas a correção de uma condição é desencorajada porque é chata. Como dito por ais523 no Nineteeth Byte:

  Eu prefiro fazer com que os truques dos meus esolangs fiquem mais firmes no idioma

• Deve ser interessante como uma linguagem esotérica independente.

Legendre

Essa linguagem é apenas completa em Turing se, e somente se, a conjectura de Legendre for falsa, ou seja, existe um número inteiro n> 0, de modo que não haja números primos entre n ^ 2 e (n + 1) ^ 2. Essa linguagem se inspira no Underload, embora em alguns aspectos seja muito diferente dela.

Os programas no Legendre são compostos de séries de números inteiros positivos (0 é especialmente proibido, porque essencialmente nega todo o objetivo do idioma). Cada número inteiro corresponde a um comando base no Legendre, ou a um comando potencial definido pelo usuário. O comando ao qual está atribuído é baseado no número de primos entre seu quadrado e o próximo número inteiro (equivalente à sequência OEIS A014085 ).

Os comandos do idioma modificam uma pilha, que pode conter números inteiros positivos arbitrariamente grandes. Se a pilha contiver 0, o 0 será removido imediatamente. Em detalhes, os comandos são:

• 2 (menor número inteiro produzindo este comando: 1): Coloque o próximo número inteiro no programa na pilha.

• 3 (menor número inteiro de produção: 4): pop o número inteiro superior na pilha e execute o comando associado a ele.

• 4 (menor: 6): pop o número inteiro superior. Se fosse 1, aumente o número inteiro superior na pilha.

• 5 (10): Troque os dois principais itens da pilha.

• 6 (15): Decrementa o número inteiro superior na pilha. Se isso resultar em 0, coloque o 0 e descarte-o.

• 7 (16): duplique o número inteiro superior na pilha.

• 8 (25): Interrompa a execução e imprima o conteúdo da pilha.

Este é o conjunto de instruções básicas, que é incapaz de fazer qualquer coisa interessante, muito menos fazer um loop. No entanto, há outro comando, que pode ser acessado apenas se a conjectura de Legendre for falsa.

• 0 (desconhecido): remova todos os itens da pilha e combine-os em uma nova função, que executará todos os comandos começando na parte inferior original da pilha e terminando na parte superior, acessível como um comando cujo "número de comando" seja igual a aquele ao qual o próximo número inteiro na fonte do programa corresponde.

Se esse comando estiver acessível de alguma forma, o idioma se tornará completo em Turing, pois é possível simular uma máquina Minsky.

Quando o comando 8 é executado ou o final do programa é alcançado, o programa termina e o caractere (Unicode) correspondente a cada número inteiro na pilha é impresso.

Programas de exemplo

1 2 1 3 1 10 4

Este programa simples empurra o número 2, depois 3 e finalmente um 10, antes de executar um 4 (comando: 3), o que faz com que o 10 (comando: 5) seja exibido e executado, trocando os 2 e 3.

1 5 3 15 2 1 6 7

Este programa demonstra o uso da correspondência indireta de número inteiro para comando. Primeiro, um 5 é pressionado, depois um 15 e um 1, usando três maneiras diferentes de codificar o comando 2. Em seguida, o 1 é exibido e, como resultado, o 15 é incrementado para 16 e, finalmente, executado. O programa termina com duas instâncias do número 5 na pilha.

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

Este programa demonstra o uso do comando 0, usando? como um número de espaço reservado. O programa primeiro armazena '1 5' na função 9, depois '15 31 'em 10, antes de executar a função 9 (usando 24), que empurra 5 para a pilha e a diminui repetidamente, até atingir 0 e é removida . Então, o programa pára.

Minsky machine

Para converter uma máquina Minsky em código Legendre, o comando 0 deve ser usado. Como esse comando é inacessível, a menos que a conjectura de Legendre seja falsa, usei um espaço reservado? em vez de.

Observe que todos os nomes das linhas de instruções da máquina Minsky precisam ter números inteiros com diferentes correspondências A014085 entre si e com os comandos base, além de 24 (9) e 31 (10).

1 1 1 1 ? 24

UMA:

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

UMA:

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

Para criar o programa final, anexe todas as partes (com x, y, z substituídos por seus pares) e adicione um único número inteiro para iniciar a primeira instrução na cadeia. Isso deve provar a completude de Turing da linguagem, caso a conjectura de Legendre seja falsa por contra-exemplo.

Intérprete

Este intérprete é escrito em Python (3) e foi testado nos três exemplos acima. Use os sinalizadores -a / - allowZero para permitir? para ser usado, -f / - file para executar o código diretamente de um arquivo e -s / - stackOut para gerar a pilha como uma lista Python. Se nenhum arquivo for fornecido, o intérprete entra em uma espécie de modo REPL, que é melhor usado com --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())

União fechada

Esta linguagem de programação está completa se a conjectura dos Conjuntos fechados pela União estiver incorreta.

Controles

Lista de comandos:
x ++ Incremento x (INC)
x-- Decremento x (DEC)
j (x, y) Adicione o conjunto de instruções x se y for 0 no final da fila de instruções

Todas as variáveis ​​são inicializadas como 0

Sintaxe

Os programas são escritos como um conjunto de conjuntos de comandos.
Comando1 Comando2 Comando3 ...
Comando1 Comando2 ...
...

Para determinar se o programa está fechado, cada conjunto é responsável apenas pela lista de comandos diferentes que estão no conjunto
j (x, y)! = J (a, b)
+ (x)! = + (Y)

Se qualquer tipo de comando (+, -, j) aparecer em pelo menos metade dos conjuntos, ele não fará nada.

Os programas podem terminar se não houver instruções no final da fila de instruções

Loops infinitos, incluindo o loop vazio, podem ser alcançados usando j (x, y)

Intérprete

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>

Completude de Turing

Se todos os três comandos, j (x, y), incrementarem, diminuirem os comandos, todos estarão disponíveis, para que uma máquina Minsky possa ser simulada.

Qualquer conjunto com apenas j (x, y) atingido usando j (x, y) é HALT
x ++ é INC
x-- é DEC
j (x, y) é JZ

Se a conjectura de conjuntos fechados de união estiver correta, pelo menos um dos três comandos será sempre desativado, impossibilitando que esse idioma seja Turing completo.

Fermat primos

O idioma funciona em duas fitas potencialmente infinitas, onde cada local da fita pode armazenar um número inteiro arbitrário. As duas fitas são preenchidas -1no início. Há também duas cabeças de fita que começam na posição 0 nas duas fitas.

O intérprete primeiro lerá a entrada e armazenará os valores na primeira fita (dados), começando na posição 0.

Em seguida, ele lerá o programa fornecido. Para cada número que encontrar, ele primeiro verificará se o valor é um Fermat prime ou não. Se sim, ele gravará na segunda fita (instrução) qual Fermat prime é, caso contrário, gravará -1na fita de instruções.

Em seguida, verifique o valor no ponteiro da instrução e siga um destes procedimentos:

• -1 ou menos: saia do programa
• 0: Mova a posição da fita de dados uma para a esquerda. Mova a fita de instruções para a direita
• 1: Mova a posição da fita de dados uma para a direita. Mova a fita de instruções para a direita
• 2: Aumente o valor na posição da fita de dados. Mova a fita de instruções para a direita
• 3: Diminua o valor na posição da fita de dados. Mova a fita de instruções para a direita
• 4: Se o valor na posição atual da fita de dados for zero, mova a fita de instruções para a direita, até atingir um valor correspondente 5(ou maior) na fita de instruções ou algo menor que 0. Se for um 5(ou maior), mova o ponteiro da instrução novamente para a direita, se for menor do que 0sair do programa. Se o valor da posição atual da fita de dados não for zero, basta mover a fita de instruções uma para a direita
• 5ou mais: mova o ponteiro da instrução para a esquerda, até atingir o 4valor correspondente ou encontrar algo menor que 0. No caso deste último, saia do programa.

(combinando 5(ou mais) e 4valores, significa que, ao procurar o valor adequado na fita de instruções sempre que encontrar o mesmo valor que o comando inicial (ou 5(ou mais) ou 4), ele terá que pular o número apropriado do outro valor ( 4ou 5(ou mais) respectivamente) na pesquisa)

Loop, até que a instrução diga que você precisa sair do programa.

Quando o programa terminar, emita os valores na fita de dados da posição 0até a primeira posição da fita que contém um -1valor.

Prova

Observe que o idioma é essencialmente mapeado para um intérprete Brainfuck sem IO, onde F_5é necessário que você possa executar qualquer tipo de loops adequados.

No entanto, com base na conjectura Fermat principal, existem apenas 5 primos Fermat ( F_0- F_4). Se F_5existe, o idioma é Turing-complete, como sabemos que Brainfuck é Turing-complete. No entanto, sem F_5você não será capaz de ramificar nem fazer loop, essencialmente prendendo você em programas muito simples.

Implementação

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

Exemplos:

Isso gravará H(abreviação de Hello World!) na tela com uma nova linha:

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

Salve como example.fermate execute-o assim (nota: você sempre precisa ter uma entrada):

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

Este próximo exemplo fará uma cifra simples no estilo Caesar, incrementando cada valor da entrada em um. Obviamente, você precisa substituir ?o 5º Fermat prime:

17 65537 5 17 ? 257

Você pode testar se funciona ativando o modo de fraude e usando 2 4 1 2 5 3como código-fonte:

$ echo 'Hello' | ./fermat.rb example2_cheat.fermat

Andorinhas c / Coco v2

Como a versão anterior apresentava erros que a tornavam inválida para este concurso, e não quero que os upvotes da versão anterior sejam significativamente diferentes, essa versão está sendo enviada como uma nova postagem.

Esse idioma não é Turing completo se a conjectura de Collatz puder ser comprovada para todos os números inteiros positivos. Caso contrário, o idioma é Turing completo.

Essa linguagem foi baseada no cardeal .

Primeiro, o contVal do programa é calculado usando a fórmula
contVal = sum (soma (valores ASCII da linha) * 2 ^ (número da linha-1))

Em seguida, duas andorinhas em direções opostas são criadas em cada A ou E e todas as instruções de curva condicionais são definidas para aguardar a inicialização.
As andorinhas criadas no E são direcionadas para a esquerda / direita e as andorinhas criadas no A são direcionadas para cima / para baixo.

Por fim, o código executará as etapas até que todos os ponteiros sejam removidos ou o contVal caia para um.

Em cada etapa, se contVal% 2 == 0, ele será dividido por 2; caso contrário, será multiplicado por três e incrementado por um.

Comandos:

0: defina o valor como 0
+: aumente o valor em 1
>: altere a direção para a direita
v: altere a direção para a direita
<: altere a direção para a esquerda
^: altere a direção para a esquerda R : altere a direção para cima
R: ponteiros subsequentes após o primeiro ponteiro compararem com o valor do primeiro ponteiro. Se for igual, siga em frente, depois vire à direita.
L: Os ponteiros subsequentes após o primeiro ponteiro são comparados com o valor do primeiro ponteiro. Se for igual, siga em frente, depois vire à esquerda.
E: Duplicar o ponteiro, mas seguindo nas direções esquerda e direita
A: Duplicar o ponteiro, mas seguindo nas direções para cima e para baixo
? : Remova o ponteiro se o valor for 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>

Explicação:

Se a conjectura de Collatz puder ser comprovada para todos os números inteiros positivos, a duração de qualquer programa executado nesse idioma será finita, pois o contVal sempre convergirá para 1, finalizando o programa.

Caso contrário, eu só preciso provar que esse idioma pode implementar as seguintes funções

Incremento: representado por +
Constante 0: representado por 0
Acesso variável: as variáveis ​​são armazenadas como ponteiros enquanto viajam
Concatenação de instrução: alterando a distância percorrida para as operações, a ordem na qual as operações são executadas pode ser alterada
Loop For: Neste idioma

E   > V
    ^+R
      +
      A

atuará como um loop for> conte até 1 (código adicional pode ser adicionado ao loop)

Da mesma forma, o código

Rv
^<

Atuará como um fazer até igual ao valor condicional definido no loop R.

Perfeição / Imperfeição

Uau, isso foi divertido.

Perfeição / Imperfeição só é completa se houver números perfeitos infinitos. Se houver, chama-se Perfeição, e se não houver, chama-se Imperfeição. Até que esse mistério seja resolvido, ele possui os dois nomes.

Um número perfeito é um número cujos divisores somam o número, então seis é um número perfeito porque 1+2+3=6.

Perfeição / Imperfeição tem as seguintes funções:

Perfeição / imperfeição é baseada em pilha, com uma pilha indexada a zero.

Comandos:

p(x, y): empurra x para a pilha na posição y.

z(x, y): empurra x para a pilha na enésima posição, se livra do que estava anteriormente na enésima posição

r(x): remove o décimo item da pilha

k(x): retorna o décimo item na pilha

a(x, y): adiciona x e y. Quando usado com strings, ele os reúne na ordem xy.

s(x, y): subtrai y de x. com cadeias, remove o último len (y) de x

m(x, y): multiplica x e y. Se usado com cadeias, multiplica x vezes len y.

d(x, y): divide x por y

o(x): imprime x

i(x, y): se x for avaliado como true, ele executa a função y

n(): retorna o contador no qual o bloco de códigos está sendo chamado.

q(): retorna o comprimento da pilha

t(): entrada do usuário

e(x, y): Se x é um número inteiro, se x e y têm o mesmo valor, isso retorna 1. se y é uma string, obtém o comprimento de y. se x é uma string, ele converte y em uma string e verifica se são iguais e, se forem, retorna 1. Caso contrário, retorna 0.

l(x, y): se x for maior que y, ele retornará 1. Se houver uma sequência, ela usará o comprimento da sequência.

b(): interrompe o programa.

c(x, y): executa x e, em seguida, y.

Para obter o equivalente a um Python and, multiplique os dois valores. Para or, adicione os valores e para not, subtraia o valor de 1. Isso funciona apenas se o valor for 1 ou 0, o que pode ser alcançado dividindo o número por si próprio.

Tipos de dados: números inteiros e seqüências de caracteres. As cadeias são indicadas por ''e todos os números não inteiros são arredondados.

Sintaxe:

O código consiste em funções aninhadas dentro de dez {}s. Por exemplo, um programa que iria começar a entradas e imprimi-los adicionado seria: {o(a(t(), t()))}. No fundo do programa, existe um contador que inicia em 0 e progride em 1 toda vez que executa um bloco de código. O primeiro bloco de código é executado em 0e assim por diante. Uma vez que os dez blocos de código são executados, o sexto é executado toda vez que o contador atinge um número perfeito. Você não precisa ter todos os dez blocos de código para o programa funcionar, mas precisa de 7 se desejar fazer um loop. Para entender melhor como essa linguagem funciona, executar o seguinte programa, que imprime o contador cada vez que o contador chegar a um número perfeito: {}{}{}{}{}{}{o(n())}.

O intérprete pode ser encontrado aqui: repl.it/GL7S/37 . Selecione 1 e digite seu código no terminal ou cole seu código na code.perfectguia e selecione 2 ao executar. Fará sentido quando você tentar.

Prova de completude de Turing / falta de completude de Turing.

De acordo com este artigo de troca de pilha de engenharia de software , um Turing complete deve poder ter uma forma de repetição condicional de salto e ter uma maneira de ler ou gravar memória. Ele pode ler / gravar memória na forma de pilha e pode executar um loop devido ao fato de o sexto bloco de código ser executado toda vez que o contador atingir um número perfeito. Se houver um número infinito de números perfeitos, ele poderá fazer um loop indefinidamente e Turing estiver completo, caso contrário, não o será.

Intérprete de etiqueta cíclica auto-a-bit que aceita 5 caracteres, 1 ou 0, como entrada:

{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)))))}

Ele pode ser expandido para receber qualquer número de caracteres como entrada. Pode levar uma entrada infinita, mas apenas se houver números perfeitos infinitos!

Soles

Essa linguagem de programação é Turing completa se a conjectura de Scholz for verdadeira.

Eu escrevi esse idioma porque @SztupY estava dizendo que não haveria nenhum resultado que confiasse na conjectura para ser verdade, para que Turing estivesse completo

Lista de Comandos

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

Com esses comandos, esse idioma pode simular uma máquina Minsky

Intérprete

Eu recomendo não executar isso. Ele usa um método extraordinariamente lento de verificar a cadeia de adição.

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>

Conclusão de Turing

A linguagem usa um contador para o número de comandos executados, que são comparados com a conjectura de Scholz para modificar a integridade da linguagem.

Se a conjectura de Scholz for verdadeira, este programa funcionará exatamente como uma máquina Minsky normal com Salto de Decremento
Incrementar se Zero Parar

No entanto, se a conjectura de Scholz for falsa, o contador acabará por atingir um valor para o qual a conjectura de Scholz não é verdadeira. Como a linguagem foi projetada para sair ao atingir um número que a conjectura de Scholz é falsa, o programa será encerrado todas as vezes após a execução de muitos comandos. Portanto, todos os programas terão duração limitada. Como isso não concorda com os requisitos para o idioma ser Turing completo,

"A fita não pode ser fixada em comprimento, pois isso não corresponderia à definição especificada e limitaria seriamente o intervalo de cálculos que a máquina pode executar aos de um autômato linear delimitado",

o idioma não estaria completo em Turing, se a conjectura de Scholz fosse falsa

Prometido

Github prometido .

O leia-me e a especificação estão no github, em "README.txt".

Geralmente, um programa de noivos é composto por pares de linhas, cujos comprimentos são pares primos gêmeos distintos ou pares de noivos (nenhuma duplicata pode ocorrer). O programa é executado ao encontrar "subconjuntos flexíveis" da primeira linha do par na segunda linha. O número de tais subconjuntos, combinado com a distância levenshtein entre a segunda linha original e a segunda linha sem os subconjuntos flexíveis, determina o comando a ser executado.

Vou extrair a prova para este 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.

Paridade Amigável

Esse idioma é baseado na existência de números amigáveis com paridade oposta .

Comandos

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.  

Controle de fluxo

O programa alterna repetidamente da esquerda para a direita antes de retornar ao início. Se encontrar um "j", verifica o valor para determinar se deve alterar as linhas. Se o número for um número amigável com paridade oposta à sua correspondência, ele descerá uma linha (retornando ao topo). Caso contrário, se o número for um número amigável, ele subirá uma linha, se ainda não estiver na linha superior.

O programa só pode terminar se o programa atingir um x em qualquer linha fora da linha superior.

Completude de Turing

Este programa pode ser usado para simular uma máquina Minsky, assumindo que há um par de números amigáveis ​​com paridade oposta.

j, {e} podem ser usados ​​para simular JZ (r, x), embora verifique se há números amigáveis ​​em oposição a zero.
+ é INC (r)
- é DEC (r)
x é HALT

Se você não conseguir sair da primeira linha, os comandos x e} não farão nada. Isso faz com que o programa não consiga entrar no estado HALT, a menos que seja um programa vazio. Portanto, sob a descrição de que a integridade de Turing exige um estado HALT , o idioma seria Turing incompleto.

Intérprete

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>

Nova linha

Disclaimer: É um pouco de confusão e bastante simples. Esta é a primeira língua que já escrevi e a conjectura é a única que entendi. Sei que outro usuário teve uma resposta mais longa com a mesma, mas decidi escrever isso de qualquer maneira.

Para escrever em Nova linha, você deve ter muito tempo e novas linhas ( \n). Isso funciona com a conjectura de Legendre sendo verdadeira. Todo operador deve recorrer a um número na conjectura de Legendre que começamos com n = 1. Toda vez que você tem um operador, pega a quantidade de \ n e a conecta à Conjectura de Legendre e obtém o intervalo que a próxima quantidade principal de \ n deve cair. Então, para começar \n\n, você passa para um operador e \ndepois para outro operador, estamos com três novas linhas. Agora, o próximo é o 5, para que você adicione \n\ne atenda o operador, certificando-se de que a última linha do operador tenha a quantidade certa de novas linhas que você possui em uma quantidade principal que se enquadra na conjectura de Legendre que começamos.

Os números (a matriz) são como as variáveis. Toda vez que um operador executa (que usa números), ele aumenta.

+ 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

Desde que tenhamos números primos ilimitados que sigam as regras, esse idioma possui fita não finita.

Minsky machine

\n\ng\nr\n\n[\n\nd\n\n\n\n]

Como funciona:

\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

Experimente na KhanAcademy .

Taggis

Taggis é uma linguagem baseada em sistemas de tags .

A completude do processo de Taggis é baseada na conjectura de Collatz

Sintaxe

A sintaxe de um programa Taggis é simplesmente três strings (regras de produção) que consistem inteiramente nas letras a, bec, separadas por espaços.

Execução

O único estado do programa do Taggis é uma sequência que consiste nos mesmos três caracteres.

O Taggis implementa um sistema de tags TS (3, 2), onde a cada passo as 2 primeiras letras da "tag" atual são removidas, e a primeira letra que estava nessa parte removida recebe sua regra de produção correspondente anexada ao final de a corda.

Por exemplo, o programa Taggis bc a aaaimplementa o problema 3n + 1, em que as iterações são representadas por um número correspondente de se aa etapa 3n + 1 é substituída por (3n + 1) / 2 [1], levando à saída do programa:

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

Conclusão de Turing

Obviamente, esse sistema simples pode parecer simples demais para simular a integridade de Turing, mas acontece que qualquer máquina de Turing com 2 símbolos (uma classe que inclui máquinas universais) pode ser convertida em um sistema de tags com 2 caracteres removidos da cabeça, e regras de produção de 32 m, onde mé o número de estados na máquina de Turing.

A menor máquina universal de Turing conhecida com apenas 2 símbolos usa 18 estados e, portanto, o sistema de tags correspondente contém 576 regras de produção impressionantes [2].

No entanto, a classe computacional do conjunto de todos os sistemas de tags com 3 produções e 2 símbolos removidos está ligada à conjectura de Collatz [2]. Se a conjectura de Collatz for falsa, Taggis estará completo em Turing. Caso contrário, é baseado em OUTRO problema não resolvido em matemática, encontrando uma máquina de Turing menor do que

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. que é equivalente à função original Collatz, pois 3n + 1 de um ímpar nserá sempre par e, portanto, a divisão pode ser aplicada automaticamente

2. Sistemas de tags e funções semelhantes a Collatz, Liesbeth De Mol ,