8 ms·
Hypercomputation: Computing more than the Turing machine (2002)
- nielsbot 9y agowould love a layperson-friendly summary of this. sounds interesting but I am not a CS PhD or mathematician.
- nnfy 9y agoI do not have a PHD in CS myself, but for anyone reading this, you should still make a habit of reading papers you do not understand. You'll likely pick up bits and pieces and learn even if you dont understand what you're reading exactly, assuming you have a minimum foundation. One of the most stressful parts of grad school in a new field (to me) was pouring over dozens of papers that I did not understand. I wish I had known then that you dont HAVE to understand every part of everything you read, especially when new to an academic field with few or no textbooks. Just be sure to watch how certain you are in your conclusions until you're comfortable with the material.
- deleted 9y ago[deleted]
- throwawayjava 9y ago(Some of what I say here isn't technically accurate; i.e., it's "close to the right idea but technically wrong". Parent asked for a layperson's explanation.) There's a famous problem in CS called the halting problem. The halting problem asks for a program that tells you whether an arbitrary program (turning machine) ever halts (a.k.a. stops executing). A function that could compute a solution to the halting problem is called a halting function. Turning machines can't compute a solution to the halting problem. Therefore, if you add an oracle for the halting problem to an otherwise normal turing machine, then the resulting model of computation is stronger than turing machines alone. And oracle is basically a magical box that answers your questions in O(1) time, nevermind how. Merely assuming an oracle for the halting function is only one of many ways to build something that does things turning machines can't do. For example, allowing infinities in various places where the classical theory of computation assumes finite sets also sometimes increases the computational power of machines. E.g., we normally assume that a turing machine's tape is uninitialized or initialize only a finite subset of the tape. But by initializing a turing machine with a carefully selected infinite tape, you can compute the halting function. Some other "now make the finite thing infinite and then code up the halting function" constructions can be found in this paper. If you fix one of these various constructions, you can start to do all the classical CS theory stuff in the context of a slightly different machine. It's interesting to see results transfer, which break down, and what surprising new/nice results show up here but not in classical cs theory. It's hard to say how useful any of this is because all of these constructions basically assume we already have at hand something that we have no idea how to construct in reality. I.e., the whole paper begins with "assume false" as far as us pragmatic engineering folk are concerned. But that's perhaps basically the same thing Euclidean geometers said during the emergence of non-Euclidean geometry, so perhaps this work will end up being as revolutionary as turing machines themselves and we just can't see exactly how yet.
- nielsbot 9y agothanks for this. very interesting!
- deleted 9y ago[deleted]
- z1mm32m4n 9y agoMaybe I'm biased, but I generally view posts about hypercomputation with skepticism. From The Myth of Hypercomputation[1]: > Under the banner of "hypercomputation" various claims are being made for the feasibility of modes of computation that go beyond what is permitted by Turing computability. In this article it will be show n that such claims fly in the face of the inability of all currently accepted physical theories to deal with infinite precision real numbers. When the claims are viewed critically, it is seen that they amount to little more than the obvious comment that if non-computable inputs are permitted, then non-computable outputs are attainable. The original idea in Turing's thesis was that the Turning Machine was something that could actually be implemented, and indeed you can find many examples of people's side projects where such machines can be made and can actually compute things. On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless. [1]: http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf
- throwawayjava 9y ago> On the other hand, hypercomputation has no physical basis The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something. And that, if such a thing did exist, its existence may well be "very fundamental to the structure of the universe and should not be ignored". I agree with both you and the author. I don't think we'll ever build device capable of general-purpose "harnessable" hypercomputation. And I don't think any of the ideas described in this paper are in any meaningful sense physically realizable. But I also allow the possibility that I am wrong, especially on the first count. And if I am wrong, even just on the first count, then some of the theory surveyed in this paper might turn out to be useful.
- throwaway613834 9y agoIsn't Heisenberg's uncertainty principle sufficiently compelling? If you can't measure anything with arbitrary accuracy then that seems more than enough reason to assume you can't go beyond finite (digital) accuracy.
- colordrops 9y agoOn a related note, anyone know anything about this company? http://memcpu.com/ http://memcpu.com/ They claim to be able to solve NP-complete problems with polynomial resources using non-Turing architectures. I'd normally call them crackpots but they have serious pedrigree and have been published in Science and Nature. I'm still very skeptical, but don't have the chops to evaluate their caims.
- ikeboy 9y agohttps://www.scottaaronson.com/blog/?p=2212 https://www.scottaaronson.com/blog/?p=2212 tl;dr It's crap
- ollin 9y agoFrom Scott Aaronson's "Memrefuting" post (https://www.scottaaronson.com/blog/?p=2212 https://www.scottaaronson.com/blog/?p=2212): > all proposals along these lines simply “smuggle the exponentiality” somewhere that isn’t being explicitly considered, exactly like all proposals for perpetual-motion machines smuggle the entropy increase somewhere that isn’t being explicitly considered. The problem isn’t a practical one; it’s one of principle.
- mcguire 9y agoOne of their publications: "Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines "We introduce a class of digital machines, we name Digital Memcomputing Machines, (DMMs) able to solve a wide range of problems including Non-deterministic Polynomial (NP) ones with polynomial resources (in time, space, and energy)." http://aip.scitation.org/doi/abs/10.1063/1.4975761?journalCode=cha http://aip.scitation.org/doi/abs/10.1063/1.4975761?journalCo... The actual paper is behind a paywall. I am not Scott Aaronson. I probably could not reasonably evaluate their claims even if I could read them. But Aaronson has somewhere posted a list of the weird things that would happen if you could solve an NP-complete problem in polynomial time, and that list provides a good reason to believe you can't. A part of another abstract of one of their other papers (http://ieeexplore.ieee.org/document/7924376/?reload=true http://ieeexplore.ieee.org/document/7924376/?reload=true) is, "Our method can be extended efficiently to any level of precision, since we prove that producing n-bit precision in the output requires extending the circuit by at most n bits. This type of numerical inversion can be implemented by DMM units in hardware; it is scalable, and thus of great benefit to any real-time computing application." Which makes me suspect there are hard limits on the size of the problems their "hardware" can handle. But it's fun to chase the graph thingys around on their home page.
- mcguire 9y agoWay 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.
- gavinpc 9y agoZeno's paradox?
- deepnotderp 9y ago> required time proportional to its size due to wire delay (?). Isn't conventional wire delay RC quadratic?
- mcguire 9y agoI cannot remember the details, but the running time of the component and its subcomponents was twice the time of the component itself.
- sddfd 9y agoHow is the hypercomputation mentioned in the report related to a Turing machine with oracle?
- gfody 9y agothe paper is all about Turing machines /oracle "The paradigm hypermachine is the O-machine....."
- idlewords 9y agoIn a nutshell: you can get a lot of work done if you have infinite time or infinite memory. The implementation of either is left as an exercise for the reader.
- deleted 9y ago[deleted]
- davesque 9y agoI've often thought that results in computer science about the performance characteristic of classes of algorithms are also, in a sense, making statements about physics. In other words, in a universe where bits of information can be sent instantaneously through worm holes, it may not be correct to say that there's no better comparison-based sort bound than O(n log n). I'm not an expert at physics or computational complexity so maybe my intuition is way off here. But I wonder if, when I hear about innovations in "hypercomputation", I should understand the researchers to be making claims which are essentially as likely to pan out as a claim of having sent bits through wormholes.
- mikeash 9y agoResults about computational complexity are always relative to some specific model of computation. For example, a standard Turing machine cannot sort in O(n log n) time. Because it has to walk along the tape one position at a time, it takes longer. When the big-O of an algorithm is given without mention of the machine model, it typically refers to a machine with random-access memory, since that's approximately what real computers have. So yes, physical possibility is definitely a big factor here, even if it's not always stated explicitly. If it were impossible to build practical random-access memory, then that wouldn't be the standard model used for computational complexity. Consider the big question of whether P=NP. The question itself is unrelated to physics, since P is defined as polynomial-time algorithms on deterministic Turing machines, and NP as polynomial-time on nondeterministic Turing machines. But the question gets a lot of attention in part because it's considered to be impossible to actually build a nondeterministic Turing machine. If that were untrue, then we could solve problems in NP in polynomial time even if P≠NP. In theory, you could build something like a nondeterministic Turing machine (without infinite memory, but close enough, much like we consider real-world computers to be close enough to normal Turing machines) if you could, say, send information back in time, or if you could split the universe into arbitrary many parallel universes, then destroy all but one. Obviously, nobody has the slightest idea of how to do this, but at least there are some vague, crazy possibilities. Hypercomputation is even worse. To accomplish it in anything like physics as we know it would require infinite time, space, and energy. In theory you can get infinite time by putting your computer into just the right orbit around a rotating black hole. Infinite space and energy are somewhat harder to come by. (You know you're in trouble when you need to do something harder than putting something into a precise orbit around a rotating black hole.) There's always the possibility of new physics. Nothing says it's impossible for there to exist some fundamental particle which acts like a Turing oracle when you poke it just right. But the chances seem pretty poor. In short, yes, barring any massive physics breakthrough, treat hypercomputation as a theoretical math construct, nothing more.
- trishankkarthik 9y agoI conjecture that hypercomputation is impossible for the following simple reason. If you could solve the Halting Problem [1], then you could build a "living" contradiction, where a machine halts if and only if it does not halt. (See proof in [2]). It won't be a mere description of a paradox, it would be an actual one. If contradictions are possible (something we implicitly believe to be impossible), then Reality is far stranger than we ever suspected or observed. [1] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem [2] https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha...
- eighthnate 9y agoThat's the accepted theory for sure. It's what every CS student learns. But never say never. "Reality/logic/math" can be a lot stranger than you think. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. And of course quantum mechanics. The duality of light ( both a wave and a particle ).
- trishankkarthik 9y agoBut never say never. "Reality/logic/math" can be a lot stranger than you think. I understand it's a Black Swan kind of problem, but I don't think we live in that reality. Please show me a contradiction. The ramifications would be stupendous, to say the least. There used to be a time when we thought that infinity ( aka countable infinity ) was the largest number. Turns how there are bigger infinities. Yes, and we know how to build Turing machines that use countable infinity. Please show me a machine that actually uses bigger infinities. Please hypercompute the digits of a real number that cannot be computed by a Turing machine. And of course quantum mechanics. The duality of light ( both a wave and a particle ). Universal quantum computers are faster than classical computers, but they are no more powerful (they are not known to be able to hypercompute).
- eighthnate 9y ago