On 02/09/2013 07:40 PM, Terry Reedy wrote: > 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.
All you have to do to show a language is turing complete is to implement a turing machine in it. Here's one in sed that I found: http://www.catonmat.net/blog/proof-that-sed-is-turing-complete/ -- http://mail.python.org/mailman/listinfo/python-list
