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

12

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 .MLLTMMLFL=RE

Aqui LTM denota a linguagem de todas as codificações máquina de Turing e FL denota o conjunto de funções computados por máquinas em L .

Isso é verdade?

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
1
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
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. MMLTM={MM is a Turing machine}FLL
Raphael
Uma maneira melhor de declarar a reivindicação seria: "Se houver uma TM com e , então .M L L M = G F G = R EMMLLM=LFL=RE
Raphael

Respostas:

13

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. 1 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  2 x codificar a máquina codificada por  x em seu próprio esquema de codificação favorito para máquinas de Turing. M  está na linguagem  L aceita por  MM2xxMLMmas  não está completo de Turing.FL


1 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  Q ( x , y ) , há uma número inteiro  p tal que ϕ p  é a função que mapeia y para Q ( p , y ) . Então, em particular, seja Q a função que aceita se x = y(ϕi)i0Q(x,y)pϕpyQ(p,y)Qx=ye rejeita o contrário. Pelo teorema, existe um número inteiro  que codifica o programa ϕ p ( y ) = Q ( p , y ) . Ou seja, accepts p aceita sua própria codificação  p e rejeita todas as outras entradas.pϕp(y)=Q(p,y)ϕpp

David Richerby
fonte
1
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
1
Eu acho que @immibis tem razão: seu compilador é c ( P ) = { x r e t u r n P } enquanto todos os programas no idioma são P ( x ) = P , então c claramente não está no idioma . Estou esquecendo de algo? cc(P)={xreturn P}P(x)=Pc
Raphael
1
@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
1
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