<p>See <a href="https://cs.stackexchange.com/q/22418/103110">https://cs.stackexchange.com/q/22418/103110</a></p>
<p>The short answer is that Turing Machines and RAM models are polynomially equivalent in the sense that if a computation can be  performed by a RAM model in <span class="math-container">$O(n^k)$</span> time then it can be performed by a Turing Machine in <span class="math-container">$O(n^{ck})$</span> time.</p>
<p>For clarity, I am going to split the relevant branches of theoretical computer science into to. The first is algorithm design and analysis. This is the subfield in which you study the running time of specific algorithms and the complexity classes of specific problems. The other subfield is theory of computation. This is the area concerned with decidability and complexity classes as a whole.</p>
<p>In algorithm design and analysis, algorithms are usually given in high-level pseudocode anyway (much like how programs are written in high-level languages rather than CPU instructions), with the understanding that any single instruction in the pseudocode can be translated to a constant number of instructions in the underlying model of computation, whether it be a RAM model or Turing machine.</p>
<p>I am not an expert in the theory of computation, but I assume they use Turing Machines as their model of computation for a combination of two reasons. First is inertia. The second is that it might be easier to work with mathematically. If you are trying to show that <em>no</em> computer program can accomplish something (like solve PCP or find a Hamiltonian cycle in polynomial number of steps) then you would want your model of computation to be &quot;simpler&quot;.</p>

CC BY-SA 4.0
2024-02-28T18:54:22.880Z
2024-02-28T18:54:22.880Z
NaturalLogZ
<p>In the popular book &quot;Introduction to algorithms&quot; by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead they assume a RAM model of computation where many primitive operations are allowed.</p>
<p>When I check the book &quot;Introduction to the Theory of Computation&quot; by M. Sipser., in the computational complexity section even though the definitions of P and NP are given with respect to Turing machines, in later parts, the algorithms are introduced in the style of CLRS book and in various proofs there is no mention of Turing Machines. This is not the case in decidability proofs. For example in the proof of undecidability of Post's Correspondence Problem, Turing Machine model is heavily used.</p>
<p>So, what is the role of Turing Machines in computational complexity? Do computational complexity researchers use Turing machine model in their studies and how? Can you point to some examples?</p>

CC BY-SA 4.0
2024-02-28T21:22:26.103Z
Please ask this question on cs.stackexchange.com, as this site is intended for research-level questions. (You may delete this question once you ask it there.)
Andrej Bauer
<time-complexity><turing-machines><complexity>
The role of Turing machines in computational complexity
Sanyo Mn
# The role of Turing machines in computational complexity

(Asked by: username_0 on 2024-02-28)

In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead they assume a RAM model of computation where many primitive operations are allowed.

When I check the book "Introduction to the Theory of Computation" by M. Sipser., in the computational complexity section even though the definitions of P and NP are given with respect to Turing machines, in later parts, the algorithms are introduced in the style of CLRS book and in various proofs there is no mention of Turing Machines. This is not the case in decidability proofs. For example in the proof of undecidability of Post's Correspondence Problem, Turing Machine model is heavily used.

So, what is the role of Turing Machines in computational complexity? Do computational complexity researchers use Turing machine model in their studies and how? Can you point to some examples?

**Tags:** time-complexity, turing-machines, complexity

> **Comments:**
> **username_1**: Please ask this question on cs.stackexchange.com, as this site is intended for research-level questions. (You may delete this question once you ask it there.)  

---

## 1 answers

### Answer by username_2 on 2024-02-28. Score: 2

See <https://cs.stackexchange.com/q/22418/103110>

The short answer is that Turing Machines and RAM models are polynomially equivalent in the sense that if a computation can be performed by a RAM model in $O(n^k)$ time then it can be performed by a Turing Machine in $O(n^{ck})$ time.

For clarity, I am going to split the relevant branches of theoretical computer science into to. The first is algorithm design and analysis. This is the subfield in which you study the running time of specific algorithms and the complexity classes of specific problems. The other subfield is theory of computation. This is the area concerned with decidability and complexity classes as a whole.

In algorithm design and analysis, algorithms are usually given in high-level pseudocode anyway (much like how programs are written in high-level languages rather than CPU instructions), with the understanding that any single instruction in the pseudocode can be translated to a constant number of instructions in the underlying model of computation, whether it be a RAM model or Turing machine.

I am not an expert in the theory of computation, but I assume they use Turing Machines as their model of computation for a combination of two reasons. First is inertia. The second is that it might be easier to work with mathematically. If you are trying to show that *no* computer program can accomplish something (like solve PCP or find a Hamiltonian cycle in polynomial number of steps) then you would want your model of computation to be "simpler".


---

