Ustalenie, czy język jest kompletny, jest bardzo ważne przy projektowaniu języka. Na początku jest to dość trudne zadanie dla wielu ezoterycznych języków programowania, ale pozwólmy mu podnieść poprzeczkę. Zróbmy kilka języków programowania, które są tak trudne do udowodnienia Turing Complete, że nawet najlepsi matematycy na świecie nie udowodnią ich w żaden sposób. Twoim zadaniem jest opracowanie i wdrożenie języka, którego kompletność Turinga opiera się na głównym nierozwiązanym problemie w matematyce .
Zasady
Wybrany problem musi zostać postawiony co najmniej 10 lat temu i musi zostać nierozwiązany w chwili opublikowania tego pytania. Może to być dowolna hipoteza matematyki, a nie tylko jedna z wymienionych na stronie Wikipedii .
Musisz podać specyfikację języka i implementację w istniejącym języku.
Język programowania musi być kompletny, jeśli tylko przypuszczenie się utrzymuje. (lub jeśli i tylko wtedy, gdy domniemanie się nie zachowuje)
Musisz załączyć dowód, dlaczego Turing byłby kompletny lub niekompletny w oparciu o wybraną hipotezę. Możesz założyć dostęp do nieograniczonej pamięci podczas uruchamiania interpretera lub kompilowanego programu.
Ponieważ zajmujemy się kompletnością operacji we / wy Turinga, nie jest to wymagane, jednak celem jest stworzenie najciekawszego języka, który mógłby pomóc.
To konkurs popularności, więc wygra odpowiedź z największą liczbą głosów.
Kryteria docelowe
Co powinna zrobić dobra odpowiedź? Oto kilka rzeczy, na które należy zwrócić uwagę podczas głosowania, ale nie są one technicznie wymagane
Nie powinna to być zwykła łatka istniejącego języka. Zmiana istniejącego języka w celu dopasowania do specyfikacji jest w porządku, ale łatanie pod warunkiem jest odradzane, ponieważ jest nudne. Jak powiedział ais523 w Nineteeth Byte:
Wolę, aby sztuczki moich esolangów były mocniej upieczone w języku
Powinien być interesujący jako samodzielny ezoteryczny język.
źródło
Odpowiedzi:
Legendre
Ten język jest kompletny dla Turinga tylko wtedy i tylko wtedy, gdy hipoteza Legendre'a jest fałszywa, tzn. Istnieje liczba całkowita n> 0 taka, że nie ma liczb pierwszych między n ^ 2 a (n + 1) ^ 2. Ten język czerpie inspirację z Niedociążenia, choć pod pewnymi względami bardzo się od niego różni.
Programy w Legendre składają się z szeregu dodatnich liczb całkowitych (0 jest szczególnie zbanowany, ponieważ zasadniczo neguje cały cel języka). Każda liczba całkowita odpowiada poleceniu bazowemu w Legendre lub potencjalnemu zdefiniowanemu przez użytkownika. To, do którego polecenia jest przypisane, zależy od liczby liczb pierwszych między jego kwadratem a kolejną liczbą całkowitą (równoważną sekwencji OEIS A014085 ).
Polecenia języka modyfikują stos, który może przechowywać dowolnie duże dodatnie liczby całkowite. Jeśli stos kiedykolwiek zawiera 0, 0 jest natychmiast usuwane. Szczegółowe polecenia to:
2 (najmniejsza liczba całkowita produkująca to polecenie: 1): Wciśnij następną liczbę całkowitą w programie na stos.
3 (najmniejsza produkująca liczba całkowita: 4): Wciśnij górną liczbę całkowitą na stosie i wykonaj związane z nią polecenie.
4 (najmniejszy: 6): Pop najwyższą liczbę całkowitą. Jeśli było 1, zwiększ górną liczbę całkowitą na stosie.
5 (10): Zamień dwa górne elementy stosu.
6 (15): Zmniejsz górną liczbę całkowitą na stosie. Jeśli wynikiem jest 0, pop 0 i odrzuć go.
7 (16): Zduplikuj górną liczbę całkowitą na stosie.
8 (25): Zatrzymaj wykonanie i wydrukuj zawartość stosu.
Jest to podstawowy zestaw instrukcji, który nie jest w stanie zrobić nic interesującego, nie mówiąc już o zapętleniu. Istnieje jednak inne polecenie, do którego można uzyskać dostęp tylko wtedy, gdy przypuszczenie Legendre okaże się fałszywe.
Jeśli to polecenie jest w jakiś sposób dostępne, język staje się kompletny Turinga, ponieważ można w nim symulować maszynę Minsky'ego.
Po wykonaniu polecenia 8 lub osiągnięciu końca programu program kończy działanie i drukowany jest znak (Unicode) odpowiadający każdej liczbie całkowitej na stosie.
Przykładowe programy
Ten prosty program wypycha cyfrę 2, następnie 3, a na końcu 10, przed wykonaniem 4 (polecenie: 3), co powoduje, że 10 (polecenie: 5) jest wyskakujące i wykonywane, zamieniając 2 i 3.
Ten program demonstruje użycie pośredniej korespondencji typu integer-to-Command. Najpierw pchane jest 5, a następnie 15 i 1, przy użyciu trzech różnych sposobów kodowania polecenia 2. Następnie 1 jest wyskakiwany, w wyniku czego 15 jest zwiększane do 16, a następnie wykonywane. Program kończy się dwoma wystąpieniami liczby 5 na stosie.
Ten program demonstruje użycie polecenia 0 za pomocą? jako numer zastępczy. Program najpierw przechowuje „1 5” w funkcji 9, a następnie „15 31” na 10, a następnie uruchamia funkcję 9 (przy użyciu 24), która wypycha 5 na stos i wielokrotnie go zmniejsza, aż osiągnie 0 i zostanie usunięta . Następnie program zatrzymuje się.
Maszyna Minsky
Aby przekonwertować maszynę Minsky na kod Legendre, należy użyć polecenia 0 . Ponieważ to polecenie jest niedostępne, chyba że przypuszczenie Legendre'a jest fałszywe, użyłem symbolu zastępczego? zamiast.
Zauważ, że wszystkie nazwy linii instrukcji maszynowych Minsky muszą mieć liczby całkowite z różnymi odpowiednikami A014085 od siebie i poleceń podstawowych, a także 24 (9) i 31 (10).
Inicjalizacja: x INC (A / B) y:ZA:
B:
x DEC (A / B) yz:ZA:
B:
x HALT:Aby utworzyć końcowy program, dodaj wszystkie części (z x, y, z zastąpionymi przez ich odpowiedniki) i dodaj jedną liczbę całkowitą, aby rozpocząć pierwszą instrukcję w łańcuchu. Powinno to udowodnić kompletność języka Turinga na wypadek, gdyby domysł Legendre'a okazał się fałszywy na podstawie kontrprzykładu.
Interpretator
Ten interpreter został napisany w Pythonie (3) i został przetestowany na wszystkich trzech powyższych przykładach. Czy użyć flag -a / - allowZero, aby zezwolić? do użycia, -f / - plik do uruchomienia kodu bezpośrednio z pliku i -s / - stackOut, aby zamiast tego wyprowadzić stos jako listę Pythona. Jeśli nie podano żadnego pliku, interpreter przechodzi w tryb REPL, który najlepiej jest stosować z opcją --stackOut.
źródło
Unia zamknięta
Ten język programowania jest Turing kompletny, jeśli domniemana grupa Union-closed Sets jest niepoprawna.
Sterownica
Lista poleceń:
x ++ Przyrost x (INC)
x-- Zmniejszenie x (DEC)
j (x, y) Dodaj zestaw instrukcji x, jeśli y wynosi 0, do końca kolejki instrukcji
Wszystkie zmienne są inicjowane jako 0
Składnia
Programy są zapisywane jako zbiór zestawów poleceń.
Command1 Command2 Command3 ...
Command1 Command2 ...
...
Aby ustalić, czy program jest zamknięty, każdy zestaw uwzględnia tylko listę różnych poleceń, które znajdują się w zestawie
j (x, y)! = J (a, b)
+ (x)! = + (Y)
Jeśli jakikolwiek typ polecenia (+, -, j) pojawia się w co najmniej połowie zestawów, nic nie robi.
Programy mogą zakończyć się, jeśli na końcu kolejki instrukcji nie ma instrukcji
Nieskończone pętle, w tym pustą pętlę, można osiągnąć za pomocą j (x, y)
Interpretator
Pokaż fragment kodu
Kompletność Turinga
Jeśli wszystkie trzy komendy, j (x, y), inkrementacja, dekrementacja, wszystkie komendy są dostępne, można więc symulować maszynę Minsky'ego.
Każdy zestaw zawierający tylko j (x, y), który jest osiągany przy użyciu j (x, y), to HALT
x ++ to INC
x-- to DEC
j (x, y) to JZ
Jeśli przypuszczenie o zamkniętych zestawach unii jest prawidłowe, przynajmniej jedno z trzech poleceń będzie zawsze wyłączone, uniemożliwiając w ten sposób ukończenie tego języka przez Turinga.
źródło
Liczby Fermata
Język działa na dwóch potencjalnie nieskończonych taśmach, gdzie każda lokalizacja taśmy może przechowywać dowolną liczbę całkowitą. Obie taśmy są wypełnione
-1
na początku. Istnieją również dwie głowice taśm, które zaczynają się w pozycji 0 na obu taśmach.Tłumacz najpierw odczyta dane wejściowe i zapisze wartości na pierwszej taśmie (danych), zaczynając od pozycji 0.
Następnie odczyta dostarczony program. Dla każdej napotkanej liczby najpierw sprawdzi, czy wartość jest liczbą pierwszą Fermata, czy nie. Jeśli tak, zapisze na drugiej taśmie (instrukcji), którą jest Fermat, w przeciwnym razie zapisze
-1
na taśmie instrukcji.Następnie sprawdź wartość we wskaźniku instrukcji i wykonaj jedną z następujących czynności:
-1
lub mniej: Wyjdź z programu0
: Przesuń pozycję taśmy danych o jeden w lewo. Przesuń pozycję taśmy instrukcji o jedną w prawo1
: Przesuń pozycję taśmy danych o jedną w prawo. Przesuń pozycję taśmy instrukcji o jedną w prawo2
: Zwiększ wartość w miejscu taśmy danych. Przesuń pozycję taśmy instrukcji o jedną w prawo3
: Zmniejsz wartość w miejscu taśmy danych. Przesuń pozycję taśmy instrukcji o jedną w prawo4
: Jeśli wartość w bieżącym położeniu taśmy danych wynosi zero, przesuń taśmę instrukcji w prawo, aż osiągniesz pasującą5
(lub większą) wartość na taśmie instrukcji lub coś mniejszego niż0
. Jeśli jest5
(lub większy), ponownie przesuń wskaźnik instrukcji w prawo, jeśli jest mniejszy niż,0
to wyjdź z programu. Jeśli wartość bieżącej pozycji taśmy danych nie jest równa zero, po prostu przesuń taśmę instrukcji jedną w prawo5
lub więcej: przesuń wskaźnik instrukcji w lewo, aż osiągniesz odpowiednią4
wartość lub znajdziesz coś mniejszego niż0
. W przypadku tego ostatniego zamknij program.(przez dopasowanie
5
(lub więcej) i4
wartości oznacza to, że podczas wyszukiwania właściwej wartości na taśmie instrukcji za każdym razem, gdy napotka taką samą wartość jak polecenie początkowe (albo5
(więcej), albo4
), będzie musiał pominąć odpowiednią liczbę innej wartości (4
lub5
(odpowiednio) więcej w wyszukiwaniu)Pętla, dopóki instrukcja nie powie, że musisz wyjść z programu.
Gdy program zakończy działanie, wypisz wartości na taśmie danych od pozycji
0
do pierwszej pozycji taśmy, która zawiera-1
wartość.Dowód
Zauważ, że język zasadniczo odwzorowuje interpretera Brainfuck bez IO, gdzie
F_5
wymagana jest możliwość wykonywania wszelkiego rodzaju właściwych pętli.Jednak w oparciu o hipotezę Fermata istnieje tylko 5 liczb pierwszych Fermata (
F_0
-F_4
). JeśliF_5
istnieje, język jest kompletny, ponieważ wiemy, że Brainfuck jest kompletny. Jednak bezF_5
ciebie nie będziesz w stanie wykonywać rozgałęzień ani pętli, co zasadniczo blokuje cię w bardzo prostych programach.Realizacja
(testowany z Ruby 2.3.1)
Przykłady:
Spowoduje to napisanie
H
(skrótHello World!
) na ekranie z nową linią:Zapisz jako
example.fermat
i uruchom w ten sposób (uwaga: zawsze musisz mieć dane wejściowe):W następnym przykładzie zrobimy prosty szyfr w stylu Cezara, zwiększając każdą wartość wejściową o jeden. Oczywiście musisz zastąpić
?
piątą pierwszą Fermat:Możesz sprawdzić, czy działa, włączając tryb oszukiwania i używając
2 4 1 2 5 3
jako kodu źródłowego:źródło
5
. Mam nadzieję, że mają dobrą klawiaturę.Swallows w / Coconut v2
Ponieważ poprzednia wersja zawierała błędy, które spowodowały, że była nieważna w tym konkursie, i nie chcę, aby opinie z poprzedniej wersji były liczone dla tej wersji, która jest znacząco inna, ta wersja jest przesyłana jako nowy post.
Ten język nie jest kompletny, jeśli Twierdzenie Collatza można udowodnić dla wszystkich liczb całkowitych dodatnich. W przeciwnym razie język jest kompletny.
Ten język został oparty na Kardynale .
Po pierwsze, contVal programu jest obliczany przy użyciu formuły
contVal = suma (suma (wartości ASCII rzędu) * 2 ^ (numer wiersza-1))
Następnie na każdym A lub E tworzone są 2 jaskółki skierowane w przeciwnych kierunkach, a wszystkie warunkowe instrukcje skrętu czekają na inicjalizację.
Jaskółki utworzone w E są skierowane w lewo / prawo, a jaskółki utworzone w A są skierowane w górę / w dół.
Na koniec kod będzie wykonywał kroki, dopóki wszystkie wskaźniki nie zostaną usunięte lub contVal spadnie do jednego.
Na każdym kroku, jeśli contVal% 2 == 0 zostanie podzielony przez 2, w przeciwnym razie zostanie pomnożony przez trzy i zwiększony o jeden.
Polecenia:
0: ustaw wartość na 0
+: zwiększ wartość o 1
>: zmień kierunek w prawo
v: zmień kierunek w dół
<: zmień kierunek w lewo
^: zmień kierunek w górę
R: Kolejne wskaźniki po pierwszym wskaźniku porównaj z wartością pierwszy wskaźnik. Jeśli jest równy, idź prosto, w przeciwnym razie skręć w prawo.
L: Kolejne wskaźniki po pierwszym wskaźniku są porównywane z wartością pierwszego wskaźnika. Jeśli jest równy, idź prosto, w przeciwnym razie skręć w lewo.
E: Zduplikuj wskaźnik, ale kierujesz się w lewo i prawo.
A: Zduplikujesz wskaźnik, ale kierujesz się w górę i w dół
? : Usuń wskaźnik, jeśli wartość wynosi 0
Pokaż fragment kodu
Wyjaśnienie:
Jeśli hipotezę Collatza można udowodnić dla wszystkich liczb całkowitych dodatnich, czas trwania dowolnego programu uruchomionego w tym języku jest skończony, ponieważ contVal zawsze zbiegnie się do 1, tym samym kończąc program.
W przeciwnym razie muszę tylko udowodnić, że ten język może implementować następujące funkcje
Przyrost: który jest reprezentowany przez +
Stała 0: który jest reprezentowany przez 0
Dostęp zmienny: zmienne są przechowywane jako wskaźniki podczas podróży
Łączenie instrukcji: zmieniając odległość przebytą do operacji, można zmienić kolejność wykonywania operacji
Dla pętli: W tym języku
będzie działać jak pętla for> zliczać do 1 (do pętli można dodać kolejny kod)
Podobnie kod
Będzie działać jak do, aż będzie równa wartości warunkowej ustawionej w pętli R.
źródło
contVal
na każdym kroku (a zatem jeśli przypuszczenie jest prawdziwe, nie ma nieskończonych pętli) - ale nie widzę tego wyraźnie w nigdzie w odpowiedzi. ??Doskonałość / niedoskonałość
Uff, było fajnie.
Doskonałość / niedoskonałość jest kompletna tylko wtedy, gdy istnieje nieskończona liczba idealna. Jeśli tak, nazywa się to Doskonałością, a jeśli nie, to nazywa się Niedoskonałością. Dopóki ta tajemnica nie zostanie rozwiązana, zawiera ona oba imiona.
Liczba idealna to liczba, której dzielniki sumują się do liczby, więc sześć to liczba idealna, ponieważ
1+2+3=6
.Perfekcja / Niedoskonałość ma następujące funkcje:
Perfekcja / niedoskonałość opiera się na stosie, a stos jest indeksowany od zera.
Polecenia:
p(x, y)
: wypycha x na stosie w pozycji y.z(x, y)
: wypycha x na stos w pozycji y, pozbywa się tego, co poprzednio znajdowało się w pozycji yr(x)
: usuwa xty element ze stosuk(x)
: zwraca x pozycję na stosiea(x, y)
: dodaje xiy. W połączeniu ze stringami łączy je w kolejności xy.s(x, y)
: odejmuje y od x. z ciągami usuwa ostatnią długość (y) z xm(x, y)
: mnoży xiy. W przypadku użycia z łańcuchami mnoży x razy długość y.d(x, y)
: dzieli x przez yo(x)
: drukuje xi(x, y)
: jeśli x ma wartość true, wówczas wykonuje funkcję yn()
: zwraca licznik, w którym blok kodu jest wywoływany.q()
: zwraca długość stosut()
: dane wejściowe użytkownikae(x, y)
: Jeśli x jest liczbą całkowitą, jeśli xiy mają tę samą wartość, to zwraca 1. jeśli y jest łańcuchem, wówczas przyjmuje długość y. jeśli x jest łańcuchem, to konwertuje y na łańcuch i sprawdza, czy są takie same, a jeśli tak, zwraca 1. W przeciwnym razie zwraca 0.l(x, y)
: jeśli x jest większy niż y, to zwraca 1. Jeśli jest łańcuch, to używa jego długości.b()
: zatrzymuje program.c(x, y)
: uruchamia x, a następnie y.Aby uzyskać ekwiwalent języka Python
and
, pomnóż obie wartości razem. Dlaor
dodaj wartości, a dlanot
odejmij wartość od 1. Działa to tylko wtedy, gdy wartość wynosi 1 lub 0, co można osiągnąć, dzieląc liczbę samodzielnie.Typy danych: liczby całkowite i ciągi. Ciągi są oznaczone symbolem
''
, a wszystkie liczby niecałkowite są zaokrąglane.Składnia:
Kod składa się z zagnieżdżonych funkcji w ciągu dziesięciu
{}
sekund. Na przykład, program, który dostanie się do wejścia i wydrukować je dodany będzie:{o(a(t(), t()))}
. W tle programu znajduje się licznik, który zaczyna się od 0 i przesuwa się o 1 za każdym razem, gdy wykonuje blok kodu. Pierwszy blok kodu działa w0
i tak dalej. Po wykonaniu dziesięciu bloków kodu szósty jest wykonywany za każdym razem, gdy licznik osiągnie idealną liczbę. Nie musisz mieć wszystkich dziesięciu bloków kodu, aby program działał, ale potrzebujesz 7, jeśli chcesz utworzyć pętlę. Aby lepiej zrozumieć, jak działa ten język, uruchom następujący program, który drukuje licznik za każdym razem licznik osiągnie doskonały numer:{}{}{}{}{}{}{o(n())}
.Tłumacz można znaleźć tutaj: repl.it/GL7S/37 . Wybierz 1 i wpisz swój kod w terminalu lub wklej kod na
code.perfect
karcie i wybierz 2 po uruchomieniu. Będzie to miało sens, gdy spróbujesz.Dowód kompletności Turinga / brak kompletności Turinga.
Zgodnie z tym artykułem dotyczącym wymiany stosów inżynierii oprogramowania , kompletny Turing musi mieć możliwość warunkowego powtarzania skoku oraz mieć możliwość odczytu lub zapisu pamięci. Może odczytywać / zapisywać pamięć w postaci stosu i może zapętlać się, ponieważ szósty blok kodu jest wykonywany za każdym razem, gdy licznik osiągnie idealną liczbę. Jeśli istnieje nieskończona liczba liczb doskonałych, może zapętlać się w nieskończoność i Turing jest kompletny, a poza tym nie jest.
Interaktywny interpreter znaczników cyklicznych, który pobiera 5 znaków, 1 lub 0, jako dane wejściowe:
Można go rozszerzyć, aby pobierał dowolną liczbę znaków jako dane wejściowe. Może to wymagać nieskończonych danych wejściowych, ale tylko wtedy, gdy istnieją nieskończone liczby idealne!
źródło
Podeszwy
Ten język programowania jest Turing kompletny, jeśli przypuszczenie Scholza jest prawdziwe.
Napisałem ten język, ponieważ @SztupY mówił, że nie będzie żadnych wyników, które opierają się na przypuszczeniu, że spełnienie Turinga jest prawdziwe
Lista poleceń
Za pomocą tych poleceń ten język może symulować maszynę Minsky'ego
Interpretator
Gorąco polecam nie uruchamiać tego. Wykorzystuje wyjątkowo powolną metodę sprawdzania łańcucha dodawania.
Pokaż fragment kodu
Kompletność Turinga
Język używa licznika dla liczby uruchomionych poleceń, które sprawdza względem hipotezy Scholza w celu zmodyfikowania kompletności języka.
Jeśli hipoteza Scholza jest prawdziwa, program działa dokładnie tak jak normalna maszyna Minsky'ego z
skokiem
zmniejszania przyrostu,
jeśli zerowe
zatrzymanie
Jeśli jednak hipoteza Scholza jest fałszywa, licznik ostatecznie osiągnie wartość, dla której hipoteza Scholza nie jest prawdziwa. Ponieważ język został zaprojektowany w taki sposób, aby wychodził po osiągnięciu liczby, która według przypuszczeń Scholza jest fałszywa, program wyjdzie za każdym razem po uruchomieniu tylu poleceń. Dlatego wszystkie programy będą miały ograniczoną długość. Ponieważ nie jest to zgodne z wymogami dotyczącymi ukończenia języka przez Turinga,
język nie byłby kompletny, gdyby hipoteza Scholza była fałszywa
źródło
Narzeczony
Betrothed Github .
Plik Readme i specyfikacja znajdują się na github pod „README.txt”.
Zasadniczo program narzeczonych składa się z par linii, których długości są odrębnymi podwójnymi parami liczb pierwszych lub parami zaręczonych (nie mogą wystąpić duplikaty). Program jest wykonywany przez znajdowanie „elastycznych podzbiorów” pierwszego wiersza w parze w drugim wierszu. Liczba takich podzbiorów, w połączeniu z odległością Levenshteina między oryginalną drugą linią i drugą linią bez elastycznych podzbiorów, określają polecenie do wykonania.
Wyciągnę dowód na ten post:
źródło
b
. To interpretuje program BF, który jest umieszczony po nim, podobnie jakb+++++.
. Rozmiar programu jest jednak ograniczony do 10 znaków. Chociaż może interpretować BF, nie może obliczyć wszystkich programów, które może zrobić maszyna Turinga.Polubowny parytet
Ten język opiera się na tym, czy są jakieś polubowne liczby o przeciwnej parzystości .
Polecenia
Kontrola przepływu
Program cyklicznie powtarza się od lewej do prawej, zanim powróci do początku. Jeśli napotka „j”, sprawdza wartość, aby ustalić, czy powinna zmienić wiersze. Jeśli liczba jest liczbą polubowną z przeciwną parzystością do jej dopasowania, idzie w dół o jeden wiersz (zapętlanie z powrotem do góry), w przeciwnym razie, jeśli liczba jest polubowną, idzie w górę o jeden rząd, jeśli nie jest już w górnym rzędzie.
Program może zakończyć się tylko wtedy, gdy osiągnie x w dowolnym wierszu poza górnym wierszem.
Kompletność Turinga
Tego programu można użyć do symulacji maszyny Minsky'ego, zakładając, że istnieje para polubownych liczb o przeciwnej parzystości.
j, {i} mogą być użyte do symulacji JZ (r, x), chociaż sprawdziłby, czy liczby są polubowne w przeciwieństwie do zera.
+ to INC (r)
- to DEC (r)
x to HALT
Jeśli nie możesz opuścić pierwszego wiersza, polecenia x i} nic nie robią. Powoduje to, że program nie może wejść w stan HALT, chyba że jest to pusty program. Dlatego pod opisem, że kompletność Turinga wymaga stanu HALT , językiem byłoby Turing niepełny.
Interpretator
Pokaż fragment kodu
źródło
Nowa linia
Oświadczenie: To trochę bałagan i dość proste. To pierwszy język, jaki kiedykolwiek napisałem, a domysł jest jedynym, który zrozumiałem. Wiem, że inny użytkownik miał dłuższą odpowiedź na ten sam, ale i tak postanowiłem to napisać.
Aby pisać w Newline, musisz mieć dużo czasu i nowych linii (
\n
). To działa na zasadzie prawdziwości hipotezy Legendre. Każdy operator musi wpaść na liczbę z hipotezy Legendre'a, którą zaczynamy od n = 1. Za każdym razem, gdy masz operatora, bierzesz \ n's i podłączasz ją do hipotezy Legendre'a i uzyskujesz zasięg, który będzie następną liczbą pierwszą \ n musi wpaść. Więc na początek robisz,\n\n
a następnie przechodzisz do operatora, a\n
następnie do innego operatora, jesteśmy na 3 nowych liniach. Teraz następna to 5, więc dodajesz\n\n
i upewniasz się, że ostatnia linia operatora ma odpowiednią liczbę nowych linii, że jesteś w doskonałej ilości, która mieści się w hipotezie Legendre, którą rozpoczęliśmy.Liczby (tablica) są jak zmienne. Za każdym razem, gdy działa operator (który używa liczb), zwiększa.
Tak długo, jak mamy nieograniczone liczby pierwsze, które są zgodne z zasadami, język ten ma nieskończoną taśmę.
Maszyna Minsky
Jak to działa:
Wypróbuj to na KhanAcademy .
źródło
Taggis
Taggis to język oparty na systemach tagów .
Kompletność operacyjna Taggisa opiera się na domysłach Collatza
Składnia
Składnia programu Taggis to po prostu trzy ciągi znaków (reguły produkcji) składające się wyłącznie z liter a, b i c, oddzielone spacjami.
Wykonanie
Jedynym stanem programu Taggisa jest ciąg znaków składający się z tych samych trzech znaków.
Taggis implementuje system tagów TS (3, 2), w którym na każdym etapie usuwane są pierwsze 2 litery obecnego „tagu”, a pierwsza litera, która była w tej usuniętej części, dołącza odpowiednią regułę produkcji na końcu ciąg.
Na przykład program Taggis
bc a aaa
implementuje problem 3n + 1, w którym iteracje są reprezentowane przez odpowiednią liczbęa
s, a krok 3n + 1 jest zastępowany przez (3n + 1) / 2 [1], co prowadzi do wyjścia programu:Kompletność Turinga
Oczywiście ten prosty system może wydawać się zbyt prosty do naśladowania kompletności Turinga, ale okazuje się, że każdą maszynę Turinga z 2 symbolami (klasa obejmująca maszyny uniwersalne) można przekształcić w system tagów z 2 usuniętymi znakami z głowy, oraz 32 * m reguł produkcji, gdzie
m
jest liczba stanów w maszynie Turinga.Najmniejsza znana uniwersalna maszyna Turinga z tylko 2 symbolami wykorzystuje 18 stanów, a zatem odpowiedni system znaczników zawiera aż 576 zasad produkcji [2].
Jednak klasa obliczeniowa zestawu wszystkich systemów znaczników z 3 produkcjami i 2 usuniętymi symbolami jest powiązana z hipotezą Collatza [2]. Jeśli hipoteza Collatza okaże się fałszywa, Taggis jest kompletny w Turingu. W przeciwnym razie opiera się na KOLEJNYM nierozwiązanym problemie w matematyce, znajdując mniejszą maszynę Turinga niż
co jest równoważne oryginalnej funkcji Collatz, ponieważ 3n + 1 nieparzystego
n
zawsze będzie parzysty, dlatego podział może być zastosowany automatycznieSystemy znaczników i funkcje typu Collatz, Liesbeth De Mol ,
źródło