Резюме:

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

Вызов:

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

Примеры:

• JavaScript: +!()[]( http://www.jsfuck.com )

• Brainfuck: +<>[](предполагает размер ячейки упаковки)

• Python 2: ()+1cehrx(сделан из скриптов вроде exec(chr(1+1+1)+chr(1)))

Подсчет очков:

Эта задача оценивается в символах , а не в байтах . Например, оценки для примеров 6, 5 и 9.

Примечания:

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

• Хотя вы можете, пожалуйста, не размещайте ответы без сокращения используемых символов. Пример: Brainfuck с 8 символами (так как каждый другой символ является комментарием по умолчанию.)

• Вы ДОЛЖНЫ предоставить хотя бы краткое объяснение, почему ваша подгруппа является Turing-Complete.

Haskell, 4 символа

()=;

С помощью ()=мы можем определить S, K и I. Определения должны быть разделены или ;или NL.

Мы определяем (==)как S (вторая строка показывает более читаемую версию):

((=====)==(======))(=======)=(=====)(=======)((======)(=======))
( a     == b      ) c       = a      c       ( b       c       )

(===) просить:

(=====)===(======)=(=====)
 a     === b      = a

и (====)как я:

(====)(=====)=(=====)
(====) a     = a 

К счастью (==), (===), (====)и т.д. являются допустимыми именами функций / параметров.

Как указывает @ ais523, SKI недостаточно для строго типизированного языка, такого как Haskell, поэтому нам нужно добавить комбинатор с фиксированной точкой (=====):

(=====)(======)=(======)((=====)(======))
(=====) f      = f      ((=====) f      )

JavaScript (ES6), 5 символов

Спасибо @ETHproductions и @ATaco за помощь в этом; это был групповой проект, и хотя первоначальная идея была моей, многие детали принадлежат им. Смотрите обсуждение в чате, где это подмножество JavaScript было разработано здесь .

[]+=`

Достаточно хорошо известно, что любая Javascript-программа может быть написана с помощью символов ( []()+!), но 5 символов недостаточно . Тем не менее, это не проблема при написании произвольного JavaScript. При написании языка, полного по Тьюрингу, возникает проблема, и, учитывая, что языкам, полным по Тьюрингу, не требуется доступ к DOM или даже интерактивный ввод-вывод, получается, что мы можем написать программу со всеми необходимыми функциями. даже без какой-либо способности запустить evalили эквивалент.

Базовая начальная загрузка

JavaScript очень гибок с типами. Так, например, []это пустой массив, но +[]это 0, и это пустая []+[]строка. Примечательно, что тот факт, что мы можем создать 0 с этим набором символов, позволяет имитировать эффект скобок для группировки; (a)можно записать как [a][+[]]. Мы можем использовать этот вид трюка для создания различных символов, используя только +[]:

• [][+[]]is undefined(являющийся первым элементом пустого массива); так
• []+[][+[]]есть "undefined"(строковое значение undefined); так
• [[]+[][+[]]]is ["undefined"](оборачивая это в массив); так
• [[]+[][+[]]][+[]]есть "undefined"(его первый элемент); так
• [[]+[][+[]]][+[]][+[]]есть "u"(его первая буква).

uэто один из самых простых символов для создания, но похожие методы позволяют нам создавать ряд других символов. Та же ссылка, что и раньше, дает нам следующий список символов, доступных с +[](это тот же список, что и для +[](), за исключением того, ,что это единственная конструкция, которая использует скобки для целей, отличных от группировки / приоритета):

0123456789acdefinotuvyIN (){}.

Мы не можем произнести очень много полезных слов из этого набора символов (помните, что это набор символов, которые мы можем создавать в виде строк ; мы не можем выполнить их без какого-либо рода eval). Как таковой, нам нужен еще один персонаж. Мы будем использовать =, потому что это пригодится позже, но пока мы будем использовать его для написания оператора сравнения ==. Это позволяет нам создавать falseи true, которые можно структурировать и индексировать, и сразу же добавлять lrsсимволы, которые мы можем включить в строки.

Безусловно, самое важное слово, которое это позволяет нам записать, что мы не могли раньше, это constructor. Теперь JavaScript имеет синтаксис доступа к свойствам, который выглядит следующим образом:

object.property

но вы также можете написать это так:

object["property"]

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

object["c"+"o"+"n"+"s"+"t"+"r"+"u"+"c"+"t"+"o"+"r"]

(с письмами, сгенерированными как описано выше; код быстро становится очень длинным!); это эквивалентно object.constructor, что позволяет нам получить доступ к конструкторам произвольных объектов.

Есть несколько уловок, которые мы можем сделать с этим. От мирского до фантастического:

• Конструктор объекта - это функция. Примечательно, что у него есть имя, и это имя является частью строковой функции. Так, например, мы можем сделать так, [[]+[]][+[]]["constructor"]чтобы получить в конструкторе строку с именем String, а затем преобразовать ее в строковый Sсимвол. Это немного расширяет наш алфавит, и некоторые новые персонажи нам понадобятся позже.

• Все массивы имеют одинаковый конструктор; []["constructor"] == []["constructor"]есть true(в отличие от [] == []ложного). Это может показаться незначительным, но это очень важно, потому что это дает нам метод постоянного хранения значений; мы можем установить случайное свойство в конструкторе и прочитать его позже. (Это одна из причин, по которой мы используем =в частности, а не один из других способов генерации trueи false.) Например, мы можем оценить [[]["constructor"]["a"]=[]], а затем прочитать []["constructor"]["a"]и получить тот же массив, который мы там хранили.

  Это удовлетворяет одному из требований, необходимых нам для полноты по Тьюрингу , способности хранить и извлекать произвольные объемы данных. Мы можем создать cons-ячейку с использованием двухэлементного массива, получая значения из нашего хранилища свойств конструктора, а затем сохранить его вместо одного из этих значений, что позволит нам создавать произвольно большие структуры данных в памяти; и мы можем получить доступ к этому хранилищу, выполнив обратное действие, разорвав его на части, пока нужные нам данные не станут доступны. Чтение деструктивно, но это приемлемо, потому что у нас есть несколько мест для хранения данных, поэтому мы можем копировать их по мере их чтения и затем помещать копию обратно в исходное местоположение.

• Это позволяет нам получить конструктор для функции (существует множество функций, к которым мы можем получить доступ с помощью нашего ограниченного алфавита; []["find"]т. Е. Array.find является наиболее доступным, но есть и другие). Почему это полезно? Ну, на самом деле мы можем использовать его по назначению конструктора и создавать функции! К сожалению, с нашим набором символов мы не можем передать конструктору Function вычисленную строку. Однако использование `позволяет нам передать ему строковый литерал (например []["find"]["constructor"]`function body goes here`); это означает, что мы можем определять пользовательские значения типа функции с любым поведением при выполнении, при условии, что мы можем выразить это поведение полностью используя []+=. Например, []["find"]["constructor"]`[]+[]`довольно скучная функция, которая вычисляет пустую строку, отбрасывает ее и завершает работу; этофункция не полезна, но более сложные будут. Обратите внимание, что хотя функции не могут принимать параметры или возвращать значения, на практике это не является проблемой, поскольку мы можем использовать хранилище свойств конструктора для обмена данными от одной функции к другой. Другое ограничение заключается в том, что мы не можем использовать `в теле функции.

  Теперь мы можем определить пользовательские функции, но что сдерживает нас на этом этапе, так это сложность их вызова . На верхнем уровне программы мы можем вызывать функцию с помощью ``, но возможность вызывать функции только с верхнего уровня не позволяет нам выполнять какие-либо циклы. Скорее нам нужны функции, чтобы иметь возможность вызывать друг друга.

  Мы достигаем этого с довольно хитрым трюком. Помните капитал, который Sмы создали ранее? Это позволяет нам по буквам "toString". Мы не будем называть это; мы можем преобразовывать вещи в строки, добавляя []к ним. Скорее, мы собираемся заменить его. Мы можем использовать хранилище конструктора для определения постоянных массивов, которые остаются вокруг. Затем мы можем назначить наши созданные функции toStringметодам массивов , и эти назначения также будут сохраняться. Теперь все, что нам нужно сделать, это просто +[]в массиве, и вдруг наша пользовательская функция будет запущена. Это означает, что мы можем использовать символы+=[]вызывать функции, и поэтому наши функции могут вызывать друг друга - или самих себя. Это дает нам рекурсию, которая дает нам циклы, и вдруг у нас есть все, что нам нужно для полноты по Тьюрингу.

Вот краткое описание набора функций, обеспечивающих полноту Тьюринга, и способы их реализации:

• Неограниченное хранилище : вложенные массивы в хранилище конструктора
• Поток управления : реализован с использованием ifи рекурсии:
  • if: преобразовать логическое число в число и индексировать в массив из 2 элементов; один элемент выполняет функцию для thenслучая, когда он преобразуется в строку, другой элемент выполняет функцию для elseслучая, когда он преобразуется в строку.
  • Рекурсия : зафиксируйте соответствующий элемент хранилища конструктора
• Команда последовательности : [a]+[b]+[c]оценивает a, bи cслева направо (по крайней мере , в браузере я проверил)

К сожалению, это довольно непрактично; Мало того, что он чрезвычайно большой, учитывая, что строки должны быть построены посимвольно из первых принципов, он также не имеет возможности выполнять ввод / вывод (который не обязательно должен быть завершен по Тьюрингу). Однако, если он завершается, то, по крайней мере, впоследствии можно просмотреть хранилище конструктора вручную, поэтому отладка ваших программ не является невозможной, и они не являются полностью некоммуникативными.

Одинарный , 1 персонаж

0

Выбор персонажа на самом деле не имеет значения; длина программы определяет программу, которую он переносит. В то время как спецификация требует 0символов, большинство перевозчиков, кажется, не проверяют это.

vim, 9 8 7 6 символов

<C-v><esc>1@ad

Мы можем построить и выполнить произвольную программу vimscript следующим образом:

1. Используйте последовательность, aa<C-v><C-v>1<esc>dd@1<esc>ddddчтобы получить <C-a>в реестре 1.

2. Войдите в режим вставки с помощью a, затем вставьте a, который будет использоваться для повторного входа в режим вставки в макросе позже.

3. Для каждого символа в желаемой программе Vimscript,

   1. использовать <C-v><C-v>1<esc>для вставки буквенной последовательности <C-v>1,

   2. использовать @1(то есть <C-a><cr>, в котором финал <cr>является недопустимым из-за нахождения в последней строке) столько раз, сколько необходимо, чтобы увеличивать, 1пока не будет достигнуто значение ASCII желаемого символа,

   3. и снова войдите в режим вставки с помощью a.

4. Удалите строку (вместе с завершающим переводом строки) в 1регистр с помощью <esc>dd.

5. Выполните результат как нажатие клавиши vim с помощью @1, а затем <esc>ddудалите строку, введенную завершающей новой строкой из предыдущего шага.

6. Запустите полученную произвольную последовательность байтов с помощью dd@1. Если он начинается с a :, он будет интерпретирован как код vimscript, и он будет запущен из-за завершающего символа новой строки from dd.

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

Perl, 5 символов

<>^es

Как и в других языках сценариев, идея заключается в evalпроизвольных строках. Однако наш набор символов не включает в себя кавычки или операторы конкатенации, поэтому создание произвольных строк будет намного сложнее. Обратите внимание, что eval^"было бы гораздо проще иметь дело, но есть еще один символ.

Наш главный инструмент - s<^><CODE>eeэто уловка CODE, а затем уловка своей продукции. Больше eмогут быть добавлены, с ожидаемым эффектом.

Мы получаем строки с помощью <>оператора glob, кроме случаев, когда это не так. Первый символ не может быть <(в противном случае он выглядит как <<оператор), угловые скобки должны быть сбалансированы, и должен быть хотя бы один небуквенный символ (в противном случае он интерпретируется как оператор readline).

Соединяя эти строки вместе, мы можем получить любую комбинацию символов из ^B^V^S(*-/9;<>HJMOY[`\^begqstvтех пор, пока мы допускаем наличие некоторого мусора вокруг (первые три из них - управляющие символы).

Например, предположим, что мы хотим получить "v99". Один из способов получить v99это "><<" ^ "e>>" ^ "see" ^ "^^^", но мы не можем представить эти строки из-за ограничений на <>. Поэтому вместо этого мы используем:

<^<<^>><>>^<^^^^^<>>^<^^^^^^e>^<^^^^^^^>^<^^^^^e>^<^^^^e^>^<e^^es>^<^ee^^>^<^<^^^^^>>^<^<>^^^^>^<^^^^^^^e>^<^^^^^^^^>

Выше приведен результат Y9;v99;, который при eval-ed дает тот же результат, что и обычный v99(а именно символ с кодом ASCII 99).

Таким образом, мы можем использовать весь ^B^V^S(*-/9;<>HJMOY[`\^begqstvнабор символов для генерации нашей произвольной строки, затем преобразовать ее, как указано выше, и вставить ее в a s<><CODE>eeeeдля ее выполнения. К сожалению, эта кодировка все еще очень ограничена, без какого-либо очевидного способа выполнения конкатенации.

Но, к счастью, он содержит звезду. Это позволяет нам писать *b, что приводит к строке "*main::b". Тогда *b^<^B[MMH^V^SY>(^ B ^ V и ^ S являются буквальными управляющими символами) дают нам (6, $&);, что, когда Eval-й изд снова возвращает значение переменного соответствия в Perl, $&. Это позволяет нам использовать ограниченную форму конкатенации: мы можем многократно дописывать вещи к $_использованию s<^><THINGS>e, а затем использовать s<\H*><*b^<^B[MMH^V^SY>>eeeдля eval $_( \Hсоответствует всему, кроме горизонтального пробела; мы используем его вместо точки, которой нет в нашей кодировке).

Используя 9-/, мы можем легко сгенерировать все цифры. Используя цифры vи конкатенацию, мы можем генерировать произвольные символы (vXXX возвращает символ с кодом ASCII XXX). И мы можем объединить их, чтобы мы могли генерировать произвольные строки. Похоже, мы можем сделать что-нибудь.

Давайте напишем полный пример. Предположим, нам нужна программа, которая печатает свой собственный PID. Начнем с естественной программы:

say$$

Мы конвертируем его в v-нотацию:

s<><v115.v97.v121.v36.v36>ee

Мы переписываем это, используя только ^B^V^S(*-/9;<>HJMOY[`\^begqstv(пробел предназначен только для удобства чтения и не влияет на вывод):

s<^><
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-99/-9-99/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-9/9-9/9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><999/9-9/-9-9/-9-9/-9-9/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<\H*><*b^<^B[MMH^V^SY>>eee;
>eee;

Наконец, мы конвертируем вышеуказанную программу в <>^es: pastebin . К сожалению, это Excessively long <> operatorприводит к краху Perl , но это всего лишь техническое ограничение и не должно приниматься во внимание.

Фу, это было довольно путешествие. Было бы очень интересно увидеть, как кто-то придумает набор из 5 символов, который делает вещи проще.

РЕДАКТИРОВАТЬ: используя немного другой подход, мы можем избежать ограничения по длине <>. Полнофункциональный переводчик Brainfuck с использованием только <>^es: попробуйте онлайн! , Автоматизированный Perl для <>^esтранспорта: pastebin .

Python 2, 7 символов

exc="%\n

Любая программа на Python 2 может быть закодирована с использованием этих 7 символов ( \nперевод строки).

Построение произвольных строк

Мы можем выполнить конкатенацию, многократно применяя оператор подстановки %к одной строке. Например, если a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cдаст нам строку "123". К счастью, письма execдают нам доступ %xи %cкоторые в основном hex()и chr(). С помощью %cмы можем построить любую строку, если у нас есть необходимые числа, которые представляют символы. Затем мы можем выполнить эту строку как код Python, используя execключевое слово.

Сделать номера

Мы можем получить доступ 0и 1сразу с помощью сравнений ( ==). Посредством комбинации объединяющих цифр и по модулю можно построить число, 43которое представлено +в ASCII. Это позволяет нам строить числа, которые нам нужны для нашего кода.

Положить его вместе

В этом объяснении я опустил несколько деталей, поскольку они не важны для понимания того, как программы с этими ограничениями могут быть написаны. Ниже приведена написанная мной программа на Python 2, которая преобразует любую программу на языке Python в функционально эквивалентную версию, в которой используются только эти 7 символов. Используемые методы вдохновлены этим представлением о гольфе анархии k. Некоторые простые приемы также используются для поддержания размера сгенерированных программ в разумных пределах.

import sys

var = {
    43: 'e',
    'prog': 'x', # the program will be stored in this variable
    'template': 'c',
    0: 'ee',
    1: 'ex',
    2: 'ec',
    4: 'xe',
    8: 'xx',
    16: 'xc',
    32: 'ce',
    64: 'cc',
    'data': 'cx', # source program will be encoded here
}

unpacker = 'exec"".join(chr(eval(c))for c in {}.split())'.format(var['data'])

source = sys.stdin.read()
charset = sorted(list(set(source+unpacker)))
codepoints = map(ord, charset)

output = (
    # create template for joining multiple characters
    '{}="%c%%c%%%%c%%%%%%%%c"\n'.format(var['template']) +

    # create 1
    '{0}={1}=={1}\n'.format(var[1], var['template']) +

    # create 0
    '{}={}==""\n'.format(var[0], var['template']) +

    # create 3
    # store it at var[43] temporarily
    (
        'exec"{0}=%x%%x"%{2}%{2}\n' +
        'exec"{0}%%%%%%%%=%x%%x%%%%x"%{1}%{2}%{1}\n'
    ).format(var[43], var[0], var[1]) +

    # create 4
    # this step overwrites the value stored at var[0]
    (
        'exec"{1}=%x%%x"%{0}%{1}\n' +
        'exec"{1}%%%%=%x%%x"%{2}%{0}\n'
    ).format(var[43], var[0], var[1]) +

    # create 43
    'exec"{0}=%x%%x"%{1}%{0}\n'.format(var[43], var[0])
)

# create powers of 2
for i in [2, 4, 8, 16, 32, 64]:
    output += 'exec"{0}={1}%c{1}"%{2}\n'.format(var[i], var[i/2], var[43])

for i, c in enumerate(codepoints):
    # skip if already aliased
    if c in var:
        continue

    # generate a new name for this variable
    var_name = ''
    if i < 27:
        for _ in range(3):
            var_name += 'exc'[i%3]
            i /= 3
    else:
        i -= 27
        for _ in range(4):
            var_name += 'exc'[i%3]
            i /= 3
    var[c] = var_name

    # decompose code point into powers of two
    rem = c
    pows = []
    while rem:
        pows.append(rem&-rem)
        rem -= rem&-rem

    # define this variable
    front = 'exec"{}={}'.format(var[c], var[pows.pop()])
    back = '"'
    for i, p in enumerate(pows):
        front += '%'*(2**i) + 'c' + var[p]
        back += '%' + var[43]
    output += front + back + '\n'

# initialise the unpacker
output += 'exec"""{}=""\n"""\n'.format(var['prog'])
i = 0
length = len(unpacker)
while i < length:
    if (length-i) % 4 == 0:
        # concat 4 characters at a time
        w, x, y, z = [var[ord(unpacker[i+j])] for j in range(4)]
        output += 'exec"{}%c={}%%{}%%{}%%{}%%{}"%{}\n'.format(var['prog'], 
                    var['template'], w, x, y, z, var[43])
        i += 4
    else:
        output += 'exec"""{}%c="%%c"%%{}"""%{}\n'.format(var['prog'],
                    var[ord(unpacker[i])], var[43])
        i += 1

# encode source data
output += var['data'] + '="""'
output += '\n'.join(var[ord(c)] for c in source)
output += '"""\n'

# execute the program
output += 'exec"exec%c{}"%{}'.format(var['prog'], var[32])

print output

Попробуйте онлайн

Mathematica, 5 4 персонажа

I[]

является Unicode-символом частного использования , который действует как оператор Function, позволяющий писать литералы для неназванных функций с именованными аргументами. Персонаж очень похож ↦на Mathematica, поэтому я буду использовать его для остальной части этого ответа для ясности.

С их помощью можно реализовать S, Kи Iкомбинаторы комбинаторной логики:

I -> II↦II
K -> II↦III↦II
S -> II↦III↦IIII↦II[IIII][III[IIII]]

Одна из синтаксических проблем с ними заключается в том, что ↦у них очень низкий приоритет, что будет проблемой, если мы попытаемся передать аргументы этим комбинаторам. Обычно вы исправляете это, заключая комбинатор Cв скобки (C), но у нас нет скобок. Тем не менее, мы можем использовать Iи []обернуть Cв какую-то другую магию, которая имеет достаточно высокий приоритет, чтобы мы могли использовать ее позже:

I[C][[I[[]]I]]

И, наконец, написать заявление A x y z(где Aнаходится комбинатор « в скобках» , как показано выше, и x, y, zможет или не может быть заключена в скобках, или могут быть большими выражениями), мы можем написать:

A[x][y][z]

Это оставляет вопрос о том, как на самом деле работает эквивалент скобок. Я постараюсь объяснить это примерно в том порядке, в котором я это придумал.

Таким образом, для синтаксической группировки чего-либо мы используем скобки []. Скобки появляются в Mathematica двумя способами. Либо как вызовы функций f[x], либо как оператор индексации f[[i]](что на самом деле просто сокращение Part[f, i]). В частности, это означает, что [C]ни [[C]]синтаксис, ни действительный. Нам нужно что-то перед этим. Теоретически это может быть что угодно. Если мы используем Iуже имеющиеся у нас, мы можем получить, I[C]например. Это остается неоцененным, потому что Iэто не унарная функция (это вообще не функция).

Но теперь нам нужен какой-то способ извлечения Cснова, потому что иначе он фактически не будет оцениваться, когда мы пытаемся передать ему аргумент x.

Здесь пригодится то, что f[[i]]можно использовать для произвольных выражений f, а не только для списков. Предполагая, что fсам по себе имеет форму head[val1,...,valn], затем f[[0]]дает head, f[[1]]дает val1, f[[-1]]дает valnи так далее. Таким образом, нам нужно получить либо 1или -1извлечь Cснова, потому что либо I[C][[1]]или I[C][[-1]]оценивает C.

Мы можем получить 1произвольный неопределенный символ, например x, но для этого нам понадобится другой символ для деления ( x/xдает 1для неопределенного x). Умножение является единственной арифметической операцией, которую мы можем выполнять без каких-либо дополнительных символов (в принципе), поэтому нам нужно некоторое значение, которое можно умножить, чтобы дать -1или 1. Это и стало причиной, по которой я специально выбрал Iнаши идентификаторы. Потому что Iсам по себе является встроенным символом Mathematica для воображаемой единицы.

Но это оставляет одну последнюю проблему: как мы на самом деле умножаемся Iна себя? Мы не можем просто написать, IIпотому что это анализируется как один символ. Нам нужно отделить эти токены без а) изменения их значения и б) с использованием любых новых символов.

Последний бит магии - это часть недокументированного поведения: f[[]](или эквивалентно Part[f]) является допустимым синтаксисом и возвращает fсебя. Таким образом, вместо умножения Iна I, мы умножаем I[[]]на I. Вставка скобок заставляет Mathematica впоследствии искать новый токен и I[[]]Iоценивает его по -1мере необходимости. И вот как мы в конечном итоге I[C][[I[[]]I]].

Обратите внимание, что мы не могли использовать I[]. Это вызов функции без аргументов I, но, как я уже говорил, Iэто не функция, поэтому она останется без оценки.

Python 2, 8 символов

exc'%~-0

Эти символы позволяют переводить / выполнять любую программу на Python, используя строки формата и exec. Хотя для полной полноты по Тьюрингу не требуется возможность переводить любую программу, но я знаю, что это наименьшее количество символов, которые делают ее TC в любом случае. То, что это так сильно, это просто бонус.

Можно также использовать двойную кавычку, а также любую одну цифру, кроме нуля. (Теперь, когда я думаю об этом, 1несомненно , будет лучше, в результате чего в более короткие программы, так как вы могли бы использовать 1, 11и 111, как хорошо.)

Вот программа print:

exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Попробуйте онлайн

Базовая программа требует

exec''

Каждый символ, xдобавленный в программу, требует (char - count):

• % - 2**(n-1)
• c - 1
• - - ord(x)*2
• ~ - ord(x)*2
• 0 - 1

Исключением является то, что для оптимизации закодированной программы можно использовать определенные оптимизации / ярлыки, такие как использование %'0'символа 0вместо 48 -~и т. Д.

Практическое использование (AKA golfing): я использовал эту тактику для решения этой задачи без использования дополнительного персонажа с гандикапом.

Кредит для списка символов и программы кодировщика: здесь

Для получения информации о поиске нижней границы результирующего размера программы (без оптимизации) см. Этот комментарий .

Количество необходимых байтов увеличивается O(2**n), поэтому этот метод не рекомендуется для игры в гольф. Quine, использующий это ограничение источника, будет безумно длинным.

C (непереносимый), 24 18 13 символов

aimn[]={};,1+

Это охватывает все программы вида

main[]={<sequence of constants>};

... где последовательность констант (вида 1 + 1 + 1 ...) содержит представление машинного кода вашей программы. Это предполагает, что ваша среда разрешает выполнение всех сегментов памяти (очевидно, верно для tcc [спасибо @Dennis!] И некоторых машин без бита NX). В противном случае для Linux и OSX вам может понадобиться добавить ключевое слово, constа для Windows вам может понадобиться добавить #pragmaявную пометку сегмента как исполняемого.

Например, следующая программа, написанная в вышеуказанном стиле, печатает Hello, World!на Linux и OSX на x86 и x86_64.

main[]={111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+11111+11111+11111+11111+11111+11111+11111+11111+111+11+11+11+11+11+11+1+1,1111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1+1+1,111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+111+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+11+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+1+1+1+1+1+1+1,1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1,1111111111+111111111+111111111+111111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1,111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11+11+11+11+11,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+11+11+11+1,111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1+1,11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1+1};

Попробуйте онлайн!

Сетчатка , 6 символов

$%`{¶

А также переводы строки (0x0A).

С одной стороны, я удивлен, что смог получить это так низко. С другой стороны, я очень недоволен включением %¶. Каждый из $`{них используется повторно для двух или даже трех целей, но %¶ вместе служат только одной цели. Это заставляет их казаться довольно расточительными и слегка разрушает элегантность подхода. Я надеюсь, что есть способ победить эту конструкцию.

На доказательство. Я собираюсь описать простой способ перевода систем циклических тегов в Retina с использованием вышеуказанных символов.

Прежде всего, мы будем использовать `и {для двоичного алфавита вместо 0и 1. Это удобно, потому что их не нужно экранировать в регулярном выражении, но они имеют значение либо для Retina, либо в синтаксисе замещения. Я использую `для 0и {для 1, но этот выбор произвольный. Кроме того, мы собираемся перевернуть строку (и продукцию) в памяти, потому что работа с последним символом позволяет нам использовать $и $`вместо ^и $', максимизируя повторное использование символов.

Если начальное слово обозначено, Sа ith (обратное) производство вызвано , результирующая программа будет выглядеть следующим образом:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Эта конструкция неизбежно увеличивается в памяти каждый раз, когда применяется производство, и она вряд ли завершится - фактически, в тот момент, когда система циклических тегов завершится (когда рабочая строка станет пустой), поведение результирующей программы Retina станет в основном не определено.

Давайте посмотрим на то, что делает программа:

S

Мы начинаем с инициализации рабочей строки начальным словом.

{`

Это оборачивает оставшуюся часть программы в программу, которая запускается до тех пор, пока ей не удастся изменить результирующую строку (эй, наивное встроенное обнаружение бесконечного цикла бесплатно ...). Два перевода строки там на самом деле не нужны, но они более четко отделяют цикл от отдельных производств. Остальная часть программы проходит через каждое из произведений, и благодаря циклу мы эффективно обрабатываем их циклически снова и снова.

Каждое производство обрабатывается в два этапа. Сначала мы имеем дело со случаем, который является ведущим (или в нашем случае завершающим) символом {, и в этом случае мы используем продукцию:

{$
¶pi$%``

Регулярное выражение соответствует, только если строка заканчивается на {. Если это так, мы заменим его на:

• Перевод строки ( ¶). Мы будем когда-либо работать только с последней строкой рабочей строки, поэтому до сих пор это эффективно отбрасывает рабочую строку (поэтому использование памяти программой будет расти и расти).
• Текущее производство ( ), которое мы тем самым добавляем к рабочей строке (куда система циклических тегов добавляет ее).pi
• Предыдущая оставшаяся рабочая строка ( $%`). Вот почему нам нужно вставить ¶: $%`забирает все, что осталось от совпадения, но только на одной строке. Следовательно, это не видит весь мусор, который мы оставили от более ранних производств. Этот трюк позволяет нам соответствовать что - то в конце рабочей строки , чтобы вставить что - то в начале рабочей строки, без необходимости использовать что - то вроде (.+)и $1что значительно взрывать количество символов нам нужно.
• Одиночный тик ( `). Это эффективно заменяет {( 1-символ), который мы сопоставили, с `( 0-символом), так что на следующем этапе не нужно знать, обрабатывали ли мы уже текущую продукцию или нет.

Вторая часть каждого производства - это тривиальный случай, когда производство пропускается:

``$

Мы просто удаляем трейлинг `. Причина, по которой нам нужно два `в первой строке, заключается в том, что Retina считает первый обратный удар делителем между конфигурацией и регулярным выражением. Это просто дает ему пустую конфигурацию, чтобы мы могли использовать обратные пометки в самом регулярном выражении.

Java 7, 18 17 символов

\bcdefu0123456789

Весь исходный код Java может быть уменьшен до кодовых точек Unicode. «а» не требуется, так как он используется только для *:jJzZ. Звездочка используется для умножения или блокировки комментариев. Умножение - это просто повторное сложение, и вы можете использовать однострочные комментарии (или просто опустить их). Двоеточие используется для троичных операторов, для которых вместо этого можно использовать оператор if и цикл foreach, который можно заменить на обычный цикл for. J и Z не являются частью каких-либо ключевых слов в Java.

Попытка удалить любой другой символ требует, чтобы мы добавили по крайней мере один из символов, требуемых в плите Java class a{public static void main(String[]a){}}. Смотри ниже:

1 -> a (which has already been removed)
2 -> r (required for "String")
3 -> S (required for "String")
4 -> t (required for "static")
5 -> S (required for "String")
6 -> v (required for "void")
7 -> g (required for "String")
8 -> ( (required for "main(String[]a)"
9 -> i (required for "static")
b -> { (required for "class a{")
c -> l (required for "class")
d -> } (required for "(String[]a){}}")
e -> n (required for "main")
f -> o (required for "void")

Вот пример с программой Hello World. Попробуйте онлайн!

Java 8, 16 символов

\bdefu0123456789

Спасибо ais523 за указание на это. Java 8 позволяет интерфейсам иметь статические методы, что означает, что мы можем отбросить «c», потому что он нам не нужен для «l» в «классе». «c» используется для, ,<lL\|поэтому мы теряем чуть больше Java-функциональности, чем когда мы удаляли «a», но у нас все еще достаточно, чтобы завершить работу. Попробуйте онлайн!

Лабиринт , 5 персонажей

~{}

Плюс перевод строки (0x0A) и пробелы (0x20).

Я собираюсь набросать доказательство в форме сокращения от Smallfuck (сокращенный вариант Brainfuck, который использует 1-битные ячейки). Обратите внимание, что Smallfuck сам по себе не является полным по Тьюрингу, потому что язык указывает, что его лента должна быть конечной, но мы собираемся предположить вариант Smallfuck с бесконечной лентой, который затем будет полным по Тьюрингу (поскольку у Лабиринта нет памяти ограничения по дизайну).

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

Лабиринт имеет два стека, которые изначально заполнены бесконечным (неявным) количеством 0s. {и }сдвиньте верхнее значение между этими стеками. Если мы считаем вершину основного стека текущей ячейкой, то эти два стека можно рассматривать как две полубесконечные половины бесконечной ленты, используемой Smallfuck. Однако для обеспечения инварианта, упомянутого выше, будет удобнее иметь по две копии каждого значения ленты в стеках. Поэтому <и >будет переведено на {{и }}, соответственно (вы можете поменять их местами, если хотите).

Вместо того, чтобы разрешать значения ячеек 0и 1, мы используем 0и -1, между которыми мы можем переключаться ~(побитовое отрицание). Точные значения не имеют значения для целей полноты по Тьюрингу. Мы должны изменить обе копии значения в стеке, что снова дает нам четный перевод: *становится ~}~{.

Это оставляет команды потока управления []. Лабиринт не имеет явного потока управления, но вместо этого поток управления определяется макетом кода. Нам нужны пробелы и переводы строк, чтобы сделать это макет.

Во-первых, обратите внимание, что ~~это запрет, так как эти два действия ~эффективно отменяются. Мы можем использовать это, чтобы иметь произвольно длинные пути в коде, если их длина четна. Теперь мы можем использовать следующую конструкцию для перевода AA[BB]CCв Лабиринт (я использую двойные буквы, чтобы размер каждого фрагмента в Лабиринте был четным, как это гарантировано инвариантом):

      ~~~~
      ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Вот ..подходящее число, ~которое соответствует ширине BB.

Еще раз отметим, что ширина конструкции остается ровной.

Теперь мы можем понять, как работает этот цикл. Код вводится через AA. Первый ~~ничего не делает и позволяет нам добраться до перекрестка. Это примерно соответствует [:

• Если текущее значение ячейки равно нулю, IP-адрес продолжается прямо, что в конечном итоге будет пропущено BB. ..Часть до сих пор нет-оп. Затем мы достигаем одного ~на другом перекрестке. Теперь мы знаем, что текущее значение не равно нулю, поэтому IP действительно поворачивает на север. Он идет вокруг поворота наверху, пока не достигнет другого перекрестка после шести ~. Таким образом, в этот момент текущее значение все еще ненулевое, и IP снова поворачивает, чтобы двигаться на восток в направлении CC. Обратите внимание, что три ~перед CCвозвращением текущего значения 0, как и должно быть, когда цикл был пропущен.
• Если текущее значение ячейки в начале цикла не равно нулю, IP поворачивает на юг. Он проходит еще шесть, ~прежде чем достичь BB(которые ничего не делают), а затем еще шесть, ~прежде чем достичь следующего перекрестка. Это примерно соответствует ].
  • Если текущая ячейка равна нулю, IP продолжает двигаться на север. Следующий ~делает значение ненулевым, так что IP принимает этот второй переход, который объединяет путь со случаем, что цикл был полностью пропущен. Опять же, три ~возвращают значение в ноль, прежде чем достичь CC.
  • Если текущая ячейка отлична от нуля, IP поворачивает на запад. Есть ~до следующего перехода, что означает, что на данный момент текущее значение равно нулю, так что IP продолжает идти на запад. Тогда будет еще нечетное число ~до того, как IP снова достигнет начального соединения, так что значение будет возвращено, -1и IP переместится на юг в следующую итерацию.

Если программа содержит какие-либо циклы, то самую первую AAнеобходимо расширить до верха программы, чтобы IP-адрес находил правильную ячейку для запуска:

~     ~~~~
~     ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Ничего не поделаешь. Обратите внимание, что программы, полученные в результате этого сокращения, никогда не прекратят работу, но это не является частью требований полноты по Тьюрингу (рассмотрим Правило 101 или Фрактран).

Наконец, у нас остается вопрос, является ли это оптимальным. Что касается символов рабочей нагрузки, я сомневаюсь, что это можно сделать лучше, чем три команды. Я мог видеть альтернативную конструкцию, основанную на машинах Минского с двумя регистрами, но для этого потребовалось бы наличие =()или =-~наличие только одной команды управления стеком, а затем двух арифметических команд. Я был бы счастлив оказаться неправым в этом. :)

Что касается команд компоновки, я считаю, что перевод строки необходим, потому что полезный поток управления невозможен в одной строке. Однако, места не являются технически необходимыми. Теоретически может быть возможно придумать конструкцию, которая заполняет всю сетку ~{}(или =()или =-~) или использует рваный макет, где линии не имеют одинаковую длину. Однако написание такого кода невероятно сложно, потому что Labyrinth будет рассматривать каждую ячейку как соединение, и вам нужно быть очень осторожным, чтобы не допустить ветвления кода, когда вы этого не хотите. Если кто-то может доказать или опровергнуть, возможно ли исключение пробела для полноты по Тьюрингу, я был бы рад выделить за это значительную награду. :)

Haskell, 5 7 персонажей

()\->=;

Как функциональный язык, на Хаскеле, конечно же, есть лямбды, поэтому моделировать лямбда-исчисление легко. Синтаксис лямбды такой, что нам нужны хотя бы символы . Кроме того, нам нужно неограниченное количество переменных символов, чтобы иметь возможность строить произвольные лямбда-выражения. К счастью , нам не нужны новые символы для этого, так как , , , ..., все действительные имена переменных. Фактически каждая комбинация внутри круглых скобок является допустимым именем переменной, за исключением just и , которые зарезервированы для лямбда-выражений и которые запускают строковый комментарий.(\variable->body)argument()\->
(>)(>>)(>>>)\->\->--

Примеры:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))типы для(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))типы дляt -> t1 -> t
• Я = (\(>)->(>))типы дляt -> t

Редактировать: Однако, как указывает ais523 в комментариях, эта конструкция реализует типизированное лямбда-исчисление , которое само по себе не является полным по Тьюрингу, поскольку в нем отсутствует возможность ввода бесконечных циклов. Чтобы это исправить, нам нужна функция, которая выполняет рекурсию. До сих пор мы использовали безымянные лямбды, которые не могут называть себя, потому что, ну, у них нет имени. Итак, мы должны добавить символы =и ;реализовать fixфункцию:

(>)=(\(-)->(-)((>)(-)));   -- equivalent to: f =(\ x -> x ( f  x ));

С этой декларации наша лямбда - исчисление становится Тьюринга, однако , добавив =и ;, нам не нужно больше лямбды, как вы можете видеть в ответ Ними в котором используется только ()=;.

CJam, 3 персонажа

Удалено )в соответствии с предложением Мартина Эндера

'(~

Подобно Python, приведенному в качестве примера.

С помощью '~вы можете получить ~персонажа. Затем, используя (, вы можете уменьшить его, чтобы получить любой символ, который вы хотите ( ~это последний печатный символ ASCII). ~Обнуляет любую строку как обычный код CJam. Строки могут быть созданы путем получения символа [(посредством уменьшения ~), его оценки, добавления некоторой последовательности других символов, а затем оценки символа ]. Благодаря этому вы можете создавать и выполнять любую CJam-программу, используя только эти три символа.

Расчет 2 + 2, используя только '(~

Brain-Flak , 6 персонажей

(){}[]

Brain-Flak - это минималистский язык с 8 доступными символами. Однако можно доказать, что существует подмножество Brain-Flak, которое также завершается по Тьюрингу, используя только 6 символов.

Первое, что мы сделаем, это реализуем Minsky Machine только с одним стеком Brain-Flak. Если мы сможем доказать, что Minsky Machine возможна только с одним стеком, мы можем показать, что Brain-Flak завершается по Тьюрингу без nilads <>и []Это не спасет персонажей сразу, но будет в будущем, когда мы покажем, что в <...>этом нет необходимости.

Машина Минского - это тип полного автомата Тьюринга, который имеет конечное число неограниченных регистров и две инструкции:

• Увеличить регистр

• Если ненулевой декремент, иначе переход к указанной инструкции

Чтобы настроить структуру goto в Brain-Flak, мы можем использовать следующий фрагмент:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Это уменьшит счетчик и будет работать, %sесли ноль. Куча этих цепочек позволит нам поместить в стек число, которое укажет на какую строку мы хотим перейти. Каждый из них будет уменьшать вершину стека, но только один из них будет фактически выполнять код.

Мы используем это в качестве оболочки для всех наших инструкций Minsky Machine.

Увеличение определенного регистра довольно легко без переключения стека. Это может быть достигнуто с помощью этой строковой формулы:

"({}<"*n+"({}())"+">)"*n

Например, чтобы увеличить третий регистр, мы напишем следующий код:

({}<({}<({}<({}())>)>)>)

Теперь нам осталось реализовать вторую операцию. Проверить, является ли число нолем, довольно просто в Brain-Flak:

(({})){(<{}%s>)}{}

будет выполняться только %sесли TOS равен нулю. Таким образом, мы можем сделать нашу вторую операцию.

Так как Minsky Machines является полной по Тьюрингу, Brain-Flak также является полной по Тьюрингу без использования операций <>и [].

Однако мы не уменьшили количество символов еще потому , что <...>и [...]до сих пор используются. Это можно исправить с помощью простой замены. Так <...>как на самом деле эквивалентно [(...)]{}во всех случаях. Таким образом , Brain-Flak является Тьюринга без использования <и >символов (плюс все не-OPS).

> <> , 3 символа

> <> выполнимо в 3 с 1p-, что:

1          Push 1
p          Pop y, x, c and put the char c in cell (x, y) of the codebox
-          Subtraction: pop y, x and push x-y

pобеспечивает отражение, изменяя исходный 2D-код, помещая символы в кодовое поле. С помощью 1-вы можете поместить любое число в стек, так как 1-вычитает единицу и 111-1--( x-(1-1-1) = x+1) добавляет единицу.

Как только все 1p-команды выполнены, указатель инструкций оборачивается, позволяя ему выполнить «настоящий» код.

Пример программы, которая вычисляет числа Фибоначчи (из этого ответа ):

111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1-1--1p

Попробуйте онлайн! После выполнения всех 1p-команд кодовое окно выглядит следующим образом:

01aa+v1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1- ...
@+&1->:?!;&:nao:

За исключением всего, что находится vв первой строке, это стандартная программа Фибоначчи> <>.

Баш, 9 символов

01456\$ '

Bash имеет синтаксис $'\nnn'для ввода символов с восьмеричными значениями ascii. Мы можем ввести evalкоманду в этом формате как $'\145\166\141\154'. Сначала мы превращаем желаемый результат в восьмеричные значения. Затем мы преобразуем любые восьмеричные значения, используя цифры, отличные от 0, 1, 4, 5 и 6, в выражения, оценивающие указанные восьмеричные значения, используя $(())и вычитание, добавляя evalперед собой. На последнем шаге мы добавим еще один evalи преобразуем скобки и знак минус в их восьмеричные значения. Используя этот метод, мы можем выполнить любую команду bash, поэтому это подмножество завершено.

Пример:

dc становится

$'\144\143' который становится

$'\145\166\141\154' \$\'\\144\\$((144-1))\' который становится

$'\145\166\141\154' $'\145\166\141\154' $'\$\\\'\\\\144\\\\$\050\050144\0551\051\051\\\''

Инцидент , 2 персонажа

Неважно, какие два персонажа вы выберете; Любая комбинация двух октетов является полной по Тьюрингу в Инциденте.

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

До доказательства немного предыстории. Инцидент выводит токены, используемые в программе, путем просмотра источника (токен - это строка, которая появляется в источнике ровно три раза, не является подстрокой другого токена и не перекрывается с другим потенциальным токеном). Таким образом, любая программа может быть преобразована для использования практически любого набора символов путем изменения токенов; язык полон по Тьюрингу (и также имеет полноту для ввода-вывода!), несмотря на то, что он невероятно сложен для программирования, поэтому «все», что вам нужно, - это метод кодирования токенов, чтобы они работали всего с двумя символами.

А теперь вот краткое изложение доказательства (которое было найдено Орджаном, резидентом математики Эсоланга). Идея состоит в том, что мы кодируем токен, используя две копии одного символа (скажем 1) в большом море другого символа (скажем 0). Расстояние между 1s отличается для каждого токена, но всегда кратно 4. Затем для заполнения между токенами мы используем дополнительный список 0s с a 1в середине, но число 0 на каждой стороне 1is не кратное 4, а число, уникальное для той конкретной частоты возникновения программы, которая отсутствует в других местах программы. Это означает, что каждый 1...1внутри отступа может появиться только дважды, поэтому не будет частью токена; каждый намеченный токен содержит ровно две единицы, и ни один фиктивный токен не может содержать более одной 1. Затем мы просто добавляем отступы в сторону, чтобы удалить все возможные токены, содержащие один 1или ноль 1, добавив как минимум четыре их копии.

Сетчатка , 3 персонажа

{`

и перевод строки.

Во-первых, нам нужна новая строка, чтобы иметь возможность делать подстановки (необходимо, если мы не хотим поместить всю программу в одно регулярное выражение, для которого потребуется больше символов); и `и {являются наименее интенсивным символом способ делать циклы. Оказывается, нам больше ничего не нужно.

Наш целевой язык для реализации - это детерминированный вариант Thue (недетерминированность не обязательна для полноты по Тьюрингу; можно написать программу Thue для правильной работы независимо от того, какой порядок оценки используется). Основная идея состоит в том, чтобы собрать pattern::=replacementв

`pattern
replacement

(это прямой перевод Retina с Thue; альтернативно, если вы знаете Retina, но не Thue, вы можете использовать его как метод изучения работы Thue); как исключение, {`вместо самого первого шаблона предшествует (для того, чтобы поместить всю программу в цикл; программы Thue продолжают работать до тех пор, пока больше не будут возможны замены, и это заставит Retina работать аналогичным образом).

Конечно, это означает , что нам нужно доказать Thue Тьюринг только с {и `в узорах и заменах, но это достаточно просто; мы заменяем символ с кодом ASCII n на `, n +1 {и другой `. Очевидно, что шаблон не может совпасть нигде, кроме как на границах символов, поэтому в конечном итоге будет сделано то же самое, что и в исходной программе.

Брахилог , 5 знаков

~×₁↰|

Это подмножество символов позволяет нам реализовать версию Fractran, в которой единственными числами, которые могут появляться, являются произведения повторений (то есть произведения чисел, которые могут быть записаны в десятичном виде с использованием только цифры 1). ~×(с целым числом в качестве нижнего индекса) делит текущее значение на это целое число, но только в том случае, если оно делится точно (в противном случае оно «терпит неудачу» и ищет другой случай для выполнения; |разделяет случаи). ×позволяет нам умножить на целое число. Таким образом, используя ~×₁|мы можем реализовать один шаг выполнения Fractran. Затем ↰давайте вернемся, снова запустив всю программу на новом текущем значении. Вот пример очень простой программы Fractran ( 11111111111111111111111/111), переведенной на Brachylog.

Так завершен ли этот Тьюринг? Все, что нам нужно, чтобы завершить Фрактран Тьюринг, - это достаточно большое количество простых чисел (достаточно, чтобы написать интерпретатор для полного языка Тьюринга в самом Фрактране). Есть пять проверенных и четыре подозреваемыхвоссоединить простые числа, в дополнение, вполне возможно, те, которые еще не были обнаружены. Это на самом деле больше, чем нам нужно в этом случае. Программа проверяет возможности слева направо, поэтому мы можем использовать одно простое число в качестве указателя инструкции и еще два в качестве счетчиков, демонстрируя полноту по Тьюрингу только с тремя простыми числами (это тоже хорошо, потому что позволяет использовать повторения с 2, 19). и 23 цифры, без необходимости прибегать к проверенным, но досадно большим повторениям с 317 или 1031 цифрами, что затруднит написание исходного кода). Это позволяет реализовать машину Минского с двумя счетчиками (достаточно для полноты по Тьюрингу).

Вот как конкретно работает компиляция. Мы будем использовать следующие две команды для нашей машинной реализации Minsky (это известно как завершение Тьюринга), и каждая команда будет иметь целое число в качестве метки:

• Метка L: если счетчик {A или B} равен нулю, перейдите к X. В противном случае уменьшите его и перейдите к Y.
• Метка L: увеличить счетчик {A или B}, затем перейти к Z.

Мы выбираем, какую команду выполнять, помещая силы 11 в знаменатель, сначала высшие силы; показатель степени 11 является меткой команды. Таким образом, первая соответствующая дробь будет текущей выполняемой командой (потому что предыдущие не могут делиться на все эти 11). В случае команды декремента мы также помещаем множитель 1111111111111111111 или 11111111111111111111111 в знаменатель для счетчика A или B соответственно, и следуем за ним с другой командой без этого фактора; регистр «декремент» будет реализован первой командой, регистр «ноль» - второй. Между тем, «goto» будет обрабатываться в числителе соответствующей степенью 11, а «приращение» - в 1111111111111111111 или 11111111111111111111111 в числителе.

Befunge-98, 3 персонажа

Насколько я знаю, Befunge-98 должен быть завершен, поэтому нам просто нужно показать, как можно сгенерировать любую программу Befunge-98, используя всего три символа. Мое первоначальное решение основывалось на следующих четырех символах:

01+p

Мы можем получить любое положительное целое число в стеке, добавив несколько 1значений вместе с +командой, и для нуля мы просто используем 0. Как только у нас появится возможность нажимать любое нужное число, мы можем использовать команду p(put), чтобы записать любое значение ASCII в любое место в игровом поле Befunge.

Однако, как указал Sp3000 , вы можете обойтись всего тремя символами:

1-p

Любое отрицательное число можно вычислить, начав с 1последующего многократного вычитания 1(например, -3 будет 11-1-1-1-). Тогда любое положительное число может быть представлено вычитанием 1-n из 1, где 1-n - отрицательное число, с которым мы уже знаем, как обращаться (например, 4 = 1 - (- 3), что будет 111-1-1-1--).

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

Например, вот загрузчик, который генерирует код Befunge, необходимый для суммирования 2 + 2, и выводит результат: 22+.@

И для более сложного примера это «Hello World»: "!dlroW olleH"bk,@

Рубин, 8 символов

eval"<1+

Вдохновленный ответами Python

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

• eval может использоваться для выполнения произвольной строки.
• «<1+ - это минимальный набор символов, необходимый для построения любой строки

Строка в ruby ​​может быть построена с использованием пустой строки в качестве начальной точки и добавления к ней символов ascii, например, так:

eval ""<<111+1<<11+11+11+1<<111<<11+11+11+1

на самом деле эквивалентно

eval ""<<112<<34<<111<<34

который оценивает строку

p"o"

OCaml, 9 символов

fun->()`X

Этих символов достаточно для реализации исчисления SKI Combinator в OCaml. Примечательно, что мы можем избежать использования пространства с достаточными круглыми скобками. К сожалению, лямбда-выражения в OCaml требуют funключевого слова, поэтому более краткое решение невозможно. Эти же буквы могут использоваться для построения произвольных имен переменных, если, однако, требуются более сложные лямбда-выражения.

S Combinator:

fun(f)(u)(n)->f(n)(u(n)) с типом ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinator:

fun(f)(u)->u с типом 'a -> 'b -> 'b

Я комбинатор:

fun(f)->f с типом 'a -> 'a

Как отмечает ais523, недостаточно просто кодировать SKI. Вот кодировка для Z с использованием полиморфных вариантов для манипулирования системой типов. С этим мое подмножество должно быть завершено.

Z Combinator:

fun(f)->(fun(`X(x))->(x)(`X(x)))(`X(fun(`X(x))y->f(x(`X(x)))y))

с типом (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Основанные на стеке конкатенационные языки, 4 символа

недогрузка

():^

GolfScript

{}.~

CJam

{}_~

GS2

• Backspace, Tab,, @пробел (я знал, что GS2 часто использовал непечатные, но это смешно ...)

dc (предложено @seshoumara)

[]dx

Недостаточная нагрузка была доказана полной по Тьюрингу с использованием только ():^(благодаря постоянному математику Эсоланга Орджану). Доказательство слишком длинное, чтобы объяснять здесь, но если вам интересно, вы можете прочитать об этом здесь .

Команды, о которых идет речь, ()(размещение литерала кода в стеке), :(дублирование элемента верхнего стека) и ^(оценка вершины стека). Эти команды довольно распространены в стековых языках (особенно в конкатенационных), и поэтому я привел кое-что из их коллекции выше; все эти языки полны по Тьюрингу по 4 символа по той же причине, что и недогрузка.

Пробел, 3 символа

STL

Sэто пробел, Tтабуляция и Lперевод строки.

Ракетка (Схема), 4 персонажа

(λ)

Используя только λ, скобки и пробел, мы можем напрямую программировать в подмножестве Lambda Calculus на Схеме. Мы повторно используем символ λ для всех идентификаторов, объединяя их вместе, чтобы обеспечить произвольно большое количество уникальных идентификаторов.

В качестве примера приведу классический комбинатор Omega, который работает вечно.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))

Python 3, 9 символов

exc('%1+)

Смотрите мой ответ на Python 2 для базового объяснения. Этот ответ основан на этом.

Вместо того, чтобы просто использовать те же символы, что и в Python два, с добавлением символа (), мы можем удалить символ, поскольку теперь у нас есть скобки. Программы по-прежнему будут иметь базовую форму

exec('%c'%stuff)

но мы сокращаем длину программы, используя +вместо -, а затем мы можем удалить ~, используя 1вместо 0. Затем мы можем добавить 1, 11и 111получить требуемые значения ASCII.

В print()кратчайшие сроки программа становится следующей:

exec('%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%(111+1)%(111+1+1+1)%(11+11+11+11+11+11+11+11+11+1+1+1+1+1+1)%(11+11+11+11+11+11+11+11+11+11)%(111+1+1+1+1+1)%'('%')')

Попробуйте онлайн

Вы можете подумать про себя, как можно создать байт NUL без 0? Не бойся, молодой кузнечик! потому что у нас есть возможность использовать %для математики, создавая ноль с 1%1.

PHP 7, 6 символов

'().;^

Идея состоит в том, что возможно выполнить произвольный код, используя следующую конструкцию:

('create_function')('','<code>')();

eval не будет работать здесь, потому что это языковая конструкция и не может быть вызвана с использованием переменных функций.

create_function и код может быть написан как конкатенация побитовых XOR доступных символов:

(<char1_1>^<char1_2>^...).(<char2_1>^<char2_2>^...)...

Используя ().;^для <charX_Y>, мы можем получить

()./:;<=JKLMXY^_bcdepqvw

и некоторые непечатные символы. Этого недостаточно, но теперь мы можем позвонить 'eXp'()и получить несколько числовых символов:

''.'eXp'('eXp'('')) -> 1
''.'eXp'('eXp'('eXp'(''))) -> 2.718281828459
''.'eXp'('eXp'('eXp'('eXp'('eXp'(''))))) -> 3814279.1047602

Это дает нам 1, 2и 3(другие символы будут проигнорированы XOR, если другая строка длиной один символ). Из ().;^123теперь мы можем генерировать все кодировки ASCII.

Попробуйте онлайн

Пайк, 5 персонажей

0h.CE

Это способно производить бесконечно большое число, превращать его в строку и затем оценивать как код Pyke.

Пояснение к коду:

0- Добавить 0 в стек. Это необходимо, чтобы начать номер

h- Увеличьте число до. Повторяя это произвольное количество раз, вы можете создавать бесконечно большие числа. Pyke поддерживает bignums, как написано на Python, который использует их по умолчанию.

.C- Превратить число в строку, используя следующий алгоритм: ( ссылка на Github )

def to_string(num):
    string = ""
    while num > 256:
        num, new = divmod(num, 256)
        string = chr(new) + string
    string = chr(num) + string
    return string

К этому моменту мы можем создать произвольное количество строк и натуральных чисел в Pyke с произвольными значениями. Числа могут быть созданы в форме, соответствующей регулярному выражению, 0(h)*и строки могут быть созданы с 0(h)*.C. Они могут быть переплетены друг с другом, чтобы создать произвольную смесь строк и целых чисел.

Eоценивать строку как код Pyke. Он использует ту же среду, что и код Pyke, который уже запущен, поэтому будет делиться такими вещами, как ввод

Попытка доказать, что Пайк завершен по Тьюрингу.

Один из самых простых способов показать язык - это выполнить Brainf * ck. Это, вероятно, намного сложнее в Pyke, чем во многих других языках, потому что его операции со списком и словарем практически не существуют из-за отсутствия необходимости в них, в той области, в которой Pyke предназначен для работы: code-golf .

Сначала мы создаем интерпретатор для brainf * ck и кодируем его, используя наш алгоритм выше, чтобы создать число, а затем выражаем это число с помощью 0и h. Затем мы создаем строку, содержащую код для запуска точно таким же образом. Если бы мы оставили все как есть, у нас был бы стек

string containing brainf*ck code
string containing brainf*ck interpreter

Это означает, что код должен быть в противоположной форме, так как стек Pyke первым и последним вышел.

Теперь самое интересное: интерпретатор brainf * ck с колоссальными 216 байтами!

Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\.qI~LZ@.CpK)~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN

Попробуй это здесь!

Если вы хотите попробовать код в полузаполненной, но редактируемой форме, попробуйте здесь!

Чтобы преобразовать строку в число, вы можете использовать следующий код Python:

def conv(string, t=0):
    t *= 256
    t += ord(string[0])
    if len(string) != 1:
        return conv(string[1:], t)
    return t

(Почти) окончательное решение можно попробовать здесь!

Объяснение переводчика Brainf * ck

Сначала давайте разделим программу на части:

• Инициализация:

​

Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".:          - input.replace("><+-.,[]", "><ht.,")
                       - replace the characters in brainf*ck with some modified ones. 
                       - this means we can `eval` the add and subtract bits easily.
             =B;       - set `B` to this.
                       - The `B` variable contains the instructions
                Z]1=L; - set `L` to [0]
                       - `L` contains the stack, initialised with 0

• Основной цикл:

​​ ​ ​

W~Bo@D=c !code! ~o~BlN - The main loop
W                      - do
 ~Bo@D=c               -  c=B[o++]
                       -  the c variable is used to store the current character.
                ~o~BlN - while
                ~o     -   o 
                     N -  ^ != V 
                  ~Bl  -   len(B)
                       -  this stops the program running once it's finished.

• Инструкции
  • Увеличение / уменьшение:+-

​​ ​ ​

"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I                 ) - if c in "ht"
        ~LZ@             -  L[Z]
                         -  `Z` contains the current stack pointer
      ~c    E            -  eval current character with ^ as an argument
                         -  returns the contents of `Z` either incremented or decremented
             Z]1~LR3:=L  - L[Z] = ^

• Вход ,:

​​ ​ ​

~c\,qIz.oZ]1~LR3:=L) - The code for output 
~c\,qI             ) -  if character == ",":
      z.o            -    ord(input)
         Z]1~LR3:=L  -   L[Z] = ^

• Выход .:

​​ ​ ​

~c\.qI~LZ@.CpK) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)

• Сдвиг влево / вправо <>:

​​ ​ ​

~c"<>"{I~c"<>""th".:ZE=Z - main part 
~c"<>"{I                 - if "<>" in c:
        ~c"<>""th".:     -  c.replace("<>", "th")
                    ZE=Z -  Z = eval(char, Z)

Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI                ) - if Z == -1:
     0=Z               -  Z = 0
        ~L0"":         -  L.insert("", 0)
              0]10:=L  -  L[0] = 0

Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI                ) - if Z == len(L):
        ~Ll"":          -  L.insert("", len(L))
      ~L      1_]10:=L  -  L[-1] = 0

• Условия [:

​​ ​ ​

~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI                      ) - if c == "[":
      ~LZ@0qI              )  -  if L[Z] == 0:
               ~B~o>          -     B[o:]
             \]     @         -    ^.find("]")
                     ~o+h=o   -   o = o + ^ + 1

- и ]:

​​ ​ ​

~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI               ) - if c == "]":
          ~B~o<_       -    reversed(B[:o])
        \[      @      -   ^.find("[")
      ~o         -t=o  -  o = o - ^ -1

Сложено, 5 символов

{!n:}

Это на удивление коротко. Если Stacked может реализовать каждую из комбинаций SKI, то это Turing Complete. Резюме:

• I комбинатор - функция тождества. x -> x
• K комбинатор - постоянная функция. x -> y -> x
• S комбинатор - функция подстановки. (x, y, z) -> x(z)(y(z))

Я комбинатор: {!n}

Теперь о сложенной специфике. {! ... }это н-лямбда. Это унарная функция, аргумент которой неявно n. Затем последнее выражение возвращается из функции. Таким образом, {!n}это функция, которая принимает аргумент nи дает n.

K комбинатор: {!{:n}}

Теперь {:...}это функция, которая не принимает аргументов и возвращает .... Объединяя это с нашей n-лямбда-формой, мы получаем (добавляя пробел для ясности):

{! { : n } }
{!         }   n-lambda. arguments: (n)
   { : n }     lambda.   arguments: ()
       n       yields n.

S Combinator: {n!nn!nnn:nnn{!n}!nn!nnn{!n}!n!!}

Хорошо, это выглядит немного сложнее. Итак, лямбда принимает аргументы, разделенные неидентификационными символами. Таким образом, лямбда в заголовке эквивалентна:

{n nn nnn:nnn{!n}!nn!nnn{!n}!n!!}

Это лямбда , которая принимает три аргумента, n, nnи nnn. Давайте заменить их x, yи zдля ясности:

{x y z:z{!n}!y!z{!n}!x!!}

Эти две {!n}!функции просто идентичны, чтобы снова избежать пробелов, где !означает «выполнить». Итак, опять же, сокращение:

{x y z:z y!z x!!}

С объяснением:

{x y z:z y!z x!!}
{x y z:         }  three arguments
       z y!        apply `y` to `z` -- `y(z)`
           z x!    apply `x` to `z` -- `x(z)`
               !   apply `x(z)` to `y(z)` -- `x(z)(y(z))`

И, следовательно, это комбинатор S.