A mais pequena, e universal, linguagem de programação
O cálculo
é 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 é 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, haltCriado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo