Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed1.swip.net!uio.no!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <5253b935$0$29976$c3e8da3$5496439d@news.astraweb.com>
References: <mailman.571.1380663065.18130.python-list@python.org> <87had0axxy.fsf@dpt-info.u-strasbg.fr> <CAMjeLr9KPf=Z4pJoQtU8LXiT686dABg-fpNoWYb9reEPRSsYjA@mail.gmail.com> <524C80B6.3010204@unistra.fr> <mailman.651.1380747919.18130.python-list@python.org> <87li292wnt.fsf@dpt-info.u-strasbg.fr> <mailman.732.1380925974.18130.python-list@python.org> <878uy52ea0.fsf@dpt-info.u-strasbg.fr> <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> <48454d8d-19be-49e4-a63e-9718067e6417@googlegroups.com> <mailman.826.1381209439.18130.python-list@python.org> <5253b935$0$29976$c3e8da3$5496439d@news.astraweb.com>
From: Ravi Sahni <ganeshsahni07@gmail.com>
Date: Tue, 8 Oct 2013 18:16:01 +0530
Subject: Re: Formal-ity and the Church-Turing thesis
To: "Steven D'Aprano" <steve@pearwood.info>
Content-Type: text/plain; charset=ISO-8859-1
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.852.1381236385.18130.python-list@python.org>
Lines: 48
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:56391

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