✍ A mais pequena, e universal, linguagem de programação

Cálculo lambda...

O cálculolatex2png equation é mais pequena, e universal, linguagem de programação. Consiste apenas numa única regra de transformação (substituição de uma variável) e um modo de definir funções. Foi construída por Alonzo Church em 1930 como um modo de formalizar o conceito de computabilidade. O cálculo latex2png equation é universal no sentido em que qualquer função computável pode ser expressa e calculada (evaluated) usando este formalismo. É pois equivalente a uma máquina de Turing. No entanto, este cálculo enfatiza o uso de regras de transformação e não considera em muito detalhe qual a possível máquina em que tais transformações poderiam ter lugar. Pode dizer-se que é uma abordagem que se aproxima mais do software do que do hardware.

Algumas funções matemáticas são computáveis, outras não. Em geral nas linguagens de programação é possível escrever um programa que implementa toda e qualquer função computável em principio. Por outro lado o limite da computabilidade, ou daquilo que é computável, também limita o tipo de coisas que uma linguagem de programação pode fazer.

Uma função parcial é uma função que está definida para alguns valores do seu argumento e não definida para outros, isto é, partilha da definição de função apenas a unicidade da imagem dado um objecto.

Intuitivamente uma função é computável se existe um programa que a calcula (computa). Mais especificamente, uma função é computável se existe um algoritmo que para um dado x o programa pára (halt), ao fim de um tempo finito, e dá a resposta y=f(x).

O que é mais estranho é que, apesar de se poder escrever programas que implementam o cálculo de funções, muitas vezes nem sempre é possível responder à pergunta simples: dado um input x será que um dado programa nos dá a resposta y. Em geral, o problema de determinar se um dado programa pára, ou não, é não computável! Ou seja, não é possível, em geral, dado um programa, construir um outro programa que nos diz se o primeiro nos dá a resposta.

Palavras chave/keywords: lambda, programação, linguagem, halt

Criado/Created: NaN

Última actualização/Last updated: 23-01-2017 [09:19]


GNU/Emacs

1999-2017 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.