Is Python programming language?

Michael Torrie torriem at gmail.com
Sun Feb 10 03:55:53 CET 2013


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/



More information about the Python-list mailing list