Jump to content

Talk:Blum's speedup theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[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 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)[reply]