Formal-ity and the Church-Turing thesis

Newsgroups	comp.lang.python
Date	2013-10-07 20:17 -0700
References	(8 earlier) <5252F610.9040403@rece.vub.ac.be> <mailman.821.1381188514.18130.python-list@python.org> <525348d7$0$29984$c3e8da3$5496439d@news.astraweb.com> <CAMjeLr_ZdDURyE4Z8rj=TKzNntZZqXY3stKJG3-Ck+qC_4GeGA@mail.gmail.com> <mailman.822.1381191857.18130.python-list@python.org>
Message-ID	<48454d8d-19be-49e4-a63e-9718067e6417@googlegroups.com> (permalink)
Subject	Formal-ity and the Church-Turing thesis
From	rusi <rustompmody@gmail.com>

Show all headers | View raw

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

Thread

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

csiph-web