# Connection of “modern” runtimes and number of steps on a Turing machine

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.

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.
• 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. – Kurt Mueller Aug 11 '14 at 13:45