2 ms·
One issue with lambda calculus that could indicate it is not the "simplest possible computational framework" is that there is no bound on the amount of work a s
by danharaj 6y ago
One issue with lambda calculus that could indicate it is not the "simplest possible computational framework" is that there is no bound on the amount of work a single step of beta reduction will do. It is dubious to call such a black box computational action simple. You can decompose beta reduction into smaller steps but I wouldn't say it's obvious which refinement of lambda calculus is simplest.
Furthermore, the complexity of beta reduction means that there are a multiplicity of strategies for executing it which are external to the definition of lambda calculus. Not so simple.
Lambda calculus also has a bias for the flow of information from the leaves of a term up to its root while demands flow from the root to the leaves. This is basically how functions work but it produces an asymmetry between a term and its environment. Higher order terms allow information to flow in very complex ways but there are simple computational ideas that are hard to capture in lambda calculus without monstrously complicated recursion schemes or modifications to lambda calculus. Think of the symmetric possibilities of flow of information in a spreadsheet.
Asynchronous computation, concurrent processing, and sharing of work have been with us since the dawn of computers and have their own basic mechanisms and principles, but they are at odds with beta reduction and functional information flow.
Lambda calculus is amazing but there surely is a frontier beyond it. Human reasoning is frequently biased to think functionally, in terms of inputs and outputs where outputs are treated differently from inputs, but the world and computation are full of relations and processes, too.