Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(nlog(n)) and therefore Turing machine which implements this algorithm will do O(nlog(n)) steps. Why is this conclusion correct? And vise versa: if there's no deterministic Turing machine which takes less than exponential number of steps to solve some problem, we aren't able to find efficient algorithm solving this problem.


Your premise that turing machines can implement algorithms with the same efficiency as a modern computer is not correct.

Turing machines can simulate 'enhanced' turing machines that have the properties of modern computers (e.g. random access into memory, multiple memory spaces, etc) with only polynomial slowdown.

However, not all problems can be solved exactly as fast on a turing machine. For example, consider the problem PALINDROME to determine if the input is a palindrome. On a modern computer there is an obvious $O(n)$ algorithm, where you just read the front and back character, and if they match recurse on the inner substring. This problem is known to require $\Omega(n^2)$ time for a classical turing machine to solve. This means turing machines are decidedly "weaker" by some amount compared to an ideal modern computer.

| cite | improve this answer | |
  • $\begingroup$ OK. In some books authors say that NP problems are problems that can't be solved in polynomial time. They consider algorithms at all, not only turing machine. But strict definition of NP problems is only about turing machines - there's no deterministic turing machine that solves problem in polynomial time. So, why does nonexistence of polynomial turing machine causes nonexistence of polynomial algorithm? $\endgroup$ – Alexander_KH Aug 11 '14 at 13:41
  • 1
    $\begingroup$ As I said, a turing machine can simulate a modern machine with polynomial slowdown -- thus, if a modern machine can solve a problem in, say, $O(n^3)$, then a turing machine can solve it within $O(n^5)$ or so. In other words, multiplying two polynomials always gives you a polynomial, so in terms of polytime vs not-polytime we may as well treat TMs and modern machines as the same thing even though they are not exactly the same. $\endgroup$ – Kurt Mueller Aug 11 '14 at 13:45
  • $\begingroup$ Thank you very much! Where can I read more about this conclusion "turing machine can simulate a modern machine with polynomial slowdown"? Where can I read about correlation of abstract mathematical models of a computer and real modern computers? $\endgroup$ – Alexander_KH Aug 11 '14 at 13:49
  • $\begingroup$ I should clarify that by 'simulate a modern machine', I mean simulate another turing machine that has all the properties of a modern machine, such as random access memory, partitioned memory spaces, etc. You can learn more about the proofs of these simulations in any book on complexity theory, such as amazon.com/Computational-Complexity-Approach-Sanjeev-Arora/dp/… (this book is pretty tough and mathematical, but rigorous) $\endgroup$ – Kurt Mueller Aug 11 '14 at 13:55
  • 2
    $\begingroup$ "In some books authors say that NP problems are problems that can't be solved in polynomial time." -- that is wrong. Read again. If they actually say so, don't read these books. $\endgroup$ – Raphael Aug 11 '14 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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