1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – plop
    Commented Aug 27, 2020 at 18:00
  • $\begingroup$ Yes i get that part... but how is that related to church turing thesis $\endgroup$
    – rohit sharma
    Commented Aug 27, 2020 at 18:08
  • $\begingroup$ 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. $\endgroup$
    – plop
    Commented Aug 27, 2020 at 18:12
  • $\begingroup$ Partial duplicate, also by @RobinSuri: cs.stackexchange.com/questions/129529/… $\endgroup$
    – Aaron Rotenberg
    Commented Aug 27, 2020 at 19:14
  • $\begingroup$ 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. $\endgroup$
    – Mars
    Commented Aug 27, 2020 at 21:01

1 Answer 1

Reset to default
2
$\begingroup$

The Church–Turing thesis is the following philosophical claim:

Our intuitive notion of computability coincides with the mathematical notion of computability.

Here the mathematical notion of computability states that a language is computable if some Turing machine computes it, and the intuitive notion of computability is necessarily vague.

Turing machines with infinitely many states can compute any language (exercise), and so are more powerful than the usual Turing machines, which can only compute computable languages. We know that not all languages are computable. Indeed, almost all languages are uncomputable, since there are only countably many computable languages, but uncountably many languages. Also, certain concrete languages such as the Halting Problem are known to be uncomputable.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It is worth keeping in mind that people's intuitions about "computable" have changed since the time the Church-Turing thesis was formulated. In Turing's time "computer" was a person. Nowadays children are surrounded by computers (machines) since an early age – of course "computable" means "computable by a computer"! $\endgroup$
    – Andrej Bauer
    Commented Aug 28, 2020 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.