Hypercomputation: Computing more than the Turing machine (2002)

Re:Hypercomputation: Computing more than the Turing machine ... by mcguire on Sunday September 10, 2017 @06:22PM (#15214607)

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.

[ Parent | on HN ]

Re:Hypercomputation: Computing more than the Turing machine ... by gavinpc on Sunday September 10, 2017 @06:32PM (#15214649)

Zeno's paradox?

[ Parent | on HN ]

Re:Hypercomputation: Computing more than the Turing machine ... by mcguire on Sunday September 10, 2017 @06:50PM (#15214719)

Yup.

[ Parent | on HN ]

Re:Hypercomputation: Computing more than the Turing machine ... by BooglyWoo on Monday September 11, 2017 @05:45AM (#15217254)

Also sounds a bit like Thompson's Lamp.

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

[ Parent | on HN ]

Re:Hypercomputation: Computing more than the Turing machine ... by deepnotderp on Sunday September 10, 2017 @07:58PM (#15214961)

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

Isn't conventional wire delay RC quadratic?

[ Parent | on HN ]

Re:Hypercomputation: Computing more than the Turing machine ... by mcguire on Sunday September 10, 2017 @09:27PM (#15215233)

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

[ Parent | on HN ]