Uwaga: specyfika tego wyzwania jest z natury trudna do zrozumienia. Prawdopodobnie wymaga co najmniej pierwszego kursu teorii obliczeń lub równoważnego czytania w tle. Ponadto samo wyzwanie jest dość trudne. Udzielenie odpowiedzi będzie wymagało napisania całego tłumacza dla wybranego podzbioru wybranego przez ciebie języka, i nie tylko to, ale tłumacz będzie musiał mieć formę czegoś w rodzaju quine. Jeśli twoja odpowiedź nie robi tego wszystkiego, prawie na pewno nie spełnia specyfikacji.
Nie musisz rozwiązać problemu zatrzymania (nawet częściowo), aby rozwiązać to wyzwanie. Jednak prawie na pewno zrobić potrzebę napisania tłumacza (języka używanego, napisany w tym samym języku, to interpretuje), choć nie musi być cechą kompletne. To właśnie sprawia, że jest to interesujące wyzwanie.
Obiecałem przyznać nagrodę w wysokości 500 punktów za pierwszą odpowiedź spełniającą specyfikację, a ta zostanie przyznana odpowiedzi BF Jo Kinga .
Wyzwanie
Surowa, uproszczona wersja dowodu Alana Turinga na nierozwiązywalność problemu zatrzymania wygląda mniej więcej tak:
Załóżmy, że napisałem program, F
który ma rozwiązać program zatrzymujący. Oznacza to, że F
pobiera kod źródłowy innego programu jako dane wejściowe i F(G)
powinien zwrócić, 1
jeśli zostanie G
zatrzymany, i w 0
inny sposób.
Ale jeśli dam ci mój program F
, możesz zbudować inny program H
, który uruchamia mój program H
jako jego dane wejściowe. Jeśli F(H)
zwraca, 0
to H
wraca 0
, ale w przeciwnym razie celowo przechodzi w nieskończoną pętlę. Prowadzi to do paradoksu i musimy stwierdzić, że w F
końcu nie można rozwiązać problemu zatrzymania.
Twoim zadaniem jest napisanie programu H
, ale z niespodzianką: nie dam ci mojego programu. Zamiast tego twój program odbierze kod źródłowy mojego programu jako dane wejściowe. To jest:
Twój program odbierze mój program jako dane wejściowe w postaci kodu źródłowego. (Np. Jako plik lub dane wejściowe z wiersza poleceń, szczegóły zależą od Ciebie.)
Mój program zostanie napisany w tym samym języku co Twój program, a także pobiera dane wejściowe w postaci ciągu kodu źródłowego.
Jeśli mój program powróci,
0
gdy podasz program jako dane wejściowe, twój program powinien się zatrzymać (i powrócić0
), gdy poda mój program jako dane wejściowe. (Dokładne znaczenie słowa „returing0
” należy do Ciebie).jeśli mój program się nie zatrzyma lub jeśli zwróci coś innego niż
0
podany jako dane wejściowe, program powinien działać bez końca.
Rzecz w tym, że aby uczynić to naprawdę o wiele trudniejszym, musisz przestrzegać następujących zasad:
Nie można użyć żadnej wbudowanej funkcji
exec
lubeval
typu.Nie można użyć żadnych metod „oszukiwania”, aby uzyskać kod źródłowy własnego programu. (Na przykład nie możesz powiedzieć „zapisz to w pliku o nazwie„ program ”, a następnie
open(program)
umieść w swoim programie).
Oznacza to, że twój program musi być jakimś zwariowanym super-quine'em, który może nie tylko odtwarzać własny kod źródłowy w postaci łańcucha, ale także potrafi poprawnie parsować i interpretować język, w którym jest napisany.
Aby uczynić to nieco mniej niesamowicie trudnym, możesz używać tylko (kompletnego Turinga) wybranego języka. Więc jeśli twój program jest napisany w Pythonie i będzie działał tylko wtedy, gdy mój program zawiera tylko if
s i while
pętle oraz podstawowe operacje na łańcuchach, to jest OK, o ile twój program również używa tylko tych rzeczy. (Oznacza to, że nie musisz się martwić implementacją całej standardowej biblioteki wybranego języka!) Jednak Twój program musi się uruchomić - nie możesz po prostu stworzyć własnego języka.
To konkurs popularności , więc wygrywa odpowiedź z największą liczbą głosów. Jednakże, jak wspomniano powyżej, poważnym wyzwaniem jest w ogóle spełnienie specyfikacji, więc przyznam nagrodę w wysokości 500 punktów za pierwszą odpowiedź, która to zrobi, zgodnie z moim osądem.
Uwaga: bez wątpienia istnieje wiele sposobów „oszukiwania” w tym wyzwaniu, biorąc pod uwagę dokładne sformułowanie, którego użyłem. Jednak naprawdę liczę na odpowiedzi, które wpisują się w ducha pytania. Wyzwanie zgodnie z planem jest bardzo trudne, ale możliwe, i naprawdę mam nadzieję, że uda mi się znaleźć oryginalne rozwiązania. Nie przyznam nagrody za odpowiedź, która według mnie jest oszukiwana.
Uwaga: to wyzwanie zostało pierwotnie opublikowane jako konkurs popularności , ale zostało zamknięte w 2016 r. Z powodu braku „obiektywnego kryterium wygranej” i zmieniłem je na code-golf , aby je ponownie otworzyć. Jednak odkryłem, że od stycznia 2018 r popularity-contest s nie są w rzeczywistości zakazane na PPCG (z tego jest najnowsza meta dyskusja) zamykając go na pierwszym miejscu był przeciwny polityce miejscu. Rozumiem, że popcony nie są obecnie popularne, ale jest to stare wyzwanie, a jego natura naprawdę nie nadaje się do gry w golfa kodowegosystem oceniania. Jeśli ktoś nadal uważa, że nie powinno to być dozwolone, zróbmy meta dyskusję, zanim zaczną się rzucać bliskie głosy. Wreszcie, na wszelki wypadek, że ktoś spędził ostatni rok na próbowaniu golfa swojego rozwiązania, zapewniam cię, że będzie tak samo konkurencyjny w tym wyzwaniu i równie godny nagrody, jak w przypadku golfa kodowego wersja.
źródło
F
do pliku i wprowadzanie go byłoby nielegalneimport
? ; 3Odpowiedzi:
brainfuck ,
601348774376 bajtówEdycja: -1136 bajtów. Przełączono na lepszy sposób generowania danych dla quine
Edycja2: -501 bajtów. Ponownie odwiedziłem mojego interpretera i skróciłem go o kilkaset bajtów
Wypróbuj online! Dane wejściowe to prosty program cat (
,[.,]
), który wydrukuje sam program.„Zwrot 0” jest definiowany poprzez zakończenie programu w komórce o wartości 0.
Bezbożna kombinacja dwóch programów, które napisałem w przeszłości, quine i self-tłumacza. Pierwsza sekcja to część quine, która pobiera dane i zapełnia taśmę generowaniem danych, a następnie kodem źródłowym. Następny jest interpreter, który bierze program i uruchamia go. Jest to prawie niezmieniona kopia normalnego interpretera, z tą różnicą, że zamiast brać dane bezpośrednio, pobiera dane od początku sekcji danych, ustawiając komórkę na 0, jeśli nie ma już danych wejściowych. Na koniec zakończ bieżącą komórkę programu i uruchom
[]
. Jeśli zwrócona wartość to 0, mój program zakończy się na zero. Jeśli jest coś innego, uruchomi nieskończoną pętlę. Jeśli twój program działa wiecznie,mój program będzie działał wiecznie.Jak to działa:
Część 1: Generowanie danych
Ta część stanowi sekcję danych w quine i jest to zdecydowanie większość kodu o 3270 bajtach. Początek
-
jest znacznikiem początku danych. Każda z nich>+++
reprezentuje znak kodu po tej sekcji.Część 2: Wygeneruj sekcję danych na podstawie danych
Wykorzystuje dane z części pierwszej, aby dodać znaki używane do generowania danych do sekcji kodu. Dodaje on
>
na końcu sekcji kodu i wartość tej komórki wiele plusów.Część 3: Wygeneruj resztę kodu na podstawie danych
Niszczy sekcję danych i dodaje resztę kodu źródłowego do sekcji kodu
Część 4: Pobierz wprowadzony program
Pobiera wprowadzony program. Usuwa postacie niemądre i reprezentuje każdą postać liczbą:
Reprezentuje koniec programu za pomocą
255
.Część 5: Interpretacja danych wejściowych
Interpretuje program. Jedyną różnicą od normalnej jest to, że dane wejściowe są pobierane od początku sekcji kodu zamiast danych wejściowych.
Część 6: Zatrzymaj się, jeśli zwrot nie będzie wynosił 0
Przejdź do końcowej komórki programu i uruchom nieskończoną pętlę, jeśli wartością zwracaną nie jest 0. Jeśli jest to 0, wyjdź z pętli i zakończ na tym samym 0.
Wejścia testowe:
Zawsze zwraca 0 (zatrzymuje i zwraca 0)
Zawsze zwraca 1 (działa wiecznie)
Zwraca wszystkie dane dodane razem, mod 256 (zwraca 211, więc działa wiecznie)
Zwraca 0, jeśli ostatnie dwa znaki kodu są nieskończoną pętlą (
[]
) ( twój program zwraca 0, gdy otrzyma mój program , dlatego mój program zatrzymuje się)Ciekawostka dla tych, którzy wciąż czytają
Jeśli dane wejściowe dla tego programu są kodem źródłowym tego programu, zacznie się on cyklicznie powtarzać, wielokrotnie tworząc self-interpretery, które uruchamiają ten program, a następnie ponownie nadaje mu ten sam program. To daje mi kilka ciekawych pomysłów na tworzenie rzeczywistych programów rekurencyjnych w pieprzeniu mózgu. Zamiast sprawdzania wartości zwracanej i rozpoczynania nieskończonej pętli, jak w tym pytaniu, wartość zwracaną można zapisać i wykorzystać. Prostym przykładem może być program czynnikowy
Oczywiście jest to całkowicie szalony sposób kodowania pieprzenia mózgów, biorąc pod uwagę, że uruchamianie rekurencyjnych interpreterów zwiększy wykładniczo czas działania.
źródło
.
. Chociaż ponieważ nie jest to już kwestia golfa, obsługa całego języka może być bardziej imponująca.