To jest policjanci i złodzieje wyzwanie polegające na zdefiniowaniu języków i udowodnieniu, że są one kompletne.

To jest wątek gliniarzy. Wątek rabusiów jest tutaj .

Gliny

Jako policjant przygotujesz dwie rzeczy:

• Formalna specyfikacja języka programowania lub innego systemu obliczeniowego. (Systemy obliczeniowe są zdefiniowane poniżej.)

• Dowód na to, że twój system jest kompletny, według nieco ścisłej definicji poniżej.

Opublikujesz specyfikację swojego języka, a złodzieje spróbują go „złamać”, udowadniając jego kompletność. Jeśli zgłoszenie nie zostanie złamane w ciągu tygodnia, możesz oznaczyć je jako bezpieczne i opublikować dowód. (Twoja odpowiedź może zostać unieważniona, jeśli ktoś znajdzie błąd w twoim dowodzie, chyba że możesz go naprawić).

To jest konkurs popularności, więc zwycięzcą zostanie odpowiedź, która ma najwięcej głosów, i która nie jest pęknięta ani unieważniona. Wyzwanie jest otwarte - nie przyjmuję odpowiedzi.

Ze względu na to wyzwanie system obliczeniowy zostanie zdefiniowany jako cztery rzeczy:

• „Zestaw programów” P. Będzie to niezliczony zestaw nieskończony, np. Łańcuchy, liczby całkowite, drzewa binarne, konfiguracje pikseli na siatce itp. (Ale patrz ograniczenie techniczne poniżej).

• „Zestaw danych wejściowych” I, który będzie również licznym zestawem nieskończonym i nie musi być takim samym zestawem jak P(choć może być).

• „Zestaw wyjściowy” O, który podobnie będzie licznym zestawem nieskończonym i może, ale nie musi być taki sam jak PlubI

• Deterministycznej, mechanistyczny procedura wytwarzania wyjście oz programu pi wprowadzania i, w którym p, ii osą członkami P, Ii Oodpowiednio. Ta procedura powinna być taka, aby mogła być w zasadzie zaimplementowana na maszynie Turinga lub innym abstrakcyjnym modelu obliczeniowym. Procedura może oczywiście nie zostać zatrzymana, w zależności od programu i jego wkładu.

Zestawy P, Ii Omusi być taka, że można wyrazić je jako ciągi w przeliczalnych sposób. (W przypadku najbardziej rozsądnych wyborów nie będzie to miało znaczenia; ta reguła istnieje, aby uniemożliwić wybranie dziwnych zestawów, takich jak zestaw maszyn Turinga, które się nie zatrzymują).

Kompletność Turinga zostanie zdefiniowana następująco:

• Dla każdej obliczalnej funkcji częściowej fod Ido Oistnieje program pw Ptaki sposób, że podany pi wprowadzony i, wyjście ma wartość f(i)if f(i). (W przeciwnym razie program się nie zatrzyma.)

Słowo „obliczalny” w powyższej definicji oznacza „można obliczyć za pomocą maszyny Turinga”.

Zauważ, że ani reguła 110, ani bitowy znacznik cykliczny nie jest zgodny z Turinga, ponieważ nie mają wymaganej struktury wejścia-wyjścia. Rachunek lambda jest zakończony według Turinga, o ile zdefiniujemy Ii Obędziemy liczbami kościelnymi . (Nie jest to kompletna metoda Turinga, jeśli weźmiemy Ii Obędziemy ogólnie wyrażeniami lambda.)

Pamiętaj, że nie musisz podawać implementacji swojego języka, ale jeśli chcesz, możesz dołączyć ją do swojej odpowiedzi. Nie należy jednak polegać na implementacji, aby w jakikolwiek sposób definiować język - specyfikacja powinna być sama w sobie kompletna, a jeśli istnieje sprzeczność między specyfikacją a implementacją, należy ją traktować jako błąd w implementacji.

Arytmetyka z zasłoniętymi oczami

Prawdopodobnie dość łatwy język na początek, relatywnie mówiąc. (Istnieją ograniczenia dotyczące tego, jak trudny mogę uczynić język, ponieważ sam muszę to udowodnić - Turing - ukończ!)

Dla tego języka zestaw programów jest zestawem programów arytmetycznych z zasłoniętymi oczami, jak podano w sekcji „program” poniżej, zestaw wejściowy jest zbiorem liczb całkowitych dodatnich, a zestaw wyjściowy jest zbiorem liczb całkowitych (cały zestaw, nie tylko dodatnie liczby całkowite).

Ten język jest dość interesujący - może nawet praktycznie przydatny - ponieważ ma mniej lub bardziej całkowity brak kontroli, ponieważ jest całkowicie oparty na obliczeniach na liczbach, których nie widać. To czyni go potencjalnie użytecznym jako język do implementacji programów w systemach homomorficznego szyfrowania .

Specyfikacja

Blindfolded Arithmetic to ezoteryczny język programowania o następujących specyfikacjach:

Przechowywanie danych

Stan działającego programu arytmetycznego z zasłoniętymi oczami składa się z sześciu zmiennych, z których każda może przechowywać liczbę całkowitą. (Nie ma żadnych ograniczeń na to jak duże lub małe Liczby te mogą się, w szczególności, mogą iść negatyw). Zmienne są nazywane a, b, c, d, e, i i.

Na początku programu, aaby ewłącznie każdy zainicjowany na 0 i ijest inicjowany do liczby całkowitej dodatniej zaczerpnięte z danych wprowadzanych przez użytkownika. (Jeśli dane wejściowe nie są dostępne, iinicjowane jest na 1.)

Jeśli program zaprzestanie wykonywania (może to nastąpić tylko z powodu dzielenia przez zero), wartość iwyjściowa bezpośrednio przed próbą podziału jest używana jako wynik programu.

Program

Program arytmetyczny z zasłoniętymi oczami to lista poleceń, z których każda ma jedną z następujących postaci (gdzie v można zastąpić dowolną nazwą zmiennej, potencjalnie inną nazwą za każdym razem, gdy jest używana):

• v = v + v
• v = v - v
• v = v * v
• v = v / v

Zauważ, że każdy operand poleceń musi być zmienną; ten język nie pozwala na użycie literalnych liczb całkowitych.

Wykonanie programu odbywa się poprzez uruchomienie każdego z poleceń w sekwencji, a następnie zapętlenie z powrotem do początku i kontynuowanie uruchamiania poleceń w sekwencji, ad infinitum (lub dopóki nie nastąpi próba podzielenia przez zero, co zakończy program) .

Każde polecenie ma taką samą semantykę, jakiej można się spodziewać po notacji, która nie różni się od tej używanej przez większość praktycznych języków programowania: pobierane są wartości drugiej i trzeciej zmiennej podanej w poleceniu, operacja arytmetyczna (dodawanie / odejmowanie / multiply / divide odpowiednio dla czterech form poleceń) jest do nich stosowany, a wynikowa wartość przechowywana w pierwszej zmiennej. Dzielenie tutaj jest dzieleniem całkowitym, zaokrąglanym w kierunku 0.

Nie ma żadnego przepływu sterującego innego niż wyjście z programu; polecenia zawsze zmieniają się kolejno, aż do wystąpienia podziału przez zero (jeśli występuje) i kończy program. W szczególności nie ma możliwości bezpośredniego odczytu zmiennych, a jedynie wykorzystania ich jako źródła obliczeń, których wyniki wpływają na wartości przypisane innym zmiennym.