Общий язык, который может интерпретировать только полный язык Тьюринга

Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор. Я понятия не имею, где я это прочитал, но я видел, что это использовалось несколько раз. Кажется, что это порождает своего рода «окончательный» нетуринговский законченный язык; те, которые могут толькоинтерпретироваться машиной Тьюринга. Эти языки не обязательно будут способны вычислять все полные функции от натуральных до натуральных, и при этом они не обязательно будут изоморфными (то есть, возможно, конечные языки A и B существуют так, что существует функция F, которую A может вычислять, но B не может). Агда может интерпретировать систему Т Годеля, а Агда является тотальной, так что такой конечный язык должен быть строго более мощным, чем могло бы показаться системе Т Годеля. Мне кажется, что такой язык был бы по крайней мере таким же мощным, как и агда (хотя у меня нет доказательств, только догадка).

Было ли проведено какое-либо исследование в этом направлении? Какие результаты известны (а именно такой «конечный» язык известен)?

Бонус: я обеспокоен тем, что существует патологический случай, который не может вычислить функции, которые System T Годеля еще может интерпретировать только машиной Тьюринга, поскольку она позволяет вычислять некоторые действительно странные функции. Так ли это, или мы можем знать, что такой язык сможет вычислять все, что может вычислить Godel System T?

Это плохо сформулированный вопрос, поэтому давайте сначала разберемся с ним. Я собираюсь сделать это в стиле теории вычислимости. Таким образом, я буду использовать числа вместо строк: часть исходного кода является числом, а не строкой символов. Это действительно не имеет значения, вы можете заменить с й т г я н г в течение ниже.$\mathbb{N}$$\mathtt{string}$

Пусть быть функцией спаривание .$\langle m, n\rangle$

Допустим, что язык программирования задается следующими данными:$L = (P, ev)$

1. разрешимо множество из «действующих программ», и$P \subseteq \mathbb{N}$
2. вычислимы и частичная функция .$ev : P \times \mathbb{N} \to \mathbb{N}$

Тот факт, что разрешимо, означает, что существует полное вычислимое отображение v a l i d : N → { 0 , 1 } такое, что v a l i d ( n ) = $P$$valid : \mathbb{N} \to \{0,1\}$ . Неформально мы говорим, что можно определить, является ли данная строка допустимым фрагментом кода. Функция e v по сути является интерпретатором для нашего языка: e v ( m , n ) выполняет код m на входе n - результат может быть неопределенным.$valid(n) = 1 \iff n \in P$$ev$$ev(m,n)$$m$$n$

Теперь мы можем ввести некоторую терминологию:

1. Язык является всего , если является полной функцией для всех м ∈ P .$n \mapsto ev(m,n)$$m \in P$
2. Язык интерпретирует язык L 2 = ( Р 2 , е v 2 ) , если существует у ∈ Р 1 таким образом, что е v 1 ( U , ⟨ п , м ⟩ ) ≃ е v 2 ( n , m ) для всех 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$и . Здесь u - симулятор для L 2, реализованный в L 1 . Он также известен как универсальная программа для L 2 .$m \in \mathbb{N}$$u$$L_2$$L_1$$L_2$

Возможны и другие определения « интерпретирует L 2 », но позвольте мне не вдаваться в подробности.$L_1$$L_2$

Мы говорим, что и L 2 эквивалентны, если они интерпретируют друг друга.$L_1$$L_2$

Существует «самый мощный» язык машин Тьюринга (который вы называете «машиной Тьюринга»), в котором n ∈ N - это кодировка машины Тьюринга, а φ ( n , m ) - частично вычислимая функция, которая «запускает машину Тьюринга, кодирующую n на входе m ». Этот язык может интерпретировать все другие языки, очевидно, так как мы требовали, чтобы e v была вычислимой.$T = (\mathbb{N}, \varphi)$$n \in \mathbb{N}$$\varphi(n,m)$$n$$m$$ev$

Наше определение языков программирования очень расслаблено. Чтобы выполнить следующее, давайте потребуем еще три условия:

• реализует функцию-преемник: существует такое s u c c ∈ P , что e v ( s u c c , m ) = m + 1 для всех m ∈ N ,$L$$succ \in P$$ev(succ,m) = m+1$$m \in \mathbb{N}$
• реализует диагональ функция: есть d I в г ∈ P такоечто е V ( д я г , т ) = ⟨ м , м ⟩ для всех м ∈ N ,$L$$diag \in P$$ev(diag,m) = \langle m, m \rangle$$m \in \mathbb{N}$
• замкнуто относительно композиции функций: если L реализует f и g, то оно также реализует f ∘ g ,$L$$L$$f$$g$$f \circ g$

Классический результат таков:

Теорема: если язык может интерпретировать сам себя, то он не тотален.

Доказательство. Предположим , что является универсальная программа для полного LANGAUGE L , реализованного в L , то есть, для всех т Е Р и п Е N , е V ( U , ⟨ м , п ⟩ ) ≃ е v ( т , п ) . Как преемник, диагональ, и e v ( u , - ) реализованы в L , так же как и их композиция k $u$$L$$L$$m \in P$$n \in \mathbb{N}$

$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$ $ev(u, {-})$$L$ . Там существует п 0 ∈ P такоечто е v ( п 0 , к ) ≃ е V ( U , ⟨ к , к ⟩ ) + 1 , а затем е V ( U , ⟨ п 0 , п 0 ⟩ ) ≃ е 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$ Поскольку существует число не равна его собственного преемника, то отсюда следуетчто L не является полным иличто L не интерпретирует себя. QED. $$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$

Заметьте, что мы могли бы заменить карту-преемник любой другой картой без фиксированной точки.

Вот небольшая теорема, которая, я думаю, устранит недоразумение.

Теорема. Каждый общий язык может быть интерпретирован другим общим языком.

Доказательство. Пусть тотальный язык. Мы получаем итоговое значение L ′, которое интерпретирует L , присоединяя к L его вычислитель e v . Точнее, пусть Р ' = { ⟨ 0 , п ⟩ | п ∈ P } ∪ { ⟨ 1 , 0 ⟩ } и определим е V ' , как е V ' ( ⟨ б , н ⟩ , $L$$L'$$L$$L$$ev$$P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$$ev'$ Очевидно, что L ' является полнымпотому что L является полным. Для того, чтобы видетьчто L ' может имитировать L просто взять у = ⟨ 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$ , С тех пор е V ' ( U , ⟨ м , н ⟩ ) ≃ е V ( т , п ) ,мере необходимости. QED.$u = \langle 1, 0\rangle$$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$

Упражнение: [добавлено 2014-06-27] Построенный выше язык не замкнут по составу. Закрепить доказательство теоремы , так что L ' удовлетворяет дополнительные требования , если L делает.$L'$$L'$$L$

Другими словами, вам никогда не понадобится вся мощь машин Тьюринга для интерпретации общего языка - достаточно более мощного общего языка L ′ . Язык L ′ строго более мощный, чем L, потому что он интерпретирует L , но L не интерпретирует себя.$L$$L'$$L'$$L$$L$$L$

Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор.

Это утверждение неверно. Рассмотрим язык программирования, в котором семантикой каждой строки является «Игнорировать ваш ввод и немедленно остановиться». Этот язык программирования не является полным по Тьюрингу, но каждая программа является интерпретатором языка.