According to Turing thesis, Can we say all programming languages that support turing machine like C have same power for solving problems and performing algorithms? In other words is there any algorithm or problem that one of them can solve it and the other can't?


1 Answer 1


The notion you are looking for is probably Turing completeness. All languages that are Turing complete are essentially equivalent in what problems they can solve (at least in principle). Most general-purpose programming languages are Turing complete.

  • 5
    $\begingroup$ I'll add a caveat that there are other notions of completeness and expressivity that are not well modelled by Turing machines. For instance, the pi-calculus is Turing complete but can express concurrency. It is known that more expressive process calculi exist than the pi-calculus however. Similar issues arise in higher type computability. $\endgroup$
    – Jake
    Commented Jul 6, 2018 at 15:22

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.