Funções recursivas primitivas para programadores práticos

• Discussões no estilo “se não for Turing-complete, então é seguro” destoam do significado matemático do termo, e a não completude de Turing em geral é separada de propriedades práticas como terminação, determinismo e sandboxing
• Cálculos de uma Máquina de Turing cujo tempo de execução é limitado por uma função recursiva primitiva da entrada podem ser reescritos como funções recursivas primitivas
• Funções recursivas primitivas sempre terminam, mas ainda podem crescer rapidamente, como 2^(2^N), então garantia de terminação não significa necessariamente tempo de execução prático
• Na prática, um programa que nunca para e outro que só termina daqui a bilhões de anos causam problemas parecidos, e mesmo linguagens Turing-complete podem ser interrompidas à força com um contador de passos
• A qualidade de uma linguagem de configuração depende mais de determinismo, semântica clara, pureza, segurança e sandboxing, controle do tempo de execução e simplicidade do que de ela ser ou não Turing-complete

---

O equívoco central no debate sobre Turing-completeness

• Programadores na internet frequentemente falam de “não ser Turing-complete” em certos domínios como se isso fosse uma vantagem ou um requisito
• Porém, Turing completeness é um termo técnico específico vindo da matemática, então usá-lo como substituto para várias propriedades desejadas na prática acaba diluindo seu sentido
• As propriedades realmente necessárias são garantia de terminação, execução rápida, comportamento determinístico, sandboxing e uma linguagem de configuração simples, e elas em sua maioria são ortogonais à Turing completeness
• Para entender essa diferença, é preciso um resultado teórico simples sobre funções recursivas primitivas (Primitive Recursive Functions, PRF)

Uma Turing Machine suficientemente rápida pode ser convertida em PRF

• Mesmo que um programa tenha sido escrito em uma linguagem Turing-complete, se soubermos que seu tempo de execução é mais rápido que O(2^(2^N)), então o mesmo algoritmo pode ser implementado também em uma linguagem não Turing-complete
• A maior parte dos problemas práticos cai numa faixa que termina mais rápido que 2^(2^N)
• Portanto, uma linguagem não Turing-complete não restringe de forma significativa a capacidade de cálculo usada no trabalho real, nem concede automaticamente um poder especial de controle sobre a computação
• Do ponto de vista prático, os dois programas abaixo causam essencialmente o mesmo problema
  • um programa que não termina
  • um programa que só termina depois de algo como 10^9 vezes 10^9 passos
• Até linguagens Turing-complete podem simplesmente evitar o problema da não terminação na implementação ao contar o número de passos e abortar com erro após um certo limite

FSM: sempre termina, mas tem expressividade limitada

• Uma Finite State Machine (FSM) é um reconhecedor que recebe uma string como entrada e retorna “yes” ou “no”
• Uma FSM é composta por um conjunto finito de estados, um estado inicial, um conjunto de estados “yes” e uma função de transição
• Após aplicar repetidamente a função de transição a cada símbolo da entrada, o resultado é determinado por o estado final pertencer ou não ao conjunto “yes”.
• O poder expressivo de uma FSM é equivalente ao de uma expressão regular (regular expression)
• Uma FSM executa em tempo linear no tamanho da entrada e sempre termina, mas não consegue reconhecer qualquer conjunto de strings
  • Por exemplo, o conjunto de strings como 1, 010, 00100, 0001000, em que há a mesma quantidade de 0 dos dois lados de 1, não pode ser reconhecido por uma FSM
  • Em entradas suficientemente longas, os estados acabam se repetindo e surge um ciclo; se esse trecho cíclico for duplicado, a FSM ainda chega a um estado “yes”, mas a condição da string deixa de valer

Turing Machine: um modelo que adiciona fita mutável à FSM

• Uma Turing Machine (TM), assim como uma FSM, tem estados e função de transição, mas opera sobre uma fita mutável em vez de uma entrada imutável
• Em cada passo, a TM lê o símbolo atual da fita e executa a próxima ação
  • substitui o símbolo atual por outro símbolo
  • muda o estado interno
  • move a cabeça uma posição para a esquerda ou para a direita
• Quando a TM chega a um estado de halt, ela para, e o conteúdo da fita nesse momento se torna o resultado
• Enquanto a FSM é um reconhecedor binário, a TM é um dispositivo para calcular funções
• Uma TM não necessariamente para; ela pode ficar indo e voltando pela fita e mudando de estado sem nunca alcançar um estado final

Universal Turing Machine e capacidade de computação

• O programa de uma TM não é um código fornecido como entrada do usuário, mas sim embutido na própria função de transição
• Ainda assim, é possível codificar uma TM arbitrária e sua entrada como um arquivo de texto e construir uma TM “intérprete” que decodifique isso
• Essa TM é uma Universal Turing Machine, que simula outra TM recebida como entrada
• É possível criar um intérprete de TM em Python e, por outro lado, implementar um intérprete de Python como TM, então ambos podem ser vistos como equivalentes em capacidade de computação
• A FSM é mais fraca que a TM
  • a TM pode simular uma FSM
  • a TM pode decidir, manipulando a fita, se uma string tem a mesma quantidade de 0 dos dois lados e um 1 no meio
  • a FSM não consegue resolver esse mesmo problema

A fita pode ser vista como duas pilhas

• A fita de uma TM é uma abstração incômoda de implementar diretamente em linguagens de programação comuns
• A fita e a posição da cabeça podem ser representadas por duas pilhas
  • o conteúdo à esquerda da cabeça fica na pilha da esquerda
  • o conteúdo à direita da cabeça fica na pilha da direita, com a ordem invertida
• Mover a cabeça para a esquerda ou para a direita passa a corresponder a fazer pop em uma pilha e push na outra
• Portanto, uma TM tem o mesmo poder computacional que uma “FSM com duas pilhas”
• Se os símbolos da pilha forem apenas 0 e 1, a própria pilha pode ser representada por um único número natural
  • ver o topo: stack % 2
  • pop: stack / 2
  • push x: stack * 2 + x

Limites da Turing Machine: Halting Problem e resultados do tipo Rice

• Como toda TM pode ser codificada como texto, é possível listar todas as TMs possíveis em uma lista infinita
• Usando um argumento de diagonalização, é possível mostrar que existem funções que não podem ser calculadas por TM
• Um exemplo mais concreto é o Halting Problem
  • dado o código-fonte de uma TM e uma entrada, decidir se essa TM vai parar em algum momento
• Se supusermos que halts(program, input) sempre termina com a resposta correta, surge uma contradição com um programa weird que recebe seu próprio código-fonte como entrada
  • se for julgado que ele para, então ele entra em loop infinito e não para
  • se for julgado que ele não para, então ele termina imediatamente
• Portanto, halts precisa errar em alguns casos ou então não terminar em alguns casos
• De forma mais geral, não é possível decidir algoritmicamente propriedades não triviais que preservam o comportamento de uma TM arbitrária
  • propriedades sintáticas podem ser verificadas, mas propriedades comportamentais que continuam valendo após refatoração em geral não podem ser decididas

Funções recursivas primitivas: um mecanismo de cálculo que sempre termina

• Uma função recursiva primitiva (PRF) é definida como uma função que recebe uma tupla de números naturais e retorna um único número natural
• As funções básicas são zero e succ
  • zero = 0
  • succ(x) = x + 1
• É possível criar constantes por composição de funções
  • succ(zero) = 1
  • succ(succ(zero)) = 2
• Recursão geral não é permitida, mas um laço restrito com número de repetições fixado de antemão, LOOP(init, f, n), é permitido
  • LOOP(init, f, 0) = init
  • LOOP(init, f, 1) = f(init)
  • LOOP(init, f, 2) = f(f(init))
• A restrição central é que o número de iterações n fica fixado antes de o laço começar, e o corpo do laço não pode alterar o contador do laço

Construindo estruturas básicas de programação com PRF

• A adição pode ser definida como add(x, y) = LOOP(x, succ, y)
• A multiplicação pode ser definida como mul(x, y) = LOOP(0, add x, y)
• A exponenciação pode ser definida como pow(x, y) = LOOP(1, mul x, y)
• Com isso, também é possível criar funções de crescimento rápido
  • pow_2(n) = pow(2, n)
  • pow_2_2(n) = pow_2(pow_2(n))
• Se adicionarmos pred às funções básicas, dá para construir subtração saturada e operações booleanas
  • sub(x, y) = LOOP(x, pred, y)
  • and(x, y) = mul(x, y)
  • not(x) = sub(1, x)
  • if(cond, a, b) também pode ser expresso por fórmula aritmética
• Operações de comparação, resto e divisão também podem ser implementadas usando iteração limitada e expressões condicionais

Estruturas de dados em PRF e simulação de TM

• A PRF pode receber vários argumentos, mas seu resultado é sempre um único número natural, então é preciso codificar estruturas de dados como números naturais
• Um par (a, b) pode ser representado como 2^a * 3^b
• Para extrair os componentes, basta encontrar o maior expoente de um primo específico
  • fst(p) é o maior expoente de 2 que divide p
  • snd(p) é o maior expoente de 3 que divide p
• Do mesmo modo, três valores (S, stack1, stack2) também podem ser empacotados em um único número natural
• Uma configuração de TM pode ser representada pelos três elementos a seguir
  • estado atual S
  • pilha esquerda da fita
  • pilha direita da fita
• Como as operações sobre pilhas podem ser implementadas com resto, multiplicação e divisão, é possível codificar em PRF um passo único de uma TM
• Com LOOP(initial_config, single_step, n), é possível simular uma TM por exatamente n passos
• O problema é não sabermos qual n é suficiente, mas se o tempo de execução for limitado por alguma PRF, então basta iterar esse tanto
• No fim, qualquer cálculo de TM cujo tempo de execução seja limitado por uma função recursiva primitiva pode ser substituído por PRF

Limites da PRF: sempre terminar não significa ser tão forte quanto TM

• A PRF sempre termina, mas não expressa todas as funções que terminam
• Existem funções calculáveis por TM que não podem ser calculadas por PRF
• Para mostrar isso, estabelece-se um limite superior para a taxa de crescimento com base na profundidade da árvore sintática da PRF
• Uma PRF de profundidade até d pode receber um limite de modo a não crescer mais rápido do que uma certa função unária A_d
• A(d, x) é definida assim
  • A(1, x) = x + 1
  • A(d + 1, 0) = A(d, A(d, 0))
  • A(d + 1, x) = A(d, A(d + 1, x - 1))
• Nessa definição, a cada chamada recursiva o par (d, x) diminui em ordem lexicográfica, então, se calculada em uma TM, ela termina
• a(x) = A(x, x) cresce mais rápido do que qualquer PRF; é calculável por TM, mas não por PRF

Voltando à prática: não ser Turing-complete, por si só, não basta

• Uma Turing Machine pode não parar
• Mesmo mecanismos que sempre terminam, como FSM e PRF, não garantem execução rápida
• A PRF pode calcular funções enormes como 2^(2^N), então garantir terminação não garante tempo de execução prático
• Muitos algoritmos do mundo real têm tempo de execução limitado por PRF, então também podem ser expressos em mecanismos não Turing-complete
• Um método geral para fazer um cálculo Turing-complete se comportar mais como PRF é adicionar um contador de iterações e interromper à força quando ele fica grande demais

Propriedades que uma linguagem de configuração realmente precisa

• Muitas linguagens de configuração colocam como objetivo de projeto “não ser Turing-complete”, mas o que de fato se precisa são várias propriedades mais fortes

• Determinismo

  • Uma linguagem de configuração deve ser determinística
  • Um comportamento como id([]) em Python, que pode devolver valores diferentes em execuções diferentes, pode ser aceitável em programação geral, mas é inadequado para configuração
  • Configurações costumam ser usadas como chave em sistemas de build incremental ou cache, e a presença de não determinismo desestabiliza o funcionamento do cache

• Semântica clara

  • O comportamento da linguagem deve estar claramente fixado por uma referência consultável
  • É possível tornar id([]) determinístico em Python desativando ASLR e usando um allocator específico, mas isso não garante que o resultado seja previsível nem igual entre implementações
  • Para garantir o mesmo comportamento em outras implementações ou após mudança de versão do Python, a semântica precisa ser clara

• Pureza

  • Se a configuração puder ler variáveis de ambiente ou arquivos no disco, o significado da configuração passa a depender do ambiente de avaliação
  • Para que o cache funcione corretamente, a linguagem de configuração precisa ter pureza

• Segurança e sandboxing

  • Tanto pureza quanto segurança podem ser alcançadas ao não expor IO geral
  • Mas os objetivos das duas propriedades são diferentes
  • Pureza serve para impedir que o resultado se torne não determinístico
  • Segurança serve para impedir que recursos como tokens de acesso sejam expostos a um atacante

• Controle do tempo de execução

  • Mesmo controlando IO, uma configuração maliciosa ainda pode fazer um ataque de negação de serviço consumindo CPU
  • Para garantir o tempo de execução, há duas abordagens
  • restringir a linguagem a uma estrutura obviamente linear em que o processamento seja diretamente proporcional ao tamanho da entrada
  • usar execução medida (metered execution), decrementando um contador a cada passo atômico e interrompendo quando ele chegar a 0

• Simplicidade

  • A linguagem de configuração deve induzir o usuário a escrever programas simples
  • Proibir recursão e loops infinitos pode funcionar como uma lombada para incentivar simplicidade
  • Porém, como mostra o exemplo de PRF, essa proibição não impede completamente a escrita de programas recursivos arbitrários; ela apenas exige código mais indireto
  • Um exemplo relacionado pode ser visto em some roundabout code

Resumo final

• Um algoritmo de Turing Machine cujo tempo de execução sobre a entrada é limitado por alguma função recursiva primitiva também pode ser implementado como função recursiva primitiva
• A não completude de Turing pode fornecer uma única propriedade, a garantia de terminação, mas não garante automaticamente limites práticos de tempo de execução nem a qualidade de uma linguagem de configuração
• No projeto de linguagens de configuração, questões mais importantes do que Turing completeness em si são determinismo, semântica clara, pureza, sandboxing, medição do tempo de execução e simplicidade

[GN⁺]

Comentários do Hacker News

• Autopromoção: https://www.nayuki.io/page/primitive-recursive-functions

  • É muito melhor que o texto original, mas hoje em dia parece que todo mundo prefere explicações fáceis no estilo ELI5

• Na conclusão do artigo há critérios bem bons relacionados a linguagens de configuração, e fico curioso se há alguma linguagem atual que satisfaça todos ou a maioria deles

  • Exemplos que atendem a esses critérios são Dhall [1] e Cue [2], mas, em certo sentido, não são exemplos tão interessantes
    Dhall é deliberadamente uma linguagem total funcional, então segue na direção de “não ser Turing-completa”, e Cue não tem funções, portanto não há recursão possível
    Eu diria que RCL [3] satisfaz os critérios. É determinística e pura, oferece execução medida e trata o acesso ao sistema de arquivos em sandbox. Se a política da sandbox permitir, ela pode ler arquivos, mas esses arquivos são considerados parte do código-fonte e se comportam da mesma forma que um import
    Em RCL, eu não quis seguir o caminho de “não ser Turing-completa” pelos motivos mencionados pelo autor. O fato de um programa eventualmente terminar não é uma propriedade muito útil na prática; por outro lado, mesmo em linguagens totais funcionais como Agda é possível escrever programas muito complexos, então a não completude de Turing não garante programas/configurações simples
    Em RCL, todos os loops têm limites, mas há funções, então recursão também é possível. Não há chamadas de cauda, então inicialmente coloquei um limite de profundidade de recursão para evitar estouro da pilha nativa, mas o fuzzer encontrou uma função que trava mesmo executando com espaço de pilha constante, e ainda não a entendo completamente: let f = g => g(g(h => k => g(g(h)))); f(f)
    No fim, poder expressar esse tipo de função patológica não é um problema na prática. Basta impor um limite no número de etapas de execução, isto é, um “limite de gas”, ou a “execução medida” mencionada pelo autor. Para manter o código simples, é um bom incentivo que as estruturas de repetição embutidas tenham limites e que a recursão seja inconveniente, mas, no fim, as ferramentas mais valiosas são revisão de código e bom julgamento
    [1]: https://dhall-lang.org/
    [2]: https://cuelang.org/
    [3]: https://rcl-lang.org/
  • Embora seja imperativa e nem sequer “pura”, até mesmo C foi projetada em uma direção que permite saber, antes de entrar em cada loop, um limite superior para o número de iterações, e por isso é primitivamente recursiva
    A pesquisa de Dennis Ritchie no MIT se concentrou no tema que ele chamava de programação de loops
    The complexity of loop programs - ALBERT R. MEYER and DENNIS M. RITCHIE
    https://people.csail.mit.edu/meyer/meyer-ritchie.pdf
    A programação estruturada, que quase todos os programadores modernos seguem por padrão, é, na prática, um paradigma que empurra na direção das funções primitivas recursivas. Como a programação estruturada foi aceita quase universalmente em comparação com os outros dois tipos, como pop e funcional, parece que o artigo “goto é prejudicial”, de Dijkstra, acaba sendo mal compreendido
    Funções primitivas recursivas não abrangem todas as funções computáveis, mas abrangem quase todas as funções intuitivas cuja terminação é garantida. Claro que há casos em que loops cujo número de iterações não é conhecido ao entrar no loop são realmente necessários, mas, quando usados apenas quando indispensáveis, são uma armadilha que pode ser evitada
    Até COBOL foi modernizado ao deslocar o goto ilimitado para o comando ALTER. Não consigo pensar em uma linguagem moderna e útil que não permita funções PR
    Mesmo em C, se você escrever evitando while e evitando explicitamente fall-through, quase sempre consegue criar código de funções totais que necessariamente termina
    Há também casos patológicos, como a inferência de tipos de ML. O custo real é muito mais barato do que sua classe de complexidade sugere, então vale a pena aceitar isso, mesmo que a linguagem não consiga restringir esse uso por não se tratar de funções totais
    De um ponto de vista prático, todas as linguagens em geral oferecem padrões que dão suporte à maioria desses critérios, mas restrições que os imponham limitariam seriamente a utilidade da linguagem. Eu diria que até os criticados SOLID e Clean Framework empurram nessa direção
    A programação estruturada se tornou tão onipresente que é fácil esquecer esse ponto, e às vezes nem conseguimos ensiná-lo. Como um velho barbudo, lembro de ter aprendido os perigos de WHILE e afins
  • Talvez baste escolher Dhall e ver em quais critérios ela falha. Parece ser a mais próxima

• Dizer que roda mais rápido que O(2^(2^N)) provavelmente era uma simplificação, mas a parte de “número muito grande” reduz um pouco a confiança
  O correto seria dizer “uma função que cresce muito rapidamente”. Ou então parece significar que o programa termina em menos de O(2^(2^N)) etapas

• Olhando só para a primeira parte, de que uma linguagem restrita é melhor para algumas aplicações, acho que a vantagem é poder calcular estaticamente um limite superior para o número de etapas necessárias.
  Assim, para qualquer entrada, uma computação que viole o limite poderia ser rejeitada e retornar um erro significativo.
  Já a abordagem de impor um limite em tempo de execução a uma linguagem Turing-completa pode acabar definindo um limite baixo demais para algumas entradas que importam. Não dá para saber até executar e bater no limite. Vejo isso às vezes em recursão de templates em C++.
  Posso estar completamente confuso, então seria bom se alguém que entende melhor explicasse.

  • Um ex-colega definiu um número perto de 3x e, anos depois, uma carga de trabalho real bateu nesse limite; desde então eu uso um limite de 10x sobre uma quantidade de computação razoável.
    Mesmo que um fluxo de trabalho ruim demore algumas vezes mais para falhar, ainda fica na casa dos milissegundos, então não vejo grande prejuízo.
    Normalmente você encontra esse problema quando alguém tratou o domínio do problema como um grafo direcionado acíclico, mas não conseguiu impor o “acíclico”. Modelar o problema como um grafo direcionado acíclico é como a Dark Galadriel pensando se aceita o anel de Frodo. “Todos me amarão e se desesperarão.” Quem cria essas coisas sempre se orgulha delas muito mais do que deveria.
    No fim, os clientes atraídos por uma solução cara e complexa ficam sem dinheiro, e o problema deles também começa a parecer muito menor. Então, literalmente, sobra apenas um app cujo custo por tarefa não pode ser reduzido o bastante para manter o negócio do cliente.
  • Prever com precisão o uso de combustível de uma computação em blockchain pode ser interessante para outras pessoas, mas não para mim.
    Acho mais interessante usá-lo como mais um martelo na caixa de ferramentas para capturar bugs que passaram por martelos anteriores, como verificação estática de tipos, ausência de null e ausência de mutabilidade.
    O fato de terminar em tempo finito não prova correção, mas, se eu declaro que meu código termina em tempo finito e o compilador discorda, vou acreditar que o código está errado.
  • Um limite superior determinado estaticamente pode superestimar bastante a complexidade real de tempo de execução no caso comum. Isso porque, em geral, não dá para prever como serão avaliadas as condicionais que causam saída antecipada na recursão.
    Para que a saída antecipada afete o tempo de execução, é preciso pressupor avaliação preguiçosa ou condicionais com curto-circuito, mas uma linguagem prática normalmente acaba tendo isso.
  • E se esse limite superior for extremamente frouxo? Por exemplo, quicksort determinístico normalmente é n log n, mas tem um limite superior quadrático em relação ao tamanho da entrada.
    Então você vai rejeitar a computação do quicksort? Indo mais ao extremo, o algoritmo de Hindley–Milner tem limite superior exponencial, mas na prática muitas vezes roda em tempo linear.
  • Não sei se isso é “calculado estaticamente”, mas vejo que a única vantagem de restringir muito a capacidade de uma linguagem é poder impor um limite de computação que não dependa dos dados.
    Só que é difícil pensar em qualquer situação em que isso seja de fato um requisito forte. Quantos sistemas não podem emitir um erro de “a consulta demorou demais”?

• Eu queria experimentar uma linguagem de programação web de backend baseada no princípio de não encerrar/ter limites.
  A ideia é que o compilador prove que toda função, para um estado e argumentos dados, executa dentro de limites, e consiga mostrar que X é o limite inferior e Y o limite superior. Essa informação se propagaria até os pontos de entrada.
  Concordo com o autor quando ele diz que precisamos de semânticas mais fortes, e foi por isso que pensei nessa linguagem. Muitas vezes queremos garantias sobre o tempo de execução do programa.
  O núcleo seria baseado em funções recursivas primitivas, mas na prática poderia ser Turing-completo. Assim como Rust rejeita borrows incorretos, mas oferece unsafe para ponteiros brutos, essa linguagem também calcularia limites com base em primitivas simples de repetição, ou permitiria usar um operador unsafe e fornecer uma fórmula alternativa para os limites.

• Não entendi muito bem a parte curta de reclamação/motivação do texto.
  É a parte que diz: “Normalmente, em certos domínios, o fato de não ser Turing-completa é exaltado como uma vantagem ou requisito. Acho que a maior parte dessas discussões está enganada — não ser Turing-completa não significa o que as pessoas esperam.”
  Por que essas discussões estariam erradas? A maioria das ferramentas de análise formal, como Coq, Isabelle e Agda, normalmente exige uma prova de que a função termina. Isso equivale a provar que a função é total e, portanto, não significa que ela é recursiva primitiva?

  • Não li até o fim, mas este texto parece ter surgido do fato de algumas linguagens de configuração anunciarem “não ser Turing-completas” como recurso. Quando o recurso que elas provavelmente querem divulgar é tempo de execução razoavelmente limitado.
    Isso também apareceu recentemente em uma discussão sobre CEL:
    https://news.ycombinator.com/item?id=40954652
  • Se você está falando de prova formal, então, não no sentido de contraexemplos científicos usados na programação moderna: no caso geral, provar que uma função é total é um problema de busca NP-completo.
    Se lembro corretamente, isso é equivalente a NP com um oráculo co-NP, ou ao segundo nível da hierarquia polinomial. Mesmo quando possível em problemas pequenos, é caro.
    Essas ferramentas funcionam melhor quando você estrutura o programa para que ele seja uma função total. Entre as formas mais comuns está usar apenas FOR na programação estruturada, ou WHILE/recursão com número de iterações limitado.
    Embora esteja relacionado apenas a SAT, as formas tratáveis cobertas pelo teorema da dicotomia de Schaefer são a lente mais acessível que consigo imaginar.
  • Como o texto mostra, existem funções que terminam mas não são recursivas primitivas, portanto uma prova de totalidade da função não implica que ela seja recursiva primitiva.
    Agda, e provavelmente outras ferramentas também, consegue provar a terminação de algumas funções recursivas não primitivas que terminam. Claro que não de todas.
    O mal-entendido de que o texto reclama parece ser mais ou menos este: “Completude de Turing significa conseguir fazer computação, e não completude de Turing significa não conseguir computar e ter boas propriedades para linguagens de configuração.”
    O ponto do texto é que, mesmo não sendo Turing-completa, uma linguagem ainda pode fazer muitas coisas computacionalmente caras ou complicadas; e, para uma linguagem de configuração, são necessárias restrições muito mais rígidas do que simplesmente não ser Turing-completa.
  • Há outras formas de não ser Turing-completa além de ser uma função total que termina de forma limpa. Por exemplo, um loop infinito nem consegue computação universal nem termina.

• Eu sou desenvolvedor do CUE. O CUE é recursivo primitivo e também atende aos critérios esperados de uma “boa” linguagem de configuração

  • Só por diversão, aqui está um exemplo em CUE que simula um número arbitrário, mas finito, de etapas da Rule 110: https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=...
    [0] https://en.wikipedia.org/wiki/Rule_110