É realmente possível ter uma linguagem de programação 'útil' que não seja Turing completa?

Coq , Agda , HOL e ACL2 são linguagens muito úteis e extremamente poderosas, embora não sejam completas.

Uma característica comum que os torna não-Turing-completos é o fato de que sempre é possível provar a terminação. Uma limitação muito simples é suficiente: chamadas recursivas só são permitidas 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 o própria linguagem muitas outras úteis coisas ainda são possíveis, como um compilador C certificado .

A Wikipédia responde isso muito bem, de acordo com o que meu instinto disse. Primeiro eu estava pensando em matemática pura, então eu me lembrei de regexp, e a Wikipedia listou o epigrama que eu acredito que estaria na veia da 'pura matemática'.

link

Non-Turing-complete languages

Many computational languages exist which are not Turing complete. One such example is the set of regular languages, most commonly regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata and context-free grammars, which are commonly used to generate parse trees in an initial stage of program compiling. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions, or a series of mathematical formulae in a spreadsheet with no cycles.[citation needed] In total functional programming languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory, whereas Epigram uses dependent types.

Data languages

The notion of Turing-completeness does not apply to languages such as XML, JSON, YAML and S-expressions, because they are typically used to represent structured data, not describe computation. These are sometimes referred to as markup languages, or more properly as "data description languages".

Ele também menciona que as representações da estrutura de dados não são linguagens, mas eu pensaria que o XSLT deveria contar como uma representação de computação, XPath talvez não baseado no que Yannis disse acima sobre SQL ser uma linguagem de consulta e não uma linguagem de computação. Talvez T-SQL ou PL / SQL contam como linguagens de computação, já que você pode fazer uma grande quantidade de computações usando seus agregados, onde a forma generalizada de SQL não especifica agregados, talvez.

Eu entendo que o SQL é bastante popular entre os tipos de negócios

A completude de Turing é necessária para que um idioma seja adequado para uso como linguagem de propósito geral. Mas não é suficiente , ou seja, só porque é Turing completo, não é adequado para todos os domínios do problema:

• O espaço em branco é comprovadamente Turing completo, mas é obviamente inadequado para qualquer domínio de problema fora do entretenimento do programador.
• Os modelos C ++ foram provados como Turing completo, mas você nunca escreveria programas inteiros com eles.

Por outro lado, um DSL é adequado para o domínio do problema para o qual foi projetado (supondo que ele tenha sido decentemente projetado ), mesmo sem Turing completude:

• HTML ^* fornece uma maneira concisa de descrever uma árvore DOM. Enquanto o JavaScript é Turing completo e pode ser usado para fazer exatamente o mesmo, é muito mais barulhento e pouco claro
• XPath e outras linguagens de consulta, PCRE sem código incorporado e são ferramentas poderosas para o único trabalho para o qual foram projetadas

^* IIRC foi provado que HTML com animações CSS é Turing completo, usando-os para implementar o Game of Life de Conway em uma variedade de caixas de seleção. Mas a utilidade do HTML é válida até mesmo em navegadores que não suportam animações CSS.

Existem linguagens de programação, onde você pode escrever apenas programas "eficientes". Eficiente nesse sentido significa que todo programa escrito em tal linguagem representa uma linguagem em P . Bellantoni, Niggl e Schwichtenberg descreva essa língua aqui .

O pré-processador C não é Turing-complete (por design), mas ainda pode implementar um intérprete para um idioma que é Turing completo (o pedido-o-idioma, como descrito na documentação, é basicamente uma coisa do tipo ML / Scheme puramente funcional, e seria relativamente pouco notável - provavelmente muito bom de usar - se não fosse pela implementação incomum).

O truque por trás disso é 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 o linguagem, mas pode:

1. fornece um número dinâmico excessivamente grande (2 ^ 64 por padrão), grande o suficiente para resolver problemas mais realistas usando um processo de expansão exponencial ( mumble mumble vida do universo mumble ).

2. use um limite estático arbitrário para o número acima, ou seja, enquanto o número de etapas deve ser um número finito, você pode alterar o limite específico em "compilar" alterando as configurações estáticas do mecanismo do interpretador. Como não há limite (teórico) sobre o valor real deste limite, ele pode (teoricamente) ser estendido para se ajustar ao requisito de espaço para qualquer programa de terminação.

Não argumentar que Order é necessariamente "útil" por si só, ou que qualquer mecanismo implementado pelo CPP seria, mas é uma prova de conceito interessante. Também é supostamente digitado dinamicamente , o que é incomum para esta área.

Sim, na verdade, é possível ter uma linguagem útil que não seja Turing completa. Veja aqui: link

Outro exemplo de uma linguagem incompleta útil de Turing é o SQL. (E ainda outro é planilhas como Gnumeric ou Excel, embora não sejam realmente linguagens de programação.)

Por que você quereria uma linguagem que não é Turing completa: porque isso permite que você faça algumas strongs garantias sobre o comportamento em tempo de execução.

Completar a completude, em termos simples, 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 completude de Turing requer gerenciamento de memória e / ou coleta de lixo.

Proibir 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 poderia permitir avaliar uma lista infinita e preguiçosa.

Uma interessante "linguagem de programação sub-Turing" não foi mencionada até agora, então vou adicioná-la.

É chamado de "Crema" . Descreve-se como:

Crema is a LLVM front-end that aims to specifically execute in sub-Turing Complete space. Designed to be simple to learn, and practical for the majority of programming tasks needed, Crema can restrict the computational complexity of the program to the minimum needed to improve security.

É um nível bastante minimalista e bastante baixo.

Deve parecer familiar aos desenvolvedores de C.

Foi inicialmente financiado pela Agência de Projetos de Pesquisa Avançada de Defesa (DARPA), mas parece completamente não-mantido no momento em que foi escrito. Mas talvez alguém esteja interessado, no entanto.