<p>Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it.</p>
<p>What Cobham was actually talking about in his paper &quot;The Intrinsic Computational Difficulty of Functions&quot; [<em>Proc. 1964 Congress for Logic, Methodology, and the Philosophy of Science,</em> pp. 24-30, 1964,
North-Holland] was how many computational steps it takes to compute a function, not to recognize a language, so he was talking about what we would today call FP and not P. What Cobham actually said in his paper is:</p>
<blockquote>
<p>if we formalize the above definition [of FP] relative to various classes of computing machines we seem to always end up with the same well-defined class of functions.</p>
</blockquote>
<p>He never mentions <em>physical device</em>, and I suspect that he was not thinking about physical devices, but about mathematical models of computation.</p>
<p>Thus, the thesis that Cobham actually proposed is that the class of functions FP is independent of the machine it is defined on (with the unwritten addendum that this machine is sufficiently powerful). This is quite closely related to Oded Goldreich's definition, and much farther from the Wikipedia definition.</p>

CC BY-SA 4.0
2024-07-18T04:43:04.410Z
FWIW, Cobham actually does mention physical devices, but not in rel'n to "Cobham's thesis": "Now the class $E^2$ is so rich [...] that it is almost inconceivable to me that there could exist *real* computers not having mathematical models whose arithmetization could be carried out in such a way that these associated functions would fall within it." and "It may turn out that some measure related to the physical notion of work will lead to the most satisfactory analysis; or we may ultimately find that no single measure adequately reflects our intuitive concept of difficulty."
Joshua Grochow
CC BY-SA 4.0
2024-07-18T05:00:38.330Z
On re-reading it, I guess the first quote actually is about Cobham's thesis.
Joshua Grochow
CC BY-SA 4.0
2021-06-12T18:04:36.210Z
2021-06-12T18:37:13.277Z
2021-06-12T18:37:13.277Z
Peter Shor 
<p>In wikipedia, <a href="https://en.wikipedia.org/wiki/Cobham%27s_thesis" rel="nofollow noreferrer">Cobham's thesis</a> (or Cobham-Edmonds thesis) states:</p>
<blockquote>
<p>computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time</p>
</blockquote>
<p>So according to my understanding, Cobham says that all problems that are in class <span class="math-container">$P$</span>, then there exists a physical device that can solve this problem in short time (or a physical device that people can see the answer in their life-time).</p>
<p><a href="http://index-of.co.uk/Theory-of-Computation/Computational%20Complexity%20A%20Conceptual%20Perspective%20-%20Oded%20Goldreich.pdf" rel="nofollow noreferrer">Oded Goldreich's textbook</a> of Computational Complexity states:</p>
<blockquote>
<p>Cobham-Edmonds Thesis asserts that the time complexities in any two reasonable and general models of computation are polynomially related.That is, a problem has time complexity t in some reasonable and general model of computation if and only if it has time complexity poly(t) in the model of single-tape Turing machine.</p>
</blockquote>
<p>It seems that Goldreich's definition of Cobham's thesis is that all model of computation that solve problems in complexity class P are polynomially related. I don't see any different from Goldreich's definition and the Extended Church-Turing Thesis which the later is not credited to any paper or person as far as I know.</p>
<p>Now can you clarify which definition is true for Cobhams' thesis, Is it by wikipedia definition or by Goldreich's definition? If you don't see any contradiction, then can you explain how these two definitions are related.</p>

<cc.complexity-theory><ho.history-overview><definitions>
Are there two definitions of Cobham's thesis?
user777
# Are there two definitions of Cobham's thesis?

(Asked by: username_0 on 2021-06-06)

In wikipedia, [Cobham's thesis](https://en.wikipedia.org/wiki/Cobham%27s_thesis) (or Cobham-Edmonds thesis) states:

> computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time

So according to my understanding, Cobham says that all problems that are in class $P$, then there exists a physical device that can solve this problem in short time (or a physical device that people can see the answer in their life-time).

[Oded Goldreich's textbook](http://index-of.co.uk/Theory-of-Computation/Computational%20Complexity%20A%20Conceptual%20Perspective%20-%20Oded%20Goldreich.pdf) of Computational Complexity states:

> Cobham-Edmonds Thesis asserts that the time complexities in any two reasonable and general models of computation are polynomially related.That is, a problem has time complexity t in some reasonable and general model of computation if and only if it has time complexity poly(t) in the model of single-tape Turing machine.

It seems that Goldreich's definition of Cobham's thesis is that all model of computation that solve problems in complexity class P are polynomially related. I don't see any different from Goldreich's definition and the Extended Church-Turing Thesis which the later is not credited to any paper or person as far as I know.

Now can you clarify which definition is true for Cobhams' thesis, Is it by wikipedia definition or by Goldreich's definition? If you don't see any contradiction, then can you explain how these two definitions are related.

**Tags:** cc.complexity-theory, ho.history-overview, definitions


---

## 1 answers

### Answer by username_1 on 2021-06-12. Score: 10 | Accepted answer

Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it.

What Cobham was actually talking about in his paper "The Intrinsic Computational Difficulty of Functions" [*Proc. 1964 Congress for Logic, Methodology, and the Philosophy of Science,* pp. 24-30, 1964,
North-Holland] was how many computational steps it takes to compute a function, not to recognize a language, so he was talking about what we would today call FP and not P. What Cobham actually said in his paper is:

> if we formalize the above definition [of FP] relative to various classes of computing machines we seem to always end up with the same well-defined class of functions.

He never mentions *physical device*, and I suspect that he was not thinking about physical devices, but about mathematical models of computation.

Thus, the thesis that Cobham actually proposed is that the class of functions FP is independent of the machine it is defined on (with the unwritten addendum that this machine is sufficiently powerful). This is quite closely related to Oded Goldreich's definition, and much farther from the Wikipedia definition.

> **Comments:**
> **username_2**: FWIW, Cobham actually does mention physical devices, but not in rel'n to "Cobham's thesis": "Now the class $E^2$ is so rich [...] that it is almost inconceivable to me that there could exist *real* computers not having mathematical models whose arithmetization could be carried out in such a way that these associated functions would fall within it." and "It may turn out that some measure related to the physical notion of work will lead to the most satisfactory analysis; or we may ultimately find that no single measure adequately reflects our intuitive concept of difficulty."  
> **username_2**: On re-reading it, I guess the first quote actually is about Cobham's thesis.  

---

