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: 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:2**0': 0.23; 'programming': 0.23; '>': 0.23; "haven't": 0.23; 'cc:no real name:2**0': 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: References: <1360328631.24677.YahooMailClassic@web125203.mail.ne1.yahoo.com> <6lmdh8t7osnvjj5v5vnrav8q5anum6ln3q@4ax.com> <5116E168.6030707@gmail.com> Date: Mon, 11 Feb 2013 15:46:13 -0800 Subject: Re: Is Python programming language? From: Dan Stromberg To: Terry Reedy 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 --005045029f34ab9ad604d57b834a Content-Type: text/plain; charset=ISO-8859-1 Sent from my android phone. On Feb 9, 2013 6:41 PM, "Terry Reedy" 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 --005045029f34ab9ad604d57b834a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

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. =A0It has syntax, variables and expres= sions. =A0I
>>> suspect it is Turing-complete, although I haven't seen a p= roof 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. =A0I know it's be= en shown that
>> sed is turing complete, and awk probably is too! =A0If I recall, t= he way
>> to show a language is turing complete is to implement a turing mac= hine
>
>
> If the language has arrays, conditional execution, and explicit (while= ) loops or recursion, you can be pretty sure it is Turing complete. I presu= me this covers awk and bash. Something like the game of Life, where the loo= ping in implicit in the operation, is much harder to show Turing complete. = I suspect sed is non-trivial also.

http://e= n.m.wikipedia.org/wiki/Turing_completeness

For proving something Turing-complete, you only need to prove equivalenc= e 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-comple= te, 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

--005045029f34ab9ad604d57b834a--