Me deparei com um problema estranho ao escrever um intérprete que (deveria) ser vinculado a programas / funções externas: As funções em 'C' e 'C ++' não podem vincular funções variadas , por exemplo, eu não posso criar uma função que chame 'printf' com exatamente os mesmos argumentos que obteve e, em vez disso, precisa chamar uma versão alternativa que aceite um objeto variado. Isso é muito problemático, pois quero poder criar um objeto que contenha um gancho anônimo.

Então, pensei que isso era estranho, já que Forth , JavaScript e talvez uma infinidade de outras linguagens podem fazer isso com muita facilidade, sem ter que recorrer à linguagem assembly / código de máquina. Como outras linguagens podem fazer isso tão facilmente, isso significa que a classe de problemas que cada linguagem de programação pode resolver realmente varia de acordo com a linguagem, mesmo que todas essas linguagens estejam completas em Turing ?

Turing linguagens completas pode calcular o mesmo conjunto de funções , que é o conjunto de funções parciais recursivas gerais. É isso aí.$\mathbb{N}^k \rightarrow \mathbb{N}$

Isso não diz nada sobre os recursos de idioma. Uma máquina de Turing possui características composicionais muito limitadas. O calcculus não tipificado é muito mais composicional, mas carece de muitos recursos comumente encontrados em linguagens modernas.$\lambda$

A integridade de Turing não diz nada sobre ter tipos, matrizes / números inteiros / dicionários, recursos de entrada / saída, acesso à rede, multithreading, alocação dinâmica, ...

Só porque o Java não possui o recurso X (digamos, macros, tipos de classificação mais alta ou tipos dependentes), ele de repente não deixa de ser Turing completo.

A perfeição de Turing e a expressividade da linguagem são duas noções diferentes.

Turing completude é um conceito abstrato de computabilidade. Se um idioma é Turing completo, ele é capaz de fazer qualquer cálculo que qualquer outro idioma completo de Turing possa fazer.

Isso não diz, no entanto, quão conveniente é fazê-lo. Alguns recursos fáceis em alguns idiomas podem ser muito difíceis em outros, devido a opções de design. A perfeição de Turing apenas diz que você pode fazer o cálculo. Como exemplo extremo, pode ser difícil conectar funções varádicas em C ++, mas é possível escrever um intérprete JavaScript em C ++ que possa conectar funções variadas.

O design de idiomas é uma arte bastante interessante. Uma das principais etapas que você deve executar é identificar quais comportamentos você deseja formar a espinha dorsal do seu idioma. Esses comportamentos são fáceis de fazer no seu idioma, porque estão embutidos no térreo. Tomamos decisões de design sobre quais recursos incluir em todos os idiomas.

Quanto ao seu exemplo particular, quando o C foi desenvolvido, ele foi projetado para operar muito próximo da maneira como as linguagens de montagem do dia operavam. As funções Variadic simplesmente colocavam argumentos na pilha, com muito pouca segurança de tipo. A implementação dessas funções variadas foi deixada para o compilador, para garantir a máxima portabilidade. Consequentemente, muito poucas suposições foram feitas sobre os recursos do hardware. Quando o JavaScript apareceu, a cena havia mudado. Ele já opera em uma máquina virtual como uma linguagem interpretada, de modo que o equilíbrio muda para conveniência. Permitir a conexão de funções variadas torna-se razoável. Mesmo no caso do JavaScript compilado Just In Time, nossos compiladores estão dispostos a armazenar muito mais informações extras sobre os argumentos do que os compiladores C de outrora estavam dispostos a armazenar.

Pense nas linguagens de programação como diferentes veículos terrestres: bicicletas, carros, hovercars, trens.

Turing Completeness diz que "este veículo pode ir a qualquer lugar que qualquer outro veículo possa ir". Ou seja, você pode calcular todas as mesmas funções. Entrada para saída, do início ao fim.

Mas, essa afirmação não diz nada sobre como você chega lá. Pode estar nos trilhos, nas estradas, no ar. Da mesma forma, Turing Completeness não diz nada sobre como você calcula uma função. Você pode usar recursão, iteração ou alguns autômatos celulares estranhos. Você pode usar tipos ou não, técnicas dinâmicas ou estáticas. Mas, se tudo o que você considera são funções (ou conjuntos / linguagens formais), você pode calcular, desde que seja o Turing Complete, esses recursos oferecem o mesmo poder.

O que você está perguntando é essencialmente a diferença entre o poder computacional e o que é comumente chamado de poder expressivo (ou apenas expressividade ) de uma linguagem (ou sistema de computação).

Poder computacional

O poder computacional refere-se a quais tipos de problemas a linguagem pode computar. A classe mais conhecida de potência computacional é aquela que é equivalente a uma Máquina Universal de Turing . Há uma série de outros sistemas de computação, tais como Random Access Machines , λ-cálculo , SK cálculo combinator , funções u-recursiva , WHILEprogramas, e muitos outros. E, como se vê, tudo isso pode simular um ao outro, o que significa que todos eles têm o mesmo poder computacional.

Isso dá origem à tese de Church-Turing (em homenagem a Alonzo Church, que criou o λ-cálculo e Alan Turing, que criou a Universal Turing Machine). A tese de Church-Turing é uma hipótese sobre computabilidade com dois aspectos:

1. todos os sistemas de computação capazes de computação geral são igualmente poderosos, e
2. um ser humano seguindo um algoritmo pode calcular exatamente as funções que uma Máquina de Turing (e, portanto, qualquer outro sistema) pode calcular.

O segundo é mais importante no campo da filosofia da mente do que na ciência da computação.

No entanto, existem duas coisas que a Tese da Igreja não diz, que são muito relevantes para a sua pergunta:

1. quão eficientes são as várias simulações e
2. quão conveniente é a codificação de um problema.

Um exemplo simples para (1): em uma máquina de acesso aleatório, copiar uma matriz leva um tempo proporcional ao comprimento da matriz. Em uma Máquina de Turing, no entanto, leva um tempo proporcional ao quadrado do comprimento da matriz, porque a Máquina de Turing não possui acesso aleatório à memória, ela pode se mover pela fita uma célula por vez. Portanto, ele precisa se mover pelos n elementos da matriz n vezes para copiá-los. Portanto, diferentes modelos de computação podem ter características de desempenho diferentes, mesmo no caso assintótico, onde tentamos abstrair dos detalhes da implementação.

Existem muitos exemplos para (2): tanto o cálculo λ quanto o Python são completos em Turing. Mas você prefere escrever um programa em Python ou em λ-calculus?

Há também uma terceira ruga que eu contornei até agora: todos esses sistemas originais foram projetados por lógicos, filósofos ou matemáticos, não por cientistas da computação ... simplesmente porque os computadores e, portanto, a ciência da computação não existiam. Tudo isso remonta ao início dos anos 30, mesmo antes das primeiras experiências de Konrad Zuse (que não eram programáveis ​​e / ou concluídas por Turing). Eles falam apenas de "funções computáveis ​​nos números naturais".

Agora, como se vê, há muito que você pode expressar como funções em números naturais - afinal, nossos computadores modernos ainda se dão bem com muito menos que isso (basicamente 3-4 funções nos números 0 e 1, e é isso ), mas, por exemplo, que função um sistema operacional calcula?

Essa noção de E / S, efeitos colaterais, interagindo com o meio ambiente, não é capturada pela idéia de "funções sobre números naturais". E, no entanto, é meio importante, pois, como Simon Peyton Jones disse uma vez "Toda uma função pura sem efeitos colaterais faz com que sua CPU fique quente" , à qual um membro da platéia respondeu "na verdade, esse é um lado -efeito também! "

Edwin Brady , o designer de Idris , (apenas metade) usa de brincadeira (não sei se ele o inventou) o termo "Tetris-complete" para expressar essa diferença entre "pode ​​calcular qualquer função computável em números naturais" e "pode ser usado para escrever programas não triviais que interagem com o ambiente ". Ainda mais ironicamente, ele demonstra isso implementando um clone do Space Invaders em Idris , mas ele diz estar confiante de que Tetris se reduz a Space Invaders.

Outra coisa a salientar é que não apenas a equivalência de Turing não é necessariamente suficiente para falar sobre realmente escrever programas "úteis", como também a OTOH nem mesmo é necessária . Por exemplo, o SQL só se tornou equivalente a Turing com o ANSI SQL: 1999 , mas ainda era útil antes disso. De fato, alguns podem argumentar que torná-lo equivalente a Turing não aumentou sua utilidade. Existem muitos idiomas específicos do domínio que não são equivalentes ao Turing. O idioma de descrição de dados normalmente não é (e não deveria ser). O Total Languages ​​obviamente não pode ser equivalente a Turing, mas você ainda pode gravar loops de eventos, servidores da Web ou sistemas operacionais neles. Também existem idiomas equivalentes a Turing, mas onde isso é realmente considerado um erro.

Portanto, apesar de tudo, a equivalência de Turing não é muito interessante, a menos que você queira analisar estaticamente os programas.

Expressividade

Supondo que nosso sistema de computação seja computacionalmente poderoso o suficiente para resolver nosso problema, o que temos a fazer a seguir é expressar nosso algoritmo para resolver esse problema em algum tipo de notação formal para esse sistema. Em outras palavras: precisamos escrever um programa em alguma linguagem de computador. É aí que entra a noção de expressividade .

Refere-se, essencialmente, a quão "fácil" ou "agradável" é escrever nosso programa em nossa linguagem de programação específica. Como você pode ver, a noção é bastante vaga, subjetiva e mais psicológica do que técnica.

No entanto, existem tentativas de definições mais precisas. A mais famosa (e a mais rigorosa que conheço) é de Matthias Felleisen em seu artigo Sobre o poder expressivo das linguagens de programação (as duas primeiras páginas contêm uma introdução suave, o restante do artigo é mais carnudo).

A principal intuição é a seguinte: ao traduzir um programa de um idioma para outro idioma, algumas das alterações que você precisa fazer estão localmente contidas (como, por exemplo, transformar FORloops em WHILEloops ou loops em GOTOs condicionais ), e algumas exigem uma alteração no global estrutura do programa.

Quando você pode substituir um recurso de um idioma por um recurso diferente de um idioma diferente apenas por transformações locais, diz-se que esses recursos não afetam o poder expressivo. Isso é chamado de açúcar sintático .

Por outro lado, se exigir uma alteração na estrutura global do programa, o idioma para o qual você está traduzindo será incapaz de expressar o recurso. E o idioma do qual você está traduzindo é mais expressivo (com relação a esse recurso).

Observe que isso fornece uma definição objetiva mensurável de expressividade. Observe também que a noção depende do contexto do recurso e é comparativa. Portanto, se todo programa no idioma A puder ser traduzido para o idioma B apenas com alterações locais, e houver pelo menos um programa no idioma B que não possa ser traduzido para A com apenas alterações locais, o idioma B será estritamente mais expressivo que o idioma UMA. No entanto, o cenário mais provável é que muitos programas nos dois idiomas possam ser traduzidos para frente e para trás, mas existem alguns programas nos dois idiomas que não podem ser traduzidos para o outro. Isso significa que nenhum idioma é estritamente mais expressivo que o outro, apenas possui recursos diferentes que permitem que diferentes programas sejam expressos de maneiras diferentes.

Isso fornece uma definição formal do que significa ser "mais expressivo", mas ainda não captura as noções psicológicas por trás do fenômeno. Por exemplo, o açúcar sintático, de acordo com esse modelo, não aumenta o poder expressivo de um idioma, porque pode ser traduzido usando apenas alterações locais. No entanto, sabemos por experiência que tem FOR, WHILEe IFdisponível, mesmo se eles são apenas açúcar sintático para condicionais GOTOmarcas expressar nossa intenção mais fácil .

O fato é que idiomas diferentes têm recursos diferentes que tornam mais fácil ou difícil expressar maneiras diferentes de pensar sobre um problema. E algumas pessoas podem encontrar uma maneira de expressar suas intenções mais facilmente e outras de uma maneira diferente.

Um exemplo que encontrei na tag Ruby no StackOverflow: muitos usuários que seguem a tag Ruby afirmam que os loops são mais fáceis de entender do que a recursão e a recursão é apenas para programadores funcionais avançados e os loops são mais intuitivos para os novatos, mas já vi vários casos de conclua os novatos que escrevem intuitivamente código como este:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

O que geralmente leva várias pessoas a comentar que "isso não funciona" e "eles estão fazendo errado" e a "maneira correta" é esta:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Portanto, claramente, existem pessoas para quem a recursão da cauda é uma maneira mais natural de expressar o conceito de "loop" do que as construções de loop.

Sumário

O fato de duas línguas serem equivalentes a Turing diz uma e exatamente uma coisa: que elas podem calcular o mesmo conjunto de funções em números naturais que uma máquina de Turing. É isso aí.

Não diz nada sobre a rapidez com que eles calculam essas funções. Não diz nada sobre a facilidade de expressar essas funções. E não diz nada sobre o que mais eles podem fazer além de computar funções em números naturais (por exemplo, vincular a bibliotecas C, ler entradas do usuário, gravar saída na tela).

isso significa que a classe de problemas que cada linguagem de programação pode resolver varia de acordo com a linguagem, mesmo que todas essas linguagens estejam completas?

Sim.

1. Existem problemas que não são cobertos pelo termo "Turing-complete" (que se preocupa apenas com as funções de computação em números naturais), como imprimir na tela. Dois idiomas podem ser completos em Turing, mas um pode permitir a impressão na tela e o outro não.
2. Mesmo que os dois idiomas possam resolver os mesmos problemas, isso não diz nada sobre a complexidade da codificação e como é fácil expressar essa codificação. Por exemplo, C pode resolver todos os problemas que Haskell pode, simplesmente escrevendo um intérprete Haskell em C ... mas você deve escrever o intérprete Haskell primeiro para resolver um problema dessa maneira!

Todas as linguagens de programação completas de Turing podem implementar o mesmo conjunto de algoritmos. Portanto, se você perceber que algum algoritmo é muito difícil de ser implementado em uma linguagem específica, isso não significa que seja impossível.

Lembre-se de que uma linguagem consiste em sintaxe e semântica. Às vezes, o conjunto de palavras pertencentes a algum idioma não é mínimo para ser considerado completo como Turing, existem recursos que facilitam as coisas (é por isso que são chamados recursos ). Se você usar esses recursos, o idioma ainda estará completo.

Alguns destes podem ser de interesse:

• Compilador fonte a fonte na Wikipedia

• Sobre a importância da perfeição de Turing em Lambda the Ultimate

Todos os idiomas completos de Turing podem calcular as mesmas coisas.

Se você tentar implementar uma linguagem moderna, perceberá que a maioria de seus recursos não adiciona nenhum recurso computacional. Muitos desses recursos podem ser reduzidos para os mais simples que já existem no mesmo idioma.

aqui estão alguns exemplos:

• Se você não tiver enumerações, poderá usar números inteiros.
• Se você não possui buffers que sabem seu tamanho, é possível criar um tipo que contenha um tamanho e um buffer que não saiba seu tamanho.
• Se você não tem verificação de limites de buffers, basta verificar o índice sempre que usá-los.
• Se você não tiver funções variadas, poderá criar uma função que utilize um buffer que saiba seu tamanho e ler nesse buffer as mesmas informações que obteria dos argumentos formais.
• Se você não tiver operadores, poderá usar funções.
• Se você não possui tipos que podem se herdar, é possível criar tipos que se contenham e acessá-los por meio de um nível extra de indireção, com a subtipagem sendo simplesmente uma transformação do tipo manipular para todo o tipo em um lidar com o tipo contido.
• Se você não tiver delegados, mas tiver ponteiros de função, poderá criar um tipo que contenha o objeto referente e um ponteiro de função.
• Se você não tiver delegados, mas tiver interfaces, poderá declarar uma interface que contenha um único método com a assinatura desejada.
• Se você não possui tipos genéricos, pode usar tipos não genéricos que assumem apenas os limites superior ou inferior do seu interesse (e talvez execute projeções apropriadas nos pontos de uso, para manter o compilador feliz).
• Se você não possui um sistema de tipo linear / afim, pode evitar o uso de qualquer variável mais de uma vez.
• ...e assim por diante.

O design da linguagem mainstream concentra-se em recursos que tornam mais fácil e conveniente calcular as coisas mais rapidamente, reconhecer nossos erros anteriormente, programar contra componentes desconhecidos, tornar o paralelismo mais seguro e assim por diante.

As coisas puramente computacionais foram pregadas há muito tempo.

As respostas existentes apontam corretamente que a integridade de Turing não é uma boa maneira de comparar idiomas. De fato, quase todas as línguas são Turing completas. ("Se todo mundo é especial, ninguém é especial", como costumavam dizer Os Incríveis.)

No entanto, é possível comparar a expressividade das linguagens com a precisão matemática. Dê uma olhada no poder expressivo das linguagens de programação de Felleisen . Basicamente, a idéia é fazer a seguinte pergunta: Posso converter qualquer programa no idioma A em um programa no idioma B fazendo apenas alterações locais ? Em outras palavras, Felleisen fornece uma forma matematicamente precisa à sua intuição.

Além das respostas de todos os outros, aqui está outra analogia.

Para lavar roupas, você precisa de três coisas: um reservatório que retenha água, algum tipo de detergente e um mecanismo de agitação. Isso pode ser realizado de várias maneiras. O reservatório de água é qualquer coisa que retenha água suficiente (por exemplo, uma banheira, um lago, um rio). O mecanismo de agitação pode ser um dispositivo mecânico, uma tábua de lavar roupa ou até uma pedra contra a qual as roupas são batidas. E os detergentes também têm várias formas.

Então, qual é a diferença entre uma moderna máquina de lavar computadorizada e uma pedra ao lado de um rio?

Tudo se resume a três coisas: eficiência, segurança e conveniência. Alguns métodos de lavagem consomem menos energia, poluem menos o meio ambiente, usam menos água e assim por diante. Alguns métodos de lavagem requerem atividades manuais menos repetitivas (que resultam em ferimentos) ou estar ao ar livre com o tempo inclemente. E alguns métodos de lavagem não exigem que um ser humano cuide do processo.

As linguagens de programação completas de Turing são de uso geral, portanto, elas são colocadas em mais de uma tarefa. No entanto, para uma determinada tarefa, algumas linguagens de programação são mais eficientes, mais convenientes e mais seguras (no sentido de que menos pode dar errado quando o programa é realmente usado) do que outras.

Outros forneceram muitas boas respostas, mas não mencionam explicitamente uma ressalva que uma vez me confundiu bastante: a integridade de Turing não implica que uma linguagem possa expressar funções computáveis ​​arbitrárias de suas entradas a suas saídas. É mais fraco: deve haver algum maneira de representar o domínio e o intervalo do conjunto de funções computáveis ​​como entradas e saídas, de modo que cada uma dessas funções seja mapeada para um programa que leve uma representação de suas entradas às saídas correspondentes.

Tomemos, por exemplo, uma linguagem que expressa máquinas de Turing. Cada programa no idioma é uma máquina de Turing.

Agora considere a sub-linguagem de todas as máquinas de Turing que lêem e escrevem apenas os caracteres a, be branco. É Turing completo, mas não pode expressar nenhum programa que, por exemplo, produza c em todas as entradas, porque não pode gravar nenhum cs. Ele só pode expressar todas as funções computáveis ​​em entradas e saídas codificadas como sequências de as e bs.

Portanto, não é verdade que todas as linguagens completas de Turing possam calcular as mesmas coisas, nem mesmo quando limitamos essas coisas às funções computáveis ​​de suas entradas em potencial a suas saídas em potencial. O idioma pode exigir que entradas e saídas sejam codificadas de determinadas maneiras.