Por que as linguagens funcionais do Turing estão completas?

Talvez minha compreensão limitada do assunto esteja incorreta, mas é isso que eu entendo até agora:

• A programação funcional é baseada no Lambda Calculus, formulado pela Alonzo Church.

• A programação imperativa é baseada no modelo de máquina de Turing, feito por Alan Turing, aluno da Igreja.

• O cálculo Lambda é tão poderoso e capaz quanto a Máquina de Turing,
  o que significa que eles são equivalentes em potência computacional.

Se a programação funcional é baseada no Lambda Calculus e não na máquina de Turing, por que algumas delas (ou todas) são descritas como completas de Turing e não Lambda completa ou algo parecido? O termo "perfeição de Turing" é especial para as máquinas de Turing ou é apenas uma palavra?

Por fim, se as linguagens imperativas são baseadas na Máquina de Turing, e os computadores são basicamente máquinas de Turing, sem memória infinita, isso significa que elas têm um desempenho melhor do que as linguagens de programação funcionais em nossos PCs modernos?

Se for esse o caso, qual seria o equivalente a uma máquina de cálculo lambda?

Eu sei que isso parece ser três perguntas separadas, mas todas elas estão intimamente relacionadas, e cada uma delas depende da pergunta anterior ser uma pergunta válida para começar.

Em poucas palavras :

O que caracteriza as linguagens de programação imperativas mais próximas das máquinas de Turing e dos computadores comuns, como os PCs (mais próximos das máquinas de acesso aleatório (RAM) do que das máquinas de Turing)) é o conceito de memória explícita que pode ser modificada para armazenar (resultados intermediários ) É uma visão de autômato da computação, com um conceito de estado (incluindo controle de estado finito e conteúdo da memória) que pode mudar à medida que a computação avança.

A maioria dos outros modelos é mais abstrata. Embora eles possam expressar a computação como uma sucessão de etapas de transformação de uma estrutura original, essas transformações são aplicadas em uma espécie de universo intemporal de significados matemáticos. Isso pode preservar propriedades, como transparência referencial, que podem simplificar a análise matemática. Mas é mais distante dos modelos físicos naturais que dependem da concorrência da memória.

Portanto, não há máquinas funcionais naturais, exceto em um sentido mais amplo, conforme explicado abaixo, pois o software não é realmente separável do hardware.

A referência a Turing como parâmetro de computabilidade deriva provavelmente do fato de que seu modelo, a máquina de Turing, estava mais próxima dessa restrição de realização física, o que a tornava um modelo de computação mais intuitivo.

Considerações adicionais :

Existem muitos modelos de computação, que foram projetados para capturar da maneira mais geral possível o conceito de computação. Eles incluem máquinas de Turing, na verdade em muitos sabores diferentes, o cálculo lambda (sabores também), sistemas de reescrita semi-Thue, função recursiva parcial, lógica combinatória.

Todos eles capturam alguns aspectos das várias técnicas usadas pelos matemáticos para expressar ou conduzir cálculos. E a maioria tem sido usada até certo ponto como base de algum projeto de linguagem de programação (por exemplo, Snobol para sistemas de reescrita, APL para combinadores, Lisp / Scheme para cálculo lambda) e pode ser combinado de diversas maneiras nas linguagens de programação modernas.

Um resultado importante é que todos esses modelos de computação se mostraram equivalentes, o que levou à tese de Church-Turing de que nenhum modelo de computação fisicamente realizável pode fazer mais do que qualquer um desses modelos. Um modelo de computação é dito Turing completo se for possível provar que é equivalente a um desses modelos, portanto equivalente a todos eles.

O nome poderia ter sido diferente. A escolha da máquina de Turing (TM) como referência provavelmente se deve ao fato de ser provavelmente o mais simples desses modelos, imitando de perto (embora simplisticamente) a maneira como um ser humano calcula e é fácil de implementar (de forma finita limitada) ) como um dispositivo físico, a tal ponto que as máquinas de Turing foram construídas com conjuntos de Lego . A idéia básica não requer sofisticação matemática. Provavelmente, é a simplicidade e a capacidade de realização do modelo que lhe deram essa posição de referência.

Na época em que Alan Turing criou seu dispositivo de computação, outras propostas estavam em cima da mesa para servir como definição formal de computabilidade, uma questão crucial para os fundamentos da matemática (veja Entscheidungsproblem ). A proposta de Turing foi considerada pelos especialistas da época como o trabalho conhecido mais convincente sobre o que deveria ser calculável (consulte Computability and Recursion , RI Soare, 1996, consulte a seção 3.2). As várias propostas foram equivalentes, mas as de Turing foram mais convincentes. _{[dos comentários de Yuval Filmus]}

Deve-se notar que, do ponto de vista do hardware, nossos computadores não são máquinas de Turing, mas o que é chamado de RAM (Random Access Machines) , que também é Turing completo.

Linguagem puramente imperativa (o que isso possa significar) provavelmente são os formalismos usados ​​para os modelos mais básicos, como máquinas de Turing, ou a linguagem assembly (ignorando sua codificação binária) dos computadores. Ambos são notoriamente ilegíveis e muito difíceis de escrever com programas significativos. Na verdade, até a linguagem assembly possui alguns recursos de nível superior para facilitar um pouco a programação, em comparação ao uso direto das instruções da máquina. Modelos imperativos básicos estão fechados aos mundos físicos, mas não são muito úteis.

Isso levou rapidamente ao desenvolvimento de modelos de computação de nível superior, que começaram a misturar uma variedade de técnicas computacionais, como subprogramas e chamadas de funções, nomeação de localização da memória, escopo de nomes, quantificação e variáveis ​​dummy, já utilizadas de alguma forma em matemática e lógica, e até conceitos muito abstratos como reflexão ( Lisp 1958).

A classificação das linguagens de programação em paradigma de programação, como imperativo, funcional, lógico e orientado a objetos, baseia-se na preeminência de algumas dessas técnicas no design da linguagem e na presença ou ausência de alguns recursos de computação que reforçam algumas propriedades dos programas. ou fragmentos de programa escritos no idioma.

Alguns modelos são convenientes para máquinas físicas. Alguns outros são mais convenientes para uma descrição de alto nível de algoritmos, que pode depender do tipo de algoritmo a ser descrito. Alguns teóricos até usam especificação não determinística de algoritmos, e mesmo isso pode ser traduzido em termos de programação mais convencionais. Mas não há problema de incompatibilidade, porque desenvolvemos uma sofisticada tecnologia de compilador / intérprete que pode traduzir cada modelo em outro conforme necessário (que também é a base da tese de Church-Turing).

Agora, você nunca deve considerar o seu computador como hardware bruto. Ele contém circuitos booleanos que fazem um processamento muito elementar. Mas grande parte é dirigida por microprogramas dentro do computador que você nunca conhece. Então você tem o sistema operacional que faz com que sua máquina pareça ainda diferente do que o hardware faz. Além disso, você pode ter uma máquina virtual que executa código de bytes e, em seguida, uma linguagem de alto nível, como Pyva e Jathon ou Haskell ou OCaml, que pode ser compilado em código de bytes.

Em cada nível, você vê um modelo de computação diferente. É muito difícil separar o nível de hardware do nível de software, portanto, atribuir um modelo computacional específico a uma máquina. E, como são intertraduzíveis, a idéia de um modelo de computação de hardware definitivo é praticamente uma ilusão.

A máquina de cálculo lambda existe: é um computador que pode reduzir as expressões de cálculo lambda. Anúncio que é feito com facilidade.

Sobre arquiteturas especializadas de máquinas

Na verdade, complementando a resposta de Peter Taylor e acompanhando a inter-vitória de hardware / software, máquinas especializadas foram produzidas para se adaptarem melhor a um paradigma específico e tiveram seu software básico escrito em uma linguagem de programação baseada nesse paradigma.

Esses incluem

• O Burroughs B5000 e seus sucessores (década de 1960), que foram adaptados para uma implementação eficiente da recursão, representada na época pelo idioma Algol 60 .

• O Western Digital WD / 9000 Pascal MicroEngine , uma máquina baseada em um bytecode microprogramado especializado para a linguagem de programação Pascal , no início dos anos 80.

• Diversas marcas de máquinas Lisp na década de 1980.

Fundamentalmente, essas também são estruturas de hardware imperativas, mas atenuadas com recursos especiais de harware ou intérpretes microprogramados para melhor adaptação ao paradigma pretendido.

Na verdade, o hardware especializado para paradigmas específicos parece nunca ter tido sucesso a longo prazo. O motivo é que a tecnologia de compilação para implementar qualquer paradigma no hardware vanilla se tornou cada vez mais eficaz, de modo que o hardware especializado não era tão necessário. Além disso, o desempenho do harware estava melhorando rapidamente, mas o custo da melhoria (incluindo a evolução do software básico) foi mais facilmente amortizado no hardware básico do que no hardware especializado. O hardware especializado não poderia competir a longo prazo.

No entanto, e embora eu não tenha dados precisos sobre isso, eu suspeitaria que esses empreendimentos deixaram algumas idéias que influenciaram a evolução de máquinas, memórias e arquitetura de conjuntos de instruções.

Turing-complete é apenas um nome. Você pode chamá-lo de Abdul-complete, se quiser. Os nomes são decididos historicamente e geralmente recebem o nome das pessoas "erradas". É um processo sociológico que não possui critérios claros. O nome não tem significado além de sua semântica oficial.

Linguagens imperativas não são baseadas em máquinas de Turing. Eles são baseados em máquinas RAM. Seu computador é uma máquina de RAM. Máquinas de Turing são um bom modelo teórico, mas não são um modelo muito bom de computadores reais.

Linguagens de programação baseadas em outros paradigmas podem ser muito bem-sucedidas, mesmo que a CPU subjacente não as suporte nativamente; por exemplo, impressoras executam um idioma de pilha. Há mais na programação do que no código da máquina.

Porque "Turing-complete" significa apenas "ele pode calcular o que uma máquina Turing pode calcular".

Parece que uma de suas perguntas ainda não foi respondida:

Se for esse o caso, qual seria o equivalente a uma máquina de cálculo lambda?

Uma máquina Lisp . Hardware projetado especificamente para se ajustar ao modelo de computação LISP. O artigo da Wikipedia fala sobre produtos comerciais, mas meu diretor de estudos da universidade tinha um construído à mão em seu escritório.

as linguagens funcionais na forma de cálculo lambda inventadas por Church foram comprovadas como Turing completas. esta é uma prova matemática real que pode ser encontrada em artigos científicos publicados "reduzindo" o cálculo lambda a operações / cálculos em máquinas de Turing. por volta do tempo do artigo de Turings, 1936 e depois, diferentes modelos "abrangentes" de computação foram propostos / circulando. foi não imediatamente percebi que todos eram equivalentes. as provas de que eram equivalentes foram publicadas aproximadamente no final das décadas de 1930 e 1940, após o artigo de Turings.

a máquina de Turing é . é um notável objeto / construção conceitual que une / unifica dois mundos diferentes, o aplicado e o teórico. dá um novo significado abstrato às entidades físicas, por exemplo, "tempo e espaço". não é mera coincidência que os matemáticos às vezes se refiram a "tecnologia", "maquinário" ou "dispositivos" de provas. Turing conseguiu engenhosamente fundir tudo isso em sua invenção conceitual. sua definição é bastante simples, mas sua análise exibe alguns dos comportamentos emergentes mais extraordinários já vistos na história do pensamento científico / matemático. Turing foi o primeiro cientista / matemático a compreender muito desse significado / poder / potencial. conceitualmente (mas não funcionalmente) mais simples que os outros modelos e isso é provavelmente uma parte significativa do motivo pelo qual a completude de Turing recebeu o nome dele. outras idéias, como o cálculo lambda, são mais abstratas e começaram / se originaram principalmente na teoria matemática / lógica. Turing propôs uma máquina teórica . uma "máquina" é literalmente um "dispositivo físico"