Hacker News new | ask | show | jobs
by bunderbunder 5181 days ago
It doesn't get into what exactly a "Super-Turing" machine is capable of that a Turing machine is not.

I'm not great at interpreting technobabble, but I think it means everything in NP-Hard is now solvable in linear time.

Or something.
2 comments
aqme28 5181 days ago
That isn't right. Super-Turing just means that it has capabilities a classical Turing machine does not[1], which is why this article is so terrible. What are these extra capabilities it does and how does it do them?

[1]: http://en.wikipedia.org/wiki/Hypercomputation

link
bunderbunder 5181 days ago
Yeah, that's what I was trying to poke fun at. Me bad at jokes, apparently.
link
bitwize 5181 days ago
No, stronger. It means the Halting Problem can be solved. Time to break out the bubbly! Or not.

The more I look into it, the more this Super-Turing business sounds like the computability-theory version of FTL neutrinos. According to Martin Davis, Siegelmann's paper involves neural nets with arbitrary real-numbered (as opposed to integer or rational) weights being able to recognize languages on the alphabet {a,b} that a Turing machine can't.

So you have this thing that can get uncomputable results because it's given uncomputable inputs! In other words, no more interesting, or practical, than attempting to do computation with the n-body problem, and almost certainly nothing we can actually build.

link