2 ms·
'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.' I totally agree, which is part of why the article didn
by dllthomas 12y ago
'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'
I totally agree, which is part of why the article didn't clear it up.
"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."
A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?
Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.