Você pode especificar uma linguagem de programação sem implementação?

11

É teoricamente possível especificar uma linguagem de programação para a qual não existe implementação? Uma linguagem de programação é uma maneira de definir funções. Uma implementação significa um método para executar um determinado programa nesse idioma em uma determinada entrada para a saída da função correspondente ao programa nessa entrada.

Quais são os requisitos mínimos de um idioma assim?

formal-languages computability programming-languages Kaveh
fonte
3
O que é uma "implementação" de um idioma?
Raphael
@Raphael: Foi você quem mudou o idioma da programação para o idioma. Antes da sua edição, estava claro o significado de uma implementação de uma linguagem.
Tsuyoshi Ito
@TsuyoshiIto: Não é bem assim; Apenas adaptei o título para corresponder à pergunta, que foi alterada em cstheory.SE. Eu mudei de volta, mas ainda não está claro o que isso significa. Um compilador? Um interprete? De qualquer forma, migrar uma pergunta para cá com quase um ano de idade e por um usuário que aparentemente nunca revisou a pergunta foi mal recomendada.
Raphael
@Raphael: Perguntando "o que é uma implementação de uma linguagem?" depois de remover todas as pistas estava simplesmente além do meu entendimento. Mas concordo que a questão não ficou clara desde o início.
Tsuyoshi Ito
Eu acho que sua suposta definição de "linguagem de programação" é mal concebida. Deveria pelo menos ser alterado substituindo "funções" por "funções computáveis". Caso contrário, não está claro por que você escolheria chamar o idioma de "Idioma de programação". Depois que você a altera, a pergunta fica sem sentido, porque não existem "linguagens de programação para as quais nenhuma implementação possa existir".
precisa

Respostas:

7

Geralmente, implementar uma linguagem de programação é, pelo menos, fornecer um intérprete em uma linguagem (ou um compilador a uma linguagem) que não seja mais do que Turing-complete.

Usando esta "definição", podemos especificar uma linguagem de programação como esta:

  • existe apenas um programa possível HALT;

  • especificação de HALT: é uma função que resolve o problema de parada .

A implementação dessa linguagem de programação requer a solução do problema de parada com a implementação. (O que é impossível, pois nossa implementação não deve ser mais poderosa que uma máquina de Turing).

A especificação lida com a lógica e, portanto, pode exigir muito mais. Outra especificação que será impossível de implementar é "false". (Ou qualquer sentença contraditória na especificação) Mas isso não parece uma especificação, e é por isso que usei o exemplo do problema de parada.

jmad
fonte
1
Generalizado: Qualquer linguagem que especifique uma função que resolva um problema indecidível não pode ser implementada.
EdA-qa mort-ora-y
@ edA-qamort-ora-y Tecnicamente, poderia ser implementado. Você não pode decidir o Problema da Parada, mas uma TM pode simular outra máquina e aceitar se ela parar; o idioma aceito por essa TM é exatamente o idioma das (codificações de) máquinas que são interrompidas. Mas, para fins práticos, normalmente gostamos de garantir que as operações primitivas das linguagens de programação terminem! (pelo menos no "sensata" de entrada)
Ben
1
Sim, as funções de uma língua deve ter uma complexidade de tempo inferior a :)O(∞)
EDA-qa mort-ora-y
@ edA-qamort-ora-y nem sempre é verdade. Por exemplo, na semântica denotacional Haskell e, portanto, é no modelo de custo óbvio. Na prática, todas as implementações do Haskell diferenciam entre exceção e divergência, e o GHC possui uma semântica de operação especificada que explica como as exceções devem funcionar. Mas, seria possível ter uma implementação em conformidade que se repetisse para sempre na divisão por zero! 1/0 ohms ( ∞ )≡ let loop = loop in loopΩ(∞)
Philip JF
3

Apenas uma observação lateral curiosa: o mecanismo de modelo C ++ é completo em Turing

Teorema 1: Na ausência de limites de instanciação, os modelos C ++ estão completos em Turing.

Corolário 1: Na ausência de limites de instanciação, se um compilador C ++ será interrompido ao compilar um determinado programa é indecidível.

... então o próprio C ++ pode ser considerado uma linguagem de programação para a qual não existe "implementação" ... :-D

Vor
fonte
Então, um "compilador" C poderia ser usado como intérprete se alguém não se importasse com o código gerado, mas simplesmente com o diagnóstico produzido?
Supercat
Sim, como mostrado no documento, o compilador interrompe com uma lista de erros que correspondem ao histórico de computação da máquina de Turing (e sua configuração final de fita). Obviamente, a entrada não pode ser interativa (ela deve ser codificada no código-fonte antes de executar o compilador).
Vor
2

Não está claro o que você quer dizer com "linguagem de programação" e "implementação de uma linguagem". Você precisa fornecer definições rigorosas desses dois para obter uma resposta.

Uma linguagem de "programação" para calcular funções (parciais) sobre cadeias de caracteres pode ser considerada um mapeamento de para . Enquanto uma das funções desconectáveis ​​estiver no intervalo, o idioma não poderá ser implementado.2 Σ *Σ∗2Σ∗

Por exemplo, pode-se usar aritmética de primeira ordem. Então é fácil definir funções que não são computáveis, por exemplo, a função que fornece um TM , decide se retorna em todas as entradas. Isso pode ser facilmente expresso por uma fórmula de primeira ordem na linguagem da aritmética. Por outro lado, é um resultado fácil na teoria da computabilidade que ela não seja uma função computável; portanto, não pode haver implementação da função.M 0MM0

Mas esse não é o tipo de linguagem de especificação que as pessoas querem dizer quando usam a frase "linguagem de programação". Uma linguagem de programação costuma ser uma linguagem para expressar funções computáveis ​​(processos, ...) e comunicar as instruções a uma máquina e, portanto, existe uma TM que pode simular esses programas e produzir seus resultados. Portanto, de certa forma, ter uma linguagem de programação que não pode ser implementada não é significativo.

(Meu palpite é que você provavelmente está confundindo linguagens de programação com linguagens de especificação ou linguagens formais . De qualquer forma, podemos definir linguagens que não são computáveis.)

Kaveh
fonte
Tenho certeza de que "linguagem de programação" significa uma linguagem de programação da maneira como normalmente falaríamos sobre ela, e "uma implementação de uma linguagem" significa um ambiente para executar programas nessa linguagem em computadores reais. A questão não está formalizada , mas certamente não está clara? Eu posso escrever facilmente uma especificação para uma nova linguagem de programação sem me preocupar em implementá-la; a questão é simplesmente perguntar se é possível fazê-lo de tal maneira que o idioma não possa ser implementado.
Ben
@ Ben, se você olhar para a pergunta original na história, verá que não há programação de palavras na pergunta apenas no título. A pergunta postada pelo OP é definitivamente clara. ps: Eu estaria interessado em uma definição rigorosa (não precisa ser formal) do que é uma linguagem de programação. Não podemos provar resultados negativos sobre linguagens de programação apenas com base em intuição e exemplos. Se você tiver referência para uma definição, publique-a como uma edição ou comentário para a pergunta.
Kaveh
É justo, embora o SE afirme que você o respondeu há 9 horas, muito tempo depois de ter sido migrado e editado. Ainda assim, eu faria a mesma interpretação com base na pergunta original. Quanto à definição de uma linguagem de programação, eu diria que uma linguagem óbvia é uma gramática formal, mais a redução de algum outro modelo computacional bem compreendido (cálculo lambda, máquina de turing etc.) ou uma semântica operacional rigorosa. O modelo de redução tornaria a resposta a essa pergunta um trivial "não", obviamente.
Ben
1

Existem muitas linguagens especificadas sem uma implementação, por exemplo, o Algol 60 deveria ser uma linguagem para escrever algoritmos, não para ser implementada. Algumas das muitas linguagens "apenas por diversão" foram especificadas muito antes da implementação, o Intercal vem à mente.

vonbrand
fonte