rusi wrote:
------------------------
From
http://www.cse.uconn.edu/~dqg/papers/cie05.pdf
may be of interest (and also other papers of Peter Wegner questioning
the universality of Turing machines lambda calculus etc)
This is very interesting indeed.
see: http://en.wikipedia.org/wiki/Lambda_calculus
This block quote below is sited from the above link... and gets at
my point in a simple way... but the remaining article is worth a read
too. This goes somewhat beyond the simple single taped Turing machine
concept. We are not talking about the 'universality' of the machine...
only that the software running in the machine is 'equivalent' to the
lambda calculus.
Software itself (the source symbols specifically) can be argued to
be nothing more nor less than another form of the symbols themselves
used in the lambda calculus. In fact, we ought to be able to build an
interpreter for reading and running lambda notation, or translating pure
lambda notations into any source lang we desire. Why not?
see also, for interest only:
http://lambda-the-ultimate.org/node/1490
=====block quote=====
Lambda calculus and programming languages
As pointed out by Peter Landin's 1965 paper A Correspondence between
ALGOL 60 and Church's Lambda-notation, sequential procedural programming
languages can be understood in terms of the lambda calculus, which
provides the basic mechanisms for procedural abstraction and procedure
(subprogram) application.
Lambda calculus reifies "functions" and makes them first-class objects,
which raises implementation complexity when implementing lambda
calculus. A particular challenge is related to the support of
higher-order functions, also known as the Funarg problem. Lambda
calculus is usually implemented using a virtual machine approach. The
first practical implementation of lambda calculus was provided in 1963
by Peter Landin, and is known as the SECD machine. Since then, several
optimized abstract machines for lambda calculus were suggested, such as
the G-machine[12] and the categorical abstract machine.
The most prominent counterparts to lambda calculus in programming are
functional programming languages, which essentially implement the
calculus augmented with some constants and datatypes. Lisp uses a
variant of lambda notation for defining functions, but only its purely
functional subset ("Pure Lisp") is really equivalent to lambda calculus.
=====/block quote=====
kind regards,
m harris
--
http://mail.python.org/mailman/listinfo/python-list
