Ustalenie, czy język jest kompletny, jest bardzo ważne przy projektowaniu języka. Na początku jest to dość trudne zadanie dla wielu ezoterycznych języków programowania, ale pozwólmy mu podnieść poprzeczkę. Zróbmy kilka języków programowania, które są tak trudne do udowodnienia Turing Complete, że nawet najlepsi matematycy na świecie nie udowodnią ich w żaden sposób. Twoim zadaniem jest opracowanie i wdrożenie języka, którego kompletność Turinga opiera się na głównym nierozwiązanym problemie w matematyce .

Zasady

• Wybrany problem musi zostać postawiony co najmniej 10 lat temu i musi zostać nierozwiązany w chwili opublikowania tego pytania. Może to być dowolna hipoteza matematyki, a nie tylko jedna z wymienionych na stronie Wikipedii .

• Musisz podać specyfikację języka i implementację w istniejącym języku.

• Język programowania musi być kompletny, jeśli tylko przypuszczenie się utrzymuje. (lub jeśli i tylko wtedy, gdy domniemanie się nie zachowuje)

• Musisz załączyć dowód, dlaczego Turing byłby kompletny lub niekompletny w oparciu o wybraną hipotezę. Możesz założyć dostęp do nieograniczonej pamięci podczas uruchamiania interpretera lub kompilowanego programu.

• Ponieważ zajmujemy się kompletnością operacji we / wy Turinga, nie jest to wymagane, jednak celem jest stworzenie najciekawszego języka, który mógłby pomóc.

• To konkurs popularności, więc wygra odpowiedź z największą liczbą głosów.

Kryteria docelowe

Co powinna zrobić dobra odpowiedź? Oto kilka rzeczy, na które należy zwrócić uwagę podczas głosowania, ale nie są one technicznie wymagane

• Nie powinna to być zwykła łatka istniejącego języka. Zmiana istniejącego języka w celu dopasowania do specyfikacji jest w porządku, ale łatanie pod warunkiem jest odradzane, ponieważ jest nudne. Jak powiedział ais523 w Nineteeth Byte:

  Wolę, aby sztuczki moich esolangów były mocniej upieczone w języku

• Powinien być interesujący jako samodzielny ezoteryczny język.

Legendre

Ten język jest kompletny dla Turinga tylko wtedy i tylko wtedy, gdy hipoteza Legendre'a jest fałszywa, tzn. Istnieje liczba całkowita n> 0 taka, że ​​nie ma liczb pierwszych między n ^ 2 a (n + 1) ^ 2. Ten język czerpie inspirację z Niedociążenia, choć pod pewnymi względami bardzo się od niego różni.

Programy w Legendre składają się z szeregu dodatnich liczb całkowitych (0 jest szczególnie zbanowany, ponieważ zasadniczo neguje cały cel języka). Każda liczba całkowita odpowiada poleceniu bazowemu w Legendre lub potencjalnemu zdefiniowanemu przez użytkownika. To, do którego polecenia jest przypisane, zależy od liczby liczb pierwszych między jego kwadratem a kolejną liczbą całkowitą (równoważną sekwencji OEIS A014085 ).

Polecenia języka modyfikują stos, który może przechowywać dowolnie duże dodatnie liczby całkowite. Jeśli stos kiedykolwiek zawiera 0, 0 jest natychmiast usuwane. Szczegółowe polecenia to:

• 2 (najmniejsza liczba całkowita produkująca to polecenie: 1): Wciśnij następną liczbę całkowitą w programie na stos.

• 3 (najmniejsza produkująca liczba całkowita: 4): Wciśnij górną liczbę całkowitą na stosie i wykonaj związane z nią polecenie.

• 4 (najmniejszy: 6): Pop najwyższą liczbę całkowitą. Jeśli było 1, zwiększ górną liczbę całkowitą na stosie.

• 5 (10): Zamień dwa górne elementy stosu.

• 6 (15): Zmniejsz górną liczbę całkowitą na stosie. Jeśli wynikiem jest 0, pop 0 i odrzuć go.

• 7 (16): Zduplikuj górną liczbę całkowitą na stosie.

• 8 (25): Zatrzymaj wykonanie i wydrukuj zawartość stosu.

Jest to podstawowy zestaw instrukcji, który nie jest w stanie zrobić nic interesującego, nie mówiąc już o zapętleniu. Istnieje jednak inne polecenie, do którego można uzyskać dostęp tylko wtedy, gdy przypuszczenie Legendre okaże się fałszywe.

• 0 (nieznane): Usuń wszystkie elementy ze stosu i połącz je w nową funkcję, która wykona wszystkie polecenia, zaczynając od pierwotnego dołu stosu i kończąc na górze, dostępne jako polecenie, którego „numer polecenia” jest równy odpowiada kolejnej liczbie całkowitej w źródle programu.

Jeśli to polecenie jest w jakiś sposób dostępne, język staje się kompletny Turinga, ponieważ można w nim symulować maszynę Minsky'ego.

Po wykonaniu polecenia 8 lub osiągnięciu końca programu program kończy działanie i drukowany jest znak (Unicode) odpowiadający każdej liczbie całkowitej na stosie.

Przykładowe programy

1 2 1 3 1 10 4

Ten prosty program wypycha cyfrę 2, następnie 3, a na końcu 10, przed wykonaniem 4 (polecenie: 3), co powoduje, że 10 (polecenie: 5) jest wyskakujące i wykonywane, zamieniając 2 i 3.

1 5 3 15 2 1 6 7

Ten program demonstruje użycie pośredniej korespondencji typu integer-to-Command. Najpierw pchane jest 5, a następnie 15 i 1, przy użyciu trzech różnych sposobów kodowania polecenia 2. Następnie 1 jest wyskakiwany, w wyniku czego 15 jest zwiększane do 16, a następnie wykonywane. Program kończy się dwoma wystąpieniami liczby 5 na stosie.

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

Ten program demonstruje użycie polecenia 0 za pomocą? jako numer zastępczy. Program najpierw przechowuje „1 5” w funkcji 9, a następnie „15 31” na 10, a następnie uruchamia funkcję 9 (przy użyciu 24), która wypycha 5 na stos i wielokrotnie go zmniejsza, aż osiągnie 0 i zostanie usunięta . Następnie program zatrzymuje się.

Maszyna Minsky

Aby przekonwertować maszynę Minsky na kod Legendre, należy użyć polecenia 0 . Ponieważ to polecenie jest niedostępne, chyba że przypuszczenie Legendre'a jest fałszywe, użyłem symbolu zastępczego? zamiast.

Zauważ, że wszystkie nazwy linii instrukcji maszynowych Minsky muszą mieć liczby całkowite z różnymi odpowiednikami A014085 od siebie i poleceń podstawowych, a także 24 (9) i 31 (10).

1 1 1 1 ? 24

ZA:

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

ZA:

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

Aby utworzyć końcowy program, dodaj wszystkie części (z x, y, z zastąpionymi przez ich odpowiedniki) i dodaj jedną liczbę całkowitą, aby rozpocząć pierwszą instrukcję w łańcuchu. Powinno to udowodnić kompletność języka Turinga na wypadek, gdyby domysł Legendre'a okazał się fałszywy na podstawie kontrprzykładu.

Interpretator

Ten interpreter został napisany w Pythonie (3) i został przetestowany na wszystkich trzech powyższych przykładach. Czy użyć flag -a / - allowZero, aby zezwolić? do użycia, -f / - plik do uruchomienia kodu bezpośrednio z pliku i -s / - stackOut, aby zamiast tego wyprowadzić stos jako listę Pythona. Jeśli nie podano żadnego pliku, interpreter przechodzi w tryb REPL, który najlepiej jest stosować z opcją --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())

Unia zamknięta

Ten język programowania jest Turing kompletny, jeśli domniemana grupa Union-closed Sets jest niepoprawna.

Sterownica

Lista poleceń:
x ++ Przyrost x (INC)
x-- Zmniejszenie x (DEC)
j (x, y) Dodaj zestaw instrukcji x, jeśli y wynosi 0, do końca kolejki instrukcji

Wszystkie zmienne są inicjowane jako 0

Składnia

Programy są zapisywane jako zbiór zestawów poleceń.
Command1 Command2 Command3 ...
Command1 Command2 ...
...

Aby ustalić, czy program jest zamknięty, każdy zestaw uwzględnia tylko listę różnych poleceń, które znajdują się w zestawie
j (x, y)! = J (a, b)
+ (x)! = + (Y)

Jeśli jakikolwiek typ polecenia (+, -, j) pojawia się w co najmniej połowie zestawów, nic nie robi.

Programy mogą zakończyć się, jeśli na końcu kolejki instrukcji nie ma instrukcji

Nieskończone pętle, w tym pustą pętlę, można osiągnąć za pomocą j (x, y)

Interpretator

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>

Kompletność Turinga

Jeśli wszystkie trzy komendy, j (x, y), inkrementacja, dekrementacja, wszystkie komendy są dostępne, można więc symulować maszynę Minsky'ego.

Każdy zestaw zawierający tylko j (x, y), który jest osiągany przy użyciu j (x, y), to HALT
x ++ to INC
x-- to DEC
j (x, y) to JZ

Jeśli przypuszczenie o zamkniętych zestawach unii jest prawidłowe, przynajmniej jedno z trzech poleceń będzie zawsze wyłączone, uniemożliwiając w ten sposób ukończenie tego języka przez Turinga.

Liczby Fermata

Język działa na dwóch potencjalnie nieskończonych taśmach, gdzie każda lokalizacja taśmy może przechowywać dowolną liczbę całkowitą. Obie taśmy są wypełnione -1na początku. Istnieją również dwie głowice taśm, które zaczynają się w pozycji 0 na obu taśmach.

Tłumacz najpierw odczyta dane wejściowe i zapisze wartości na pierwszej taśmie (danych), zaczynając od pozycji 0.

Następnie odczyta dostarczony program. Dla każdej napotkanej liczby najpierw sprawdzi, czy wartość jest liczbą pierwszą Fermata, czy nie. Jeśli tak, zapisze na drugiej taśmie (instrukcji), którą jest Fermat, w przeciwnym razie zapisze -1na taśmie instrukcji.

Następnie sprawdź wartość we wskaźniku instrukcji i wykonaj jedną z następujących czynności:

• -1 lub mniej: Wyjdź z programu
• 0: Przesuń pozycję taśmy danych o jeden w lewo. Przesuń pozycję taśmy instrukcji o jedną w prawo
• 1: Przesuń pozycję taśmy danych o jedną w prawo. Przesuń pozycję taśmy instrukcji o jedną w prawo
• 2: Zwiększ wartość w miejscu taśmy danych. Przesuń pozycję taśmy instrukcji o jedną w prawo
• 3: Zmniejsz wartość w miejscu taśmy danych. Przesuń pozycję taśmy instrukcji o jedną w prawo
• 4: Jeśli wartość w bieżącym położeniu taśmy danych wynosi zero, przesuń taśmę instrukcji w prawo, aż osiągniesz pasującą 5(lub większą) wartość na taśmie instrukcji lub coś mniejszego niż 0. Jeśli jest 5(lub większy), ponownie przesuń wskaźnik instrukcji w prawo, jeśli jest mniejszy niż, 0to wyjdź z programu. Jeśli wartość bieżącej pozycji taśmy danych nie jest równa zero, po prostu przesuń taśmę instrukcji jedną w prawo
• 5lub więcej: przesuń wskaźnik instrukcji w lewo, aż osiągniesz odpowiednią 4wartość lub znajdziesz coś mniejszego niż 0. W przypadku tego ostatniego zamknij program.

(przez dopasowanie 5(lub więcej) i 4wartości oznacza to, że podczas wyszukiwania właściwej wartości na taśmie instrukcji za każdym razem, gdy napotka taką samą wartość jak polecenie początkowe (albo 5(więcej), albo 4), będzie musiał pominąć odpowiednią liczbę innej wartości ( 4lub 5(odpowiednio) więcej w wyszukiwaniu)

Pętla, dopóki instrukcja nie powie, że musisz wyjść z programu.

Gdy program zakończy działanie, wypisz wartości na taśmie danych od pozycji 0do pierwszej pozycji taśmy, która zawiera -1wartość.

Dowód

Zauważ, że język zasadniczo odwzorowuje interpretera Brainfuck bez IO, gdzie F_5wymagana jest możliwość wykonywania wszelkiego rodzaju właściwych pętli.

Jednak w oparciu o hipotezę Fermata istnieje tylko 5 liczb pierwszych Fermata ( F_0- F_4). Jeśli F_5istnieje, język jest kompletny, ponieważ wiemy, że Brainfuck jest kompletny. Jednak bez F_5ciebie nie będziesz w stanie wykonywać rozgałęzień ani pętli, co zasadniczo blokuje cię w bardzo prostych programach.

Realizacja

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

Przykłady:

Spowoduje to napisanie H(skrót Hello World!) na ekranie z nową linią:

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

Zapisz jako example.fermati uruchom w ten sposób (uwaga: zawsze musisz mieć dane wejściowe):

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

W następnym przykładzie zrobimy prosty szyfr w stylu Cezara, zwiększając każdą wartość wejściową o jeden. Oczywiście musisz zastąpić ?piątą pierwszą Fermat:

17 65537 5 17 ? 257

Możesz sprawdzić, czy działa, włączając tryb oszukiwania i używając 2 4 1 2 5 3jako kodu źródłowego:

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

Swallows w / Coconut v2

Ponieważ poprzednia wersja zawierała błędy, które spowodowały, że była nieważna w tym konkursie, i nie chcę, aby opinie z poprzedniej wersji były liczone dla tej wersji, która jest znacząco inna, ta wersja jest przesyłana jako nowy post.

Ten język nie jest kompletny, jeśli Twierdzenie Collatza można udowodnić dla wszystkich liczb całkowitych dodatnich. W przeciwnym razie język jest kompletny.

Ten język został oparty na Kardynale .

Po pierwsze, contVal programu jest obliczany przy użyciu formuły
contVal = suma (suma (wartości ASCII rzędu) * 2 ^ (numer wiersza-1))

Następnie na każdym A lub E tworzone są 2 jaskółki skierowane w przeciwnych kierunkach, a wszystkie warunkowe instrukcje skrętu czekają na inicjalizację.
Jaskółki utworzone w E są skierowane w lewo / prawo, a jaskółki utworzone w A są skierowane w górę / w dół.

Na koniec kod będzie wykonywał kroki, dopóki wszystkie wskaźniki nie zostaną usunięte lub contVal spadnie do jednego.

Na każdym kroku, jeśli contVal% 2 == 0 zostanie podzielony przez 2, w przeciwnym razie zostanie pomnożony przez trzy i zwiększony o jeden.

Polecenia:

0: ustaw wartość na 0
+: zwiększ wartość o 1
>: zmień kierunek w prawo
v: zmień kierunek w dół
<: zmień kierunek w lewo
^: zmień kierunek w górę
R: Kolejne wskaźniki po pierwszym wskaźniku porównaj z wartością pierwszy wskaźnik. Jeśli jest równy, idź prosto, w przeciwnym razie skręć w prawo.
L: Kolejne wskaźniki po pierwszym wskaźniku są porównywane z wartością pierwszego wskaźnika. Jeśli jest równy, idź prosto, w przeciwnym razie skręć w lewo.
E: Zduplikuj wskaźnik, ale kierujesz się w lewo i prawo.
A: Zduplikujesz wskaźnik, ale kierujesz się w górę i w dół
? : Usuń wskaźnik, jeśli wartość wynosi 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>

Wyjaśnienie:

Jeśli hipotezę Collatza można udowodnić dla wszystkich liczb całkowitych dodatnich, czas trwania dowolnego programu uruchomionego w tym języku jest skończony, ponieważ contVal zawsze zbiegnie się do 1, tym samym kończąc program.

W przeciwnym razie muszę tylko udowodnić, że ten język może implementować następujące funkcje

Przyrost: który jest reprezentowany przez +
Stała 0: który jest reprezentowany przez 0
Dostęp zmienny: zmienne są przechowywane jako wskaźniki podczas podróży
Łączenie instrukcji: zmieniając odległość przebytą do operacji, można zmienić kolejność wykonywania operacji
Dla pętli: W tym języku

E   > V
    ^+R
      +
      A

będzie działać jak pętla for> zliczać do 1 (do pętli można dodać kolejny kod)

Podobnie kod

Rv
^<

Będzie działać jak do, aż będzie równa wartości warunkowej ustawionej w pętli R.

Doskonałość / niedoskonałość

Uff, było fajnie.

Doskonałość / niedoskonałość jest kompletna tylko wtedy, gdy istnieje nieskończona liczba idealna. Jeśli tak, nazywa się to Doskonałością, a jeśli nie, to nazywa się Niedoskonałością. Dopóki ta tajemnica nie zostanie rozwiązana, zawiera ona oba imiona.

Liczba idealna to liczba, której dzielniki sumują się do liczby, więc sześć to liczba idealna, ponieważ 1+2+3=6.

Perfekcja / Niedoskonałość ma następujące funkcje:

Perfekcja / niedoskonałość opiera się na stosie, a stos jest indeksowany od zera.

Polecenia:

p(x, y): wypycha x na stosie w pozycji y.

z(x, y): wypycha x na stos w pozycji y, pozbywa się tego, co poprzednio znajdowało się w pozycji y

r(x): usuwa xty element ze stosu

k(x): zwraca x pozycję na stosie

a(x, y): dodaje xiy. W połączeniu ze stringami łączy je w kolejności xy.

s(x, y): odejmuje y od x. z ciągami usuwa ostatnią długość (y) z x

m(x, y): mnoży xiy. W przypadku użycia z łańcuchami mnoży x razy długość y.

d(x, y): dzieli x przez y

o(x): drukuje x

i(x, y): jeśli x ma wartość true, wówczas wykonuje funkcję y

n(): zwraca licznik, w którym blok kodu jest wywoływany.

q(): zwraca długość stosu

t(): dane wejściowe użytkownika

e(x, y): Jeśli x jest liczbą całkowitą, jeśli xiy mają tę samą wartość, to zwraca 1. jeśli y jest łańcuchem, wówczas przyjmuje długość y. jeśli x jest łańcuchem, to konwertuje y na łańcuch i sprawdza, czy są takie same, a jeśli tak, zwraca 1. W przeciwnym razie zwraca 0.

l(x, y): jeśli x jest większy niż y, to zwraca 1. Jeśli jest łańcuch, to używa jego długości.

b(): zatrzymuje program.

c(x, y): uruchamia x, a następnie y.

Aby uzyskać ekwiwalent języka Python and, pomnóż obie wartości razem. Dla ordodaj wartości, a dla notodejmij wartość od 1. Działa to tylko wtedy, gdy wartość wynosi 1 lub 0, co można osiągnąć, dzieląc liczbę samodzielnie.

Typy danych: liczby całkowite i ciągi. Ciągi są oznaczone symbolem '', a wszystkie liczby niecałkowite są zaokrąglane.

Składnia:

Kod składa się z zagnieżdżonych funkcji w ciągu dziesięciu {}sekund. Na przykład, program, który dostanie się do wejścia i wydrukować je dodany będzie: {o(a(t(), t()))}. W tle programu znajduje się licznik, który zaczyna się od 0 i przesuwa się o 1 za każdym razem, gdy wykonuje blok kodu. Pierwszy blok kodu działa w 0i tak dalej. Po wykonaniu dziesięciu bloków kodu szósty jest wykonywany za każdym razem, gdy licznik osiągnie idealną liczbę. Nie musisz mieć wszystkich dziesięciu bloków kodu, aby program działał, ale potrzebujesz 7, jeśli chcesz utworzyć pętlę. Aby lepiej zrozumieć, jak działa ten język, uruchom następujący program, który drukuje licznik za każdym razem licznik osiągnie doskonały numer: {}{}{}{}{}{}{o(n())}.

Tłumacz można znaleźć tutaj: repl.it/GL7S/37 . Wybierz 1 i wpisz swój kod w terminalu lub wklej kod na code.perfectkarcie i wybierz 2 po uruchomieniu. Będzie to miało sens, gdy spróbujesz.

Dowód kompletności Turinga / brak kompletności Turinga.

Zgodnie z tym artykułem dotyczącym wymiany stosów inżynierii oprogramowania , kompletny Turing musi mieć możliwość warunkowego powtarzania skoku oraz mieć możliwość odczytu lub zapisu pamięci. Może odczytywać / zapisywać pamięć w postaci stosu i może zapętlać się, ponieważ szósty blok kodu jest wykonywany za każdym razem, gdy licznik osiągnie idealną liczbę. Jeśli istnieje nieskończona liczba liczb doskonałych, może zapętlać się w nieskończoność i Turing jest kompletny, a poza tym nie jest.

Interaktywny interpreter znaczników cyklicznych, który pobiera 5 znaków, 1 lub 0, jako dane wejściowe:

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

Można go rozszerzyć, aby pobierał dowolną liczbę znaków jako dane wejściowe. Może to wymagać nieskończonych danych wejściowych, ale tylko wtedy, gdy istnieją nieskończone liczby idealne!

Podeszwy

Ten język programowania jest Turing kompletny, jeśli przypuszczenie Scholza jest prawdziwe.

Napisałem ten język, ponieważ @SztupY mówił, że nie będzie żadnych wyników, które opierają się na przypuszczeniu, że spełnienie Turinga jest prawdziwe

Lista poleceń

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

Za pomocą tych poleceń ten język może symulować maszynę Minsky'ego

Interpretator

Gorąco polecam nie uruchamiać tego. Wykorzystuje wyjątkowo powolną metodę sprawdzania łańcucha dodawania.

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>

Kompletność Turinga

Język używa licznika dla liczby uruchomionych poleceń, które sprawdza względem hipotezy Scholza w celu zmodyfikowania kompletności języka.

Jeśli hipoteza Scholza jest prawdziwa, program działa dokładnie tak jak normalna maszyna Minsky'ego z
skokiem
zmniejszania przyrostu,
jeśli zerowe
zatrzymanie

Jeśli jednak hipoteza Scholza jest fałszywa, licznik ostatecznie osiągnie wartość, dla której hipoteza Scholza nie jest prawdziwa. Ponieważ język został zaprojektowany w taki sposób, aby wychodził po osiągnięciu liczby, która według przypuszczeń Scholza jest fałszywa, program wyjdzie za każdym razem po uruchomieniu tylu poleceń. Dlatego wszystkie programy będą miały ograniczoną długość. Ponieważ nie jest to zgodne z wymogami dotyczącymi ukończenia języka przez Turinga,

„Taśmy nie można ustalić długości, ponieważ nie odpowiadałoby to podanej definicji i poważnie ograniczyłoby zakres obliczeń wykonywanych przez maszynę do obliczeń automatu z liniowym ograniczeniem”,

język nie byłby kompletny, gdyby hipoteza Scholza była fałszywa

Narzeczony

Betrothed Github .

Plik Readme i specyfikacja znajdują się na github pod „README.txt”.

Zasadniczo program narzeczonych składa się z par linii, których długości są odrębnymi podwójnymi parami liczb pierwszych lub parami zaręczonych (nie mogą wystąpić duplikaty). Program jest wykonywany przez znajdowanie „elastycznych podzbiorów” pierwszego wiersza w parze w drugim wierszu. Liczba takich podzbiorów, w połączeniu z odległością Levenshteina między oryginalną drugą linią i drugą linią bez elastycznych podzbiorów, określają polecenie do wykonania.

Wyciągnę dowód na ten 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.

Polubowny parytet

Ten język opiera się na tym, czy są jakieś polubowne liczby o przeciwnej parzystości .

Polecenia

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.  

Kontrola przepływu

Program cyklicznie powtarza się od lewej do prawej, zanim powróci do początku. Jeśli napotka „j”, sprawdza wartość, aby ustalić, czy powinna zmienić wiersze. Jeśli liczba jest liczbą polubowną z przeciwną parzystością do jej dopasowania, idzie w dół o jeden wiersz (zapętlanie z powrotem do góry), w przeciwnym razie, jeśli liczba jest polubowną, idzie w górę o jeden rząd, jeśli nie jest już w górnym rzędzie.

Program może zakończyć się tylko wtedy, gdy osiągnie x w dowolnym wierszu poza górnym wierszem.

Kompletność Turinga

Tego programu można użyć do symulacji maszyny Minsky'ego, zakładając, że istnieje para polubownych liczb o przeciwnej parzystości.

j, {i} mogą być użyte do symulacji JZ (r, x), chociaż sprawdziłby, czy liczby są polubowne w przeciwieństwie do zera.
+ to INC (r)
- to DEC (r)
x to HALT

Jeśli nie możesz opuścić pierwszego wiersza, polecenia x i} nic nie robią. Powoduje to, że program nie może wejść w stan HALT, chyba że jest to pusty program. Dlatego pod opisem, że kompletność Turinga wymaga stanu HALT , językiem byłoby Turing niepełny.

Interpretator

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>

Nowa linia

Oświadczenie: To trochę bałagan i dość proste. To pierwszy język, jaki kiedykolwiek napisałem, a domysł jest jedynym, który zrozumiałem. Wiem, że inny użytkownik miał dłuższą odpowiedź na ten sam, ale i tak postanowiłem to napisać.

Aby pisać w Newline, musisz mieć dużo czasu i nowych linii ( \n). To działa na zasadzie prawdziwości hipotezy Legendre. Każdy operator musi wpaść na liczbę z hipotezy Legendre'a, którą zaczynamy od n = 1. Za każdym razem, gdy masz operatora, bierzesz \ n's i podłączasz ją do hipotezy Legendre'a i uzyskujesz zasięg, który będzie następną liczbą pierwszą \ n musi wpaść. Więc na początek robisz, \n\na następnie przechodzisz do operatora, a \nnastępnie do innego operatora, jesteśmy na 3 nowych liniach. Teraz następna to 5, więc dodajesz \n\ni upewniasz się, że ostatnia linia operatora ma odpowiednią liczbę nowych linii, że jesteś w doskonałej ilości, która mieści się w hipotezie Legendre, którą rozpoczęliśmy.

Liczby (tablica) są jak zmienne. Za każdym razem, gdy działa operator (który używa liczb), zwiększa.

+ 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

Tak długo, jak mamy nieograniczone liczby pierwsze, które są zgodne z zasadami, język ten ma nieskończoną taśmę.

Maszyna Minsky

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

Jak to działa:

\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

Wypróbuj to na KhanAcademy .

Taggis

Taggis to język oparty na systemach tagów .

Kompletność operacyjna Taggisa opiera się na domysłach Collatza

Składnia

Składnia programu Taggis to po prostu trzy ciągi znaków (reguły produkcji) składające się wyłącznie z liter a, b i c, oddzielone spacjami.

Wykonanie

Jedynym stanem programu Taggisa jest ciąg znaków składający się z tych samych trzech znaków.

Taggis implementuje system tagów TS (3, 2), w którym na każdym etapie usuwane są pierwsze 2 litery obecnego „tagu”, a pierwsza litera, która była w tej usuniętej części, dołącza odpowiednią regułę produkcji na końcu ciąg.

Na przykład program Taggis bc a aaaimplementuje problem 3n + 1, w którym iteracje są reprezentowane przez odpowiednią liczbę as, a krok 3n + 1 jest zastępowany przez (3n + 1) / 2 [1], co prowadzi do wyjścia programu:

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

Kompletność Turinga

Oczywiście ten prosty system może wydawać się zbyt prosty do naśladowania kompletności Turinga, ale okazuje się, że każdą maszynę Turinga z 2 symbolami (klasa obejmująca maszyny uniwersalne) można przekształcić w system tagów z 2 usuniętymi znakami z głowy, oraz 32 * m reguł produkcji, gdzie mjest liczba stanów w maszynie Turinga.

Najmniejsza znana uniwersalna maszyna Turinga z tylko 2 symbolami wykorzystuje 18 stanów, a zatem odpowiedni system znaczników zawiera aż 576 zasad produkcji [2].

Jednak klasa obliczeniowa zestawu wszystkich systemów znaczników z 3 produkcjami i 2 usuniętymi symbolami jest powiązana z hipotezą Collatza [2]. Jeśli hipoteza Collatza okaże się fałszywa, Taggis jest kompletny w Turingu. W przeciwnym razie opiera się na KOLEJNYM nierozwiązanym problemie w matematyce, znajdując mniejszą maszynę Turinga niż

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. co jest równoważne oryginalnej funkcji Collatz, ponieważ 3n + 1 nieparzystego nzawsze będzie parzysty, dlatego podział może być zastosowany automatycznie

2. Systemy znaczników i funkcje typu Collatz, Liesbeth De Mol ,