Talk:Blum's speedup theorem
| This is the talk page for discussing improvements to the Blum's speedup theorem article. This is not a forum for general discussion of the article's subject. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Is this definition right? I don't think it is. Here follows an important algorithm for which there is not speedup: f(x) -> true; 12.198.223.226 (talk)JH — Preceding undated comment added 19:55, 23 December 2014 (UTC)
"Optimal functions"[edit]
The most important sentence in the introduction throws me off completely:
for any complexity measure there are computable functions that are not optimal with respect to that measure.
I don't see how any function could be considered optimal. Especially, since the first part of the introduction explained when programs are considered optimal.
I would have expected something like » for any complexity measure there are computable functions which have no program representation that is optimal with respect to the given complexity measure. « (That's what I understood from reading http://mathworld.wolfram.com/BlumsSpeed-UpTheorem.html, but I don't know much about Blum's speedup theorem, therefore I don't want to edit this article). — Preceding unsigned comment added by 88.68.123.116 (talk) 13:28, 7 January 2018 (UTC)