Is 'computation' really universal and fundamental? Turing machines, lambda calculus, algorithmic notations, they're all human-made formalisms. Are the halting problem and the limits of computability actually constraints that exist only within these human-made formal systems? When we constrain a formalism to reduce complexity, it feels like necessity emerges from within those constraints. For example, when we say 'CRU…
We can still test the theory that computation describes physical reality with experiment (presumably it makes predictions). The scientific method still holds.
Computation as realized by computers is a formalism invented by Turing, Church, Kleene and others to make precise the intuitive notion of "algorithm". An algorithm, at its root, is a procedure rooted in human understanding that human beings can follow. When Turing and others first introduced this formal notion, not all mathematicians were even fully convinced it was an adequate representation of the informal intuitiv…
The computational view of the universe and the nature of reality has provided us with some new insights.
Sure, others would also claim the "financial view" of the universe has also provided insight. That doesn't mean I go around claiming the money is some fundamental universal substance of the real.
This. I'll never understand people who reify "information" as though it is some object with independent existence from man. No information without an interpretation. The "amount" of information is completely dependent on the observer. You'd think people who work constantly with abstraction wouldn't fall prey to reifying abstractions but they actually seem more susceptible to it than anyone else.
I think you are prematurely dismissing something deeper here. The more I learn about the fundamental nature of the electron, probability in quantum mechanics, and the wave function in general... the more information being fundamental substrate makes sense. I'm not saying it is... just that it makes more sense the deeper you get.
Yeah, but my point is that "information" is not really a substantive concept. It is an abstraction. It is a useful technical tool. For the record, I am a nominalist when it comes to mathematics. Thinking that information is some "real thing" with meaning independent of theoretical context and interpreters is a definitely Platonisist perspective (the idea that our mathematical representations are not merely useful technical models but that they correspond to some real substantive elements of the real).
Claiming that "information" is the underlying basis of the real is the same as effectively saying that "stuff" is the underlying basis of existence. It's essentially Platonism. It is not informative. What is informative is the operational use of the mathematical concept of information as defined by Shannon to understand real things or to structure theories. But this is a very different thing than identifying a substance that exists, independently of us in the universe. This "making real" of what is ultimately a mathematical abstraction is precisely reification.
Information and computation are not the same thing. I was very specifically talking about Turing machines and other theoretical models of computation. That said, you are still making the same mistake I pointed out, elevating human symbolic information to a higher plateau than it deserves. I think it's because you're being too vague about the connection, when it's fairly mundane. The "fundamental connection" is that p…
I’ve always hated the use of the word “information” in relation to things like spin. Information and order are effects of human perception and preference. They exist as abstractions in the mind and not in reality.
This is the way. But what is interesting to contemplate is _why_ smart people try to reinvent religion. I think it reflects their deep need for meaning and immortality. Religion in the naive sense, a bunch of stories, myths and bearded gods, if obviously silly and childish. The modern rationalist who has not managed to shed his reflex/need for religion, then reifies (or perhaps better said... "deifies") information, and thus introduces all kinds of potential immortality and an ideal realm. Just like the myths of religion did, in a more naive sense, since time immemorial.
Agreed, and I'll add: the universe is sufficiently messy and complex that some of the claimed undecidability results may never occur in practice. For your Turing machine example: even if we built such a machine, it would never truly be giving an answer to the halting problem, because any stray cosmic particle could excite the electron and cause it to cross whatever plane. For a more realistic example: the ground stat…
A quantum Turing machine would be needed to simulate a truly quantum process. Stochasticity exists in classical systems, but that's an entirely different type of randomness.
Quantum computers can be simulated on classical computers, but it takes exponential time (completely impractical).
Information and computation are not the same thing. I was very specifically talking about Turing machines and other theoretical models of computation. That said, you are still making the same mistake I pointed out, elevating human symbolic information to a higher plateau than it deserves. I think it's because you're being too vague about the connection, when it's fairly mundane. The "fundamental connection" is that p…
A more concise explanation is that, computation is the transformation of information. Any transformation of information is computation, and is thus subject to some theory of computation. A physical process involves the transformation of information, so can be studied with a theory of computation.
Both P and NP are computable. That is, a Turing machine can compute both of them. Those quantum processes are interesting. Take the random numbers generated from radioactive decay. They are (after some cleanup) truly random. That is what we think. But how could we tell the difference from pseudorandom numbers, generated by a sufficiently advanced algorithm? We couldnt. So particles could simply be Turing Machines run…
There is such thing as a quantum Turing machine you know (Deutsch 1985).
Yes I know.
When I wrote Turing Machine, I was thinking about the classical determinstic Turing Machine.
Im not super knowledgable about Quantum Turing Machines, but as far as I know, they dont do better than the classical deterministic Turing Machines when we are talking about computability.
I think Gödel undecidable sentence is always relative to a formal system (the title of the paper spoke about systems in the expressive power rank of Russell's Principia, of which he gives one particular example assuming it shows how his methods apply to the whole family of systems), but now Hilbert problem #6 still stands for the lack of a comprehensive axiomatization of Physics, as its modern heir the mass-gap mille…
Also, correct me if I'm wrong, the mass gap problem involves quantum physics, not classical, so the underlying math/logic is different.
mmh I'd don't say that much, I think the logic and math foundations is common in both classic and quantum theories, only content changing, so you would say "import mathlib" from both classic-phys.lean and quant-phys.lean if writing Lean proof assistant code (I am guessing the "import" command). Concepts from linear algebra as eigendecomposition, to say something, will be used in both applications.