Why an evaluation of Turing machine efficiency is equal to the algorithm which i

Question

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.

Explanation / Answer

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 ?(n2) time for a classical turing machine to solve. This means turing machines are decidedly "weaker" by some amount compared to an ideal modern computer.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.