On 4/12/2011 2:44 PM, Dan Stromberg wrote:
On Tue, Apr 12, 2011 at 10:32 AM, Terry Reedy<tjre...@udel.edu> wrote:
On 4/11/2011 4:36 AM, rusi wrote:
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)
Thank you for that reference. In summary, it says that while Turing machine
are universal for finite function calculations, infinite interactive
processes are not (finite) function calculations, and therefore need an
extension to TMs. This is pretty obviously correct.
Python iterators, and especially generators, implement the extension that
the authors call 'persistent Turing machines' (PTMs, section 6.2), except
that iterators (and generators by default) operate in 'pull' mode, while
they describe PTMs as operating in 'push' mode (as with generator.send()).
I didn't read the paper,
If you are interested in the subject, I recommend it. It is pretty clear
and not long.
but I believe Turing Machines are infinite.
An 'effective' algorithm/TM turns a finite input into a finite output in
a finite time, without outside intervention, and then halts. The Halting
Problem arose because of the requirement that effective machines halt,
and indeed, a particular proof that a particular algorithm halts on all
inputs in the defined domain is part of the proof that it is 'correct'.
Interactive processes don't seem, at least to me, to change the
applicability of Turing Machines - you merely pretend you have a bunch
of squares preinitialized with your various inputs. If you have an
infinite number of inputs, that's fine, you can have them with a
preinitialized turing machine.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
