Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #38709

Re: Is Python programming language?

Show all headers | 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