How can we know that? If memory in some way uses energy levels for encoding then we know it must be finite because of quantization but do we know that?
Taking the SI base units, which can be used to derive all the others that we know about :
Time, Energy ~ Mass and Length are quantified by Heisenberg's Uncertainty Principle.
Temperature doesn't really exist, it's kind of a proxy for information through energo-informatics, quantified, thanks again to the HUP : http://www.av8n.com/physics/thermo/entropy-more.html#sec-pha...
Electric Current by the charges being discrete.
Mole by definition.
Candela is not a physical unit (but one based on human biology).
----
Of course, that's a different question of whether their amounts in our universe can be (countably) infinite : so far as we know, time is (and maybe space, which should make other space-extensive quantities like mass-energy and charges also (countably) infinite ?)
We might never get a "theory of everything", and we shouldn't assume the existence of new physical properties without any other reason to do so, this goes against the principle of parsimony ! (Especially continuous ones, none of which seem to exist for now !)
And if our understanding of physics does change, it could have other dramatic consequences - that Bekenstein bound might not be valid any more for instance...
(yes, that's a ridiculously high bar, but still finite)
also, what about accumulated 'memory' in our human culture? how finite is that? how do you quantify this? (I'd think it'd be quantified by a timestamp, like a reference to an era or an historic age?? shrug)
> How to define an abstract neural network with some explicit memory component, which can grow to infinite sizes?
I think "culture" is the answer.. but maybe I actually mean a free "natural language" (in contrast with a formal (or synthetic) language)
But also, a human can easily augment his/her own memory by some pen and paper, or by a computer. That way, a human can solve more complex problems.
While this is true, I'd like to point out that this distinction is purely theoretical. Nothing infinite exists in the real world, but some things are so plentiful we might consider them infinite for the sake of easier reasoning.
A very practical example of this is cloud computation. All data centers in the world obviously have a finite amount of memory, however, the amount is so huge that for the sake of any practical computation, we might as well consider them infinite (though we are more limited by the money required than by the physical resources themselves).
Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ?
Not a physicist, so better get a second opinion, but I do not think that this is something you can get out of the uncertainty principle. As far as I can tell it does not turn continuous space and time into some discrete voxel space, i.e. while there is uncertainty, the location of the peak of the amplitude, for example, can still be located anywhere in continuous space.
Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ?
The total energy of the universe might be zero. [1]
While we still don't know what spacetime looks like at the smallest scales (we're still waiting on a quantum theory of gravity), quantum field theory measures spacetime using continuous real numbers
IIRC, the uncertainty principle limits the precision in any possible measurement to something like 60 or 70 digits. So yes, current theories use continuous real numbers, but I wouldn't generalize that to say that's confirmed because we're nowhere near being able to test that level of precision.
There is not even a real limit imposed by the uncertainty principle, you can measure positions as precisely as you want, you just have to pay in momentum uncertainty. Where we really seem to run into a wall is that if you keep making the measurement more and more precise, you need higher and higher energies to achieve ever shorter wavelengths and dumping a lot of energy into a small volume to measure the position really precisely will eventually result in black holes.
Yes, that's the current continuous model of how this works. That isn't necessarily reflective of reality though.
> Where we really seem to run into a wall is that if you keep making the measurement more and more precise, you need higher and higher energies to achieve ever shorter wavelengths and dumping a lot of energy into a small volume to measure the position really precisely will eventually result in black holes.
Exactly. In other words, all measurements necessarily have finite precision due to various uncertainties or other physical limits.
I didn't pull this limit out of the aether, I came across it from one of Shor's posts [1] where he states that physical constants can't be defined to greater precision than what I specified. If the physical constants can't have more than 60 digits of precision, then neither can any calculations or measurements based on them.
The fact is, we're bounded on all sides to finite precision.
[1] https://physics.stackexchange.com/questions/16889/non-comput...
> So yes, current theories use continuous real numbers, but I wouldn't generalize that to say that's confirmed because we're nowhere near being able to test that level of precision.
Agreed, though I personally find continuous quantities implausible, despite preferring them at one point. As long as we had a discrete theory with equal predictive and explanatory power and it was equally parsimonious to a continuous theory, I would likely prefer it. I think the next revolution in physics will see an expansion of discretization or other forms of finitism.
> On the other hand we could also observe effects that clearly indicate a non-continuous structure of space without running into some measurement limit.
Agreed as well.
http://www.av8n.com/physics/thermo/entropy-more.html#sec-pha...
Note that this underlying structure is subjective, relative to the observer, not something objective... (but we already know that there's no such thing as an "objective underlying structure" from elsewhere from quantum mechanics and also from relativity)
No we don't. Don't confuse the map with the territory.
Even philosophy has pretty much given up that claim : with Gödel/Church/Turing having blown up to smithereens the positivist project of a "theory of everything" for mathematics, and Wittgenstein/Kuhn/Derrida/Foucault/Chomsky having redirected the rest of philosophy towards "the naming of things".
And that project had been ironically doomed from before its start anyway : Descartes both laid the groundwork for it by elevating epistemology to "fist philosophy" and for solipsism - which, while a dead-end, cannot be ruled out !
(Also honorable mention for Max Tegmark's Mathematical Universe I guess, which, in a way, indirectly achieves the claim by positing a mathematical multiverse so vast that "our" reality can only be contained inside it.)
So the only discipline left that still lays claim on Truth and the True Nature of Reality is theology. (Note that this is how Descartes "solved" the problem of solipsism.)
There's also a point in how one paradigm might be ontologically radically different compared to the previous one... but what science cares about more is the new paradigm being a "tighter fit" between its new models and the results of the new experiments.
Also, beyound a single "thing", it's when we start considering collections of things that the situation can get very tricky very fast, like chaotic behavior from something as simple as 3 masses under the Newtonian paradigm ! (See also : "emergence")
Or the concept of temperature : it doesn't go "down" to the "true nature of reality", but is a statistical one that is not even always defined, yet is still quite useful.
But yet again I would like to emphasize how in several subfields of physics we now are in a situation where we had to give up an objective viewpoint of the situation for a subjective one, and where the information itself that we have about a system (aka negative entropy) is another variable in a super system that includes us (and our instruments) and the system being studied, and we are forced to consider that supersystem instead, or at least also, in order to go "deeper".
(It's also impressive how in some cases we now study "turtles all the way down" situations, with models having an infinite number of correction steps that we can cheat around thanks to the use of advanced mathematics. But maybe in the future these will be seen as trivial as we see the Zeno paradox today ?)
And would you get quantification of mass~energy from that of the impulse (through v having dimensions of space and time), or do you need to use a different approach and assume black holes ? (Or both, and pick the biggest value ?)
> And would you get quantification of mass~energy from that of the impulse (through v having dimensions of space and time), or do you need to use a different approach and assume black holes ? (Or both, and pick the biggest value ?)
Neither, though the impulse thing is at least in the right neighborhood. (Black holes have absolutely nothing to do with this). You get quantized energy whenever the Hamiltonian of your system has a pure point spectrum. Typically this happens for finite dimensional systems, and infinite dimensional systems with potentials that grow rapidly with increasing distance. Generic infinite dimensional systems will usually have continuous spectra.
Why?
[1] https://physics.stackexchange.com/questions/16889/non-comput...
Don't they have, in the sense that to keep probing ever more precisely, you need ever more energy, and at some point too much mass~energy in a too small volume is going to form a black hole and you cannot go further ?
----
Argh, I should have known that this discussion would start to involve operators at some point, especially ones with an infinite number of dimensions... XD
Though this seems related mathematically to how the uncertainty principle can be interpreted through Fourier transforms : localized <=> spread out ; quantized <=> continuous ; finite (+ conditions on potential) <=> infinite (+ other conditions on potential) ?
This may or may not be true - we can't probe those length scales yet, and maybe ever, so we don't really know - but it has no bearing on ordinary QM, which is nonrelativistic.
> Though this seems related mathematically to how the uncertainty principle can be interpreted through Fourier transforms
Not especially. They're both results in functional analysis, but that's about it.
What I meant to say is that nothing that can be used for computation is infinite. Resources are finite, there is a finite amount of RAM/hard drive/paper space in the world.
Space is infinite, but we haven't yet found a technique to use pure space as computational memory.
Time is infinite in theory, but not practically. Time is fairly meaningless after the heat death of the universe. Some quantum field theories also suggest that space becomes unstable if it falls below a certain density IIRC, so even spacetime expansion might have a limit.
Language classes are about the code, not about the computer. With a finite state automaton, you have to commit to the size of the input in advance and write the state transitions explicitly. While there exist structurally similar automata that can handle larger inputs, your automaton – your code – cannot handle them. You can generate those automata algorithmically, but in order to do that, you need a more expressive formalism that can handle n items.
> only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks
I guess because in practice (for computers, not brains... at least not yet) we can actually cheat by using "extensible on demand memory" rather than an actually infinite one (which is impossible) ?
Also, I wonder if the difference between countable infinite (a Turing's machine tape) and the continuum (that, assuming ZFC, might be somehow achieved by doubling a number for each slot on the Turing tape) might be of relevance even in their finite, extensible at will (for all practical purposes) equivalents ??
> The point of stating that a mathematical model is Turing Complete is to reveal the capability of the model to perform any calculation, given a sufficient amount of resources (i.e. infinite), not to show whether a specific implementation of a model does have those resources. Non-Turing complete models would not be able to handle a specific set of calculations, even with enough resources, something that reveals a difference in the way the two models operate, even when they have limited resources. Of course, to prove this property, you have to do have to assume that the models are able to use an infinite amount of resources, but this property of a model is relevant even when resources are limited.
In other words, when you have reasonably big practical finite problem with limited memory. FSA runs quickly out of memory.
Yes this is a difference in the expressiveness of each model, because FSAs can require a combinatorial explosion in the number of states to model a finite Turing machine. The parent is still technically correct though.
First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have finite memory, it is always only just as powerful as a FSA. Adding one (infinite) stack will give you pushdown automata complexity, and adding two (or more) (infinite) stacks will get you to Turing machines.
Consider that a float in hardware (f32, bf16, or whatever you like), but also in reality (think of the neuronal spike voltage) is not infinite in memory but finite. This is different from mathematics, where you can store infinite memory in a real number. Note that there is an infamous paper, "On the computational power of neural nets", Siegelmann & Sonntag, 1992, which states that RNNs are Turing complete. But this construction assumes that you can store infinite memory in a single neuron activity, which is never true in practice. In practice, a RNN or LSTM has finite memory.
However, in practice, also any computer has finite memory. Also the human brain has finite memory. So, it follows, you always only have the complexity of FSAs. But is this right? Wouldn't the intuition say sth different? Maybe the Chomsky hierarchy is not really so relevant? Or the question is somewhat ill posed.
What would make a computer Turing complete? You need infinite memory. So, you need to abstract away from a particular computer towards the concept of a computer with infinite memory. The official C language definition calls this an "abstract machine". This abstract machine is Turing complete.
How can you apply this to neural networks? How to define an abstract neural network with some explicit memory component, which can grow to infinite sizes? You get to memory-augmented models like the differential neural computer (extended from the neural Turing machine). In theory, you can think of abstract variants of those models with infinite memory, and then you can think about the Chomsky hierarchy.
In practice, the memory is always finite though. What they do in the paper is to focus more on the Chomsky hierarchy in practice, i.e. applied to some actual benchmarks. When you limit the length of the input problems, there is some maximum amount of memory which should be sufficient to solve them. Depending on the structure of the neural model, it gives you a clue to what compute complexity it mostly corresponds to when you test it.
I have written down some own thoughts on this here: https://stackoverflow.com/questions/2990277/how-useful-is-tu...