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

Комментарий к tex.SE заставил меня задуматься. Утверждение по существу:

Если я могу написать компилятор для языка X на языке X, то X полон по Тьюрингу.

В терминах вычислимости и формальных языков это:

Если решает , и , то . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Здесь обозначает язык всех машины Тьюринга кодирования и обозначает множество функций , вычисленных машин в . $L_{\mathrm{TM}}$ $F_L$ $L$

Это правда?

computability turing-completeness Рафаэль
источник

близко, подумайте / согласитесь, должен быть какой-то реальный смысл, близкий к этому, например, любой "нетривиальный" или "достаточно сложный" язык, который может выразить свой собственный симулятор, является ТМ полным. Компилятор обычно является частью симулятора. это действительно «шаблон проектирования», встречающийся во многих доказательствах полноты ТМ, но, возможно, он не был обобщен / формализован. Может быть, тема для дальнейшего анализа / обсуждения в чате информатики . подозрение / гипотеза, есть еще кое-что интересное, например, «каждый нетривиальный / достаточно сложный рекурсивный и рекурсивно перечислимый язык может быть отображен / приведен к любому другому».

vzn

Я создал эзотерический язык под названием InterpretMe, который ничего не может сделать, кроме как выразить свой собственный интерпретатор, поэтому он определенно не завершен по Тьюрингу.

неконтекстовое правописание

Можете ли вы объяснить второе утверждение? Что такое

? Как это утверждение связано с первым?

⟨ M ⟩

$\langle M \rangle$

reinierpost

@reinierpost

, как правило , обозначает число

, учитывая некоторые (допустимо) кодирование. Следовательно,

. Через

я обозначаю множество функций, вычисленных языком

машин Тьюринга.

⟨ 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$

Рафаэль

Лучший способ заявить требование будет: «Если есть ТМ

, то

M

$M$

⟨ M ⟩ \in L

$\langle M \rangle \in L$

L_{M} = L

$L_M = L$

F_{L} = R E

$F_L = \mathrm{RE}$

Рафаэль

Ответы:

Неформальное утверждение не соответствует действительности, как показано на следующем языке программирования. Любая строка, скажем, символов ASCII, является допустимой программой, и смысл каждой программы: «Вывести программу, которая просто выводит копию своего ввода». Таким образом, каждая программа на этом языке является компилятором для языка, но язык не является тьюрингово-полным.

$M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ $F_L$

$(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$

Дэвид Ричерби
источник

В каком смысле каждая программа на этом языке является компилятором для этого языка? Каждая программа - это программа, которая вводит программу на этом языке и выводит другую программу на этом языке, да, но квинны обычно не считаются компиляторами.

user253751

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$

@immibis Я (запоздало) думаю, что ты прав. Кажется, что я хотел написать, это то, что семантика каждой программы - это просто «вывод вашей информации». Это кажется достаточно близким к тому, что я написал, что это было, вероятно, то, что я хотел сказать в первую очередь. Или, может быть, мне очень повезло, что расстояние редактирования от моего неправильного ответа до правильного ответа было таким маленьким. :-)

Дэвид Ричерби

Ответ теперь говорит: «игнорирует ввод и выводит копию ввода» - вы не можете сделать и то, и другое.

user253751

@immibis Я приду снова .

Дэвид Ричерби