Talk:Blum's speedup theorem

Latest comment: 5 years ago by in topic "Optimal functions"
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-priority on the project's priority scale.

Is this definition right? I don't think it is. Here follows an important algorithm for which there is not speedup: f(x) -> true; (talk)JH — Preceding undated comment added 19:55, 23 December 2014 (UTC)Reply[reply]

"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, 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 (talk) 13:28, 7 January 2018 (UTC)Reply[reply]