Is Python programming language?
Dan Stromberg
drsalists at gmail.com
Mon Feb 11 18:46:13 EST 2013
Sent from my android phone.
On Feb 9, 2013 6:41 PM, "Terry Reedy" <tjreedy at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130211/d2ca3d85/attachment.html>
More information about the Python-list
mailing list