Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Way back, years ago, A.K. Dewdney published one of his computing recreations columns in Scientific American where he discussed models of computation stronger than Turing machines/lambda calculus/recursive functions/etc., etc. His contribution was a model that solved a NP-Hard (?) problem in linear time: it passed the input to two sub-processors, which either solved the problem or passed it to two sub-sub-processors each. Since each sub-processor was half the size of its parent and required time proportional to its size due to wire delay (?).

Anyway, the bottom line was that it did an unbounded amount of work in a bounded amount of time.

I stopped paying attention to Dewdney after that.



Zeno's paradox?


Yup.


Also sounds a bit like Thompson's Lamp.

EDIT: Whoops, that's pretty much the same thing as Zeno's paradox.


> required time proportional to its size due to wire delay (?).

Isn't conventional wire delay RC quadratic?


I cannot remember the details, but the running time of the component and its subcomponents was twice the time of the component itself.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: