# Church–Turing thesis and infinite Turing machines

What exactly is the definition of church turing thesis? It's really confusing.

I want to prove the following statement:

A Turing machine with infinitely many states is more powerful than a regular Turing machine, as it can accept all languages.

How does this statement not contradict the Church–Turing thesis?

I don't exactly understand the definition of the Church–Turing thesis, and how it applies in this context.

• To see that with infinite states you can accept any language, consider any language $L$, and look at the trie formed by all its words. Get one state for each node of the trie, making the leaves accepting states. Let the transition function be defined by the edges of the trie. – plop Aug 27 at 18:00
• Yes i get that part... but how is that related to church turing thesis – rohit sharma Aug 27 at 18:08
• It isn't related to Church-Turing thesis, which talks about effective, mechanical computation. The 'machine' above could be considered mechanical, but it is not considered effective, since it has infinitely many instructions. – plop Aug 27 at 18:12
• Partial duplicate, also by @RobinSuri: cs.stackexchange.com/questions/129529/… – Aaron Rotenberg Aug 27 at 19:14
• There are different versions of the Church-Turing thesis, and some discussion about which is the "real" one and what it means. There is also a standard understanding of what it means. If you're interested in the discussion about different versions of the thesis, I can add links to articles, but I don't think that's what you want. It sounds like you are working on an exercise, either from a book or as assigned for a class. In that case, isn't there a version of the Church-Turing thesis that the book or professor has stated? That's the one you should use in your reasoning. – Mars Aug 27 at 21:01