4 ms·

At best this is using the fact that computation of the real numbers is very powerful (and then pretending their electrical circuits at hand actually work over t

by jmount 12y ago

At best this is using the fact that computation of the real numbers is very powerful (and then pretending their electrical circuits at hand actually work over the real numbers). The point is none of our constructible devices implement ideal real number arithmetic, we only abstract them as nearly doing so. Likely their "figure 1 decoder" needs more and more accuracy (and becomes less and less possible to actually implement) as problem size goes up. Idea analog computing is very powerful (in theory). Actual analog computing is also powerful. But one of the things digital avoids is: if each analog component is only faithful to a factor of (1-epsilon) then it is easy to run into problems where an n-stage analog system is off by (1-epsilon)^n ~ e^{-n episilon}. Which is exponentially bad in n (meaning if you assume epsilon=0 you may be assuming way an exponential amount of loss). Also they are not ambitious enough. Assuming constant time arithmetic of the real numbers should get you more (like maybe even the halting problem).

xxxyy 12y ago
That was my impression too. Real numbers are in fact very surreal [1][2]. Using higher and higher frequencies is somewhat equivalent to saying: first step will take us 1 second, second step will take us 0.5 seconds, and in less that 2 seconds we will have executed anything you want. Although I'm not quite sure I understand this paper. [1] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [2] "God made the integers; all else is the work of man", Leopold Kronecker
- jmount 12y ago
  Yah- I got the impression they are running white or pink noise through a bunch of filters and looking to see if there is any spectrum remaining at the perfect balance condition that represents a successful bin-packing. The idea is they thus exploit the assumed linearity (and accuracy) of ideal circuits by claiming an independent calculation is happening at each frequency (and they trigger the calculations form the noise source). Not implementable.
cbennett 12y ago
"Also they are not ambitious enough. Assuming constant time arithmetic of the real numbers should get you more (like maybe even the halting problem)." Agreed. They do at least broach the idea though, this is from the companion paper (more theoretical): "We have thus shown that a UMM is Turing-complete, namely it can simulate any Turing machine (whether deterministic or not). Note, however, that the reverse is not necessarily true. Namely, we have not demonstrated that a UTM can simulate a UMM, or, equivalently, we have not demonstrated that a UMM is Turing-equivalent. It is worth pointing out that, if we could prove that a UMM is not Turing-equivalent, some (Turing) undecidable problems, such as the halting problem [2], may find solution within our UMM paradigm, thus contradicting the Church-Turing hypothesis [2]. Although this is an intriguing–albeit unlikely– possibility, we leave its study for future work." http://arxiv.org/pdf/1405.0931.pdf http://arxiv.org/pdf/1405.0931.pdf

by jmount 12y ago

xxxyy 12y ago

That was my impression too. Real numbers are in fact very surreal [1][2]. Using higher and higher frequencies is somewhat equivalent to saying: first step will take us 1 second, second step will take us 0.5 seconds, and in less that 2 seconds we will have executed anything you want. Although I'm not quite sure I understand this paper. [1] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [2] "God made the integers; all else is the work of man", Leopold Kronecker

jmount 12y ago
Yah- I got the impression they are running white or pink noise through a bunch of filters and looking to see if there is any spectrum remaining at the perfect balance condition that represents a successful bin-packing. The idea is they thus exploit the assumed linearity (and accuracy) of ideal circuits by claiming an independent calculation is happening at each frequency (and they trigger the calculations form the noise source). Not implementable.

cbennett 12y ago

"Also they are not ambitious enough. Assuming constant time arithmetic of the real numbers should get you more (like maybe even the halting problem)." Agreed. They do at least broach the idea though, this is from the companion paper (more theoretical): "We have thus shown that a UMM is Turing-complete, namely it can simulate any Turing machine (whether deterministic or not). Note, however, that the reverse is not necessarily true. Namely, we have not demonstrated that a UTM can simulate a UMM, or, equivalently, we have not demonstrated that a UMM is Turing-equivalent. It is worth pointing out that, if we could prove that a UMM is not Turing-equivalent, some (Turing) undecidable problems, such as the halting problem [2], may find solution within our UMM paradigm, thus contradicting the Church-Turing hypothesis [2]. Although this is an intriguing–albeit unlikely– possibility, we leave its study for future work." http://arxiv.org/pdf/1405.0931.pdf http://arxiv.org/pdf/1405.0931.pdf