Re: Formal-ity and the Church-Turing thesis

[Chris Angelico]

On Wed, Oct 9, 2013 at 12:11 AM, Steven D'Aprano
 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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Mark Janssen]

>> 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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Robert Day]

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. 



-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[rusi]

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]

> 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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Steven D'Aprano]

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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Ravi Sahni]

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 but I not
clear the connection with computers, programming, computer science and
so on.  Also this Mr. Mark Lawrence question.

-- 
Ravi
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Ravi Sahni]

On Tue, Oct 8, 2013 at 1:20 PM, Steven D'Aprano  wrote:
> On Tue, 08 Oct 2013 10:46:50 +0530, Ravi Sahni wrote:
>
>> On Tue, Oct 8, 2013 at 8:47 AM, rusi  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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Steven D'Aprano]

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

> On Tue, Oct 8, 2013 at 8:47 AM, rusi  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
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Mark Lawrence]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[rusi]

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?

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[rusi]

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]
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Formal-ity and the Church-Turing thesis

[Mark Janssen]

> 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
-- 
https://

Re: Formal-ity and the Church-Turing thesis

[Ravi Sahni]

On Tue, Oct 8, 2013 at 8:47 AM, rusi  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
-- 
https://mail.python.org/mailman/listinfo/python-list

Formal-ity and the Church-Turing thesis

[rusi]

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
-- 
https://mail.python.org/mailman/listinfo/python-list