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!
Odpowiedzi:
XOISC
Ten OISC oparty jest na X-kombinatorze Fokkera, który jest zdefiniowany następująco:
Jak działa XOISC
Gdy nie będzie już żadnych instrukcji, XOISC wypchnie wszystkie argumenty wiersza poleceń (jeśli istnieją) na stos, na przykład:
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:
Wypróbuj online!
Przykład
Weźmy powyższy przykład (stos rośnie w prawo):
Kompletność Turinga
Dowód na pomysł
0
0
2
0
2
Tak więc otrzymujemy inny (ale semantycznie równoważny) program XOISC:
0 0 2 0 2 0 2
Wypróbuj online!Formalny dowód
Biorąc pod uwagę, że rachunek SKI jest zakończony w Turinga, musimy pokazać dwie rzeczy:
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 * .
0
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
S
kombinatora\\\(3 1 (2 1))
(lubλλλ(3 1 (2 1))
). Jednak to także rozpoznajeS
,K
,I
i oczywiścieX
COMBINATOR.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
-b
flaga, 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ą
-a
flagi, 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!
źródło
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 (
x
iy
) i jeszcze dwóch identyfikatorów linii (a
ib
).Trasy programowe w sposób następujący:
Począwszy od linii zidentyfikowanego jako
start
ze strzałką skierowaną do pozycji (0, 0), przesuń wskaźnik w kwocie określonej przezx
ay
i zaznaczyć kwadrat wskaźnik jest teraz (chyba, że plac jest już oznakowane, w takim przypadku wykonanie kończy się). Następnie przeskocz do linii,a
jeśli co najmniej jeden z bezpośrednio sąsiadujących pól jest również zaznaczony, i dob
innej 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
zamienia się w ten alternatywny program:
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.
inc
,dec
Inop
są 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ącyinc 2
:Zmień liczby w
i1_x
częściach na indeks bieżącej instrukcji, awi2_x
częściach na indeks następnej instrukcji do wykonania.nop
Instrukcja może być tłumaczone jako takie:To jest zmniejszenie:
i3_x
odnosi się do instrukcji, która ma zostać wywołana, jeśli licznik ma już 1.Postój:
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 .
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):
źródło
-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ńcuchLABEL
ze stosu. JeśliLABEL
jest 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ściA
orazB
: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
Ustawia zmienną
i
na7
, zwiększając7
czasy.Mnoży to
i+1
przez 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.
źródło