Sent from my android phone. On Feb 9, 2013 6:41 PM, "Terry Reedy" <tjre...@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
-- http://mail.python.org/mailman/listinfo/python-list
