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

22

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.

Abdul
fonte
6
Não é uma resposta, mas você mencionou que nem todas as versões do cálculo lambda são Turing Complete. O Cálculo Lambda de Digitação Simples e as versões mais fortes do Coq e Agda com base na verificação de terminação não são o Turing Complete (porque eles têm problemas de parada decidíveis). Linguagens fortemente tipadas como Haskell e SML contornam isso, permitindo a recursão arbitrária com um combinador de ponto de fixação, um termo com tipo (a -> a) -> a.
jmite
É tão errado dizer "definido para ser Turing completo". Podemos mudar o título?
Andrej Bauer 04/07
@AndrejBauer Obrigado pela edição do título, mas estou curioso para saber por que está ( definido como Turning Complete ) errado? É porque é um adjetivo? Descreveria uma palavra melhor que definir?
Abdul
1
@ Abdul Bem, o problema é a palavra "definido". Se você diz que "linguagens funcionais são definidas como Turing completas", está dizendo que a definição de "linguagem funcional" ou a definição de "Turing completa" afirma que as linguagens funcionais são completas de Turing. De fato, nenhuma definição diz isso.
22418 Tanner Swett

Respostas:

20

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

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.

babou
fonte
A escolha da máquina de Turing como referência, na medida em que ela é realmente feita, é motivada principalmente pela história: Turing foi a primeira a criar uma definição satisfatória de computabilidade.
Yuval Filmus
@YuvalFilmus E por que era mais uma "definição satisfatória de computabilidade"?
babou 10/07/2015
Foi o que Gödel pensou. Bob Soare tem algumas palavras a dizer sobre o assunto aqui: cs.uchicago.edu/~soare/Publications/compute.ps .
Yuval Filmus
@YuvalFilmus São 46 páginas. Quero dizer, estou dando algumas razões pelas quais deveria ser mais satisfatório. Eles podem ser ingênuos. Se houver uma mais convincente que explique o sucesso, ela será mencionada explicitamente.
babou
Veja a Seção 3.2. Havia definições anteriores de computabilidade, mas elas não eram convincentes. O de Turing foi o primeiro que foi convincente, pelo menos para algumas pessoas importantes.
Yuval Filmus
21

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.

Yuval Filmus
fonte
"As máquinas de Turing são um bom modelo teórico, mas não são um modelo muito bom de computadores reais". Exceto pela falta de memória infinita, por que outras razões não são um bom modelo para computadores reais? Além disso, eu estava correto ao pensar que as linguagens funcionais se baseiam no cálculo lambda?
Abdul
5
λ
11
Linguagens imperativas tendem a permitir acessos de matriz em tempo constante, em C A[x]. Máquinas de Turing não podem fazer isso em tempo constante. É por isso que, mesmo na ciência da computação teórica, o tempo de execução dos algoritmos é analisado no modelo de máquina RAM, e não no modelo de máquina de Turing.
Yuval Filmus
14
Na verdade, as Máquinas de Turing são uma boa quantidade de computadores reais ... exceto que, quando Turing escreveu seu artigo, "computador" era uma descrição do trabalho de um humano que trabalha com caneta e papel. A cabeça de leitura / gravação é um modelo de caneta, a fita é um modelo de uma pilha infinita de folhas de papel (basta cortá-las em pequenas tiras e colá-las), o alfabeto é um modelo de, bem, nosso alfabeto , e as transições finitas são um modelo da quantidade limitada de regras que se pode manter na cabeça.
Jörg W Mittag
3
Essa foi a melhor idéia que eu já tive sobre por que diabos escolheu a máquina de Turing. Eu sempre me perguntei "por que ele escolheu um modelo de computação tão ruim?". Sempre pensei que se tivesse me deixado inventar a teoria da computação (que Deus nos ajude; não demoraríamos muito) provavelmente teria ainda escolhido um modelo melhor de computação. Agora eu chego de onde ele estava vindo e faz muito mais sentido.
Jake
10

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

David Richerby
fonte
Turing-complete também poderia ser nomeado em homenagem a Turing (a pessoa), que apresentou a primeira definição filosoficamente satisfatória de computabilidade; ou poderia ser nomeado em homenagem ao artigo de Turing no qual ele descreve esse conceito.
Yuval Filmus
1
@YuvalFilmus: ele poderia ser nomeado após a mãe de Alan Turing, mas a afirmação aqui é que não é ;-)
Steve Jessop
@YuvalFilmus Pode ser (embora, até onde eu saiba, não seja). Mas de onde o termo vem é de importância apenas secundária. O que importa aqui é o que o termo significa .
David Richerby
2
Isso é curto e agradável, mas talvez um pouco curto demais. O que uma máquina de Turing "faz"? Bem, entre as coisas que eles "fazem" está a leitura e gravação de fitas, que as expressões lambda não fazem. Melhor seria "Modelos de computação completos em Turing permitem que todas as funções computáveis ​​sejam computadas".
Theodore Norvell
@TheodoreNorvell Acho que seu comentário é semelhante ao que eu estava pensando. Eu sabia que o cálculo lambda e a máquina de Turing são equivalentes em potência, mas diferentes em mecanismo (e agora aprendi que existem outros), mas estava pensando se o termo "perfeição de Turing" era de alguma forma especial para a máquina de Turing, ou se fosse apenas um nome.
Abdul
6

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.

Peter Taylor
fonte
0

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"

vzn
fonte
em outras palavras, pode-se dizer que Turing foi o primeiro a identificar / "reconhecer" o significado do fenômeno da completude de Turing e, por sua vez, CS "o reconhece" por essa conquista monumental através do uso do termo.
vzn
Sua redução é o contrário. Para provar a integridade de Turing de algum sistema,X, você precisa reduzir o cálculo da máquina de Turing para esse sistema.
David Richerby