Podsumowanie:

Jaka jest najmniejsza liczba unikalnych znaków dla danego języka dla danego języka, aby był on kompletny w Turingu ?

Wyzwanie:

Dla dowolnego wybranego języka znajdź najmniejszy podzbiór znaków, który pozwala na ukończenie Turinga. Możesz ponownie użyć zestawu znaków tyle razy, ile chcesz.

Przykłady:

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

• Brainfuck: +<>[](przyjmuje rozmiar owijającej się komórki)

• Python 2: ()+1cehrx(wykonany ze skryptów takich jak exec(chr(1+1+1)+chr(1)))

Punktacja:

To wyzwanie jest oceniane postaciami , a nie bajtami . Na przykład, wyniki dla przykładów wynoszą 6, 5 i 9.

Uwagi:

• To wyzwanie różni się od innych w tym sensie, że tylko Twój język jest Turing-Complete (niekoniecznie możliwość korzystania z każdej funkcji języka).

• Chociaż możesz, nie publikuj odpowiedzi bez zmniejszania liczby używanych znaków. Przykład: Brainfuck z 8 znakami (ponieważ każda inna postać jest domyślnie komentarzem).

• MUSISZ podać przynajmniej krótkie wyjaśnienie, dlaczego twój podzbiór jest Turing-Complete.

Haskell, 4 znaki

()=;

Dzięki ()=jesteśmy w stanie zdefiniować S, K i I. Definicje muszą być oddzielone przez jeden ;lub NL.

Definiujemy (==)jako S (druga linia pokazuje bardziej czytelną wersję):

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

(===) zapytać:

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

i (====)jak ja:

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

Na szczęście (==), (===), (====), itd. Są poprawne nazwy funkcji / parametrów.

Jak wskazuje @ ais523, SKI nie wystarcza w silnie napisanym języku, takim jak Haskell, dlatego musimy dodać kombinator punktów stałych (=====):

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

JavaScript (ES6), 5 znaków

Dzięki @ETHproductions i @ATaco za pomoc w tym; był to projekt grupowy i chociaż pierwotny pomysł był mój, wiele szczegółów należy do nich. Zobacz dyskusję na czacie, na której opracowano ten podzbiór JavaScript tutaj .

[]+=`

Jest dość dobrze ustalone, że każdy program Javascript może być napisany za pomocą znaków ( []()+!), ale 5 znaków to za mało . Nie jest to jednak wyzwanie związane z pisaniem dowolnego kodu JavaScript. Wyzwaniem jest napisanie kompletnego języka Turinga i wykorzystanie faktu, że języki kompletne Turinga nie potrzebują dostępu do DOM, ani nawet interaktywnych wejść / wyjść, okazuje się, że możemy napisać program ze wszystkimi wymaganymi funkcjami , nawet bez możliwości uruchomienia evallub równoważnego.

Podstawowe ładowanie

JavaScript jest bardzo elastyczny z typami. Na przykład []jest pustą tablicą, ale +[]ma wartość 0 i []+[]jest łańcuchem pustym. W szczególności fakt, że możemy wygenerować 0 za pomocą tego zestawu znaków, umożliwia symulację efektu nawiasów dla grupowania; (a)można zapisać jako [a][+[]]. Możemy użyć tego rodzaju sztuczki, aby stworzyć różne postacie, używając tylko +[]:

• [][+[]]jest undefined(będąc pierwszym elementem pustej tablicy); więc
• []+[][+[]]jest "undefined"(rygoryzacja undefined); więc
• [[]+[][+[]]]jest ["undefined"](zawijanie tego w tablicę); więc
• [[]+[][+[]]][+[]]jest "undefined"(jej pierwszy element); więc
• [[]+[][+[]]][+[]][+[]]jest "u"(pierwsza litera).

ujest jedną z najłatwiejszych do stworzenia postaci, ale podobne techniki pozwalają nam stworzyć szereg innych postaci. Ten sam link jak poprzednio daje nam następującą listę znaków dostępnych za pomocą +[](jest to ta sama lista co dla +[](), z wyjątkiem, ,ponieważ jest to jedyna konstrukcja, która używa nawiasów w celu innym niż grupowanie / pierwszeństwo):

0123456789acdefinotuvyIN (){}.

Nie możemy przeliterować zbyt wielu użytecznych słów z tego zestawu znaków (pamiętaj, że jest to zestaw znaków, które możemy wytworzyć jako ciągi ; nie możemy wykonać ich bez jakiegoś rodzaju eval). Dlatego potrzebujemy innej postaci. Użyjemy =, ponieważ przyda się później, ale na razie użyjemy go do przeliterowania operatora porównania ==. To pozwala nam tworzyć falsei true, które można skreślić i zaindeksować, i od razu dodawać lrsdo znaków, które możemy zawrzeć w łańcuchach.

Zdecydowanie najważniejszym słowem, które pozwala nam to przeliterować, czego nie mogliśmy wcześniej zrobić, jest constructor. Teraz JavaScript ma składnię dostępu do właściwości, która wygląda następująco:

object.property

ale możesz też napisać to w ten sposób:

object["property"]

i nic nie stoi na przeszkodzie, abyśmy używali obliczonej właściwości, a nie dosłownego łańcucha. W ten sposób możemy zrobić coś w stylu

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

(z literami wygenerowanymi jak opisano powyżej; kod szybko staje się bardzo długi!); jest to równoważne z object.constructor, co pozwala nam uzyskać dostęp do konstruktorów dowolnych obiektów.

Istnieje kilka sztuczek, które możemy z tym zrobić. Od przyziemnych po fantastyczne:

• Konstruktor obiektu jest funkcją. Warto zauważyć, że ma ona nazwę, która jest częścią łańcucha znaków funkcji. Na przykład, możemy zrobić, [[]+[]][+[]]["constructor"]aby dostać się do konstruktora dla łańcucha, którego nazwa to String, a następnie skretyfikować, aby uzyskać Sznak wielkiej litery. To trochę rozszerza nasz alfabet i będziemy potrzebować trochę nowych znaków później.

• Wszystkie tablice mają tego samego konstruktora; []["constructor"] == []["constructor"]jest true(w przeciwieństwie do [] == [], co jest fałszem). Może się to wydawać niewielkie, ale jest to bardzo ważne, ponieważ daje nam metodę trwałego przechowywania wartości; możemy ustawić losową właściwość w konstruktorze i odczytać ją później. (Jest to jeden z powodów, dla których korzystamy =w szczególności, a nie jeden z innych sposobów generowania truei false.) Na przykład możemy ocenić [[]["constructor"]["a"]=[]], a później odczytać []["constructor"]["a"]i odzyskać tę samą tablicę, którą tam zapisaliśmy.

  Spełnia to jeden z wymogów, których potrzebujemy do kompletności Turinga , zdolności do przechowywania i pobierania dowolnych ilości danych. Możemy utworzyć komórkę przeciw przy użyciu tablicy dwuelementowej, pobierając wartości z naszego magazynu właściwości konstruktora, a następnie przechowując ją z powrotem w miejscu jednej z tych wartości, co pozwala nam budować dowolnie duże struktury danych w pamięci; i możemy uzyskać do niego dostęp, wykonując czynności odwrotne, niszcząc go kawałek po kawałku, aż dane, które chcemy, będą dostępne. Czytanie jest destrukcyjne, ale jest to dopuszczalne, ponieważ mamy więcej niż jedno miejsce do przechowywania danych, więc możemy je skopiować podczas czytania, a następnie umieścić kopię z powrotem w oryginalnej lokalizacji.

• Pozwala nam dotrzeć do konstruktora funkcji (istnieje wiele funkcji, do których możemy uzyskać dostęp za pomocą naszego ograniczonego alfabetu; []["find"]tzn. Array.find jest najłatwiej dostępny, ale są też inne). Dlaczego to jest przydatne? Cóż, właściwie możemy go używać do zamierzonego celu konstruktora i konstruować funkcje! Niestety, dzięki naszemu zestawowi znaków nie możemy przekazać konstruktorowi funkcji obliczonego ciągu. Jednak użycie `pozwala nam przekazać dosłowny ciąg znaków (np. []["find"]["constructor"]`function body goes here`); oznacza to, że możemy zdefiniować niestandardowe wartości typu funkcji z dowolnym zachowaniem po wykonaniu, o ile możemy wyrazić to zachowanie w całości przy użyciu []+=. Na przykład []["find"]["constructor"]`[]+[]`jest dość nudną funkcją, która oblicza ciąg zerowy, odrzuca go i kończy działanie; żefunkcja nie jest przydatna, ale będą bardziej złożone. Zauważ, że chociaż funkcje nie mogą przyjmować parametrów ani zwracać wartości, nie są to w praktyce problemami, ponieważ możemy używać pamięci konstruktora-właściwości do komunikowania się z jednej funkcji do drugiej. Kolejnym ograniczeniem jest to, że nie możemy używać `w ciele funkcji.

  Teraz możemy zdefiniować niestandardowe funkcje, ale tym, co nas powstrzymuje, jest trudność z ich wywołaniem . Na najwyższym poziomie programu możemy wywoływać funkcję za pomocą ``, ale możliwość wywoływania funkcji tylko z najwyższego poziomu nie pozwala nam na wykonywanie żadnej pętli. Potrzebujemy raczej funkcji, aby móc się nawzajem wywoływać.

  Osiągamy to z dość sprytną sztuczką. Pamiętasz kapitał, Sktóry wcześniej wygenerowaliśmy? To pozwala nam przeliterować "toString". Nie będziemy tego tak nazywać; możemy konwertować rzeczy na ciągi, dodając []do nich. Zamiast tego zamierzamy go zastąpić . Możemy użyć pamięci konstruktora do zdefiniowania trwałych tablic, które się trzymają. Następnie możemy przypisać utworzone przez nas funkcje do toStringmetod tablic , a te przypisania również pozostaną. Teraz wszystko, co musimy zrobić, to prosta +[]tablica i nagle nasza niestandardowa funkcja zostanie uruchomiona. Oznacza to, że możemy używać znaków+=[]do wywoływania funkcji, a zatem nasze funkcje mogą wywoływać się nawzajem - lub same. To daje nam rekurencję, co daje nam pętle i nagle mamy wszystko, czego potrzebujemy do kompletności Turinga.

Oto podsumowanie zestawu funkcji zapewniających Turingowi kompletność i sposób ich realizacji:

• Nieograniczona pamięć masowa : zagnieżdżone tablice w pamięci konstruktora
• Przepływ sterowania : zaimplementowany przy użyciu ifi rekurencji:
  • if: zamień wartość logiczną na liczbę i zindeksuj w tablicy 2-elementowej; jeden element uruchamia funkcję dla thensprawy, gdy jest ona strunowana, drugi element uruchamia funkcję dla elsesprawy, gdy jest ona strunowana
  • Rekurencja : należy skreślić odpowiedni element pamięci konstruktora
• Sekwencjonowanie komenda : [a]+[b]+[c]ocenia a, bi cod lewej do prawej (przynajmniej w przeglądarce sprawdziłem)

Niestety jest to dość niepraktyczne; jest nie tylko bardzo duży, biorąc pod uwagę, że ciągi znaków muszą być konstruowane znak po znaku, zgodnie z pierwszymi zasadami, ale nie ma też możliwości wykonywania operacji we / wy (co nie jest wymagane, aby było kompletne Turinga). Jeśli jednak zakończy się, przynajmniej później można ręcznie sprawdzić pamięć konstruktora, więc debugowanie programów nie jest niemożliwe i nie są one całkowicie niekomunikatywne.

Unary , 1 znak

0

Wybór postaci nie ma tak naprawdę znaczenia; długość programu określa program do pieprzenia mózgu, do którego się przenosi. Chociaż specyfikacja wymaga 0znaków, większość transpilatorów nie sprawdza tego.

vim, 9 8 7 6 znaków

<C-v><esc>1@ad

Możemy zbudować i uruchomić dowolny program vimscript w następujący sposób:

1. Użyj sekwencji, aa<C-v><C-v>1<esc>dd@1<esc>ddddaby uzyskać <C-a>rejestr wejściowy 1.

2. Wejdź do trybu wstawiania za pomocą a, a następnie wstaw a, który będzie później używany do ponownego wprowadzania trybu wstawiania w makrze.

3. Dla każdego znaku w żądanym programie vimscript

   1. użyj, <C-v><C-v>1<esc>aby wstawić literalną sekwencję <C-v>1,

   2. użyj @1(co oznacza <C-a><cr>, że finał nie <cr>działa ze względu na to, że znajduje się w ostatnim wierszu) tyle razy, ile jest to konieczne, aby zwiększyć 1wartość ASCII żądanego znaku,

   3. i ponownie wejść w tryb wstawiania za pomocą a.

4. Usuń linię (wraz z końcowym znakiem nowej linii) do 1rejestru za pomocą <esc>dd.

5. Wykonaj wynik jako naciśnięcia klawiszy vima za pomocą @1, a następnie, <esc>ddaby usunąć linię wprowadzoną przez końcowy znak nowej linii z poprzedniego kroku.

6. Uruchom wynikową dowolną sekwencję bajtów za pomocą dd@1. Jeśli zaczyna się od a :, zostanie zinterpretowany jako kod vimscript i zostanie uruchomiony z powodu końcowego znaku nowej linii od dd.

Nie jestem przekonany, że jest to minimalny zestaw postaci, ale dość łatwo jest udowodnić, że jest kompletny w Turingu.

Perl, 5 znaków

<>^es

Podobnie jak w przypadku innych języków skryptowych, chodzi o evaldowolne ciągi znaków. Jednak nasz zestaw znaków nie zawiera cudzysłowów ani operatorów konkatenacji, więc konstruowanie dowolnych ciągów będzie znacznie bardziej skomplikowane. Zauważ, eval^"że łatwiej byłoby sobie z tym poradzić, ale ma jeszcze jedną postać.

Naszym głównym narzędziem jest s<^><CODE>eeewaluacja CODE, a następnie ewaluacja wyników. Więcej emożna dodać, ze spodziewanego efektu.

Otrzymujemy łańcuchy <>, które są operatorem globalnym, chyba że tak nie jest. Pierwszym znakiem nie może być <(inaczej wygląda jak <<operator), nawiasy kątowe muszą być wyważone i musi istnieć co najmniej jeden znak nieliterowy (w przeciwnym razie jest interpretowany jako operator readline).

Łącząc te ciągi razem, możemy uzyskać dowolną kombinację znaków ^B^V^S(*-/9;<>HJMOY[`\^begqstv, o ile akceptujemy trochę śmieci (pierwsze trzy z nich to znaki kontrolne).

Załóżmy na przykład, że chcemy uzyskać "v99". Jednym ze sposobów, aby dostać v99to "><<" ^ "e>>" ^ "see" ^ "^^^", ale nie możemy reprezentować tych ciągów z powodu ograniczeń <>. Zamiast tego używamy:

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

Powyższe daje wynik Y9;v99;, który po ewaluacji daje taki sam wynik jak zwykły v99(mianowicie znak o kodzie ASCII 99).

W ten sposób możemy użyć całego ^B^V^S(*-/9;<>HJMOY[`\^begqstvzestawu znaków do wygenerowania naszego dowolnego ciągu, a następnie przekonwertować go jak powyżej i włożyć go w s<><CODE>eeeecelu wykonania. Niestety ten zestaw znaków jest nadal bardzo ograniczony, bez żadnego oczywistego sposobu przeprowadzenia konkatenacji.

Ale na szczęście zawiera gwiazdę. To pozwala nam pisać *b, który ocenia na ciąg "*main::b". Następnie *b^<^B[MMH^V^SY>(^ B ^ ^ V i S są literalne znaki kontrolne) daje nam (6, $&);, które po eval-ed ponownie zwraca wartość zmiennej meczu Perl, $&. To pozwala nam użyć ograniczonej formy konkatenacji: możemy wielokrotnie dodawać rzeczy do $_użycia s<^><THINGS>e, a następnie używać s<\H*><*b^<^B[MMH^V^SY>>eeedo ewaluacji $_( \Hdopasowuje wszystko oprócz poziomych białych znaków; używamy go zamiast kropki, która nie jest w naszym zestawie znaków).

Za pomocą 9-/możemy łatwo wygenerować wszystkie cyfry. Za pomocą cyfr vi konkatenacji możemy generować dowolne znaki (vXXX zwraca znak o kodzie ASCII XXX). Możemy je połączyć, aby wygenerować dowolne ciągi. Wygląda więc na to, że możemy zrobić wszystko.

Napiszmy pełny przykład. Załóżmy, że chcemy programu, który drukuje swój własny PID. Zaczynamy od naturalnego programu:

say$$

Konwertujemy go na notację v:

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

Przepisujemy to tylko przy użyciu ^B^V^S(*-/9;<>HJMOY[`\^begqstv(białe znaki służą wyłącznie do odczytu i nie wpływają na wynik):

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;

Na koniec konwertujemy powyższy program tylko na <>^es: pastebin . Niestety, powoduje to awarię Perla Excessively long <> operator, ale jest to tylko ograniczenie techniczne i nie powinno być brane pod uwagę.

Uff, to była całkiem podróż. Byłoby naprawdę interesujące, gdyby ktoś wymyślił zestaw 5 znaków, który upraszcza sprawę.

EDYCJA: stosując nieco inne podejście, możemy uniknąć przekroczenia limitu długości <>. W pełni funkcjonalny interpreter pieprzenia mózgu za pomocą <>^es: Wypróbuj online! . Zautomatyzowany Perl do <>^estranspilera: pastebin .

Python 2, 7 znaków

exc="%\n

Dowolny program w języku Python 2 może być kodowany przy użyciu tych 7 znaków ( \njest znakiem nowej linii).

Konstruowanie dowolnych ciągów znaków

Możemy wykonać konkatenację poprzez wielokrotne stosowanie operatora podstawienia %na jednym łańcuchu. Na przykład, jeśli a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cdadzą nam ciąg "123". Na szczęście litery te execdają nam dostęp %xi %cktóre są w zasadzie hex()i chr(). Za pomocą %cmożemy skonstruować dowolny ciąg, o ile mamy niezbędne liczby reprezentujące znaki. Następnie możemy wykonać ten ciąg jako kod Pythona za pomocą execsłowa kluczowego.

Twórz liczby

Możemy uzyskać dostęp do nietoperza 0i 1od razu dzięki porównaniom ( ==). Dzięki kombinacji cyfr łączących i modulo możliwe jest skonstruowanie liczby 43reprezentującej +w ASCII. To pozwala nam konstruować liczby potrzebne do naszego kodu.

Składając to razem

W tym objaśnieniu pominąłem kilka szczegółów, ponieważ nie są one niezbędne do zrozumienia, w jaki sposób można pisać programy z tymi ograniczeniami. Poniżej znajduje się napisany przeze mnie program w języku Python 2, który konwertuje dowolny program w języku Python na funkcjonalnie równoważną wersję, która używa tylko tych 7 znaków. Zastosowane techniki zostały zainspirowane tym oświadczeniem o anarchii golfa autorstwa K. Niektóre proste sztuczki służą również do utrzymania wielkości generowanych programów w rozsądnych granicach.

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

Wypróbuj online

Mathematica, 5 4 znaków

I[]

jest prywatnym znakiem Unicode , który działa jako operator, Functionktóry pozwala pisać literały dla nienazwanych funkcji z nazwanymi argumentami. Postać wygląda bardzo podobnie ↦do Mathematiki, więc wykorzystam ją do końca tej odpowiedzi dla jasności.

Korzystanie z nich, możemy wdrożyć S, Ki Ikombinatorów z rachunek kombinatorów:

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

Jednym z nich jest problem składniowy, który ↦ma bardzo niski priorytet, co będzie problemem, jeśli spróbujemy przekazać argumenty do tych kombinacji. Zwykle naprawiłbyś to, zawijając kombinator Cw nawiasach takich jak (C), ale nie mamy nawiasów. Możemy jednak użyć Ii []zawinąć Cw inną magię, która ma wystarczająco wysoki priorytet, abyśmy mogli z niej później skorzystać:

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

Wreszcie, aby napisać aplikację A x y z(gdzie Ajest syntezatora „parenthesised”, jak przedstawiono powyżej, i x, y, zmoże lub nie może być parenthesised lub mogą być większe wyrażeń), możemy napisać:

A[x][y][z]

To pozostawia pytanie, jak faktycznie działa odpowiednik w nawiasie. Spróbuję to z grubsza wyjaśnić w kolejności, w jakiej to wymyśliłem.

Zatem rzeczą, którą mamy składniowo, aby pogrupować coś, są nawiasy []. Nawiasy pojawiają się na dwa sposoby w Mathematica. Albo jako wywołanie funkcji f[x], albo jako operator indeksowania f[[i]](który tak naprawdę jest po prostu skrótem Part[f, i]). W szczególności oznacza to, że ani żadna, [C]ani [[C]]poprawna składnia. Potrzebujemy czegoś przed tym. To teoretycznie może być cokolwiek. Jeśli skorzystamy z tego, Ico już mamy, możemy I[C]na przykład uzyskać . Pozostaje to bezcenne, ponieważ Inie jest funkcją jednoargumentową (wcale nie jest funkcją).

Ale teraz potrzebujemy jakiegoś sposobu, aby wyodrębnić Cponownie, ponieważ w przeciwnym razie nie zostanie to faktycznie ocenione, gdy spróbujemy przekazać mu argument x.

Jest to przydatne, gdy f[[i]]można je wykorzystać do wyrażeń dowolnych f, a nie tylko list. Zakładając, że fsama ma formę head[val1,...,valn], a następnie f[[0]]daje head, f[[1]]daje val1, f[[-1]]daje valni tak dalej. Więc musimy albo 1czy -1aby wyodrębnić Cponownie, bo albo I[C][[1]]czy I[C][[-1]]ma wartość C.

Mamy mogą uzyskać 1z dowolnego nieokreślonej symbolu podobnego x, ale żeby to zrobić, musielibyśmy kolejny znak dla podziału ( x/xdaje 1za niezdefiniowany x). Mnożenie jest jedyną operacją arytmetyczną, którą możemy wykonać bez żadnych dodatkowych znaków (w zasadzie), więc potrzebujemy pewnej wartości, którą można pomnożyć, aby dać -1lub 1. To ostatecznie powoduje, że specjalnie wybrałem Inasze identyfikatory. Ponieważ Isam w sobie jest wbudowanym symbolem Mathematica dla wyimaginowanej jednostki.

Ale to pozostawia jeszcze jeden końcowy problem: jak właściwie się pomnażamy I? Nie możemy po prostu pisać, IIponieważ jest to analizowane jako pojedynczy symbol. Musimy oddzielić te tokeny bez a) zmiany ich wartości ib) za pomocą nowych znaków.

Ostatni kawałek magii to fragment nieudokumentowanego zachowania: f[[]](lub równoważnie Part[f]) jest poprawną składnią i zwraca fsię. Zamiast pomnożyć Iprzez I, pomnożymy I[[]]przez I. Wstawienie nawiasów powoduje, że Mathematica szuka nowego tokena i I[[]]Iocenia -1według potrzeb. I tak właśnie się kończy I[C][[I[[]]I]].

Pamiętaj, że nie mogliśmy użyć I[]. Jest to bezcelowe wywoływanie funkcji I, ale jak powiedziałem wcześniej, Inie jest funkcją, więc pozostanie bez oceny.

Python 2, 8 znaków

exc'%~-0

Te znaki umożliwiają tłumaczenie / wykonanie dowolnego programu w języku Python przy użyciu ciągów formatujących i exec. Chociaż możliwość przetłumaczenia dowolnego programu nie jest wymagana do kompletności Turinga, jest to najmniej znam znaków, które znam TC. To, że jest tak potężny, to tylko bonus.

Można również użyć podwójnego cudzysłowu, a także dowolnej pojedynczej cyfry oprócz zera. (Teraz, kiedy o tym myślę, 1na pewno byłoby lepiej, co skutkuje krótszymi programów, ponieważ można użyć 1, 11i 111, jak dobrze).

Oto program print:

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

Wypróbuj online

Program podstawowy wymaga

exec''

Każda postać xdodana do programu wymaga (znak - liczba):

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

Wyjątkiem jest to, że można zastosować pewne optymalizacje / skróty w celu skrócenia kodowanego programu, na przykład użycie %'0'znaku 0zamiast 48 -~itd.

Praktyczne zastosowania (AKA golf): Użyłem tej taktyki, aby rozwiązać to wyzwanie bez użycia dodatkowej postaci HCP.

Kredyt za listę znaków i program kodujący: tutaj

Aby uzyskać informacje na temat znajdowania dolnej granicy wynikowego rozmiaru programu (bez optymalizacji), zobacz ten komentarz .

Liczba wymaganych bajtów rośnie O(2**n), więc ta metoda nie jest zalecana do gry w golfa. Quine korzystająca z tego ograniczenia źródła byłaby niesamowicie długa.

C (nieprzenośne), 24 18 13 znaków

aimn[]={};,1+

Obejmuje to wszystkie programy formularza

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

... gdzie ciąg stałych (w postaci 1 + 1 + 1 ...) zawiera reprezentację kodu maszynowego twojego programu. Zakłada się, że twoje środowisko pozwala na wykonanie wszystkich segmentów pamięci (najwyraźniej prawda dla tcc [dzięki @Dennis!] I niektórych maszyn bez bitu NX). W przeciwnym razie w systemie Linux i OSX może być konieczne dodanie słowa kluczowegoconst a w systemie Windows może być konieczne #pragmawyraźne zaznaczenie segmentu jako pliku wykonywalnego.

Na przykład drukowany jest następujący program napisany w powyższym stylu Hello, World! w systemie Linux i OSX na platformach x86 i 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};

Wypróbuj online!

Siatkówka , 6 znaków

$%`{¶

Jak również linie (0x0A).

Z jednej strony jestem zaskoczony, że udało mi się to osiągnąć tak nisko. Z drugiej strony jestem bardzo niezadowolony z włączenia %¶. Każdy z nich $`{jest ponownie wykorzystywany do dwóch lub nawet trzech celów, ale %¶ razem służą tylko jednemu celowi. To sprawia, że ​​wydają się raczej marnotrawstwem i nieco niszczy elegancję podejścia. Mam nadzieję, że istnieje sposób na pokonanie tej konstrukcji.

Do dowodu. Opiszę prosty sposób na przetłumaczenie cyklicznych systemów znaczników na Retinę przy użyciu powyższych znaków.

Po pierwsze, będziemy używać `i {dla binarnego alfabetu zamiast 0i 1. Są to wygodne, ponieważ nie trzeba ich uciekać w wyrażeniu regularnym, ale mają one znaczenie zarówno dla siatkówki, jak i składni podstawienia. Używam `dla 0i {dla1 , ale ten wybór jest dowolny. Ponadto zamierzamy odwrócić łańcuch (i produkcje) w pamięci, ponieważ praca z ostatnim znakiem pozwala nam używać $i $`zamiast ^i$' , maksymalizacja ponownego wykorzystania znaków.

Jeśli początkowe słowo jest oznaczone przez Sii wywoływana jest produkcja th (odwrócona) , wynikowy program będzie wyglądał następująco:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Taka konstrukcja nieuchronnie rośnie w pamięci za każdym razem, gdy stosowana jest produkcja, i jest mało prawdopodobne, aby się zakończyła - w rzeczywistości w miejscu, w którym cykliczny system znaczników zakończyłby się (gdy łańcuch roboczy staje się pusty), zachowanie wynikowego programu Retina staje się w zasadzie niezdefiniowany.

Spójrzmy na to, co robi program:

S

Zaczynamy od zainicjowania ciągu roboczego na początkowe słowo.

{`

To zawija pozostałą część programu w działający, dopóki nie uda się zmienić wynikowego łańcucha (hej, naiwne wbudowane wykrywanie nieskończonej pętli za darmo ...). Dwa kanały nie są tak naprawdę konieczne, ale oddzielają pętlę wyraźniej od poszczególnych produkcji. Reszta programu przechodzi przez każdą z produkcji, a dzięki pętli efektywnie przetwarzamy je cyklicznie w kółko.

Każda produkcja odbywa się w dwóch etapach. Najpierw zajmiemy się przypadkiem, że wiodącym (lub w naszym przypadku końcowym) jest symbol {, w którym to przypadku używamy produkcji:

{$
¶pi$%``

Wyrażenie regularne pasuje tylko wtedy, gdy łańcuch się kończy {. W takim przypadku zastępujemy go:

• A linefeed (¶ ). Zawsze będziemy pracować tylko z ostatnią linią łańcucha roboczego, więc to skutecznie odrzuca łańcuch roboczy do tej pory (dlatego użycie pamięci programu będzie rosło i rosło).
• Obecna produkcja (pi ), którą niniejszym przygotowujemy do łańcucha roboczego (gdzie dołącza go cykliczny system znaczników).
• Poprzedni pozostały ciąg roboczy ( $%`). Dlatego musimy wstawić ¶: $%`zbiera wszystko, co pozostało z meczu, ale tylko w tej samej linii. W związku z tym nie widać wszystkich śmieci, które pozostawiliśmy po wcześniejszych produkcjach. Ta sztuczka pozwala nam dopasować coś na końcu łańcucha roboczego, aby wstawić coś na początku łańcucha roboczego, bez konieczności używania czegoś takiego jak (.+)i$1 co znacznie zwiększyłoby liczbę potrzebnych znaków.
• Pojedynczy backtick ( `). To skutecznie zastępuje {( 1-symbol), który dopasowaliśmy `( 0-symbol), dzięki czemu następny etap nie musi wiedzieć, czy już przetworzyliśmy bieżącą produkcję, czy nie.

Druga część każdej produkcji to trywialny przypadek, w którym produkcja jest pomijana:

``$

Po prostu usuwamy końcowe `. Powodem, dla którego potrzebujemy dwóch `w pierwszym wierszu, jest to, że Retina uważa, że ​​pierwszy backtick jest dzielnikiem między konfiguracją a wyrażeniem regularnym. To po prostu daje mu pustą konfigurację, dzięki czemu możemy używać backicks w samym wyrażeniu regularnym.

Java 7, 18 17 znaków

\bcdefu0123456789

Cały kod źródłowy Java można zredukować do punktów kodu Unicode. „a” nie jest potrzebne, ponieważ jest używane tylko do*:jJzZ . Gwiazdka służy do mnożenia lub blokowania komentarzy. Mnożenie jest tylko powtarzanym dodawaniem i zamiast tego możesz używać komentarzy jednowierszowych (lub po prostu je pominąć). Dwukropek jest używany dla operatorów trójskładnikowych, dla których można zamiast tego użyć instrukcji if i pętli foreach, które można zastąpić normal dla pętli. j i z nie są częścią żadnych słów kluczowych w Javie.

Próba usunięcia dowolnego innego znaku wymaga od nas dodania co najmniej jednego z znaków wymaganych w płycie kotła Java class a{public static void main(String[]a){}}. Patrz poniżej:

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

Oto przykład z programem Hello World Wypróbuj online!

Java 8, 16 znaków

\bdefu0123456789

Dzięki ais523 za zwrócenie na to uwagi. Java 8 pozwala interfejsom na stosowanie metod statycznych, co oznacza, że ​​możemy upuścić „c”, ponieważ nie potrzebujemy go dla „l” w „klasie”. Używa się „c”, ,<lL\|więc tracimy nieco więcej funkcji java niż wtedy, gdy usunęliśmy „a”, ale wciąż mamy dość, aby być w pełni ukończonym. Wypróbuj online!

Labirynt , 5 znaków

~{}

Plus wysuw linii (0x0A) i spacje (0x20).

Naszkicuję dowód w postaci redukcji z Smallfuck (zredukowany wariant Brainfuck, który wykorzystuje komórki 1-bitowe). Zauważ, że sam Smallfuck nie jest kompletny z Turinga, ponieważ język określa, że ​​jego taśma musi być skończona, ale założymy wariant Smallfuck z nieskończoną taśmą, który byłby wtedy kompletny z Turinga (ponieważ Labirynt nie ma pamięci ograniczenia według projektu).

Ważnym niezmiennikiem podczas tej redukcji będzie to, że każdy program (lub podprogram) da program Labirynt (lub podprogram), który rozpoczyna się i kończy w tym samym rzędzie i obejmuje parzystą liczbę kolumn.

Labirynt ma dwa stosy, które początkowo są wypełnione nieskończoną (domyślną) ilością 0s. {i }przesunąć najwyższą wartość między tymi stosami. Jeśli uważamy górę głównego stosu za obecną „komórkę”, wówczas te dwa stosy można postrzegać jako dwie pół-nieskończone połowy nieskończonej taśmy używanej przez Smallfuck. Jednak wygodniej będzie mieć dwie kopie każdej wartości taśmy na stosach, aby zapewnić wspomniany powyżej niezmiennik. Dlatego <i >zostaną przetłumaczone odpowiednio na {{i }}(możesz je zamienić, jeśli chcesz).

Zamiast pozwolić wartości komórek 0i 1używamy 0i -1, co możemy przełączać się pomiędzy z ~(logiczną negację). Dokładne wartości nie mają znaczenia dla celów kompletności Turinga. Musimy zmienić obie kopie wartości na stosie, co daje nam ponownie tłumaczenie równej długości: *staje się ~}~{.

To pozostawia polecenia przepływu sterowania []. Labirynt nie ma jawnego przepływu sterowania, ale zamiast tego przepływ sterowania zależy od układu kodu. Do wykonania tego układu potrzebujemy spacji i linii.

Po pierwsze, zwróć uwagę, że ~~nie ma opcji, ponieważ oba ~skutecznie anulują. Możemy użyć tego, aby mieć dowolnie długie ścieżki w kodzie, o ile ich długość jest równa. Możemy teraz użyć następującej konstrukcji do przetłumaczenia AA[BB]CCna Labirynt (używam podwójnych liter, aby rozmiar każdego fragmentu w Labiryncie był równy, co gwarantuje niezmiennik):

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

Tutaj ..jest odpowiednia liczba, ~która odpowiada szerokości BB.

Ponownie zauważ, że szerokość konstrukcji pozostaje równa.

Możemy teraz przejść przez działanie tej pętli. Kod jest wprowadzany za pomocą AA. Pierwszy ~~nic nie robi i pozwala nam dotrzeć do skrzyżowania. Odpowiada to mniej więcej [:

• Jeśli bieżąca wartość komórki wynosi zero, adres IP jest kontynuowany prosto, co ostatecznie zostanie pominięte BB. Ta ..część wciąż nie daje op. Następnie dochodzimy do jednego ~na innym skrzyżowaniu. Wiemy teraz , że bieżąca wartość jest niezerowa, więc IP skręca na północ. Objeżdża zakręt u góry, aż po szóstym dotrze do innego skrzyżowania ~. Więc w tym momencie bieżąca wartość jest wciąż niezerowa, a IP ponownie skręca, aby przejść na wschód w kierunku CC. Zauważ, że trzy ~przed CCzwróceniem bieżącej wartości do 0, tak jak powinno być, gdy pętla została pominięta.
• Jeśli bieżąca wartość komórki na początku pętli jest różna od zera, adres IP skręca na południe. Działa jeszcze sześć ~przed dotarciem BB(które nic nie robią), a następnie kolejne sześć ~przed dotarciem do następnego skrzyżowania. To z grubsza odpowiada ].
  • Jeśli bieżąca komórka wynosi zero, adres IP przesuwa się na północ. Następny ~powoduje, że wartość jest niezerowa, tak więc IP bierze to drugie połączenie, które łączy ścieżkę z przypadkiem, że pętla została całkowicie pominięta. Ponownie trójka ~zwraca wartość do zera przed osiągnięciem CC.
  • Jeśli bieżąca komórka jest niezerowa, adres IP skręca na zachód. Są ~przed następnym skrzyżowaniem, co oznacza, że ​​w tym momencie bieżąca wartość wynosi zero, więc IP kontynuuje podróż na zachód. Wtedy będzie nieparzysta liczba, ~zanim IP ponownie osiągnie początkowe złącze, tak że wartość jest zwracana, -1a IP przesuwa się na południe do następnej iteracji.

Jeśli program zawiera jakieś pętle, najpierw AAnależy rozszerzyć program na początek programu, aby adres IP znalazł prawidłową komórkę do uruchomienia:

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

To tyle. Należy pamiętać, że programy wynikające z tej redukcji nigdy się nie zakończą, ale nie jest to częścią wymagań kompletności Turinga (rozważ Regułę 101 lub Fractran).

Na koniec pozostaje nam pytanie, czy jest to optymalne. Jeśli chodzi o znaki obciążenia, wątpię, aby można było wykonać więcej niż trzy polecenia. Widziałem alternatywną konstrukcję opartą na maszynach Minsky'ego z dwoma rejestrami, ale wymagałoby to =()lub =-~, mając tylko jedno polecenie manipulacji stosem, ale potem dwa polecenia arytmetyczne. Byłbym szczęśliwy, gdyby udowodniono, że się mylę. :)

Jeśli chodzi o polecenia dotyczące układu, uważam, że przejścia między wierszami są konieczne, ponieważ użyteczny przepływ sterowania jest niemożliwy w jednym wierszu. Jednak spacje nie są technicznie konieczne. Teoretycznie możliwe jest opracowanie konstrukcji, która wypełnia całą siatkę ~{}(lub =()lub =-~), lub wykorzystuje nierówny układ, w którym linie nie są tej samej długości. Jednak pisanie takiego kodu jest niezwykle trudne, ponieważ Labyrinth będzie wtedy traktował każdą komórkę jako połączenie i musisz bardzo uważać, aby nie rozgałęzić kodu, gdy nie chcesz. Jeśli ktokolwiek może udowodnić lub obalić, czy pominięcie miejsca jest możliwe dla kompletności Turinga, z przyjemnością dam za to znaczną nagrodę. :)

Haskell, 5 7 znaków

()\->=;

Jako język funkcjonalny Haskell ma oczywiście lambdy, więc symulowanie rachunku lambda jest łatwe. Składnia lambdas jest następująca(\variable->body)argument taka, że ​​potrzebujemy przynajmniej znaków ()\->.
Ponadto potrzebujemy nieograniczonej liczby zmiennych symboli, aby móc budować dowolne wyrażenia lambda. Na szczęście nie trzeba żadnych nowych znaków dla tego, ponieważ (>), (>>), (>>>), ..., są wszystkie ważne nazwy zmiennych. W rzeczywistości każda kombinacja \->nawiasów wewnętrznych jest prawidłową nazwą zmiennej, z wyjątkiem just \i ->, które są zarezerwowane dla wyrażeń lambda, i --które rozpoczynają komentarz liniowy.

Przykłady:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))typy do(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))typy dot -> t1 -> t
• I = (\(>)->(>))typy dot -> t

Edycja: Jednakże, jak wskazał ais523 w komentarzach, ta konstrukcja implementuje typowany rachunek lambda , który sam w sobie nie jest ukończony przez Turinga, ponieważ nie ma możliwości wchodzenia w nieskończone pętle. Aby to naprawić, potrzebujemy funkcji wykonującej rekurencję. Do tej pory używaliśmy nienazwanych lambdas, które nie mogą się nazywać, ponieważ, no cóż, nie mają imienia. Musimy więc dodać znaki =i ;zaimplementować fixfunkcję:

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

Dzięki tej deklaracji nasz rachunek lambda staje się kompletny Turinga, jednak po dodaniu =i ;nie potrzebujemy już lambda, jak widać w odpowiedzi nich, która używa tylko()=; .

CJam, 3 znaki

Usunięto )zgodnie z sugestią Martina Endera

'(~

Podobny do Pythona podany jako przykład.

Za pomocą '~możesz uzyskać ~postać. Następnie za pomocą (możesz go zmniejszyć, aby uzyskać dowolny znak, jaki chcesz ( ~jest ostatnim drukowanym znakiem ASCII). ~sprawdza dowolny ciąg znaków jako normalny kod CJam. Ciągi znaków można konstruować, uzyskując postać [(poprzez dekrementację ~), ewaluując ją, umieszczając sekwencję innych znaków, a następnie ewaluując postać ]. Dzięki temu możesz zbudować i uruchomić dowolny program CJam, używając tylko tych trzech znaków.

Obliczanie 2 + 2 tylko za pomocą '(~

Brain-Flak , 6 znaków

(){}[]

Brain-Flak to minimalistyczny język z zaledwie 8 dostępnymi postaciami. Można jednak udowodnić, że istnieje podzbiór Mózgu, który również jest kompletny w Turinga, używając tylko 6 znaków.

Najpierw zaimplementujemy Maszynę Minsky'ego z tylko jednym stosem Brain-Flak. Jeśli uda nam się udowodnić, że maszyna Minsky jest możliwa tylko z jednym stosem, możemy pokazać, że Brain-Flak Turing jest kompletny bez<>[] Turingu i niladów. Nie uratuje to żadnych postaci natychmiast, ale będzie w przyszłości, gdy pokażemy, że <...>nie jest to konieczne.

Maszyna Minsky'ego jest rodzajem kompletnego automatu Turinga, który ma skończoną liczbę niezwiązanych rejestrów i dwie instrukcje:

• Zwiększ rejestr

• Jeśli zmniejszenie niezerowe w inny sposób przejdzie do określonej instrukcji

Aby skonfigurować strukturę goto w Brain-Flak, możemy użyć następującego fragmentu:

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

Spowoduje to zmniejszenie licznika i będzie działać, %sjeśli zero. Kilka tych połączonych razem pozwoli nam umieścić liczbę na stosie, która wskaże, którą linię chcemy dostać. Każdy z nich zmniejszy górną część stosu, ale tylko jeden z nich faktycznie uruchomi kod.

Używamy tego jako opakowania dla wszystkich naszych instrukcji Minsky Machine.

Zwiększanie określonego rejestru jest dość łatwe bez zmiany stosu. Można to osiągnąć za pomocą tej formuły ciągów:

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

Na przykład, aby zwiększyć trzeci rejestr, napisalibyśmy następujący kod:

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

Teraz musimy tylko wdrożyć drugą operację. Sprawdzanie, czy liczba wynosi zero, jest dość proste w Brain-Flak:

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

wykona się tylko %s wtedy, gdy TOS wynosi zero. W ten sposób możemy wykonać naszą drugą operację.

Ponieważ maszyny Minsky są Turinga kompletne, Brain-Flak jest również Turinga kompletne bez użycia <>i[] .

Jednak nie zmniejszyliśmy jeszcze liczby znaków, ponieważ <...>i [...]nadal są w użyciu. Można temu zaradzić przez proste zastąpienie. Ponieważ <...>tak naprawdę jest równoważne [(...)]{}we wszystkich przypadkach. Tak więc Brain-Flak jest w Turingu kompletny bez użycia znaków <i >(oraz wszystkich zakazów).

> <> , 3 znaki

> <> jest wykonalne w 3 z 1p-, które:

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

pzapewnia odbicie, modyfikując kod źródłowy 2D poprzez umieszczenie znaków w codcode. Za pomocą 1-możesz przesunąć dowolną liczbę na stos, ponieważ 1-odejmuje jeden i 111-1--(x-(1-1-1) = x+1 ) dodaje jeden.

Po wykonaniu wszystkich 1p-poleceń wskaźnik instrukcji otacza się, umożliwiając wykonanie „prawdziwego” kodu.

Przykładowy program, który oblicza liczby Fibonacciego (na podstawie tej odpowiedzi ) to:

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

Wypróbuj online! Po wykonaniu wszystkich 1p-poleceń, codbox wygląda następująco:

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

Pomijając wszystko po vpierwszym wierszu, jest to standardowy program Fibonacciego> <>.

uderzenie, 9 znaków

01456\$ '

Bash ma składnię $'\nnn'do wprowadzania znaków z ich ósemkowymi wartościami ascii. Możemy wprowadzić evalpolecenie w tym formacie jako $'\145\166\141\154'. Najpierw zamieniamy pożądany wynik na wartości ósemkowe. Następnie przekształcamy dowolne wartości ósemkowe za pomocą cyfr innych niż 0, 1, 4, 5 i 6 na wyrażenia przetwarzające się na wspomniane wartości ósemkowe za pomocą $(())i odejmując, dodając evaldo przodu. W naszym ostatnim kroku dodajemy kolejny evali przekształcamy nawiasy i znak minus na ich wartości ósemkowe. Za pomocą tej metody możemy wykonać dowolne polecenie bash, więc ten podzbiór jest w pełni ukończony.

Przykład:

dc staje się

$'\144\143' który staje się

$'\145\166\141\154' \$\'\\144\\$((144-1))\' który staje się

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

Incydent , 2 znaki

Nie ma znaczenia, które dwie postaci wybierzesz; dowolna kombinacja dwóch oktetów jest incydentem Turinga.

W rzeczywistości udowodnienie tego jest znacznie trudniejsze, niż można się spodziewać, a w chwili pisania tego tekstu strona dyskusji w Esolang poświęcona incydentowi poświęcona jest temu problemowi. Spróbuję jednak przedstawić streszczenie najprostszego znanego dowodu poniżej.

Przed dowodem trochę tła. Incydent wnioskuje do tokenów używanych w programie, patrząc na źródło (token jest łańcuchem, który pojawia się dokładnie trzy razy w źródle, nie jest podciągiem innego tokena i nie pokrywa się z innym potencjalnym tokenem). W związku z tym każdy program można przekonwertować tak, aby używał praktycznie dowolnego zestawu znaków, zmieniając tokeny; język jest kompletny Turinga (i ma również kompletność we / wy!), mimo że jest niezwykle trudny do zaprogramowania, więc „wszystko”, czego potrzebujesz, to metoda kodowania tokenów, aby działały tylko z dwoma znakami.

A oto podsumowanie dowodu (znalezionego przez Ørjana, matematyka-rezydenta Esolanga). Chodzi o to, że kodujemy token za pomocą dwóch kopii jednego znaku (powiedzmy 1) na dużym morzu drugiego znaku (powiedzmy 0). Odległość między 1s różni się dla każdego tokena, ale zawsze jest wielokrotnością 4. Następnie do wypełnienia między tokenami używamy dodatkowej listy 0s ze 1środkową, ale liczba 0 po każdej stronie 1jest nie wielokrotność 4, ale raczej liczba unikalna dla tej konkretnej częstotliwości występowania programu, która nie pojawia się w innym miejscu programu. Oznacza to, że każdy 1…1wewnątrz wypełnienia może pojawić się tylko dwa razy, więc nie będzie częścią tokena; każdy zamierzony token zawiera dokładnie dwa 1, a żaden fałszywy token nie może zawierać więcej niż jednego 1. Następnie po prostu dodajemy dopełnienie z boku, aby usunąć wszystkie możliwe tokeny zawierające jeden 1lub zero 1, dodając co najmniej cztery ich kopie.

Siatkówka , 3 znaki

{`

i nowa linia.

Po pierwsze, potrzebujemy nowego wiersza, aby móc dokonywać podstawień (konieczne, chyba że chcemy dopasować cały program do jednego wyrażenia regularnego, które wymagałoby więcej znaków); i `i {są najmniej charakter intensywnie sposób zrobić pętle. Okazuje się, że nie potrzebujemy nic więcej.

Nasz język docelowy do wdrożenia jest deterministycznym wariantem Thue (niedeterminizm nie jest konieczny dla kompletności Turinga; możliwe jest napisanie programu Thue działającego poprawnie, niezależnie od tego, która kolejność oceny jest używana). Podstawowym założeniem jest opracowanie pattern::=replacementw

`pattern
replacement

(który jest bezpośrednim tłumaczeniem Thue na Retinę; alternatywnie, jeśli znasz Retinę, ale nie Thue, możesz użyć jej jako metody uczenia się, jak działa Thue); jako wyjątek {`zamiast tego poprzedza się pierwszy wzorzec (w celu umieszczenia całego programu w pętli; programy Thue kontynuują działanie do momentu, gdy nie będzie już możliwe zastąpienie, co powoduje, że siatkówka działa w ten sam sposób).

Oczywiście oznacza to, że musimy udowodnić Thue Turing-complete z tylko {i `we wzorcach i wymiany, ale to jest dość proste; możemy zastąpić znak w kodzie ASCII n z `, n + 1 {, a drugi` . Wyraźnie niemożliwe jest dopasowanie wzorca w dowolnym miejscu poza granicami znaków, więc skończy się to tym samym, co oryginalny program.

Brachylog , 5 znaków

~×₁↰|

Ten podzbiór znaków pozwala nam zaimplementować wersję Fractran, w której jedyne liczby, które mogą się pojawiać, są iloczynami powtórzeń (tj. Iloczynami liczb, które można zapisać dziesiętnie za pomocą tylko cyfry 1). ~×(z liczbą całkowitą jako indeksem dolnym) dzieli bieżącą wartość przez tę liczbę całkowitą, ale tylko wtedy, gdy dokładnie ją dzieli (w przeciwnym razie „zawiedzie” i szuka innej sprawy do uruchomienia; |rozdziela przypadki). ×pozwala nam pomnożyć przez liczbę całkowitą. Tak więc za pomocą ~×₁|możemy zaimplementować jeden krok wykonania Fractran. Następnie ↰pozwól nam się powtórzyć, ponownie uruchamiając cały program z nową bieżącą wartością. Oto przykład bardzo prostego programu Fractran ( 11111111111111111111111/111) przetłumaczonego na Brachylog.

Czy to już koniec Turinga? Wszystko, czego potrzebujemy, aby Fractran Turing był kompletny, to wystarczająco duża liczba liczb pierwszych (wystarczająca do napisania tłumacza dla kompletnego języka Turinga w samym Fractran). Jest pięciu sprawdzonych i czterech podejrzanychodmień liczby pierwsze, oprócz tych, które jeszcze nie zostały odkryte. To w rzeczywistości więcej niż potrzebujemy w tym przypadku. Program sprawdza możliwości od lewej do prawej, dzięki czemu możemy użyć jednej liczby pierwszej jako wskaźnika instrukcji, a dwóch więcej jako liczników, wykazując kompletność Turinga tylko z trzema liczbami pierwszymi (to też dobrze, ponieważ pozwala nam użyć powtórzeń z 2, 19 i 23 cyfry, bez konieczności uciekania się do sprawdzonych, ale irytująco dużych repunits z 317 lub 1031 cyframi, co utrudniłoby pisanie kodu źródłowego). Umożliwia to wdrożenie maszyny Minsky'ego z dwoma licznikami (wystarczającymi do kompletności Turinga).

Oto jak działa kompilacja. Użyjemy następujących dwóch poleceń do naszej implementacji maszyny Minsky (jest to znane jako ukończenie Turinga), a każde polecenie będzie miało liczbę całkowitą jako etykietę:

• Etykieta L: Jeśli licznik {A lub B} jest równy zero, należy użyć X. W przeciwnym razie zmniejsz go i uzyskaj Y.
• Etykieta L: Licznik przyrostów {A lub B}, a następnie goto Z.

Wybieramy, które polecenie uruchomić, umieszczając moc 11 w mianowniku, najpierw najwyższe moce; wykładnik liczby 11 to etykieta polecenia. W ten sposób pierwszą pasującą frakcją będzie aktualnie wykonywane polecenie (ponieważ poprzednich nie można podzielić przez wszystkie te 11). W przypadku polecenia zmniejszania umieszczamy również w mianowniku współczynnik 11111111111111111 lub 11111111111111111111111 odpowiednio dla licznika A lub B, a następnie wykonujemy kolejne polecenie bez tego czynnika; przypadek „dekrementacji” będzie realizowany przez pierwsze polecenie, przypadek „zerowy” przez drugie. Tymczasem „goto” będzie obsługiwane przez odpowiednią moc 11 w liczniku, a „przyrost” poprzez współczynnik 1111111111111111111 lub 11111111111111111111111 w liczniku.

Befunge-98, 3 znaki

O ile mi wiadomo, Befunge-98 ma być ukończony, więc musimy tylko pokazać, w jaki sposób można wygenerować dowolny program Befunge-98 przy użyciu tylko trzech znaków. Moje początkowe rozwiązanie opierało się na następujących czterech znakach:

01+p

Możemy uzyskać dowolną dodatnią liczbę całkowitą na stos, dodając wiele 1wartości razem z +poleceniem, a dla zera po prostu używamy 0. Gdy będziemy już w stanie przesuwać dowolną liczbę, możemy użyćp (put), aby zapisać dowolną wartość ASCII w dowolnym miejscu na polu gry Befunge.

Jednak, jak wskazał Sp3000 , w rzeczywistości możesz sobie poradzić tylko z trzema postaciami:

1-p

Dowolną liczbę ujemną można obliczyć, zaczynając od, 1a następnie wielokrotnie odejmując 1(na przykład byłoby -3 11-1-1-1-). Następnie dowolną liczbę dodatnią można przedstawić, odejmując 1-n od 1, gdzie 1-n jest liczbą ujemną, którą już wiemy, jak sobie radzić (na przykład 4 = 1 - (- 3), co byłoby111-1-1-1-- ).

Możemy zatem użyć naszych trzech znaków do napisania rodzaju programu ładującego, który powoli generuje rzeczywisty kod, który chcemy wykonać. Gdy ten moduł ładujący zakończy działanie, zawinie się do początku pierwszej linii pola gry, która powinna w tym momencie zatrzymać początek naszego nowo wygenerowanego kodu.

Jako przykład, oto bootloader, który generuje kod Befunge niezbędny do sumowania 2 + 2 i wyświetla wynik: 22+.@

A dla nieco bardziej skomplikowanego przykładu jest to „Hello World”: "!dlroW olleH"bk,@

Ruby, 8 znaków

eval"<1+

Zainspirowany odpowiedziami w języku Python

Jak to działa

• eval może być użyty do wykonania dowolnego ciągu.
• „<1+ to minimalny zestaw znaków wymagany do zbudowania dowolnego łańcucha

Łańcuch w rubinie można zbudować przy użyciu pustego łańcucha jako punktu początkowego i dodając do niego znaki ascii, na przykład:

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

jest faktycznie równoważne z

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

która ocenia ciąg

p"o"

OCaml, 9 znaków

fun->()`X

Te znaki są wystarczające do zaimplementowania SKI Combinator Calculus w OCaml. W szczególności jesteśmy w stanie uniknąć użycia przestrzeni z wystarczającą liczbą nawiasów. Niestety wyrażenia lambda w OCaml wymagają funsłowa kluczowego, więc bardziej zwięzłe rozwiązanie nie jest możliwe. Te same litery mogą być użyte do budowy dowolnych nazw zmiennych, jeśli jednak pożądane są bardziej złożone wyrażenia lambda.

Kombinator S:

fun(f)(u)(n)->f(n)(u(n)) z rodzajem ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

Kombinator K:

fun(f)(u)->u z rodzajem 'a -> 'b -> 'b

I Kombinator:

fun(f)->f z rodzajem 'a -> 'a

Jak zauważył ais523, nie wystarczy po prostu zakodować SKI. Oto kodowanie dla Z przy użyciu wariantów polimorficznych do manipulowania systemem typów. Dzięki temu mój podzbiór powinien być kompletny.

Kombinator Z:

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

z rodzajem (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Języki konkatenatywne oparte na stosie, 4 znaki

Niedociążenie

():^

GolfScript

{}.~

CJam

{}_~

GS2

• backspace, tab,, @space (wiedziałem, że GS2 często używało niedrukowalnych elementów, ale to jest śmieszne ...)

dc (sugerowane przez @seshoumara)

[]dx

Udowodniono, że niedociążenie jest kompletne tylko przy użyciu ():^ (dzięki rezydentowi Esolanga, matematykowi Ørjanowi). Dowód jest zbyt długi, aby go tu wyjaśnić, ale jeśli jesteś zainteresowany, możesz przeczytać o nim tutaj .

Polecenia, o których mowa, to ()(umieść literał kodu na stosie), :(zduplikuj górny element stosu) i ^(oceń górę stosu). Te polecenia są dość powszechne w językach opartych na stosie (szczególnie w językach konkatenatywnych), dlatego podałem coś z ich kolekcji powyżej; wszystkie te języki są pełne Turinga w 4 znakach z tego samego powodu, co niedociążenie.

Biała spacja, 3 znaki

STL

Sjest spacją, Tjest tabulatorem i Ljest znakiem nowej linii.

Rakieta (schemat), 4 znaki

(λ)

Używając tylko λ, nawiasów i spacji, możemy bezpośrednio programować w podzbiorze rachunku lambda według schematu. Używamy ponownie znaku λ dla wszystkich identyfikatorów, łącząc je ze sobą, aby zapewnić dowolnie dużą liczbę unikalnych identyfikatorów.

Jako przykład, oto klasyczny kombinator Omega, który zapętla się na zawsze.

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

Python 3, 9 znaków

exc('%1+)

Zobacz moją odpowiedź na Python 2Podstawowe wyjaśnienie znajduje się w w . Ta odpowiedź opiera się na tej.

Zamiast po prostu używać tych samych znaków co Python dwa z dodatkiem (), jesteśmy w stanie upuścić znak, ponieważ teraz używamy nawiasów. Programy nadal będą miały podstawowy kształt

exec('%c'%stuff)

ale skracamy długość programu, używając +zamiast -, a następnie możemy usunąć ~, używając 1zamiast 0. Następnie możemy dodać 1, 11i, 111aby uzyskać wymagane wartości ASCII.

Program print()w najkrótszym czasie wygląda następująco:

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)%'('%')')

Wypróbuj online

Być może zastanawiasz się, jak stworzyć bajt NUL bez którego 0? Nie obawiaj się, młody konik polny! ponieważ mamy również możliwość korzystania %z matematyki, tworząc zero za pomocą 1%1.

PHP 7, 6 znaków

'().;^

Chodzi o to, że możliwe jest wykonanie dowolnego kodu przy użyciu następującej konstrukcji:

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

eval nie działałby tutaj, ponieważ jest to konstrukcja języka i nie można go wywoływać za pomocą funkcji zmiennych.

create_function a kod może być napisany jako połączenie bitowych XOR dostępnych znaków:

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

Używając ().;^do <charX_Y>, możemy dostać

()./:;<=JKLMXY^_bcdepqvw

i niektóre niedrukowalne znaki. To nie wystarczy, ale teraz możemy również zadzwonić 'eXp'()i uzyskać kilka znaków numerycznych:

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

To daje nam 1, 2i 3(inne znaki są ignorowane przez XOR, jeśli drugi ciąg jest długa jeden znak). Z ().;^123możemy teraz wygenerować cały zestaw znaków ASCII.

Wypróbuj online

Pyke, 5 znaków

0h.CE

Jest to w stanie wygenerować nieskończenie dużą liczbę, przekształcając ją w ciąg znaków, a następnie oceniając jako kod Pyke.

Objaśnienie kodu:

0- Dodaj 0 do stosu. Jest to wymagane, aby rozpocząć numer

h- Zwiększ liczbę wcześniej. Powtarzając to dowolną liczbę razy, możesz tworzyć liczby, które są nieskończenie duże. Pyke obsługuje bignum, ponieważ jest napisane w Pythonie, który używa ich jako domyślnych.

.C- Zamień liczbę na ciąg znaków za pomocą następującego algorytmu: ( link Github )

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

W tym momencie możemy utworzyć dowolną liczbę ciągów i liczb naturalnych w Pyke z dowolnymi wartościami. Liczby można tworzyć w formie odpowiadającej wyrażeniu regularnemu, 0(h)*a ciągi znaków można tworzyć za pomocą 0(h)*.C. Można je ze sobą przeplatać, aby stworzyć dowolną mieszankę ciągów i liczb całkowitych.

E- ocenia ciąg jako kod Pyke. Korzysta z tego samego środowiska co już uruchomiony kod Pyke, więc będzie udostępniać takie rzeczy jak dane wejściowe.

Próbowano udowodnić, że Pyke jest w Turingu ukończony.

Jednym z najprostszych sposobów wykazania, że ​​język jest kompletny, jest zaimplementowanie w nim Brainf * ck. Jest to prawdopodobnie o wiele trudniejsze w Pyke niż w wielu innych językach, ponieważ jego lista i operacje słownikowe praktycznie nie istnieją ze względu na brak potrzeby ich w obszarze, w którym Pyke ma działać: golf-code .

Najpierw tworzymy interpreter dla brainf * ck i kodujemy go za pomocą naszego algorytmu powyżej, aby utworzyć liczbę, a następnie wyrażamy ją za pomocą 0i h. Następnie tworzymy ciąg zawierający kod, który ma być uruchamiany dokładnie w ten sam sposób. Gdybyśmy to zostawili, mielibyśmy stos jako

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

Oznacza to, że kod musi być w odwrotnej postaci, ponieważ stos Pyke jest pierwszy na końcu.

Teraz część zabawy: interpreter brainf * ck z ogromną liczbą 216 bajtów!

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\[email protected])~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

Wypróbuj tutaj!

Jeśli chcesz wypróbować kod w częściowo ukończonej, ale edytowalnej formie, wypróbuj go tutaj!

Aby przekonwertować ciąg na liczbę, możesz użyć następującego kodu w języku Python:

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

(Prawie) ostateczne rozwiązanie można wypróbować tutaj!

Wyjaśnienie interpretera Brainf * ck

Najpierw podzielmy program na części:

• Inicjalizacja:

W pobliżu

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

• Główna pętla:

W pobliżu

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.

• Instrukcje
  • Góra / dół:+-

W pobliżu

"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] = ^

• Dane wejściowe ,:

W pobliżu

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

• Wyjście .:

W pobliżu

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

• Shift Left / Right <>::

W pobliżu

~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

• Warunki [:

W pobliżu

~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

- I ]:

W pobliżu

~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

Ułożone, 5 znaków

{!n:}

To jest zaskakująco krótkie. Jeśli Stacked może zaimplementować każdą kombinację SKI, to jest to Turing Complete. Podsumować:

• I kombinator - funkcja tożsamości. x -> x
• K kombinator - funkcja stała. x -> y -> x
• S kombinator - funkcja podstawienia. (x, y, z) -> x(z)(y(z))

I kombinator: {!n}

Teraz, dla ułożonych szczegółów. {! ... }jest n-lambda. Jest to jednoargumentowa funkcja, której argument jest niejawny n. Następnie ostatnie wyrażenie jest zwracane z funkcji. Zatem {!n}jest funkcją, która przyjmuje argument ni daje wynik n.

Kombinator K: {!{:n}}

Teraz {:...}jest funkcją, która nie przyjmuje argumentów i zwraca .... Łącząc to z naszą formacją n-lambda, otrzymujemy (dodając białe spacje dla przejrzystości):

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

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

Ok, to wygląda trochę bardziej skomplikowane. Tak więc lambda przyjmuje argumenty oddzielone znakami nie będącymi identyfikatorami. Zatem lambda w nagłówku jest równoważna:

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

To lambda, które trwa trzy argumenty, n, nn, i nnn. Załóżmy zastąpić te z x, yi zdla jasności:

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

Oba {!n}!są tylko funkcją tożsamości, aby ponownie uniknąć białych znaków, gdzie !oznacza „wykonaj”. Ponownie zmniejszając:

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

Z wyjaśnieniem:

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

I dlatego jest to kombinator S.