Free software versus software idea patents
tjreedy at udel.edu
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 udel.edu> 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