Написать язык программирования неизвестной полноты

91

Определение того, является ли язык полным по Тьюрингу, очень важно при разработке языка. Это также довольно трудная задача для многих эзотерических языков программирования, но давайте поднимем ее на ступеньку выше. Давайте создадим некоторые языки программирования, которые так трудно доказать в Turing Complete, что даже лучшие математики в мире не смогут их доказать в любом случае. Ваша задача - разработать и реализовать язык, полнота которого по Тьюрингу зависит от основной нерешенной проблемы математики .

правила

  • Выбранная вами проблема должна быть поставлена ​​не менее 10 лет назад и должна быть нерешенной на момент публикации этого вопроса. Это может быть любая доказуемая гипотеза в математике, а не только одна из перечисленных на странице Википедии .

  • Вы должны предоставить спецификацию языка и реализацию на существующем языке.

  • Язык программирования должен быть завершен по Тьюрингу тогда и только тогда, когда гипотеза верна. (или если и только если гипотеза не верна)

  • Вы должны приложить доказательство того, почему оно будет полным или неполным по Тьюрингу на основе выбранной гипотезы. Вы можете получить доступ к неограниченной памяти при запуске интерпретатора или скомпилированной программы.

  • Поскольку нас интересует Тьюринг-полнота, ввод-вывод не требуется, однако цель состоит в том, чтобы сделать наиболее интересный язык, чтобы он мог помочь.

  • Это поэтому победит ответ с наибольшим количеством голосов.

Целевые критерии

Что должен сделать хороший ответ? Вот некоторые вещи, на которые нужно обратить внимание при голосовании, но они не являются технически необходимыми

Мастер пшеницы
источник
Этот разговор был перемещен в чат .
Деннис
13
В целом, я нахожу здесь ответы неутешительными. Это в значительной степени «Начните с языка, полного по Тьюрингу, затем проверьте, является ли гипотеза X истинным / ложным, и если да, завершите или отключите ключевую функцию».
xnor
1
@xnor Я согласен с вами, я надеялся, что эта награда вызовет еще несколько интересных ответов, но, похоже, этого не произойдет.
Wheat Wizard
2
Я думаю, что одна из проблем заключается в том, что большинство гипотез было подтверждено для бесконечного числа значений, но контрпримеры также были бы верны для бесконечного числа значений. В результате почти невозможно доказать полноту Тьюринга, если она верна.
fəˈnɛtɪk
1
Я думаю, что требование, чтобы полнота по Тьюрингу была привязана один к одному с данной гипотезой, является довольно сильным требованием. Я думаю, что было бы легко, если бы доказательство или опровержение полноты по Тьюрингу решило две разные открытые проблемы соответственно. (то есть доказательство полноты по Тьюрингу решает открытую проблему A, а опровержение решает открытую проблему B).
PyRulez

Ответы:

48

Лежандра

Этот язык полон по Тьюрингу только тогда и только тогда, когда гипотеза Лежандра ложна, т. Е. Существует целое число n> 0, такое, что между n ^ 2 и (n + 1) ^ 2 нет простых чисел. Этот язык черпает вдохновение из Underload, хотя в некоторых отношениях он сильно отличается от него.

Программы в Legendre состоят из ряда натуральных чисел (0 особенно запрещено, потому что оно по существу сводит на нет всю цель языка). Каждое целое число соответствует базовой команде в Legendre или потенциальной пользовательской команде. Для какой команды она назначена, зависит от числа простых чисел между ее квадратом и следующим целым числом (эквивалентно последовательности OEIS A014085 ).

Команды языка модифицируют стек, который может содержать произвольно большие положительные целые числа. Если в стеке хранится 0, 0 сразу удаляется. Подробно, команды:

  • 2 (наименьшее целое число, производящее эту команду: 1): поместите следующее целое число в программе в стек.

  • 3 (наименьшее производящее целое число: 4): вставьте верхнее целое в стек и выполните связанную с ним команду.

  • 4 (наименьшее: 6): выведите верхнее целое число. Если это было 1, увеличьте верхнее целое число в стеке.

  • 5 (10): поменяйте местами два верхних стека.

  • 6 (15): уменьшить верхнее целое в стеке. Если это приводит к 0, вытолкните 0 и отбросьте его.

  • 7 (16): дублировать верхнее целое число в стеке.

  • 8 (25): остановить выполнение и распечатать содержимое стека.

Это базовый набор команд, который не может делать ничего интересного, не говоря уже о цикле. Однако есть другая команда, к которой можно получить доступ, только если гипотеза Лежандра окажется ложной.

  • 0 (неизвестно): удалить все элементы из стека и объединить их в новую функцию, которая будет выполнять все команды, начиная с исходного основания стека и заканчивая сверху, доступный как команда, чей «номер команды» равен следующее целое число в источнике программы соответствует.

Если эта команда каким-то образом доступна, язык становится тьюрингово-полным, так как в ней можно смоделировать машину Минского.

Когда команда 8 выполняется или достигнут конец программы, программа завершается и печатается символ (Unicode), соответствующий каждому целому числу в стеке.

Примеры программ

1 2 1 3 1 10 4

Эта простая программа вводит число 2, затем 3 и, наконец, 10, прежде чем выполнить 4 (команда: 3), что приводит к выталкиванию и выполнению 10 (команда: 5), меняя местами 2 и 3.

1 5 3 15 2 1 6 7

Эта программа демонстрирует использование косвенного целочисленного соответствия между командами. Сначала нажимают 5, затем 15 и 1, используя три разных способа кодирования команды 2. Затем 1 выталкивается, и в результате 15 увеличивается до 16 и, наконец, выполняется. Программа заканчивается двумя экземплярами числа 5 в стеке.

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

Эта программа демонстрирует использование команды 0, используя? в качестве номера заполнителя. Программа сначала сохраняет «1 5» в функции 9, затем «15 31» в 10, прежде чем запустить функцию 9 (используя 24), которая помещает 5 в стек и многократно уменьшает его, пока не достигнет 0 и не будет удалена , Затем программа останавливается.

Минский автомат

Чтобы преобразовать машину Минского в код Legendre, необходимо использовать команду 0 . Поскольку эта команда недоступна, если гипотеза Лежандра не ложна, я использовал заполнитель? вместо.

Обратите внимание, что все имена строк машинных команд Minsky должны иметь целые числа с различными соответствиями A014085 друг от друга и базовых команд, а также 24 (9) и 31 (10).

Инициализация:
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 ДЕК (A / B) yz:

A:

1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 24 ? x

B:

1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 10 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 10 1 24 ? x
х ОСТАНОВКА:
1 25 ? x

Чтобы создать конечную программу, добавьте все части (с заменой x, y, z их аналогами) и добавьте одно целое число, чтобы запустить первую инструкцию в цепочке. Это должно доказать полноту по Тьюрингу языка в случае, если гипотеза Лежандра окажется контрпримером ложной.

переводчик

Этот интерпретатор написан на Python (3) и был протестирован на всех трех приведенных выше примерах. Используйте флаги -a / - allowZero, чтобы разрешить? -f / - file для запуска кода непосредственно из файла и -s / - stackOut для вывода стека в виде списка Python. Если файл не указан, интерпретатор входит в режим REPL, который лучше всего использовать с --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())
ivzem
источник
14

Союз закрыт

Этот язык программирования является полным по Тьюрингу, если гипотеза о замкнутых множествах неверна.

управления

Список команд:
x ++ Увеличение x (INC)
x-- Уменьшение x (DEC)
j (x, y) Добавить набор инструкций x, если y равно 0, до конца очереди инструкций

Все переменные инициализируются как 0

Синтаксис

Программы написаны в виде набора наборов команд.
Команда1 Команда2 Команда3 ... Команда1 Команда2
...
...

Для определения, является ли программа закрытой объединением, каждый набор учитывает только список различных команд, которые находятся в наборе
j (x, y)! = J (a, b)
+ (x)! = + (Y)

Если какой-либо тип команды (+, -, j) присутствует хотя бы в половине наборов, он ничего не делает.

Программы могут завершиться, если в конце очереди команд нет инструкций

Бесконечные циклы, включая пустой цикл, могут быть достигнуты с помощью j (x, y)

переводчик

Полнота по Тьюрингу

Если все три команды, j (x, y), увеличивают, уменьшают, все команды доступны, то есть машина Minsky может быть смоделирована.

Любой набор только с j (x, y), который достигается с помощью j (x, y), равен HALT
x ++, равен INC
x--, DEC
j (x, y) равен JZ

Если гипотеза объединения замкнутых множеств верна, то по крайней мере одна из трех команд всегда будет отключена, что сделает невозможным выполнение этого языка по Тьюрингу.

fənɛtɪk
источник
Что бы я сделал, вместо того, чтобы иметь 3 оператора, иметь бесконечное количество значений и брать по модулю 4 каждого, чтобы получить одну из трех операций плюс неоперацию. Когда программа запускается, она проверяет, что объединение наборов закрыто, а затем удаляет все элементы, которые находятся в более чем половине наборов. Затем он повторяет это до тех пор, пока нет такого элемента. Если гипотеза верна, все программы совпадают с пустой программой, однако, если она ложна, вы можете выразить каждую возможную программу (вот почему не включена опция).
Пшеничный волшебник
@WheatWizard Определение объединения, закрытое интерпретатором, считает, что один и тот же оператор для разных переменных различен. x ++ считается отличным от y ++. В результате существует бесконечность различных наборов, которые могут быть созданы. С бесконечным числом возможных наборов, если ни один из трех основных типов не входит в более чем половину наборов, то он завершается.
fəˈnɛtɪk
Вполне возможно, что доказательство гипотезы объединения замкнутых множеств приведет к тому, что преобразование одного из трех операторов будет завершено, так как можно было бы оставить все разные операторы в программе, вам потребуется только 3 из бесконечного числа ценности, чтобы остаться.
fəˈnɛtɪk
13

Ферма простые числа

Язык работает на двух потенциально бесконечных лентах, где каждое местоположение ленты может хранить произвольное целое число. Обе ленты заполняются -1при запуске. Есть также две головки ленты, которые начинаются в позиции 0 на обеих лентах.

Интерпретатор сначала прочитает ввод и сохранит значения на первой ленте (данных), начиная с позиции 0.

Затем он будет читать предоставленную программу. Для каждого встречаемого числа сначала проверяется, является ли значение простым числом Ферма или нет. Если да, он записывает на вторую (командную) ленту, какое это простое число Ферма, в противном случае он записывает -1на ленту с инструкциями.

Затем проверьте значение в указателе инструкций и выполните одно из следующих действий:

  • -1 или меньше: выход из программы
  • 0: Переместите позицию ленты данных на одну влево. Переместить ленту инструкций на одну позицию вправо
  • 1: Переместите ленту данных на одну позицию вправо. Переместить ленту инструкций на одну позицию вправо
  • 2: Увеличить значение в позиции ленты данных. Переместить ленту инструкций на одну позицию вправо
  • 3: Уменьшить значение в позиции ленты данных. Переместить ленту инструкций на одну позицию вправо
  • 4: Если значение в текущей позиции ленты данных равно нулю, перемещайте ленту инструкций вправо, пока не достигнете соответствующего 5(или большего) значения на ленте инструкций или чего-то меньшего, чем 0. Если он 5(или больше), переместите указатель инструкции еще раз вправо, если он меньше, чем 0выйдите из программы. Если значение текущей позиции ленты данных не равно нулю, просто переместите ленту инструкций вправо
  • 5или больше: перемещайте указатель инструкций влево, пока не достигнете соответствующего 4значения или не найдете что-то меньше 0. В последнем случае выйдите из программы.

(путем сопоставления 5(или более) и 4значений это означает, что при поиске правильного значения на ленте инструкций в любое время, когда он встречает то же значение, что и исходная команда (либо 5(или более), либо 4)), ему придется пропустить соответствующее число другого значения ( 4или 5(или более) соответственно) в поиске)

Цикл, пока инструкция не говорит, что вы должны выйти из программы.

Когда программа завершает работу, выводите значения на ленте данных с позиции 0до первой позиции на ленте, содержащей -1значение.

доказательство

Обратите внимание, что язык по существу соответствует интерпретатору Brainfuck без ввода-вывода, где F_5требуется, чтобы он мог выполнять любые правильные циклы.

Однако на основе простой гипотезы Ферма есть только 5 простых чисел Ферма ( F_0- F_4). Если F_5существует, то язык полный по Тьюрингу, поскольку мы знаем, что Brainfuck является полным по Тьюрингу. Однако без F_5вас не обойдется ни ветвление, ни зацикливание, по сути, блокирование вас в очень простых программах.

Реализация

(протестировано с 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

Примеры:

Это напишет H(сокращенно Hello World!) на экран с новой строкой:

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

Сохраните как example.fermatи запустите его так (примечание: вы всегда должны иметь данные):

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

В следующем примере мы сделаем простой шифр в стиле Цезаря, увеличив каждое значение на единицу. Вы, очевидно, должны заменить ?на 5-е простое число Ферма:

17 65537 5 17 ? 257

Вы можете попробовать, что он работает, включив чит-режим и используя 2 4 1 2 5 3в качестве исходного кода:

$ echo 'Hello' | ./fermat.rb example2_cheat.fermat
SztupY
источник
2
Мне жаль бедного кодера, который должен набрать соответствующее простое число, чтобы добраться до 5. Надеюсь у них хорошая клавиатура.
AdmBorkBork
2
@AdmBorkBork Не волнуйся. У него просто больше битов, чем во вселенной элементарных частиц.
fəˈnɛtɪk
@LliwTelracs на самом деле это не имеет смысла, так как количество элементарных частиц во вселенной равно Алеф-нулю (омега), и из омеги оно начинает означать не фактический размер числа. (Если только он не один: P)
Мэтью Ро
1
@ MatthewRoh Я сделал ошибку. Я имел в виду в наблюдаемой вселенной.
fəˈnɛtɪk
2
@ MatthewRoh На самом деле, это может быть конечным, бесконечным, неисчислимым или даже несовместимым с теорией множеств! Мы никогда не узнаем, однако :(
CalculatorFeline
10

Ласточки с кокосом v2

Поскольку в предыдущей версии были ошибки, которые сделали ее недействительной для этого конкурса, и я не хочу, чтобы количество голосов предыдущей версии для этой версии значительно отличалось, эта версия представляется как новое сообщение.

Этот язык не является полным по Тьюрингу, если гипотеза Коллатца может быть доказана для всех натуральных чисел. В противном случае язык Тьюринга завершен.

Этот язык был основан на кардинал .

Во-первых, управление программой рассчитывается по формуле
contVal = sum (сумма (значения ASCII строки) * 2 ^ (номер строки-1))

Затем в каждой точке A или E создаются 2 ласточки, движущиеся в противоположных направлениях, и все операторы условного поворота устанавливаются для ожидания инициализации.
Ласточки, созданные в E, направляются влево / вправо, а ласточки, созданные в A, направляются вверх / вниз.

Наконец, код будет выполнять шаги, пока все указатели не будут удалены или контроль не упадет до одного.

На каждом шаге, если contVal% 2 == 0, он будет делиться на 2, в противном случае он будет умножен на три и увеличен на единицу.

Команды:

0: установить значение 0
+: увеличить значение на 1
>: изменить направление вправо
v: изменить направление вниз
<: изменить направление влево
^: изменить направление вверх
R: последующие указатели после первого указателя сравниваются со значением первый указатель Если равны, идите прямо, иначе поверните направо.
L: последующие указатели после первого указателя сравниваются со значением первого указателя. Если равны, идите прямо, иначе поверните налево.
E: Дублировать указатель, но в направлениях влево и вправо
A: Дублировать указатель, но в направлениях вверх и вниз
? : Удалить указатель, если значение равно 0

Объяснение:

Если гипотеза Коллатца может быть доказана для всех натуральных чисел, длительность любой программы, выполняемой на этом языке, конечна, так как contVal всегда будет сходиться к 1, тем самым завершая программу.

В противном случае мне просто нужно доказать, что этот язык может реализовывать следующие функции

Инкремент: который представлен +
константой 0: который представлен 0
Доступ к переменной: переменные сохраняются в виде указателей при их перемещении.
Конкатенация операторов: изменяя расстояние, пройденное до операций, можно изменить порядок выполнения операций.
Цикл For: На этом языке

E   > V
    ^+R
      +
      A

будет действовать как цикл for> count до 1 (дальнейший код может быть добавлен в цикл)

Точно так же код

Rv
^<

Будет действовать до тех пор, пока не станет равным условному значению, заданному в цикле R.

fənɛtɪk
источник
Ты тоже меня побил, я собирался сделать что-то с гипотезой Коллатца. Хорошая работа, на интересный взгляд. Я собирался просто создать язык, который мог бы хранить цифры только в том случае, если они сходятся к 1.
Rohan Jhunjhunwala
Я не совсем понимаю. Где функция Коллатца фигурирует в этом? Из второго прочтения я думаю, что вы хотите сказать, что функция применяется contValна каждом шаге (и, следовательно, если гипотеза верна, бесконечных циклов нет), но я не вижу этого явно сформулированного где-либо в ответе. ??
DLosc
Извините, пока я делаю это, я думаю, что в какой-то момент случайно вычеркнул это из своего описания
fəˈnɛtɪk
10

Совершенство / Несовершенство

Вот это было весело.

Совершенство / Несовершенство завершается только при наличии бесконечных совершенных чисел. Если есть, это называется Совершенство, а если нет, это называется Несовершенство. Пока эта тайна не разгадана, она держит оба имени.

Совершенное число - это число, сумма делителей которого равна числу, поэтому шесть - это идеальное число, потому что 1+2+3=6.

Совершенство / Несовершенство имеет следующие функции:

Совершенство / Несовершенство основано на стеке, с индексированным стеком.

Команды:

p(x, y): выталкивает x в стек в y-й позиции.

z(x, y): выталкивает x в стек в y-й позиции, избавляется от того, что было ранее в y-й позиции

r(x): удаляет x-й элемент из стека

k(x): возвращает x-й элемент в стеке

a(x, y): добавляет х и у. При использовании со строками он складывает их в порядке xy.

s(x, y): вычитает у из х. со строками, удаляет последний len (y) из x

m(x, y): умножает x и y. Если используется со строками, умножается в x раз на len y.

d(x, y): делит х на у

o(x): печатает х

i(x, y): если x имеет значение true, тогда он выполняет функцию y

n(): возвращает счетчик, на котором вызывается кодовый блок.

q(): возвращает длину стека

t(): пользовательский ввод

e(x, y): Если x является целым числом, если x и y имеют одно и то же значение, то это возвращает 1. Если y является строкой, то она получает длину y. если x является строкой, то он преобразует y в строку и проверяет, совпадают ли они, и, если они есть, возвращает 1. В противном случае возвращается 0.

l(x, y): если x больше, чем y, он возвращает 1. Если есть строка, то она использует длину строки.

b(): останавливает программу.

c(x, y): работает x, затем y.

Чтобы получить эквивалент Python and, умножьте два значения вместе. Для or, добавьте значения, и для not, вычтите значение из 1. Это работает, только если значение равно 1 или 0, что может быть достигнуто путем деления числа на себя.

Типы данных: целые числа и строки. Строки обозначены '', а все нецелые числа округлены.

Синтаксис:

Код состоит из вложенных функций внутри десяти {}с. Например, программа , которая получит на входы и распечатать их добавили бы: {o(a(t(), t()))}. На заднем плане программы есть счетчик, который начинается с 0 и прогрессирует на 1 каждый раз, когда он выполняет блок кода. Первый блок кода работает в 0и так далее. После выполнения десяти кодовых блоков шестой выполняется каждый раз, когда счетчик достигает идеального числа. Вам не нужно иметь все десять блоков кода для работы программы, но вам нужно 7, если вы хотите сделать цикл. Чтобы лучше понять , как работает этот язык, запустите следующую программу, которая печатает счетчик каждый раз , когда счетчик достигает совершенное число: {}{}{}{}{}{}{o(n())}.

Переводчик можно найти здесь: repl.it/GL7S/37 . Либо выберите 1 и введите свой код в терминале, либо вставьте код на code.perfectвкладке и выберите 2 при запуске. Это будет иметь смысл, когда вы попробуете это.

Доказательство полноты по Тьюрингу / отсутствие полноты по Тьюрингу.

Согласно этой статье об обмене стеками разработки программного обеспечения , завершение Тьюринга должно иметь возможность условного повторения перехода и иметь возможность чтения или записи в память. Он может считывать / записывать память в виде стека и выполнять цикл из-за того, что 6-й кодовый блок выполняется каждый раз, когда счетчик достигает идеального числа. Если существует бесконечное число совершенных чисел, оно может бесконечно зацикливаться и является полным по Тьюрингу, в противном случае это не так.

Интерпретатор Self Bitwise Cyclic Tag, который принимает 5 символов, 1 или 0, в качестве входных данных:

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

Его можно расширить, чтобы принимать любое количество символов в качестве входных данных. Это может занять бесконечный ввод, но только если есть бесконечные совершенные числа!

Товарищ Спаркл Пони
источник
1
Я думаю, что вы, возможно, только создаете новое значение для локального зацикливания, поскольку оно не используется совместно с функцией.
fəˈnɛtɪk
3
В его нынешнем виде у вас нет доказательства ТС. Статья по разработке программного обеспечения, на которую вы ссылаетесь, дает приблизительный набор требований, однако TC - это не просто набор полей для галочки. Вам нужно будет реализовать автомат TC (например, Minsky Machine) или показать, что ваш язык неразрешим.
Wheat Wizard
2
@WheatWizard Там я добавил интерпретатор побитовых циклических тегов. Он может быть модифицирован, чтобы принимать любое количество символов в качестве входных данных. Это может принять бесконечные символы в качестве входных данных, но только если есть бесконечные совершенные числа!
Товарищ SparklePony
2
«После выполнения десяти кодовых блоков шестой выполняется каждый раз, когда счетчик достигает идеального числа.» Таким образом, интерпретатор просто подсчитывает совершенные числа? Я чувствую, что это противоречит духу испытания. Фактическая спецификация языка не имеет большого значения, это может быть что угодно, полное по Тьюрингу, плюс «бегать только на шаг, только когда вы наберете идеальное число».
xnor
10

Подошвы

Этот язык программирования является полным по Тьюрингу, если гипотеза Шольца верна.

Я написал этот язык, потому что @SztupY говорил, что не будет никаких результатов, которые полагаются на гипотезу, чтобы быть правдой, чтобы быть завершенным по Тьюрингу

Список команд

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

С помощью этих команд этот язык может симулировать машину Минского.

переводчик

Я очень рекомендую не запускать это. Он использует чрезвычайно медленный метод проверки цепочки сложений.

Полнота по Тьюрингу

В языке используется счетчик количества запускаемых команд, который он проверяет на соответствие гипотезе Шольца, чтобы изменить полноту тьюринга языка.

Если гипотеза Шольца верна, эта программа работает точно так же, как обычная машина Минского, с
инкрементным
скачком уменьшения
при нулевой
остановке

Однако, если гипотеза Шольца ложна, счетчик в конечном итоге достигнет значения, для которого гипотеза Шольца не верна. Поскольку язык предназначен для выхода при достижении числа, для которого гипотеза Шольца ложна, программа будет выходить каждый раз после выполнения такого количества команд. Поэтому все программы будут иметь ограниченную длину. Поскольку это не соответствует требованиям, предъявляемым к языку, который должен быть завершен по Тьюрингу,

«Лента не может быть фиксированной по длине, поскольку она не будет соответствовать данному определению и серьезно ограничит диапазон вычислений, которые машина может выполнить, с линейным ограниченным автоматом»,

язык не будет полным по Тьюрингу, если гипотеза Шольца будет ложной

fənɛtɪk
источник
1
+1, поскольку это на самом деле жестко запекает требование гипотезы в язык, а не добавляет что-то постороннее, чтобы убить язык, если гипотеза верна / ложна
Gryphon
Я не понимаю Команды, которые вы предоставляете, являются именно теми, которые вам нужны для имитации машины Минского, поэтому, если это все, что вам нужно, ваш язык завершен по Тьюрингу независимо от гипотезы Шольца. Вы должны что-то упустить из своего объяснения.
Натаниэль
@Nathaniel Одним из требований к полному языку Тьюринга является то, что язык может оказаться в бесконечном цикле (проблема остановки). Мой код считается при выполнении инструкций, и если гипотеза Шольца ложна, программа всегда останавливается после заданного количества инструкций.
fəˈnɛtɪk
Да, но вы забыли объяснить, что приводит к остановке, если гипотеза Шольца неверна. Посмотрите еще раз на свой ответ - его там нет совсем.
Натаниэль
@Nathaniel Программа буквально работает, проверяя каждое число, если оно работает в гипотезе схолца. Он автоматически выходит, когда находит число, которое не соответствует гипотезе.
fəˈnɛtɪk
9

Обрученные

Обрученный Гитхуб .

Файл readme и спецификация находятся на github, в разделе "README.txt".

Как правило, программа обручения состоит из пар линий, длина которых представляет собой отдельные пары с двумя простыми числами или пары с обручением (дубликатов быть не может). Программа выполняется путем поиска «гибких подмножеств» первой строки в паре во второй строке. Количество таких подмножеств в сочетании с левенштейновым расстоянием между исходной второй строкой и второй строкой без податливых подмножеств определяют команду для выполнения.

Я приведу выдержку из этого поста:

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.
Конор О'Брайен
источник
4
«Теперь ни один язык не может быть Turing Complete с ограниченным размером программы». Я запутался в этом утверждении ... С одной стороны, это правда, что с ограниченным размером программы мы можем написать только конечное число различных программ, но с другой стороны, общим доказательством полноты Тьюринга является написание интерпретатора для другого Язык Turing Complete, который вообще не нуждается в неограниченном размере программы ...
Leo
1
Что ж, программу, переданную переводчику, не нужно вводить в код переводчика, ее нужно передать переводчику в качестве входных данных
Лев
7
@Лео. Я скажу , что, для того , чтобы язык , чтобы быть ТС, он должен быть в состоянии кодировать программу , который будет передан переводчику (то есть, представьте себе , что этот язык не имеет команд ввода.) Представьте себе язык , с помощью одной команды: b. Это интерпретирует программу BF, которая помещается после нее, например b+++++.. Размер программы, однако, ограничен 10 символами. Хотя он может интерпретировать BF, он не может вычислить все программы, которые может использовать машина Тьюринга.
Конор О'Брайен,
3
@EriktheOutgolfer главная проблема с вашей проблемой: «она может поместить программу BF, полученную из ввода ...». Для этого я настоятельно рекомендую вам прочитать или перечитать мой предыдущий комментарий, особенно это первое предложение. Если язык является только полным по Тьюрингу на основе входных данных, то как он может, без какого-либо ввода, быть полным по Тьюрингу? То есть для того, чтобы язык был завершен по Тьюрингу, именно сама языковая программа должна кодировать программу. В противном случае обнаруживается, что они кодируют программу на входе, что является недопустимым способом программирования.
Конор О'Брайен,
1
Я не думаю, что это решенная точка. Эта статья Esolang обсуждает проблему. (Существует также вопрос о том, является ли программа, которая печатает каждую возможную завершающую программу на языке , завершающем по Тьюрингу , вместе с ее выводом, демонстрацией полноты по Тьюрингу; она не требует ввода и может быть выполнена с помощью программы конечной длины .)
5

Дружное соотношение

Этот язык основан на том, существуют ли какие-либо дружные числа с противоположной четностью .

команды

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.  

Контроль потока

Программа циклически повторяется слева направо, а затем возвращается к началу. Если он встречает «j», он проверяет значение, чтобы определить, следует ли ему менять строки. Если число является дружественным числом с четностью, противоположной его совпадению, оно уменьшается на одну строку (возвращаясь к началу). В противном случае, если число является дружественным числом, оно поднимается на одну строку, если его еще нет в верхней строке.

Программа может завершиться только в том случае, если программа достигает x в любом ряду за пределами верхнего ряда.

Полнота по Тьюрингу

Эта программа может использоваться для моделирования машины Минского, предполагая, что есть пара дружных чисел с противоположной четностью.

j, {и} можно использовать для имитации JZ (r, x), хотя он будет проверять наличие дружных чисел, а не нуля.
+ - это INC (r)
- это DEC (r)
x - это HALT

Если вы не можете покинуть первый ряд, команды x и} ничего не делают. Это приводит к тому, что программа не может войти в состояние HALT, если она не является пустой программой. Следовательно, согласно описанию, что для полноты по Тьюрингу требуется состояние HALT , язык будет неполным по Тьюрингу.

переводчик

fənɛtɪk
источник
2

Новая линия

Отказ от ответственности: это немного беспорядок и довольно просто. Это первый язык, который я когда-либо писал, и гипотеза - единственная, которую я понял. Я знаю, что у другого пользователя был более длинный ответ с тем же, но я все равно решил написать это.

Чтобы писать в Newline, у вас должно быть много времени и новых строк ( \n). Это работает на основе гипотезы Лежандра. Каждый оператор должен попадать в число в гипотезе Лежандра, которое мы начинаем с n = 1. Каждый раз, когда у вас есть оператор, вы берете количество \ n и вставляете его в гипотезу Лежандра и получаете диапазон, следующий за следующим простым числом \ n должны войти. Итак, для начала \n\nвы переходите к оператору, а \nзатем к другому оператору, мы находимся на 3 новых строках. Теперь следующий - это 5, так что вы добавляете \n\nи включаете оператор, чтобы убедиться, что последняя строка оператора имеет правильное количество новых строк, что вы находитесь на простом количестве, которое попадает в гипотезу Лежандра, которую мы начали.

Числа (массив) похожи на переменные. Каждый раз, когда оператор запускается (использует числа), он увеличивается.

+ 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

Пока у нас есть неограниченное число простых чисел, которые следуют правилам, этот язык имеет бесконечную ленту.

Минский автомат

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

Как это устроено:

\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

Попробуйте это на KhanAcademy .

Кристофер
источник
@ не нужно зацикливаться на бесконечной памяти
Кристофер
Это работает только если это правда. Я не могу закончить писать прямо сейчас, так как я на мобильном, но сегодня вечером
Кристофер
Даже если у вас бесконечная память, вы все равно должны иметь возможность бесконечного цикла.
Павел
У меня есть петли. Пытаясь сделать их бесконечными
Кристофер
Прямо сейчас они терпят крах
Кристофер
2

Taggis

Taggis - это язык, основанный на системах тегов .

Тьюринговая полнота Таггиса основана на гипотезе Коллатца

Синтаксис

Синтаксис программы Taggis - это просто три строки (производственные правила), состоящие полностью из букв a, b и c, разделенных пробелами.

выполнение

Единственное состояние программы Taggis - это строка, состоящая из тех же трех символов.

Taggis реализует систему тегов TS (3, 2), в которой на каждом шаге удаляются первые 2 буквы текущего «тега», а к самой первой букве, которая была в этой удаленной части, добавляется соответствующее производственное правило, добавляемое в конец строка.

Например, программа Taggis bc a aaaреализует задачу 3n + 1, где итерации представлены соответствующим числом as, а шаг 3n + 1 заменяется на (3n + 1) / 2 [1], что приводит к выводу программы:

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

Полнота по Тьюрингу

Конечно, эта простая система может показаться слишком простой, чтобы эмулировать полноту Тьюринга, но оказывается, что любая машина Тьюринга с 2 символами (класс, включающий универсальные машины) может быть преобразована в систему тегов с 2 удаленными символами из головы, и 32 * m правил производства, где mчисло состояний в машине Тьюринга.

Наименьшая известная универсальная машина Тьюринга, содержащая только 2 символа, использует 18 состояний, и, следовательно, соответствующая система тегов содержит колоссальные 576 правил производства [2].

Однако вычислительный класс множества всех систем тегов с 3 продукцией и 2 удаленными символами связан с гипотезой Коллатца [2]. Если гипотеза Коллатца окажется ложной, то Таггис полон по Тьюрингу. Иначе, это основано на ДРУГОЙ нерешенной проблеме в математике, находя меньшую машину Тьюринга, чем

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. что эквивалентно исходной функции Коллатца, так как 3n + 1 нечетного nвсегда будет четным, и, следовательно, деление может быть применено автоматически

  2. Системы тегов и коллатц-подобные функции, Liesbeth De Mol ,

ThePlasmaRailgun
источник