Całkowity język, który może interpretować tylko kompletny język Turinga

Każdy język, który nie jest kompletny w Turingu, nie może napisać dla siebie tłumacza. Nie mam pojęcia, gdzie to przeczytałem, ale widziałem, że używał go wiele razy. Wydaje się, że prowadzi to do pewnego rodzaju „ostatecznego” pełnego języka Turinga; te, które mogą tylkobyć interpretowanym przez maszynę Turinga. Języki te niekoniecznie byłyby w stanie obliczyć wszystkie funkcje całkowite, od naturali do naturałów, i niekoniecznie byłyby izomorficzne (to może być języki ostateczne A i B istnieją tak, że istnieje funkcja F, którą A może obliczyć, ale B nie może). Agda może zinterpretować system T Godela, a Agda jest totalny, więc taki ostateczny język powinien być o wiele potężniejszy niż wydaje się system T Godela. Wydaje mi się, że taki język byłby co najmniej równie silny jak agda (choć nie mam dowodów, tylko przeczucie).

Czy przeprowadzono jakieś badania w tym zakresie? Jakie wyniki są znane (a mianowicie czy znany jest „ostateczny” język)?

Premia: Obawiam się, że istnieje przypadek patologiczny, który nie może obliczyć funkcji, które System T Godela mógłby jeszcze interpretować tylko za pomocą maszyny Turinga, ponieważ umożliwia obliczenie niektórych naprawdę dziwnych funkcji. Czy tak jest, czy możemy wiedzieć, że taki język byłby w stanie obliczyć wszystko, co mógłby obliczyć System T Godela?

To źle sformułowane pytanie, więc najpierw zrozummy to. Zamierzam to zrobić w stylu teorii obliczalności. Dlatego użyję liczb zamiast ciągów znaków: fragment kodu źródłowego jest liczbą, a nie ciągiem symboli. To tak naprawdę nie ma znaczenia, możesz zastąpić przez s t r i n g na dole.$\mathbb{N}$$\mathtt{string}$

Niech być funkcją parowania .$\langle m, n\rangle$

Powiedzmy, że język programowania jest podany przez następujące dane:$L = (P, ev)$

1. rozstrzygalne zestaw z „ważnych programów”, a$P \subseteq \mathbb{N}$
2. obliczeniowy i częściowo funkcją .$ev : P \times \mathbb{N} \to \mathbb{N}$

Fakt, że jest rozstrzygalne, oznacza, że ​​istnieje całkowita mapa obliczalna v a l i d : N → { 0 , 1 }, tak że v a l i d ( n ) = $P$$valid : \mathbb{N} \to \{0,1\}$ . Nieformalnie mówimy, że można stwierdzić, czy dany ciąg jest poprawnym fragmentem kodu. Funkcja e v jest w zasadzie tłumaczem naszego języka: e v ( m , n ) uruchamia kod m na wejściu n - wynik może być niezdefiniowany.$valid(n) = 1 \iff n \in P$$ev$$ev(m,n)$$m$$n$

Możemy teraz wprowadzić terminologię:

1. Języka jest całkowita , gdy to całkowita funkcja wszystkich m ∈ P .$n \mapsto ev(m,n)$$m \in P$
2. Język interpretuje język L 2 = ( P 2 , e v 2 ) czy istnieje u ∈ P 1 w taki sposób, e v 1 ( U , ⟨ n , m ⟩ ) ≃ e v 2 ( n , m ) dla wszystkich n ∈ $L_1 = (P_1, ev_1)$ $L_2 = (P_2, ev_2)$$u \in P_1$$ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$$n \in P$i . Tutaj U jest symulator L 2 realizowanego w L 1 . Jest również znany jako program uniwersalny dla L 2 .$m \in \mathbb{N}$$u$$L_2$$L_1$$L_2$

Możliwe są inne definicje „ interpretuje L 2 ”, ale pozwólcie, że nie zajmę się tym teraz.$L_1$$L_2$

Mówimy, że i L 2 są równoważne, jeśli się interpretują.$L_1$$L_2$

Istnieje „najpotężniejszy” język maszyn Turinga (który nazywamy „maszyną Turinga”), w którym n ∈ N jest kodowaniem maszyny Turinga, a φ ( n , m ) to częściowa funkcja obliczeniowa, która „uruchamia kodowanie maszyny Turinga n na wejściu m ”. Ten język może interpretować wszystkie inne języki, oczywiście, ponieważ wymagaliśmy, aby e v była obliczalna.$T = (\mathbb{N}, \varphi)$$n \in \mathbb{N}$$\varphi(n,m)$$n$$m$$ev$

Nasza definicja języków programowania jest bardzo swobodna. Aby spełnić następujące warunki, wymagamy jeszcze trzech warunków:

• implementuje funkcję następczą: istnieje s u c c ∈ P takie, że e v ( s u c c , m ) = m + 1 dla wszystkich m ∈ N ,$L$$succ \in P$$ev(succ,m) = m+1$$m \in \mathbb{N}$
• narzędzia funkcją przekątnej: jest d I a g ∈ P tak, że e v ( d i g , m ) = ⟨ m , m ⟩ wszystkie m ∈ N ,$L$$diag \in P$$ev(diag,m) = \langle m, m \rangle$$m \in \mathbb{N}$
• jest zamknięte w składzie funkcji: jeśli L implementuje f i g, to również implementuje f ∘ g ,$L$$L$$f$$g$$f \circ g$

Klasyczny wynik jest następujący:

Twierdzenie: jeśli język potrafi się interpretować, to nie jest całkowity.

Dowód. Załóżmy, jest uniwersalny program dla ogólnej biuletynie L realizowanego w L , to znaczy dla wszystkich m ∈ P i n ∈ N , e v ( u , ⟨ m , n ⟩ ) ≃ e v ( m , n ) . Ponieważ następca, przekątna i e v ( u , - ) są zaimplementowane w L , podobnie ich skład k $u$$L$$L$$m \in P$$n \in \mathbb{N}$

$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$ $ev(u, {-})$$L$ . Istnieje n 0 ∈ P tak, że e v ( n 0 , k ) ≃ e v ( u , ⟨ K , K ⟩ ) + 1 , a następnie e v ( u , ⟨ N 0 , N 0 ⟩ ) ≃ e v $k \mapsto ev(u, \langle k, k \rangle) + 1$$n_0 \in P$$ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$ Ponieważ nie ma liczbę równą własnego następcy wynika, że L nie jest całkowite lub że L nie interpretuje się. CO BYŁO DO OKAZANIA. $$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$ $L$$L$

Zauważ, że moglibyśmy zastąpić mapę następczą dowolną inną mapą pozbawioną punktów stałych.

Oto małe twierdzenie, które, jak sądzę, rozwiąże nieporozumienie.

Twierdzenie: każdy język całkowity może być interpretowany przez inny język całkowity.

Dowód. Niech będzie językiem całkowitym. Otrzymujemy całkowitą L ', która interpretuje L , przylegając do L jego oceniającego e v . Dokładniej, niech P ' = { ⟨ 0 , n ⟩ | n ∈ P } ∪ { ⟨ 1 , 0 ⟩ } i określenie e v ' a e v ' ( ⟨ b , n ⟩ , $L$$L'$$L$$L$$ev$$P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$$ev'$ Oczywiście, L " oznacza całkowitą ponieważ L jest całkowite. Aby zobaczyć, że L ' może symulować L prostu wziąć u = ⟨ 1 ,

$$ev'(\langle b, n \rangle, m) = \begin{cases} ev(n,m) & \text{if $b = 0$},\\ ev(m_0, m_1) & \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$} \end{cases}$$ $L'$$L$$L'$$L$ , Gdyż wtedy e v ' ( u , ⟨ m , n ⟩ ) ≃ e v ( m , n ) , zgodnie z wymaganiami. CO BYŁO DO OKAZANIA.$u = \langle 1, 0\rangle$$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$

Ćwiczenia: [dodano 27.06.2014] Język zbudowane powyżej nie jest zamknięta na podstawie kompozycji. Napraw dowód twierdzenia, aby L ' spełniał dodatkowe wymagania, jeśli L tak.$L'$$L'$$L$

Innymi słowy, nigdy nie potrzebujesz pełnej mocy maszyn Turinga do interpretacji całkowitego języka - wystarczy nieco mocniejszy całkowity język L ' . Język L ' jest ściśle potężniejszy niż L, ponieważ interpretuje L , ale L nie interpretuje siebie.$L$$L'$$L'$$L$$L$$L$

Każdy język, który nie jest kompletny w Turingu, nie może napisać dla siebie tłumacza.

To stwierdzenie jest niepoprawne. Zastanów się nad językiem programowania, w którym semantyką każdego łańcucha jest „Ignoruj ​​wprowadzanie i natychmiast zatrzymaj”. Ten język programowania nie jest kompletny, ale każdy program jest tłumaczem języka.