Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #55239 > unrolled thread

Tail recursion to while iteration in 2 easy steps

Back to article view | Back to comp.lang.python

Contents

  Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-01 17:30 -0400
    Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-01 22:16 -0700
      Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:23 +0200
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-02 06:29 -0700
      Re: Tail recursion to while iteration in 2 easy steps Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-03 22:57 +0530
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-04 03:52 -0700
    Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:17 +0200
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 11:59 -0700
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 14:05 -0700
        Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-04 11:49 +0200
          Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 10:51 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 18:32 -0400
            Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-07 19:15 +0200
              Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-07 19:57 +0200
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:56 +0200
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 12:49 +0300
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-07 16:42 -0400
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:19 -0400
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:41 +0200
              Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-07 22:39 +0100
              Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 18:03 -0400
              Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 15:47 -0700
                Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-07 23:50 +0000
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:24 -0700
                    Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 20:17 -0700
                      Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 10:46 +0530
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 22:44 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-10-08 07:43 +0100
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:31 +0530
                            Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-08 06:33 -0700
                        Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve@pearwood.info> - 2013-10-08 07:50 +0000
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:16 +0530
                            Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 13:11 +0000
                              Re: Formal-ity and the Church-Turing thesis Robert Day <robertkday@gmail.com> - 2013-10-08 14:25 +0100
                              Re: Formal-ity and the Church-Turing thesis Chris Angelico <rosuav@gmail.com> - 2013-10-09 08:36 +1100
                      Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 22:19 -0700
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 23:01 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-08 10:39 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:16 -0700
                    Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 02:36 +0000
                      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:27 -0700
                        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve@pearwood.info> - 2013-10-08 09:22 +0000
                          Re: Tail recursion to while iteration in 2 easy steps Charles Hixson <charleshixsn@earthlink.net> - 2013-10-09 15:45 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:46 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:25 +0300
                  Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:18 +0200
                Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:45 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:34 -0700
      Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 18:17 -0400
        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 01:24 +0000
          Re: Tail recursion to while iteration in 2 easy steps Dave Angel <davea@davea.name> - 2013-10-03 01:39 +0000
          Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-03 02:46 +0100
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 02:34 +0000
              Re: Tail recursion to while iteration in 2 easy steps Chris Angelico <rosuav@gmail.com> - 2013-10-03 14:14 +1000
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:16 -0400
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-03 15:04 -0400
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 22:41 -0400
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 01:30 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 23:06 -0400
          Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:14 -0400
          Literal syntax for frozenset, frozendict (was: Tail recursion to while iteration in 2 easy steps) Ben Finney <ben+python@benfinney.id.au> - 2013-10-04 10:18 +1000
          Re: Literal syntax for frozenset, frozendict Ethan Furman <ethan@stoneleaf.us> - 2013-10-03 18:31 -0700
      Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-03 14:52 +0000
        Re: Tail recursion to while iteration in 2 easy steps Neil Cerutti <neilc@norwich.edu> - 2013-10-03 16:03 +0000
          Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 10:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:41 -0600
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:46 -0600
              Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 11:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-04 14:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 17:14 -0400
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-05 09:39 +0200
            Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:27 -0400
              Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:43 +0200

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#56335

Alain Ketterlin <alain@dpt-info.u-strasbg.fr> writes:

> BTW, does the original callable object have a ref counter? Is it garbage
> collected in that case? If not, would it be considered a bug?

In CPython ALL objects have ref counters.
-- 
Piet van Oostrum <piet@vanoostrum.org>
WWW: http://pietvanoostrum.com/
PGP key: [8DAE142BE17999C4]

[toc] | [prev] | [next] | [standalone]

#56336

>> That's fine. My point was: you can't at the same time have full
>> dynamicity *and* procedural optimizations (like tail call opt).
>> Everybody should be clear about the trade-off.
>
> Your wrong. Full dynamics is not in contradiction with tail call
> optimisation. Scheme has already done it for years. You can rebind
> names to other functions in scheme and scheme still has working
> tail call optimisatiosn.

Yeah, and this is where two models of computation have been conflated,
creating magical effects, confusing everybody.  I challenge you to get
down to the machine code in scheme and formally describe how it's
doing both.
-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56337

On Mon, 07 Oct 2013 15:47:26 -0700, Mark Janssen wrote:

> I challenge you to get
> down to the machine code in scheme and formally describe how it's doing
> both.

For which machine?

Or are you assuming that there's only one machine code that runs on all 
computing devices?


Frankly, asking somebody to *formally* describe a machine code 
implementation strikes me as confused. Normally formal descriptions are 
given in terms of abstract operations, often high level operations, 
sometimes *very* high level, and rarely in terms of low-level "flip this 
bit, copy this byte" machine code operations. I'm not sure how one would 
be expected to generate a formal description of a machine code 
implementation.

But even putting that aside, even if somebody wrote such a description, 
it would be reductionism gone mad. What possible light on the problem 
would be shined by a long, long list of machine code operations, even if 
written using assembly mnemonics?

Far more useful would be a high-level description of Scheme's programming 
model. If names can be rebound on the fly, how does Scheme even tell 
whether something is a recursive call or not?

def foo(arg):
    do stuff here
    foo(arg-1)  # how does Scheme know that this is the same foo?



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#56338

> Only that you've got a consistent, stable (and therefore,
> formalizable) translation from your language to the machine.  That's
> all.  Everything else is magic.  Do you know that the Warren
> Abstraction Engine used to power the predicate logic in Prolog into
> machien code for a VonNeumann machine is so complex, no one has
> understood it (or perhaps even verified it)?

Sorry, I mean the Warren Abstraction Machine (or WAM).  I refer you to
www.cvc.uab.es/shared/teach/a25002/wambook.pdf.

Now, one can easily argue that I've gone too far to say "no one has
understood it" (obviously), so it's very little tongue-in-cheek, but
really, when one tries to pretend that one model of computation can be
substituted for another (arguing *for* the Church-Turing thesis), they
are getting into troubling territory (it is only a thesis,
remember)....

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56343 — Formal-ity and the Church-Turing thesis

On Tuesday, October 8, 2013 5:54:10 AM UTC+5:30, zipher wrote:
> Now, one can easily argue that I've gone too far to say "no one has
> understood it" (obviously), so it's very little tongue-in-cheek, but
> really, when one tries to pretend that one model of computation can be
> substituted for another (arguing *for* the Church-Turing thesis), they
> are getting into troubling territory (it is only a thesis,
> remember)....

The CT thesis is scientific and provable in one sense and vague/philosophical in another.
The Science: Turing computability and lambda-computability are equivalent.
The proofs just consist of writing interpreters for one in terms of the other.

The philosophy: *ALL* computational models are turing equivalent (and therefore lambda-equivalent) or weaker.
The Idea (note not proof) is that for equivalence one can write pair-interpreters like above. For the 'weaker' case, (eg DFA and TMs) one proves that TMs can interpret DFAs and disproves the possibility of the other direction.

This must remain an idea (aka thesis) and not a proof because one cannot conceive of all possible computational models.
It is hard science however for all the models that anyone has so far come up with.

Now there are caveats to this which I wont go into for now.

As for:

> I challenge you to get down to the machine code in scheme and formally 
> describe how it's doing both. 

I can only say how ironic it sounds to someone who is familiar with the history of our field: 
Turing was not a computer scientist (the term did not exist then) but a mathematician.  And his major contribution was to create a form of argument so much more rigorous than what erstwhile mathematicians were used to that he was justified in calling that math as a machine.

The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
To get out of this confusion ask yourself: Is it finite or infinite?
If the TM were finite it would be a DFA
If the Intel-machine (and like) were infinite they would need to exist in a different universe.

And so when you understand that TMs are just a kind of mathematical rewrite system (as is λ calculus as are context free grammars as is school arithmetic etc etc) you will not find the equivalence so surprising

[toc] | [prev] | [next] | [standalone]

#56346 — Re: Formal-ity and the Church-Turing thesis

On Tue, Oct 8, 2013 at 8:47 AM, rusi <rustompmody@gmail.com> wrote:
> I can only say how ironic it sounds to someone who is familiar with the history of our field:
> Turing was not a computer scientist (the term did not exist then) but a mathematician.  And his major contribution was to create a form of argument so much more rigorous than what erstwhile mathematicians were used to that he was justified in calling that math as a machine.
>
> The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
> To get out of this confusion ask yourself: Is it finite or infinite?
> If the TM were finite it would be a DFA
> If the Intel-machine (and like) were infinite they would need to exist in a different universe.

With due respect Sir, you saying that Turing machine not a machine?
Very confusion Sir!!!

>
> And so when you understand that TMs are just a kind of mathematical rewrite system (as is λ calculus as are context free grammars as is school arithmetic etc etc) you will not find the equivalence so surprising



-- 
Ravi

[toc] | [prev] | [next] | [standalone]

#56348 — Re: Formal-ity and the Church-Turing thesis

On Tuesday, October 8, 2013 10:46:50 AM UTC+5:30, Ravi Sahni wrote:
> With due respect Sir, you saying that Turing machine not a machine?
> Very confusion Sir!!!

Thanks Ravi for the 'due respect' though it is a bit out of place on a list like this :-)

Thanks even more for the 'very confusion'.  I can tell you being a teacher for 25 years that the most terrifying thing is the Dunning Kruger effect -- students who are utterly clueless and dont have a frigging clue about that.

Ive seen PhDs in CS ask questions in compiler-related degree projects that they would not ask if they really understood the halting problem.
[Or were you suggestig that I am the confused? :-) ]

So yes, its a big thing to be confused and to accept that.

To explain at length will be too long and OT (off-topic) for this list.
I'll just give you a link and you tell me what you make of it:
http://sloan.stanford.edu/mousesite/Secondary/Whorfframe2.html
[mainly concentrate on the first section]

[toc] | [prev] | [next] | [standalone]

#56351 — Re: Formal-ity and the Church-Turing thesis

On 08/10/2013 06:44, rusi wrote:
> On Tuesday, October 8, 2013 10:46:50 AM UTC+5:30, Ravi Sahni wrote:
>> With due respect Sir, you saying that Turing machine not a machine?
>> Very confusion Sir!!!
>
> Thanks Ravi for the 'due respect' though it is a bit out of place on a list like this :-)
>

With due respect Sir I'd like to point out that this appears to have 
very little to do (directly) with Python, so to go completely off topic 
I'll point out that my nephew is currently working on the film about the 
life of said Alan Turing :)

-- 
Roses are red,
Violets are blue,
Most poems rhyme,
But this one doesn't.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#56393 — Re: Formal-ity and the Church-Turing thesis

On Tue, Oct 8, 2013 at 11:14 AM, rusi <rustompmody@gmail.com> wrote:
> To explain at length will be too long and OT (off-topic) for this list.
> I'll just give you a link and you tell me what you make of it:
> http://sloan.stanford.edu/mousesite/Secondary/Whorfframe2.html


I am trying to read link. Very new idea: Buildings can catch fire by
wrong boards!!

Later part difficult for me to read.  (My English not powerful --please excuse.)
I will make my fullest efforts to read on your recommend but I not
clear the connection with computers, programming, computer science and
so on.  Also this Mr. Mark Lawrence question.

-- 
Ravi

[toc] | [prev] | [next] | [standalone]

#56396 — Re: Formal-ity and the Church-Turing thesis

On Tuesday, October 8, 2013 6:31:21 PM UTC+5:30, Ravi Sahni wrote:
> On Tue, Oct 8, 2013 at 11:14 AM, rusi  wrote:
> > To explain at length will be too long and OT (off-topic) for this list.
> > I'll just give you a link and you tell me what you make of it:
> > http://sloan.stanford.edu/mousesite/Secondary/Whorfframe2.html
> 
> 
> I am trying to read link. Very new idea: Buildings can catch fire by
> wrong boards!!
> 
> Later part difficult for me to read.  (My English not powerful --please excuse.)
> I will make my fullest efforts to read on your recommend 

Hell No! I only asked you to read the first page! 
[And 'Mr. Mark' will scold<wink>]

> but I not
> clear the connection with computers, programming, computer science and
> so on.  Also this Mr. Mark Lawrence question.

Once you get that buildings can catch fire by wrong terminology you should get that:
- the term 'Turing machine' can make people think its a machine even though its a mathematical formalism
- the term 'λ-calculus' (partly due to the word calculus and partly due to the greek lambda) makes people think its mathematics even though its a computational framework

[toc] | [prev] | [next] | [standalone]

#56364 — Re: Formal-ity and the Church-Turing thesis

On Tue, 08 Oct 2013 10:46:50 +0530, Ravi Sahni wrote:

> On Tue, Oct 8, 2013 at 8:47 AM, rusi <rustompmody@gmail.com> wrote:
>> I can only say how ironic it sounds to someone who is familiar with the
>> history of our field: Turing was not a computer scientist (the term did
>> not exist then) but a mathematician.  And his major contribution was to
>> create a form of argument so much more rigorous than what erstwhile
>> mathematicians were used to that he was justified in calling that math
>> as a machine.
>>
>> The irony is that today's generation assumes that 'some-machine'
>> implies its something like 'Intel-machine'. To get out of this
>> confusion ask yourself: Is it finite or infinite? If the TM were finite
>> it would be a DFA If the Intel-machine (and like) were infinite they
>> would need to exist in a different universe.
> 
> With due respect Sir, you saying that Turing machine not a machine? Very
> confusion Sir!!!

The mathematical ideal Turing Machine has an infinitely long tape, 
equivalent to infinite memory, and may take an unbounded amount of time 
to complete the computation. Since no *actual* physical machine can be 
infinitely big, and in practice there are strict limits on how long we 
are willing to wait for a computation to complete, in the *literal* 
sense, Turing Machines are not *actual* machines. They are a mathematical 
abstraction.

But in practice, we can wave our hands and ignore this fact, and consider 
only not-quite-Turing Machines with finite amounts of tape, and note that 
they are equivalent to physical machines with finite amounts of memory. 
One could even build such a finite Turing Machine, although of course it 
would be very slow. Or one can simulate it in software.

So in that sense, computers are Turing Machines. Anything a physical 
computing device can compute, a Turing Machine could too. The converse is 
not true though: a Turing Machine with infinite tape can compute things 
where a real physical device would run out of memory, although it might 
take longer than anyone is willing to wait.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#56391 — Re: Formal-ity and the Church-Turing thesis

On Tue, Oct 8, 2013 at 1:20 PM, Steven D'Aprano <steve@pearwood.info> wrote:
> On Tue, 08 Oct 2013 10:46:50 +0530, Ravi Sahni wrote:
>
>> On Tue, Oct 8, 2013 at 8:47 AM, rusi <rustompmody@gmail.com> wrote:
>>> I can only say how ironic it sounds to someone who is familiar with the
>>> history of our field: Turing was not a computer scientist (the term did
>>> not exist then) but a mathematician.  And his major contribution was to
>>> create a form of argument so much more rigorous than what erstwhile
>>> mathematicians were used to that he was justified in calling that math
>>> as a machine.
>>>
>>> The irony is that today's generation assumes that 'some-machine'
>>> implies its something like 'Intel-machine'. To get out of this
>>> confusion ask yourself: Is it finite or infinite? If the TM were finite
>>> it would be a DFA If the Intel-machine (and like) were infinite they
>>> would need to exist in a different universe.
>>
>> With due respect Sir, you saying that Turing machine not a machine? Very
>> confusion Sir!!!
>
> The mathematical ideal Turing Machine has an infinitely long tape,
> equivalent to infinite memory, and may take an unbounded amount of time
> to complete the computation. Since no *actual* physical machine can be
> infinitely big, and in practice there are strict limits on how long we
> are willing to wait for a computation to complete, in the *literal*
> sense, Turing Machines are not *actual* machines. They are a mathematical
> abstraction.
>
> But in practice, we can wave our hands and ignore this fact, and consider
> only not-quite-Turing Machines with finite amounts of tape, and note that
> they are equivalent to physical machines with finite amounts of memory.
> One could even build such a finite Turing Machine, although of course it
> would be very slow. Or one can simulate it in software.
>
> So in that sense, computers are Turing Machines. Anything a physical
> computing device can compute, a Turing Machine could too. The converse is
> not true though: a Turing Machine with infinite tape can compute things
> where a real physical device would run out of memory, although it might
> take longer than anyone is willing to wait.

Thanks Sir the detailed explanation. You are offering me many thoughts
inside few words so I will need some time to meditate upon the same.

Presently Sir, I wish to ask single question: What you mean "wave our hands"??

Thanks
-- 
Ravi

[toc] | [prev] | [next] | [standalone]

#56394 — Re: Formal-ity and the Church-Turing thesis

On Tue, 08 Oct 2013 18:16:01 +0530, Ravi Sahni wrote:

>> So in that sense, computers are Turing Machines. Anything a physical
>> computing device can compute, a Turing Machine could too. The converse
>> is not true though: a Turing Machine with infinite tape can compute
>> things where a real physical device would run out of memory, although
>> it might take longer than anyone is willing to wait.
> 
> Thanks Sir the detailed explanation. You are offering me many thoughts
> inside few words so I will need some time to meditate upon the same.
> 
> Presently Sir, I wish to ask single question: What you mean "wave our
> hands"??

It is an idiom very common in Australia. (It may not be well known in the 
rest of the English-speaking world.) It means to figuratively flap one's 
hands around in the air while skipping over technical details or 
complications. For example, we often talk about "hand-wavy estimates" for 
how long a job will take: "my hand-wavy estimate is it will take two 
days" is little better than a guess.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#56404 — Re: Formal-ity and the Church-Turing thesis

[Multipart message — attachments visible in raw view] — view raw

On 08/10/13 14:11, Steven D'Aprano wrote:
> On Tue, 08 Oct 2013 18:16:01 +0530, Ravi Sahni wrote:
>
>>
>> Presently Sir, I wish to ask single question: What you mean "wave our
>> hands"??
> It is an idiom very common in Australia. (It may not be well known in the
> rest of the English-speaking world.) It means to figuratively flap one's
> hands around in the air while skipping over technical details or
> complications.
It's known elsewhere as well (though mostly in technical circles) - it's 
in the Jargon File as http://www.catb.org/jargon/html/H/handwave.html. 
<http://www.catb.org/jargon/html/H/handwave.html>
<http://www.catb.org/jargon/html/H/handwave.html>

[toc] | [prev] | [next] | [standalone]

#56445 — Re: Formal-ity and the Church-Turing thesis

On Wed, Oct 9, 2013 at 12:11 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 08 Oct 2013 18:16:01 +0530, Ravi Sahni wrote:
>
>>> So in that sense, computers are Turing Machines. Anything a physical
>>> computing device can compute, a Turing Machine could too. The converse
>>> is not true though: a Turing Machine with infinite tape can compute
>>> things where a real physical device would run out of memory, although
>>> it might take longer than anyone is willing to wait.
>>
>> Thanks Sir the detailed explanation. You are offering me many thoughts
>> inside few words so I will need some time to meditate upon the same.
>>
>> Presently Sir, I wish to ask single question: What you mean "wave our
>> hands"??
>
> It is an idiom very common in Australia. (It may not be well known in the
> rest of the English-speaking world.) It means to figuratively flap one's
> hands around in the air while skipping over technical details or
> complications. For example, we often talk about "hand-wavy estimates" for
> how long a job will take: "my hand-wavy estimate is it will take two
> days" is little better than a guess.

A derivative of the term has gone mainstream, too:

http://tvtropes.org/pmwiki/pmwiki.php/Main/HandWave

The term is commonly used when moving to a higher level of abstraction
- we all know a computer doesn't have a soul, can't "feel", and is
ultimately just executing code and crunching numbers, but we handwave
that (eg) the computer "thought" that this program was a risk, and
that's why it quarantined it. When you're trying to explain to some
user that he can't email .EXE files around, it's easier to take the
slightly-inaccurate but simple explanation, hence the handwaves.

ChrisA

[toc] | [prev] | [next] | [standalone]

#56347 — Re: Formal-ity and the Church-Turing thesis

> On Tuesday, October 8, 2013 5:54:10 AM UTC+5:30, zipher wrote:
>> Now, one can easily argue that I've gone too far to say "no one has
>> understood it" (obviously), so it's very little tongue-in-cheek, but
>> really, when one tries to pretend that one model of computation can be
>> substituted for another (arguing *for* the Church-Turing thesis), they
>> are getting into troubling territory (it is only a thesis,
>> remember)....
>
> The CT thesis is scientific and provable in one sense and vague/philosophical in another.
> The Science: Turing computability and lambda-computability are equivalent.
> The proofs just consist of writing interpreters for one in terms of the other.

Ah, good, a fellow theoretician.  Now it's nice that you use language
that makes it seem quite clear, but understand that there's a hidden,
subconscious, *cultural* encoding to your *statement*.  The use of the
term "equivalent", for example.  Equivalent for the programmer, or for
the machine?  (etc., et cetera), and further:  "writing interpreters
for one in terms of the other", but again, this will change depending
on your pragmatic requirements.  To the theorist, you've accomplished
something, but then that is a self-serving kind of accomplishment.  To
the programmer, operating under different requirements, you haven't
accomplished anything.  I don't have an infinite stack to implement
lambda calculus, but I can treat my computer's memory as a TM and
*practically* infinite and only rarely hit against the limits of
physicality.  This is just being "respectful"... ;^)

(For the purposes of discussion, if I make a word in CamelCase, I am
referring to a page on the WikiWikiWeb with the same name:
http://c2.com/cgi/wiki?WikiWikiWeb.)

> The philosophy: *ALL* computational models are turing equivalent (and therefore lambda-equivalent) or weaker.
> The Idea (note not proof) is that for equivalence one can write pair-interpreters like above. For the 'weaker' case, (eg DFA and TMs) one proves that TMs can interpret DFAs and disproves the possibility of the other direction.
>
> This must remain an idea (aka thesis) and not a proof because one cannot conceive of all possible computational models.

Why not?  I can "conceive" of all possible integer numbers even if I
never "pictured" them.  Is there not an inductive way to conceive of
and define computation?  I mean, I observe that the field seems to
define several ModelsOfComputation.  Intuitively I see two primary
domains

> It is hard science however for all the models that anyone has so far come up with.

And what of "interactive computation"?

> As for:
>
>> I challenge you to get down to the machine code in scheme and formally
>> describe how it's doing both.
>
> I can only say how ironic it sounds to someone who is familiar with the history of our field:
> Turing was not a computer scientist (the term did not exist then) but a mathematician.  And his major contribution was to create a form of argument so much more rigorous than what erstwhile mathematicians were used to that he was justified in calling that math as a machine.

Hmm, I'm wondering if my use of the word "formally" is confusing you.
In mathematics, this word has a subtly differing meaning, I think,
than in computer science.  Turing was "justified in calling that math
as a machine" because he was using a definition (the translation table
+ finite dictionary) such that it remained perfectly deterministic.

And here, again, one can easily gets mixed up using the same lexicon
across two different domains:  that of math and that of CS.  I advise
you to look at the dialog at ConfusedComputerScience.

> The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
> To get out of this confusion ask yourself: Is it finite or infinite?

But this only gets us out of the confusion for the mathematicians.
For the programmer and perhaps even the computer scientist (the one's
coming from physics), it is something different.

> If the TM were finite it would be a DFA

But this is not a useful formalism.  Any particular Program implements
a DFA, even as it runs on a TM.  The issue of whether than TM is
finite or not can be dismissed because a simple calculation can
usually suffice, or at least establish a range "usefulness" so as not
to "run out of memory".

> If the Intel-machine (and like) were infinite they would need to exist in a different universe.

Ha, yeah.  Let us dismiss with that.

> And so when you understand that TMs are just a kind of mathematical rewrite system (as is λ calculus as are context free grammars as is school arithmetic etc etc) you will not find the equivalence so surprising

It's not that it's surprising, it's that it's *practically* a problem.
 The translation between one PL and another which assumes a different
model of computation can get intractible.

Maybe that makes sense....

MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56349 — Re: Formal-ity and the Church-Turing thesis

On Tuesday, October 8, 2013 10:49:11 AM UTC+5:30, zipher wrote:
> I don't have an infinite stack to implement
> lambda calculus, but...

And then

> But this is not a useful formalism.  Any particular Program implements
> a DFA, even as it runs on a TM.  The issue of whether than TM is
> finite or not can be dismissed because a simple calculation can
> usually suffice, or at least establish a range "usefulness" so as not
> to "run out of memory".

Having it both ways aren't you?

[toc] | [prev] | [next] | [standalone]

#56435 — Re: Formal-ity and the Church-Turing thesis

>> I don't have an infinite stack to implement
>> lambda calculus, but...
>
> And then
>
>> But this is not a useful formalism.  Any particular Program implements
>> a DFA, even as it runs on a TM.  The issue of whether than TM is
>> finite or not can be dismissed because a simple calculation can
>> usually suffice, or at least establish a range "usefulness" so as not
>> to "run out of memory".
>
> Having it both ways aren't you?

I'm just speaking from programmer experience and the fact that most
machines are VonNeumann architecture.  Being that as it is, maxing out
the stack simply happens, and I don't dare do any non-simple
recursion, but otherwise, practically speaking, I can calculate my
memory usage that may grow on the heap so that is effectively a
non-issue.  This may not be an important distinction for computing,
the "art" (Hello ultimate lambda friends), but it is significant for
the computing, the science.

MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56339

On Mon, Oct 7, 2013 at 4:50 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Mon, 07 Oct 2013 15:47:26 -0700, Mark Janssen wrote:
>> I challenge you to get
>> down to the machine code in scheme and formally describe how it's doing
>> both.
>
> For which machine?

Right, I should stop assuming a modern implementation of vonNeumann
architecture (even though that, too, is ambiguous) since I'm talking
about theory, but yet it is relevant.  My demarcation point for
arguments between "the scheme way" and other procedural languages
(which, apart from Pascal variants, I blithely all "the C way") gets
down to differing models of computation which shouldn't get conflated,
even though everyone thinks and lumps it all as "computation".  They
simply can't get *practically* translated between one and the other,
even though they are *theoretically* translated between each other all
the time.  Humans, of course know how to translate, but that doesn't
count from the pov of computer *science*.

> Frankly, asking somebody to *formally* describe a machine code
> implementation strikes me as confused. Normally formal descriptions are
> given in terms of abstract operations, often high level operations,
> sometimes *very* high level, and rarely in terms of low-level "flip this
> bit, copy this byte" machine code operations. I'm not sure how one would
> be expected to generate a formal description of a machine code
> implementation.

It's like this: there *should* be one-to-one mappings between the
various high-level constructs to the machine code, varying only
between different chips (that is the purpose of the compiler after
all), yet for some operations, in languages like scheme, well... I
cannot say what happens...  hence my challenge.

> But even putting that aside, even if somebody wrote such a description,
> it would be reductionism gone mad. What possible light on the problem
> would be shined by a long, long list of machine code operations, even if
> written using assembly mnemonics?

Only that you've got a consistent, stable (and therefore,
formalizable) translation from your language to the machine.  That's
all.  Everything else is magic.  Do you know that the Warren
Abstraction Engine used to power the predicate logic in Prolog into
machien code for a VonNeumann machine is so complex, no one has
understood it (or perhaps even verified it)?   One hardly knows where
these things originate.  But here it gets into dark arts best not
entered into too deeply.  It will turn you mad, like that guy in the
movie "pi".

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56340

On Mon, 07 Oct 2013 17:16:35 -0700, Mark Janssen wrote:

> It's like this: there *should* be one-to-one mappings between the
> various high-level constructs to the machine code, varying only between
> different chips (that is the purpose of the compiler after all), yet for
> some operations, in languages like scheme, well... I cannot say what
> happens...  hence my challenge.
> 
>> But even putting that aside, even if somebody wrote such a description,
>> it would be reductionism gone mad. What possible light on the problem
>> would be shined by a long, long list of machine code operations, even
>> if written using assembly mnemonics?
> 
> Only that you've got a consistent, stable (and therefore, formalizable)
> translation from your language to the machine.

You are mistaken to think that there is a single, one-to-one, mapping 
between high-level code and machine code.

In practice, only if you use the exact same source code, the exact same 
compiler, the exact same version of that compiler, with the exact same 
compiler options, and the exact same version of the language and all its 
libraries, then and only then will you will get the same machine code. 
And even that is not guaranteed.

Take, for example, the single high-level operation:

sort(alist)

What machine code will be executed? Obviously that will depend on the 
sort algorithm used. There are *dozens*. Here are just a few:

http://en.wikipedia.org/wiki/Category:Sorting_algorithms

Now sorting is pretty high level, but the same principle applies to even 
simple operations like "multiply two numbers". There are often multiple 
algorithms for performing the operation, and even a single algorithm can 
often be implemented in slightly different ways. Expecting all compilers 
to generate the same machine code is simply naive.

We can use Python to discuss this, since Python includes a compiler. It 
generates byte code, which just means machine code for a virtual machine 
instead of a hardware machine, but the principle is the same. Python even 
has a disassembler, for taking those raw byte codes and turning them into 
human-readable pseudo-assembly for the Python Virtual Machine.

Here is some "machine code" corresponding to the high-level instructions:

x = 23
y = 42
z = x + y
del x, y


py> code = compile('x = 23; y = 42; z = x + y; del x, y', '', 'exec')
py> code.co_code
'd\x00\x00Z\x00\x00d\x01\x00Z\x01\x00e\x00\x00e\x01\x00\x17Z\x02\x00[\x00
\x00[\x01\x00d\x02\x00S'


Translated into "assembly":

py> from dis import dis
py> dis(code)
  1           0 LOAD_CONST               0 (23)
              3 STORE_NAME               0 (x)
              6 LOAD_CONST               1 (42)
              9 STORE_NAME               1 (y)
             12 LOAD_NAME                0 (x)
             15 LOAD_NAME                1 (y)
             18 BINARY_ADD
             19 STORE_NAME               2 (z)
             22 DELETE_NAME              0 (x)
             25 DELETE_NAME              1 (y)
             28 LOAD_CONST               2 (None)
             31 RETURN_VALUE


You should be able to see that there are all sorts of changes that the 
compiler could have made, which would have lead to different "machine 
code" but with the exact same behaviour. This particular compiler emits 
code for x=23; y=42 in the order that they were given, but that's not 
actually required in this case. The compiler might have reversed the 
order, generating something like:

    0 LOAD_CONST               1 (42)
    3 STORE_NAME               1 (y)
    6 LOAD_CONST               0 (23)
    9 STORE_NAME               0 (x)

or even:

    0 LOAD_CONST               1 (42)
    3 LOAD_CONST               0 (23)
    6 STORE_NAME               1 (y)
    9 STORE_NAME               0 (x)

without changing the behaviour of the code. Or it might have even 
optimized the entire thing to:

    0 LOAD_CONST               0 (65)
    3 STORE_NAME               0 (z)


since x and y are temporary variables and a smart compiler could perform 
the computation at compile time and throw them away. (Nitpicks about 
"what if x and y already existed?" aside.) CPython even does this sort of 
optimization, although in a more limited fashion:

py> dis(compile('x = 23 + 42', '', 'exec'))
  1           0 LOAD_CONST               3 (65)
              3 STORE_NAME               0 (x)
              6 LOAD_CONST               2 (None)
              9 RETURN_VALUE

This is called keyhole optimization. It's not beyond possibility for a 
smarter compiler to look beyond the keyhole and make optimizations based 
on the whole program.

So you can see that there is no one-to-one correspondence from high-level 
source code to low-level machine code, even for a single machine. The 
same is even more true for languages such as C, Fortran, Pascal, Lisp, 
Scheme, Haskell, Java, etc. where people have spent years or decades 
working on compiler technology. Compilers differ in the quality and 
efficiency of the machine code they emit and the choices they make about 
translating source code to machine code.


> That's all.  Everything
> else is magic.  Do you know that the Warren Abstraction Engine used to
> power the predicate logic in Prolog into machien code for a VonNeumann
> machine is so complex, no one has understood it

That's nonsense. In your next post, you even supply a link to a book 
describing how the WAM works with detailed step-by-step instructions for 
writing your own. For those reading, here it is:

www.cvc.uab.es/shared/teach/a25002/wambook.pdf


Prolog is not some dark black magic that nobody understands. There are 
multiple implementations of Prolog-like logic languages for Python:

http://pyke.sourceforge.net/
https://github.com/logpy/logpy
https://github.com/enriquepablo/nl/
http://code.google.com/p/fuxi/
https://sites.google.com/site/pydatalog/

to say nothing of similar, more advanced languages like Mercury. Just 
because *you personally* don't understand something, don't think that 
nobody else does.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.python

csiph-web