Uwaga: Jestem gotów udzielić nagrody za każdą odpowiedź, którą uważam za interesującą.

Twoim wyzwaniem jest zaprojektowanie kompletnego zestawu instrukcji Turinga (OISC):

OISC to abstrakcyjna maszyna, która korzysta tylko z jednej instrukcji - eliminuje potrzebę używania kodu maszynowego w języku maszynowym. Dzięki rozsądnemu wyborowi pojedynczej instrukcji i nieskończonym zasobom OISC może być uniwersalnym komputerem w taki sam sposób, jak tradycyjne komputery z wieloma instrukcjami.

Oto kilka przykładów pojedynczych poleceń, które składają się na OISC-Turinga.

Zasady:

Musisz przedstawić interpretację lub dowód

Musisz zapewnić tłumacza dla twojego języka. Tłumacz ten powinien być ograniczony tylko pamięcią / czasem (np. Nie może mieć ograniczeń narzuconych przez użytkownika). Jeśli nie zapewnisz tłumacza dla swojego języka (z jakiegokolwiek innego powodu niż lenistwo), musisz udowodnić, że można go napisać. Tłumacz musi być możliwy .

Musisz udowodnić kompletność Turinga

Musisz załączyć formalny dowód, że Twój język jest kompletny w Turingu. Prostym sposobem na to jest udowodnienie, że potrafi interpretować lub zachowywać się tak samo, jak inny język kompletny Turinga. Najbardziej podstawowym językiem do tłumaczenia byłby Brainf ** k .

Na przykład normalny język, który ma wszystkie te same polecenia co Brainf ** k (i ten sam brak ograniczeń pamięci narzuconych przez użytkownika), jest Turing-complete, ponieważ wszystko, co można zaimplementować w Brainf ** k, można zaimplementować w tym języku .

Oto lista bardzo prostych do wdrożenia kompletnych języków Turinga.

Dodatkowe wymagania OISC

• Ten OISC powinien mieć tylko jedną instrukcję - nie może mieć wielu instrukcji z jedną z nich, co czyni ją kompletną metodą Turinga.

• Twój OISC może używać dowolnej składni, którą lubisz. W swojej odpowiedzi powinieneś zdefiniować, czym jest instrukcja, co to dane, a co brak możliwości (np. Białe znaki). Bądź kreatywny!

• Argumenty nie muszą być tylko liczbami całkowitymi. Na przykład /// jest pięknym przykładem kompletnego OISC Turinga.

• To, jak i czy dane wejściowe i wyjściowe są pobierane i podawane, należy do Ciebie. Większość OISC implementuje I / O poprzez określone lokalizacje pamięci, ale mogą istnieć inne sposoby na to, i zachęcamy do znalezienia takiego.

• Prawidłowa odpowiedź musi zawierać przykładowy kod w Twoim OISC, albo poprzez włączenie go do postu, albo link do prostego zadania rozwiązanego w języku.

Głosowanie

Głosujący, pamiętajcie, aby nie głosować nudnych zgłoszeń. Przykłady:

• Lenguage - równoważne
• Implementacja istniejącego OISC (odpowiedzcie, proszę stworzyć własne!)
• „OISC”, w którym pierwszy argument określa polecenie do wywołania ( przykład )

Należy jednak głosować na ciekawe, kreatywne zgłoszenia, takie jak:

• OISC oparty na równaniu matematycznym
• Kompletny ZISC Turinga oparty na sieci neuronowej
• OISC, w którym wyjściowe operacje we / wy zdarzają się w inny sposób niż niektóre lokalizacje pamięci

Zwycięski

Podobnie jak w przypadku konkursu popularności , wygrywa odpowiedź z największą liczbą głosów! Powodzenia!

XOISC

Ten OISC oparty jest na X-kombinatorze Fokkera, który jest zdefiniowany następująco:

$$X = \lambda f\ . f\ (\lambda g\ h\ x\ . g\ x\ (h\ x))\ (\lambda a\ b\ c\ . a)$$

$X$$S$$K$$I$$X$

$$\begin{align} S &= X\ (X\ X) \\ K &= X\ X \\ I = S\ K\ K &= X\ (X\ X)\ (X\ X)\ (X\ X) \end{align}$$

Jak działa XOISC

$n$

• $n$$f_1 \dots f_N$$f_1\ (f_2\ (\dots (f_N\ X) \dots ))$

Gdy nie będzie już żadnych instrukcji, XOISC wypchnie wszystkie argumenty wiersza poleceń (jeśli istnieją) na stos, na przykład:

$$[ \underbrace{s_1, \dots,\ s_M}_{\text{stack before}} ,\ \underbrace{a_1, \dots,\ a_N}_{\text{arguments}} ]$$

$(\dots ((\dots (s_1\ s_2) \dots)\ s_M)\ a_1) \dots) a_N$

---

Ponieważ jedna instrukcja w XOISC zajmuje tylko jeden argument (przesunięcie pamięci), nie ma powodu, aby nawet używać nazwy dla tej instrukcji. Tak więc prawidłowy plik źródłowy będzie składał się wyłącznie z liczb całkowitych oddzielonych znakami nowej linii lub białych znaków, takich jak na przykład:

0 0 2 0 1 0 1

Wypróbuj online!

Przykład

Weźmy powyższy przykład (stos rośnie w prawo):

$$\begin{align} & \texttt{0} & \text{pop 0 and apply (ie. push single } X \text{)}: & \quad [X] \\ & \texttt{0} & \text{again simply push } X: & \quad [X,\ X] \\ & \texttt{2} & \text{pop 2 (} a,b \text{) and push } a\ (b\ X): & \quad [X\ (X\ X)] \\ & \texttt{0} & \text{simply push } X: & \quad [X\ (X\ X),\ X] \\ & \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X: & \quad [X\ (X\ X),\ X\ X] \\ & \texttt{0} & \text{simply push } X: & \quad [X\ (X\ X),\ X\ X,\ X] \\ & \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X: & \quad [X\ (X\ X),\ X\ X,\ X\ X] \end{align}$$

$((X\ (X\ X))\ (X\ X))\ (X\ X)$$X\ (X\ X)\ (X\ X)\ (X\ X)$$S\ K\ K$

Kompletność Turinga

Dowód na pomysł

$X$

$X$

$((X\ (X\ X))\ (X\ X))\ (X\ X)$

• $X$0
• następnie jesteśmy na nowym poziomie nawiasów, więc znów potrzebujemy tylko 0
• teraz dwa nawiasy są zamknięte, więc musimy wstawić 2 elementy: 2
• znowu jesteśmy na nowym poziomie nawiasów, więc potrzebujemy 0
• dwa nawiasy, zamknij więc ponownie a 2
• i znowu to samo

Tak więc otrzymujemy inny (ale semantycznie równoważny) program XOISC:

0 0 2 0 2 0 2 Wypróbuj online!

$X$

Formalny dowód

Biorąc pod uwagę, że rachunek SKI jest zakończony w Turinga, musimy pokazać dwie rzeczy:

1. $X$
2. $X$

Pierwsza część - dowodzenie trzech równości we wstępie - jest bardzo żmudna i zajmuje dużo miejsca, a także nie jest bardzo interesująca. Zamiast umieszczać go w tym poście, możesz znaleźć tutaj ^* .

$X$

$X$$X$$f\ g$$f$$g$

0$X$$\texttt{F}_1 \dots \texttt{F}_N$$\texttt{G}_1 … \texttt{G}_K$$f$$g$$f\ g$

$\texttt{F}_1 \dots \texttt{F}_N\ \texttt{G}_1 \dots \texttt{G}_{K-1}\ (\texttt{G}_K + 1)$$f$$g$$g$$f$$f\ g$

Interpretator

Wejścia

Ponieważ niepisany rachunek lambda wymaga od nas zdefiniowania własnych typów danych dla wszystkiego, czego chcemy, i jest to kłopotliwe, tłumacz interpretuje liczby kościelne - oznacza to, że po wprowadzeniu danych wejściowych automatycznie przekształci liczby na odpowiadające im liczby kościelne.

Jako przykład podajemy program, który zwielokrotnia dwie liczby: Wypróbuj online!

Można również podać funkcje jako argumenty, używając wskaźników De Bruijn , na przykład Skombinatora \\\(3 1 (2 1))(lub λλλ(3 1 (2 1))). Jednak to także rozpoznaje S, K, Ii oczywiście XCOMBINATOR.

Wydajność

Domyślnie interpreter sprawdza, czy dane wyjściowe kodują liczbę całkowitą, jeśli to zrobi, wyświetli odpowiednią liczbę (oprócz wyniku). Dla wygody dostępna jest -bflaga, która mówi tłumaczowi, aby zamiast tego spróbował dopasować wartość logiczną (patrz ostatni przykład).

Monter

Oczywiście każdy język niskiego poziomu potrzebuje asemblera, który konwertuje na niego język wysokiego poziomu, możesz po prostu użyć dowolnego wejścia (patrz wyżej) i przetłumaczyć go na program XOISC za pomocą -aflagi, wypróbuj go online! ^**

---

^{* W przypadku gdy link nie działa, w tym poście znajduje się kopia jako komentarz HTML.}

^{** Rezultatem jest program, który sprawdza pierwotność, wypróbuj go online!}

rysować

Draw to OISC działający na siatce 2D, oznaczający kwadraty w sposób podobny do maszyny Wanga B. Jednak, aby język był jak najprostszy i OISC-y, jak to możliwe, wszystkie instrukcje (których jest w sumie jedna) zaznaczają właśnie nadepnięty kwadrat i, aby móc się zatrzymać, nadepną na zaznaczony kwadrat kończy program.

Program składa się z sekwencji wierszy zawierających identyfikator linii (dowolny ciąg znaków nie zawierający # lub białych znaków), dwóch liczb całkowitych ( xi y) i jeszcze dwóch identyfikatorów linii ( ai b).

Trasy programowe w sposób następujący:
Począwszy od linii zidentyfikowanego jako startze strzałką skierowaną do pozycji (0, 0), przesuń wskaźnik w kwocie określonej przez xa yi zaznaczyć kwadrat wskaźnik jest teraz (chyba, że plac jest już oznakowane, w takim przypadku wykonanie kończy się). Następnie przeskocz do linii, ajeśli co najmniej jeden z bezpośrednio sąsiadujących pól jest również zaznaczony, i do binnej linii .

Zachęca się tłumaczy do przedstawienia końcowego wyniku siatki jako pewnego rodzaju obrazu, płótna itp.

Kompletność Turinga

Draw jest zakończony przez Turinga, ponieważ możliwe jest skompilowanie zmodyfikowanej wersji maszyny Minsky (zwanej Alternate) na język.

Alternate działa podobnie do dwu-licznikowej maszyny Minsky'ego, ale na polecenia nakłada się duże ograniczenie: polecenia muszą zmieniać się na jeden i drugi licznik. Aby ominąć tę modyfikację, dodatkowa komenda została dodana: nop. To polecenie w ogóle nie zmienia licznika docelowego, co umożliwia „wprowadzanie” kolejnych zmian do jednego licznika, spełniając powyższe ograniczenie. Oznacza to również, że rejestr, który ma zostać zmodyfikowany, nie musi być podawany i dla każdej instrukcji można wywnioskować bezpośrednio z instrukcji, z których można do niego przejść.

Przykład: ta maszyna Minsky

1 inc A 2
2 inc A 3
3 dec A 3 4
4 halt

zamienia się w ten alternatywny program:

1 inc 2
2 nop 3
3 inc 4
4 nop 5
5 dec 6 8
6 nop 5
7 halt
8 halt

To ograniczenie jest konieczne ze względu na sposób, w jaki ewentualny program Draw obsługuje rejestry, co oznacza, że ​​w ogóle ich nie rozróżnia. Zamiast tego program Draw po prostu kopiuje rejestr, który nie został zmieniony przez poprzednią instrukcję, modyfikując go zgodnie z wykonywaną instrukcją.

Następnie program Alternate jest bezpośrednio tłumaczony na Draw w następujący sposób:

Program rozpoczyna się od tego bloku.

start 0 0 a a
a 3 0 b b
b -3 1 c c
c 3 0 d d
d -3 2 e e
e 3 0 f f
f 3 -3 i1_a i1_a

inc, decI nopsą przeliczane w prawie taki sam sposób jak każdy inny. We wszystkich przypadkach nie ma różnicy między zmianą pierwszego lub drugiego rejestru (jak wyjaśniono powyżej). Oto przyrost odpowiadający inc 2:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 0 i2_z i2_y
i1_f 5 0 i2_z i2_y

Zmień liczby w i1_xczęściach na indeks bieżącej instrukcji, aw i2_xczęściach na indeks następnej instrukcji do wykonania.

nopInstrukcja może być tłumaczone jako takie:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 -2 i2_z i2_y
i1_f 5 -2 i2_z i2_y

To jest zmniejszenie:

i1_y 0 -2 i1_z i1_y
i1_z 3 -1 i1_a i1_a
i1_a -5 1 i1_b i1_b
i1_b 0 2 i1_c i1_c
i1_c 0 2 i1_d i1_e
i1_d 0 2 i1_d i1_f

i1_e 5 -2 i3_z i3_y
i1_f 5 -4 i2_z i2_y

i3_x odnosi się do instrukcji, która ma zostać wywołana, jeśli licznik ma już 1.

Postój:

i1_y 0 0 0 0
i1_z 0 0 0 0

Zmień etykiety odpowiednio i po prostu połącz wszystko razem. Wykonanie tego dla powyższego przykładu daje programowi Draw w repozytorium z góry.

Tłumacze ustni

Obecnie jest dwóch tłumaczy pisemnych w języku Python. Można je znaleźć w repozytorium GitHub programu Draw .

1. draw.py : Ten interpreter jest przeznaczony dla wiersza poleceń i przyjmuje źródło programu jako argument. Po każdym kroku wypisuje wykonane polecenie i położenie wskaźnika instrukcji; po zatrzymaniu program wypisuje liczbę zaznaczonych komórek.
2. draw_golly.py : Ta wersja używa Golly do dokładnie niewłaściwego celu łatwiejszego wyjścia graficznego, biorąc źródło za pomocą wyskakującego okienka podczas uruchamiania skryptu. Golly może być trochę wybredny w Pythonie, więc upewnij się, że masz zainstalowany Python 2 (i nie mieszaj 32-bitowego Golly z 64-bitowym Pythonem lub odwrotnie). Dane wyjściowe są dostarczane przez wbudowaną siatkę komórek Golly.

Poniższy obraz jest przykładem danych wyjściowych z drugiego tłumacza. Uruchomienie przykładowego programu w repozytorium daje to (lub podobne):

-3

Oto sedno.

Pamięć

Pamięć to mapa taśm, w której klucze są łańcuchami, a wartości liczbami całkowitymi o dowolnym rozmiarze.

Dodatkowo istnieje zestaw etykiet, do których program może przejść.

Istnieje stos, który zawiera operandy, które są łańcuchami.

Istnieje offest, który kontroluje, gdzie na taśmach pamięci może uzyskać dostęp.

Jedna instrukcja

-. Po pierwsze, zrzuca łańcuch LABELze stosu. Jeśli LABELjest niezdefiniowana jako etykieta, definiuje etykietę i czyści źródło tej etykiety (tj. Skąd została wypchnięta) oraz bieżącą instrukcję. W przeciwnym razie wykonuje następujące obliczenia, używając dwóch najwyższych wartości Aoraz B:

if mem[A] < mem[B]:
    jump to LABEL
if mem[A] != mem[B]:
    mem[A]--
else:
    mem[B]++

Zauważ, że jeśli jest za dużo lub za mało argumentów, program popełni błąd, pokazując stan programu.

Przesunięcie można zmodyfikować, uzyskując dostęp do wartości ..

Przykładowy kod

X-

i i X-
i i X-
i i X-
i i X-
i i X-
i i X-
i i X-

Ustawia zmienną ina 7, zwiększając 7czasy.

X-

i i X-
i i X-
i i X-
LOOP-
    a a X-
    a a X-
    j i LOOP-

Mnoży to i+1przez stałą 2.

Dowód kompletności Turinga

Pomijając rozmiary int C ++ (to znaczy zakładając, że są nieskończone), -3 oznacza Turinga Kompletnego poprzez redukcję do 3-komórkowego pieprzenia mózgu . Nie mogę zignorować tego rozmiaru, ponieważ można napisać interpreter dla -3 na komputerze z nieskończoną pamięcią, która ma dowolnie duże komórki.

Uważam również, że każdy BCT można zapisać jako program -3.