In accordance with the Church-Turing thesis, the Turing machine stands to be capable of doing anything that should be called computation. It follows that if the brain is capable of simulating of a Turing machine (this is called a universal Turing machine, by the way), then it too can do any computation. So then the class of things that both can do are the same, and so it is reasonable to call them the same thing, in some sense.
If we conjecture that any physical process can be simulated by a computation then it follows that a Turing machine can simulate it.
While we don’t have any proof of this conjecture (as far as I know) neither have we discovered any exceptions.
This also doesn’t rule out the possibility of non-physical or non-mechanical elements in the brain (dualism/vitalism) but frankly I don’t even entertain that notion.
You’re just begging the question: if you assume your conclusion, any claim holds.
Which is exactly my point — everyone is completely okay with those assumptions, without justifying that. I find it suspect.
How about showing physical processes are necessarily Turing computable, that is, justifying your underlying assumptions, before the straw man implication that I’m talking about dualism?
The mathematical equivalent of your argument is that because all finite-length approximations of a number are rational, the number itself must be rational — but this is untrue, in the general case. And in fact, for almost no numbers does a finite set of those rational approximations yield a general rule to predict the full structure of the number.
It’s therefore unclear that our limited scientific models being computable mean the underlying object they’re approximating is computable. But if we don’t know reality is computable, then we don’t know it can be simulated on a Turing machine.
Just assuming an answer doesn’t help us resolve the claim.
> What I was trying to communicate was that the Turing machine believed to represent the limits of what is physically possible
Another religious tenet with no observable basis.
Where did so many hackers get this misconception that computable and physically possible are proven to be the same? Many claim the Church-Turing thesis shows this. Have they never read it carefully?
It might be easier to view entropy of a state as sort of the probability that that state would occur after randomly arranging all of its parts (usually particles). In fact this is pretty close to the actual definition.
Here's an example: Suppose you had a container and you put some marbles at the bottom such that there are reasonably large gaps between the marbles. Now if you close and then shake the container hard (this is the 'random arrangement' process), then it is with high probability when you open the container that the marbles will be arranged reasonably spread out across the bottom. In this sense, when the marbles are spread kind of far apart in the container, it is in a state of high entropy (probability).
There is also the chance that when you open the container the marbles form a perfect straight line at the bottom. However, this is much more unlikely, so that you would consider this a low entropy state.
Now, consider the universe in place of the container, and subatomic particles as the marbles. Randomly configuring all of these particles, it would be really hard to end up with a stars, galaxies, humans. These are like straight lines in the marble example. It is much more likely you just get a soup of somewhat uniformally distributed particles (as in the marbles just being sort of randomly spread out from each other). This is what you describe as "a perfectly uniformly distributed of zero temperature mass (or maybe absoute zero, not sure) of grey energy is the perfect order". It wouldn't really be 'perfect' in some senses of the word though, which may be your cause of confusion. It would be more like if you took a snapshot of the static on an old TV.
The common depiction is of a bunch of particles of two kinds, sorted into separate compartments by kind, which will mix if a divider is removed. In this picture, every part of one kind receiving a partner of the other kind, that can be called a state of order. If we take heat instead, every particle swinging differently is more chaotic--at least in my understanding--than all synching up so that their speeds relative to each other are zero ... 0 degree is just not higher order, because "high" is associated with high frequency (or energy or order).
In your shaky example, you transmit energy to the system by shaking, so if shaking a certain way, you'd well expect standing waves, if shaking a bit more you'd pulverize the marble and ultimately a hot plasma with density gradients. I wonder how hard you'd have to shake and swirl to eventually get a black hole, for which the notion of entropy doesn't even really make sense, if you aren't inside.
Yes, this is pretty much the basis to quantum key distribution protocols, and probably one of the first studied uses of quantum information in general. Consider BB84 (http://www.cse.wustl.edu/~jain/cse571-07/ftp/quantum/, https://en.wikipedia.org/wiki/BB84, apparently the first quantum cryptography protocol), which would allow the transmission of a one time pad with an any eavesdropper being unnoticed with provably exponentially decreasing probability in terms of key length. The one time pad can then be used to securely transmit data.
Thus it is possible to transmit arbitrary (classical) data with exponentially decreasing probability that we do not detect an eavesdropper. Alice and Bob can communicate with each other knowing that there is provably pretty much no chance that anyone else knows what they said to each other.
I want to add that quantum FFT performs the transform on the amplitudes in the n-qubit state. Thus its output is an n-qubit state with the amplitudes matching the fourier tranforms. We cannot actually directly extract the amplitudes of the resulting state (which is the actual transformed values) from the system, since a measurement collapses the state of the system.
While some people have figured out how to used the result of the quantum FFT to do useful things (e.g. Shor's algorithm), it does not actually provide us with the transformed values in the traditional sense as the classical algorithm does.
I think you have the right idea but the wrong terminology. A n qubit system requires amplitudes (probabilities) for all 2^n possible basis states. For example, the representation we can give to a 2-qubit system is just a probability (technically an amplitude) associated with each of states 00, 01, 10, and 11. It's not really fancy or hard to see how this increases exponentially.
Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes.
Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible).
That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you.
My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.
Parent is correct — entanglement is exactly due to the fact that there exist more vectors in Hilbert space than tensor products (~ tuples) of unit vectors.
While I agree with you, you should note that even approximation within any degree of error is NP-complete for a large class of NP-complete problems (e.g. TSP, and the problem MAX-EkSAT used in the paper).
That is, a polynomial algorithm for the approximate problem would be just as significant as one for the exact version.
While what you're saying is technically true, you have to be careful with the exact definitions. For many NPC problems, approximations are indeed hard as well, but that a worst case statement. The existence of an algorithm that finds sufficiently good solutions for all instances implies P=NP, but that doesn't mean that there aren't algorithms that find very good approximations for all instances that occur in practice, or for almost all instances that you sample uniformly at random. As long as there is an arbitrarily obscure class of instances left where the algorithm fails to provide a good approximation P!=NP remains a possibility. Experimental evaluations of approximation ratios are not sufficient to claim P=NP.
But that's being NP-Complete, and so can be converted into exact solutions for other NP-Complete problems. Otherwise, by definition, it's not NP-Complete.
So it's not clear what they're actually doing, but if they can solve NPC problems they would say that. So I expect that they are getting approximate solutions that are not then NPC.
That's correct. Given a polynomial time approximate algorithm for Ek-SAT (note, by approximate algorithm I mean along the lines of the formal definition of approximate algorithm, that the solution given by the algorithm falls in some fraction of the real answer for all instances, see https://en.wikipedia.org/wiki/Hardness_of_approximation), you would show P=NP.
Moreover, from what I can see, and as you mention as your original concern, the extent of proof for the 'exponential-speedup' claim exists in the form of some benchmarks, hardly a proof that their method actually works on all instances, which would be needed to show that it is a approximation algorithm as commonly defined.
The purpose of my post was to highlight that for some problems (for example, TSP), even a really crappy approximation algorithm would imply P=NP. As highlighted by the authors of this paper, MAX-EkSAT is in a similar situation, though judging by https://www.cse.buffalo.edu/~hungngo/classes/2006/594/notes/..., unlike TSP, approximation to SOME ratio is possible, though there exists aratio >1 which cannot be beat unless P=NP.
I was simply trying to address the statement: "So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests.
", since an actual approximation algorithm for some ratio really WOULD be significant (showing P=NP).
I don't think your first statement is true, there exist polynomial time approximation schemes and approximation algorithms for np complete problems, notably a PTAS for knapsack. In other words, an approximation of one np complete problems doesn't imply an approximation of all of them.
I can't fully articulate the reasons for this though.
This means that the runtime is polynomial in the numeric value of the knapsack. Since the encoding of that numeric value only takes logarithmic space (unless you are using unary encoding), the runtime is in fact again exponential in the size of the input.
For this reason, the knapsack problem is called weakly NP-complete:
One can show that, unless P=NP, a so-called strongly NP-hard optimization problem with polynomially bounded objective function cannot have a fully polynomial-time approximation scheme:
No. Many approximation problems are known to be NP-hard without relying on the PCP theorem. The PCP theorem is "only" one of the strongest (if not the strongest) and widely applicable result about approximation hardness. (I may be underselling it with this short summary because of the unique games conjecture; in any case, the main point is that there were approximation problems known to be hard long before the PCP theorem was found.)
Travelling salesman problem? Can't you get to within a factor of 2 of optimal by constructing a minimum spanning tree:
Once you have a MST (which can be built efficiently), the total weight of the tree is a lower bound for the total distance of a TSP solution. However, you can construct a TSP path that traverses each edge of the MST twice; which means that we know that this path (which is easy to find) is at most twice the total cost of the optimal path.
Your solution works only in metric spaces. In non-metric spaces (distances are arbitrary and you are forced to return a cycle, not a tour that repeats vertices) no constant-factor approximation is possible.
Basically, a generator neural network has two things which affect its output: an input and some parameters (weights).
Let's use the setting of the task for denoising images. They use a network who's output is to is the denoised image, and compare it to the noisy image to get a score for how good the denoised output was.
Now the strange thing is, for the input of the network, they just use random garbage. The only thing they move around to try get a good denoising score are the parameters of the network (not the input).
They find that by only adjusting the parameters, even with fixed random crap inputs, if they find the parameter setting which minimizes the noise, they actually still get great looking results.
This suggests that the networks they tested this method with (other researchers work who do well on this task) are based much more in the inherent structure of the network, rather than the model refinement from training on thousands of images, since even given random crap, they generates good results, as long as the parameters are tuned well to the noisy image.
x is actually the generated image they are testing against x0. A lower E(x; x0) means an image which fits well towards the objective based on the original image (depends on the task). The paper gives some examples. For example, for the task of image denoising, E(x; x0) is just the squared distance of the generated (denoised candidate) image x to the pixels to the original image x0. Obviously you would want this to be low in the generated version since it should still look close to x0.
R(x) is a regularization term to avoid overfitting. For example, in the denoising example, it could be a measure of the variation in color of x. Clearly, just taking x = x0, the squared error (E(x; x0)) is 0, but it will have high R(x) because of all the noise. That's why they try to minimize both quantities combined, so we get min_x E(x; x0) + R(x), to get close to the objective but also not overfit.
