Onde é aceito que uma linguagem precisa ser completa de Turing para ser útil, é realmente possível ter uma linguagem de programação 'útil' que não seja completa de Turing?
Devo esclarecer que isso é especificamente sobre linguagens de 'programação' no sentido tradicional, e não sobre linguagens de marcação ou consulta.
Respostas:
Coq , Agda , HOL e ACL2 são linguagens muito úteis e extremamente poderosas, embora não sejam completas em Turing.
Um recurso comum que os torna não completos de Turing é o fato de que sempre é possível provar o término. Uma limitação muito simples é suficiente: chamadas recursivas são permitidas apenas em termos comprovadamente estruturalmente menores. Portanto, embora não seja possível implementar um intérprete para uma linguagem completa de Turing ou mesmo para a própria linguagem, muitas outras coisas úteis ainda são possíveis, como um compilador C certificado .
fonte
Eu pensaria que o termo "mini-idioma" de Yegge se refere ao fato de que geralmente é útil usar um idioma para problemas específicos, nos quais o idioma não exige perfeição para completar a tarefa, e isso vai ao cerne de como não aprender idiomas completos pode ser útil. https://sites.google.com/site/steveyegge2/language-grubbing
A Wikipedia responde muito bem, alinhada com o que meu intestino disse. Primeiro, eu estava pensando em matemática pura, depois me lembrei do regexp, e a Wikipedia lista o Epigram, que acredito estar na linha da 'matemática pura'.
http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages
Ele também menciona que as representações da estrutura de dados não são linguagens, mas eu acho que o XSLT deve contar como uma representação da computação, XPath talvez não com base no que Yannis disse acima sobre o SQL ser uma linguagem de consulta e não uma linguagem de computação. Talvez T-SQL ou PL / SQL sejam contados como linguagens de computação, já que você pode fazer uma grande quantidade de cálculos usando seus agregados, onde a forma generalizada de SQL talvez não especifique agregados.
fonte
Entendo que o SQL é bastante popular entre os tipos de negócios
fonte
É necessário garantir a integridade de Turing para que um idioma seja adequado para uso como um idioma de uso geral. Mas não é suficiente , ou seja, apenas porque é Turing completo, não é adequado para todos os domínios de problemas:
Por outro lado, uma DSL é adequada para o domínio do problema para o qual foi projetada (assumindo que foi de fato decentemente projetada), mesmo sem a integridade de Turing:
* IIRC foi provado que o HTML com animações CSS é Turing completo, usando-os para implementar o Jogo da Vida de Conway em uma variedade de caixas de seleção. Mas a utilidade do HTML é válida até em navegadores que não suportam animações CSS.
fonte
Na verdade, existem linguagens de programação, nas quais você só pode escrever programas "eficientes". Eficiente nesse sentido significa que todo programa escrito em um idioma representa um idioma em
P
. Bellantoni, Niggl e Schwichtenberg descrevem essa língua aqui .fonte
O pré-processador C não é completo em Turing (por projeto), mas ainda pode implementar um intérprete para um idioma que é completo em Turing (a ordem do idioma, conforme descrito na documentação, é basicamente apenas uma moinho do tipo ML / Scheme puramente funcional e seria relativamente normal - provavelmente bastante agradável de usar - se não fosse a implementação incomum).
O truque subjacente é semelhante aos argumentos acima sobre a implementação de qualquer máquina de Turing em um universo físico finito: o pré-processador C não pode fornecer um número infinito de etapas, ou células de dados, para a linguagem, mas pode:
fornecer um exageradamente grande número dinâmica (2 ^ 64 ou então por padrão), grande o suficiente para resolver a maioria dos problemas realistas usando um processo de expansão exponencial ( murmúrio murmúrio tempo de vida do universo murmúrio ).
use um limite estático arbitrário para o número acima, ou seja, embora o número de etapas deva ser um número finito, você pode alterar qual é o limite específico no momento da "compilação" alterando as configurações estáticas do mecanismo do intérprete. Como não há limite (teórico) no valor real desse limite, ele pode (teoricamente) ser estendido para atender ao requisito de espaço para qualquer programa de encerramento.
Não se deve argumentar que Order é necessariamente "útil" por si só, ou que qualquer mecanismo implementado por CPP seria, mas é uma prova interessante de conceito. Também é supostamente digitado dinamicamente , o que é incomum para esta área.
fonte
Sim, é possível ter uma linguagem útil que não seja completa para Turing. Veja aqui: http://tkatchev.bitbucket.org/tab/examples.html
Outro exemplo de uma linguagem incompleta útil de Turing é o SQL. (E ainda outra são planilhas como Gnumeric ou Excel, embora não sejam realmente linguagens de programação.)
Por que você desejaria uma linguagem que não seja Turing completa: porque isso permite que você faça algumas garantias fortes sobre o comportamento em tempo de execução.
Completar Turing, de maneira clara, significa ter capacidade de recursão. Ter recursão significa ter estruturas potencialmente ilimitadas na memória. Como no mundo real a memória não é infinita, a integridade de Turing requer gerenciamento de memória e / ou coleta de lixo.
Banir a recursão é uma ótima maneira de evitar o problema realmente difícil do gerenciamento de recursos.
Nota bene! Ser Turing incompleto não implica necessariamente que qualquer programa termine necessariamente. Uma linguagem incompleta de Turing pode permitir avaliar uma lista preguiçosa infinita.
fonte
Uma "linguagem de programação sub-Turing" interessante não foi mencionada até agora, então vou adicioná-la.
É chamado "Crema" . Ele se descreve como:
É um nível bastante minimalista e bastante baixo.
Deve parecer meio familiar para os desenvolvedores C.
Foi inicialmente financiado pela Agência de Projetos de Pesquisa Avançada de Defesa (DARPA), mas parece bastante conservado no momento da redação. Mas talvez alguém esteja interessado, no entanto.
fonte