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.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
