So how would you prove that Python 2 is Turing complete ? You still have to show that Python 2 can emulate all possible Turing machines . I thought the Church Turing thesis was still called a thesis because it ' s basically a hypothesis that the Turing machine itself is Turing complete . EDIT What I mean to say is that the hypothetical Turing machine is Turingcomplete , but the actual Turing machine itself is not proven to be . This is why it ' s impossible to prove that a physical language such as Python is Turing complete , because it can not compare to a hypothetical abstract machine as a physical language itself . From another answer onlineHowever , a strict definition of Turing Completeness implies infinite storage capacity , which is of course not physically possible . Given this , no physical machine can possibly be Turing Complete , but this constraint is usually relaxed at least informally when ascribing Turing Completeness to a programming language . One trivial test of Turing Completeness for a language is whether the language can be used to implement a Turing Machine simulator .