Existe alguma linguagem que possa expressar seu próprio compilador Turing-complete?

Um comentário sobre o tex.SE me fez pensar. A afirmação é essencialmente:

Se eu posso escrever um compilador para o idioma X no idioma X, X é Turing-complete.

Em termos de computabilidade e linguagens formais, é o seguinte:

Se decidir e , então . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Aqui $L_{\mathrm{TM}}$ denota a linguagem de todas as codificações máquina de Turing e $F_L$ denota o conjunto de funções computados por máquinas em $L$ .

Isso é verdade?

computability turing-completeness Rafael
fonte

fechar, pensar / concordar que deve haver algo real próximo disso, como qualquer linguagem "não trivial" ou "suficientemente complexa" que possa expressar seu próprio simulador está completa na TM. um compilador geralmente faz parte de um simulador. é de fato um "padrão de design" encontrado em muitas provas de integridade da MT, mas talvez não tenha sido generalizado / formalizado. talvez um tópico para análise / discussão adicional no Computer Science Chat . suspeita / conjectura, há outras coisas interessantes, algo como "toda linguagem recursiva e recursivamente enumerável não trivial / suficientemente complexa pode ser mapeada / reduzida a qualquer outra".

vzn

Criei uma linguagem esotérica chamada InterpretMe, que não pode fazer nada além de expressar seu próprio intérprete, por isso certamente não é Turing completo.

Ortografia não-contextual

Você pode explicar a segunda afirmação? O que é ? Como esta afirmação está relacionada à primeira?

⟨ M ⟩

$\langle M \rangle$

Reinierpost

@reinierpost normalmente indica o número de , dada a codificação (admissível). Portanto, . Por , o conjunto de funções calculadas pela linguagem das máquinas de Turing.

⟨ 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

Uma maneira melhor de declarar a reivindicação seria: "Se houver uma TM com e , então .

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

Respostas:

A declaração informal não é verdadeira, como mostra a seguinte linguagem de programação. Qualquer sequência de caracteres, digamos, ASCII é um programa válido e o significado de cada programa é "Saída de um programa que apenas gera uma cópia de sua entrada". Portanto, todo programa nesse idioma é um compilador para o idioma, mas o idioma não é completo para Turing.

Não tenho certeza se a sua "versão da teoria da computabilidade" é equivalente, mas também não é verdadeira. Pelo segundo teorema da recursão de Kleene , para qualquer codificação de máquinas de Turing, existe uma TM que aceita sua própria codificação e rejeita todas as outras. ¹ Esta máquina é um contra-exemplo da proposição. Mais concretamente, podemos alcançar o resultado escolhendo uma codificação. Por exemplo, permita que todo número ímpar codifique a máquina definida por "Se minha entrada for ímpar, aceite-a; caso contrário, rejeite" e deixe o número codificar a máquina codificada por em seu próprio esquema de codificação favorito para máquinas de Turing. está na linguagem aceita por $M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ mas não está completo de Turing. $F_L$

¹ segunda recursão de Kleene teorema diz que, para qualquer enumeração das funções recursivas parciais (isto é, para qualquer codificação de programas como inteiros), e qualquer parcial recursiva função , há uma número inteiro tal que é a função que mapeia para . Então, em particular, seja a função que aceita se $(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ e rejeita o contrário. Pelo teorema, existe um número inteiro que codifica o programa . Ou seja, aceita sua própria codificação e rejeita todas as outras entradas. $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$

David Richerby
fonte

Em que sentido todos os programas nessa linguagem são um compilador para essa linguagem? Todo programa é um programa que insere um programa nesse idioma e gera um programa diferente nesse idioma, sim, mas geralmente não são considerados compiladores.

user253751

Eu acho que @immibis tem razão: seu compilador

enquanto todos os programas no idioma são

, então

claramente não está no idioma . Estou esquecendo de algo?

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 Eu (tardiamente) acho que você está certo. Parece que o que eu pretendia escrever era que a semântica de todo programa é apenas "output your input". Isso parece perto o suficiente do que escrevi e provavelmente foi o que eu quis dizer em primeiro lugar. Ou talvez tenha sido super sortudo que a distância de edição da minha resposta errada para a resposta correta fosse tão pequena. :-)

David Richerby

A resposta agora diz "ignora sua entrada e gera uma cópia de sua entrada" - você não pode fazer as duas coisas.

user253751

@immibis eu vou entrar novamente .

David Richerby