Czy jakikolwiek język, który może wyrazić swój własny kompilator Turing, jest kompletny?

Komentarz do tex.SE mnie zastanawiał. Oświadczenie to zasadniczo:

Jeśli mogę napisać kompilator dla języka X w języku X, to X jest Turing-complete.

Pod względem obliczalności i języków formalnych jest to:

Jeśli decyduje i , to . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Tutaj oznacza języka dla wszystkich maszyn Turinga kodowania i oznacza zbiór funkcji obliczonych przez maszyny w . $L_{\mathrm{TM}}$ $F_L$ $L$

Czy to prawda?

computability turing-completeness Raphael
źródło

zamknij, pomyśl / zgódź się, że musi istnieć jakaś prawdziwa bliskość tego, jak każdy „nietrywialny” lub „wystarczająco złożony” język, który może wyrazić swój własny symulator, jest kompletny. kompilator jest zazwyczaj częścią symulatora. jest to rzeczywiście „wzorzec projektowy” znaleziony w wielu dowodach kompletności TM, ale może nie został uogólniony / sformalizowany. może temat do dalszej analizy / dyskusji na czacie informatyki . podejrzany / przypuszczalny jest inny interesujący temat, taki jak: „każdy nietrywialny / wystarczająco złożony język rekurencyjny i rekurencyjnie wymienny może być odwzorowany / zredukowany do każdego innego”.

dniu

Stworzyłem ezoteryczny język o nazwie InterpretMe, który nie może nic zrobić poza wyrażeniem własnego tłumacza, więc na pewno nie jest on kompletny.

Pisownia bezkontekstowa

Czy możesz wyjaśnić drugie stwierdzenie? Co jest

? Jak to zdanie jest powiązane z pierwszym?

⟨ M ⟩

$\langle M \rangle$

reinierpost

@reinierpost

zwykle oznacza liczbę

, ponieważ niektóre z nich (dopuszczalne) kodującego. Stąd,

. Przez

oznaczam zestaw funkcji obliczonych przez język

maszyn Turinga.

⟨ M ⟩

$\langle M \rangle$

M

$M$

L_{T M} = {⟨ M ⟩ ∣ M is a Turing machine}

$L_{\mathrm{TM}} = \{ \langle M \rangle \mid M \text{ is a Turing machine}\}$

F_{L}

$F_L$

L

$L$

Raphael

Lepszym sposobem zawierać żądanie może być: „Jeśli jest TM

, wtedy

M

$M$

⟨ M ⟩ \in L

$\langle M \rangle \in L$

L_{M} = L

$L_M = L$

F_{L} = R E

$F_L = \mathrm{RE}$

Raphael

Nieformalne oświadczenie nie jest prawdziwe, jak pokazuje poniższy język programowania. Każdy ciąg, powiedzmy, znaków ASCII jest poprawnym programem, a znaczenie każdego programu brzmi: „Wyprowadź program, który po prostu wypisuje kopię swojego wejścia”. Zatem każdy program w tym języku jest kompilatorem języka, ale język nie jest kompletny w Turingu.

Nie jestem pewien, czy twoja „wersja teorii obliczeń” jest równoważna, ale też nie jest prawdą. Zgodnie z drugim twierdzeniem Kleene o rekurencji dla dowolnego kodowania maszyn Turinga istnieje TM, która akceptuje własne kodowanie i odrzuca wszystkie inne. ¹ To urządzenie jest kontrprzykładem do zdania. Mówiąc konkretniej, możemy osiągnąć wynik, wybierając kodowanie. Na przykład, niech każdy nieparzysty numer koduje maszynę zdefiniowaną przez „Jeśli moje dane wejściowe są nieparzyste, zaakceptuj ją, w przeciwnym razie odrzucaj” i niech cyfra koduje maszynę zakodowaną przez w twoim ulubionym schemacie kodowania dla maszyn Turinga. jest w języku zaakceptowany przez $M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ ale nie jest ukończony przez Turinga. $F_L$

¹ sekundy rekursji KLEENE Twierdzenie mówi, że na każdy wyliczenie częściowych funkcji rekurencyjnej (czyli dla każdego kodowania programów jako liczby całkowite) oraz każde częściowe funkcji rekurencyjnej nie jest liczba całkowita taka, że jest funkcją odwzorowującą na . W szczególności niech będzie funkcją, która akceptuje, jeśli $(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ i odrzuca inaczej. Według twierdzenia istnieje liczba całkowita która koduje program . Oznacza to, że przyjmuje własne kodowanie i odrzuca wszystkie inne dane wejściowe. $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$

David Richerby
źródło

W jakim sensie każdy program w tym języku jest kompilatorem tego języka? Każdy program jest programem, który wprowadza program w tym języku i generuje inny program w tym języku, tak, ale quines zasadniczo nie jest uważany za kompilator.

user253751

Myślę, że @immibis ma rację: twój kompilator

podczas gdy wszystkie programy w języku są

, więc

najwyraźniej nie jest w języku . Czy coś brakuje?

c

$c$

c (P) = {x \Rightarrow r e t u r n P}

$c(P) = \{ x \Rightarrow \mathtt{return}\ P \}$

P (x) = P

$P(x) = P$

c

$c$

Raphael

@immibis Myślę (z opóźnieniem), że masz rację. Wygląda na to, że chciałem napisać, że semantyka każdego programu to po prostu „wyjście danych wejściowych”. To wydaje się wystarczająco bliskie temu, co napisałem, że prawdopodobnie to właśnie chciałem powiedzieć w pierwszej kolejności. A może miałem szczęście, że odległość edytowania od mojej błędnej odpowiedzi do poprawnej odpowiedzi była tak mała. :-)

David Richerby,

Odpowiedź mówi teraz: „ignoruje dane wejściowe i wysyła kopię danych wejściowych” - nie możesz zrobić obu tych rzeczy.

user253751,

@immibis Wrócę ponownie .

David Richerby,

Czy jakikolwiek język, który może wyrazić swój własny kompilator Turing, jest kompletny?

Odpowiedzi: