Re: Is Python programming language?

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!ecngs!feeder2.ecngs.de!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<drsalists@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.000
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'languages,': 0.04; 'subject:Python': 0.05; 'bash': 0.07; 'if,': 0.09; 'scripting': 0.09; 'subject:language': 0.09; 'subset': 0.09; 'terry': 0.09; 'cc:addr:python-list': 0.10; 'language': 0.14; '"terry': 0.16; '>>': 0.16; 'arrays,': 0.16; 'awk': 0.16; 'conditional': 0.16; 'definition.': 0.16; 'email addr:udel.edu>': 0.16; 'email name:<tjreedy': 0.16; 'equivalence': 0.16; 'expressions.': 0.16; 'infinitely': 0.16; 'looping': 0.16; 'loops': 0.16; 'non- trivial': 0.16; 'operation,': 0.16; 'presume': 0.16; 'received:209.85.216.53': 0.16; 'reedy': 0.16; 'reedy"': 0.16; 'sed': 0.16; 'sequential': 0.16; 'simplest': 0.16; 'subject:programming': 0.16; 'syntax,': 0.16; 'wrote:': 0.17; 'variables': 0.17; 'jan': 0.18; 'tim': 0.18; '>>>': 0.18; 'feb': 0.19; 'do.': 0.21; '>>>': 0.22; 'explicit': 0.22; 'implicit': 0.22; '\xa0if': 0.22; 'cc:20': 0.23; 'programming': 0.23; '>': 0.23; "haven't": 0.23; 'cc:no real name:20': 0.24; 'machine': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply- To:1': 0.25; 'common': 0.26; 'url:wiki': 0.26; 'language.': 0.27; 'separate': 0.27; 'message-id:@mail.gmail.com': 0.27; 'arrays': 0.29; 'assert': 0.29; 'complete,': 0.29; 'optional': 0.29; 'url:wikipedia': 0.29; 'url:mailman': 0.29; 'skip:& 10': 0.29; 'probably': 0.29; "i'm": 0.29; 'that.': 0.30; 'implement': 0.32; 'url:python': 0.32; 'url:listinfo': 0.32; 'languages': 0.33; 'received:google.com': 0.34; 'pm,': 0.35; 'subject:?': 0.35; 'received:209.85': 0.35; 'something': 0.35; 'michael': 0.36; 'but': 0.36; 'url:org': 0.36; 'flow': 0.36; 'test': 0.36; 'received:209': 0.37; 'received:209.85.216': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'sure': 0.38; 'url:en': 0.38; 'where': 0.40; 'header:Received:5': 0.40; 'url:mail': 0.40; 'most': 0.61; 'real': 0.61; 'life,': 0.62; 'show': 0.63; 'covers': 0.65; 'harder': 0.65; 'computers': 0.69; '2013': 0.84; 'category.': 0.84; 'recursion,': 0.84; 'execution,': 0.91; 'url:m': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=75P2yc8MbxdPNkiIWGTfzetWc4xsijyFlY89k5/NPCM=; b=NGdWJ6xmaermsm9B0GWJYihJd4KmItx4qD1xciVQlHXOg3/Idu0OXOGHvop9goAdQP /XO/a0//JkjpgsowyvMhJ1fvalvjm9xvHpwNR/z2For0w15U8Xs1rfyEo62mNMGl9VRu 9ELnm5yCn3sSQ0qe42Ed7Kge55C4tmUi0x+wXcAP8yb1BPCLVscOQUTTzJw1/LsCxKGa pWRDK96+ekJymM44uQ+8szm0UuBkyp2Q6JxJEE7ZCK4o2rmMCoSc5+erftRKYi/Iiuzy 7RRYvamxanexqp1dLJVrGeeWU0MKEDLws45YoEiUoxdGGr8wCKSIWEW9RxYRsIUofrw4 3/IA==
MIME-Version	1.0
X-Received	by 10.229.201.86 with SMTP id ez22mr1494339qcb.9.1360626373597; Mon, 11 Feb 2013 15:46:13 -0800 (PST)
In-Reply-To	<kf71b2$5ho$1@ger.gmane.org>
References	<1360328631.24677.YahooMailClassic@web125203.mail.ne1.yahoo.com> <mailman.1500.1360329332.2939.python-list@python.org> <kf3edb$1ar$1@reader1.panix.com> <6lmdh8t7osnvjj5v5vnrav8q5anum6ln3q@4ax.com> <5116E168.6030707@gmail.com> <kf71b2$5ho$1@ger.gmane.org>
Date	Mon, 11 Feb 2013 15:46:13 -0800
Subject	Re: Is Python programming language?
From	Dan Stromberg <drsalists@gmail.com>
To	Terry Reedy <tjreedy@udel.edu>
Content-Type	multipart/alternative; boundary=005045029f34ab9ad604d57b834a
Cc	python-list@python.org
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.1671.1360626382.2939.python-list@python.org> (permalink)
Lines	111
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1360626382 news.xs4all.nl 6894 [2001:888:2000:d::a6]:53806
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:38709

Show key headers only | View raw

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

Sent from my android phone.
On Feb 9, 2013 6:41 PM, "Terry Reedy" <tjreedy@udel.edu> wrote:
>
> On 2/9/2013 6:53 PM, Michael Torrie wrote:
>>
>> On 02/09/2013 04:26 PM, Tim Roberts wrote:
>>>
>>> Most people would call bash a "scripting language", but it is also
clearly
>>> a programming language.  It has syntax, variables and expressions.  I
>>> suspect it is Turing-complete, although I haven't seen a proof of that.
>>>
>>> I would assert that scripting languages are a proper subset of
programming
>>> languages, not a separate category.
>>
>>
>> I'm pretty sure Bash is turing complete.  I know it's been shown that
>> sed is turing complete, and awk probably is too!  If I recall, the way
>> to show a language is turing complete is to implement a turing machine
>
>
> If the language has arrays, conditional execution, and explicit (while)
loops or recursion, you can be pretty sure it is Turing complete. I presume
this covers awk and bash. Something like the game of Life, where the
looping in implicit in the operation, is much harder to show Turing
complete. I suspect sed is non-trivial also.

http://en.m.wikipedia.org/wiki/Turing_completeness

For proving something Turing-complete, you only need to prove equivalence
to some other Turing-complete language.

The simplest test involves three things:
1. Sequential flow
2. An if, while or recursive function/method call
3. An arbitrary number of variables - arrays are optional

Strictly speaking, no language on a real computer is fully Turing-complete,
because real computers don't have an infinitely large memory, while TM's do.

But it's common to handwaive past that part of the definition.

> Terry Jan Reedy
>
> --
> http://mail.python.org/mailman/listinfo/python-list

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Re: Is Python programming language? Stephane Wirtel <stephane@wirtel.be> - 2013-02-08 14:15 +0100
  Re: Is Python programming language? Grant Edwards <invalid@invalid.invalid> - 2013-02-08 17:59 +0000
    Re: Is Python programming language? Tim Roberts <timr@probo.com> - 2013-02-09 15:26 -0800
      Re: Is Python programming language? Michael Torrie <torriem@gmail.com> - 2013-02-09 16:53 -0700
      Re: Is Python programming language? Terry Reedy <tjreedy@udel.edu> - 2013-02-09 21:40 -0500
      Re: Is Python programming language? Terry Reedy <tjreedy@udel.edu> - 2013-02-09 21:47 -0500
      Re: Is Python programming language? Michael Torrie <torriem@gmail.com> - 2013-02-09 19:55 -0700
      Re: Is Python programming language? Dan Stromberg <drsalists@gmail.com> - 2013-02-11 15:46 -0800

csiph-web