Free software versus software idea patents

Terry Reedy tjreedy at
Tue Apr 12 21:39:05 CEST 2011

On 4/12/2011 2:44 PM, Dan Stromberg wrote:
> On Tue, Apr 12, 2011 at 10:32 AM, Terry Reedy<tjreedy at>  wrote:
>> On 4/11/2011 4:36 AM, rusi wrote:
>>> 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

More information about the Python-list mailing list