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, but I believe Turing Machines are infinite. 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. -- http://mail.python.org/mailman/listinfo/python-list