There are a lot of long comments basically saying what I am about to say so I will try to keep this brief:
Computation is a metaphysically universal and fundamental concept, since metaphysics is (tautologically) the domain of humans and we use symbolic communication. So of course very general theories of symbolic processes (e.g. Turing machines) are pertinent to the symbolic methodology we use to understand scientific processes.
But it is a fundamental mistake to jump from that to saying computation extends to a law of the universe. Computation reflects laws of the universe, but only in the exact same way that scientific and mathematical human speech do. The mystery (still totally unsolved) is how humans are able to intuitively understand space / time / causality / etc in order to define coherent symbolic rules that reflect real processes. That computers can seemingly always implement these rules having been given the symbols is of philosophical/scientific interest, but it's solipsistic to say it's a fundamental concept of the universe.
This is a misconception. It’s more fundamental than that. There’s a fundamental connection between (Shannon) information theory and thermodynamics. The Landau Limit, whether blackholes can destroy information or not, quantum mechanics, etc.
Information is actually tangible. It’s not just an analogy or a coincidence that the word “entropy” is a word used in both physics and computer science (information theory). Thermodynamics, mind you, is perhaps THE most fundamental elements of physics and how the universe works.
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 physical quantities are information, and on the other hand information is always a large collection of semi-independent semi-stochastic physical objects and can be profitably modelled by some sort of statistical mechanics. Information theory is relevant all over physics because human agents collect all sorts of physical information. The universe "doesn't care" about information in and of itself. Shannon entropy and Boltzmann entropy have similar formulas because they measure precisely the same thing; put another way, a goofy but formally equivalent way to model a gas would be a noisy radio channel communicating each molecule's kinetic energy.
The problem with the black hole information paradox isn't that information is destroyed per se, but that it appears to be destroyed in a way that violates quantum mechanics (destroying quantum state without a measurement). The theoretically predicted destruction of information points to a more general problem.
The Laundauer limit is no more fundamental to the universe than "a mechanical crane cannot violate the laws of pulleys." It says that no matter how you design your binary (or whatever) computer, it must involve an ensemble of binary states, and statistical mechanics puts an absolute floor on how little heat is required to alter such states. Whether these states are gas molecules or the written symbols "0" and "1" is immaterial.
But that just takes us even further from physical relevance / universal fundamentals. Kolmogorov complexity is fundamental in computation, but its relevance in physical science is pretty selective.
Best way to show this is to implement information in multiple physical substrates. Make a book out of paper and make it out of clay. Same information. The physical substrate doesn’t matter.
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.
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.
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.
> A physical process involves the transformation of information, so can be studied with a theory of computation.
A rock rolling downhill has state-dependent future behavior you could describe informationally, but nothing is gained by modeling it with automata theory instead of Newtonian mechanics, and it isn't computing in any substantive sense.
> It’s not just an analogy or a coincidence that the word “entropy” is a word used in both physics and computer science (information theory).
Shannon asked von Neumann what to call it, and von Neumann said "You should call it entropy, for two reasons: In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage."
You can say things like, “In the domain of physics, X,” “Assuming the scientific method, X,” or “Assuming the premises of logic, X.”
But “computation is a fundamental aspect of the universe”, in the way it's being understood in this thread (as opposed to the article) does not remain within any of those frameworks. It makes a claim about reality as a whole.
Once you make that kind of universal claim, all the assumptions built into “computation” - about identity, distinct states, lawful transitions, causation, logic, etc. - become part of the claim. You cannot use those assumptions silently and then present the conclusion as framework-independent.
And those frameworks come with consequences. Using the language of computation, they come with "lossiness" wrt modelling "reality".
(see Aristotle Metaphysics -> Kant CoPR -> later Wittgenstein)
Metaphysics operates one level up from physics or the sciences, asking what reality has to be like for anything, including the sciences, to be possible or meaningful at all.
I know what metaphysics is (and your description isn't accurate--science is a knowledge-producing method that doesn't depend on metaphysics in order to be meaningful), but that has nothing to do with my statement. And it's called "metaphysics" because Andronicus placed that volume after the "physics" volume when he organized Aristotle's writings.
Science absolutely does depend on metaphysics. Most famously: the validity of the scientific method is ultimately a metaphysical extension of our intuitions about inductive reasoning and causality. There is no scientific proof that the scientific method is valid. ("Our intuitions" is why I said metaphysics is tautologically the domain of humans. This is essentially Kant's philosophical legacy: science will describe what it does, but humans intuitively understand reality in ways that defy noncircular scientific description, and metaphysics must be invoked to have a rational and grounded discussion about these intuitions.)
I asked for proof of claims and I just get "it absolutely does" and a bunch more assertions, and word salad like "the validity of the scientific method is ultimately a metaphysical extension of our intuitions about inductive reasoning and causality" -- there's nothing "metaphysical" about it ... the scientific method is a disciplined application of an effective process of discovery. And '"Our intuitions" is why I said metaphysics is tautologically the domain of humans' is more word salad -- "tautologically" has no business in that sentence, and none of the rest of it makes any sense either. Humans have multiple domains, not just "the" domain. Metaphysics is a field of study that non humans capable of studying can also study. Metaphysical facts govern everything, not just humans. etc. I consider this sort of junk to border on bad faith ... it certainly isn't of any use to me, and I have no interest in engaging with it.
> There is no scientific proof that the scientific method is valid.
The scientific method is provably effective in a lawful world. That the scientific method isn't provably effective is because the world is not provably lawful ... it's logically possible for the "laws" of physics--which are simply regularities that we have discovered--to suddenly change, oscillate, be random, etc. But as long as they don't the scientific method works ... and we can't do better. (Not in this world, anyway ... in some other world there might be oracles (aka gods or bibles) that always have the right answer and we could simply query them. Of course, such oracles are also not provably correct.)
There is no single "scientific method" to speak of. Your epistemic position is ultimately just as faith based as you claim faith in God etc. is, the sciences (plural) just have a set of operations which, as you point out, seem to have practical utility and seem to be better than certain alternatives for building up shared epistemic structure.
The attitude of "we can't do better" is precisely the kind of attitude that would have hampered the creation of various sciences and their methods in the first place, and the production of scientific thought is often not as pure or logically consistent as all the methodological purists or Popperians seem to believe it is. Feyerabend, Quine, Von Foerster, Dataon and Gallison and several others have made this pretty clear and make the argument pretty forcefully in my opinion.
All sciences carry an ontology and value system along with them. Religion is also a rich and highly effective epistemic structure when your underlying ontological assumptions, values, and goals differ from those established and implicit in the scientific (predominantly utilitarian) Western enlightenment value system. Science is not able to found itself on some irrefutable bedrock "truth" correspondence any more than religion is. There is no basis by which we can actually solidify empiricism as somehow more privileged and more capital T true if we admit the possibility of human error.
Agreed. I’ll also make an observation based on this thread: the idea of computation as a fundamental law is most believable (and desirable) to people who like computers and want to reduce reality to a computer.
The belief is like a cheat code: somehow our tinkering and 9-5 job somehow grants us, the computer nerds, a deep understanding of life, the universe and everything. Deeper than scientists, philosophers, etc. It’s epistemic catnip and pretty tasty at that!
A related question might be, what's the difference between mathematical (Godel), computational (Turing,) and physical (Yang-Mills) undecideabilty/computability?
For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
I loved his Algorithms course on Coursera which I did during the brief moment Stanford MOOCs were all free. So useful for a non-CS grad doing any kind of algorithmic programming.
Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection).
Our world appeared computable, but it isn't, even if P=NP.
- The physics of the universe can be completely modeled as computation, and
- It's possible to pose undecidable problems about the way the universe unfolds
This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".
Of course, if our universe is undecidable it must be the case that computable processes can be executed within it, and it might be the case that all of the processes that are ever executed within it are computable... but it might be that some of the processes that are executed are not computable... because the machine may.. or may not?
I think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
There's no way to empirically spot an uncomputable process, since it would require infinitely-many observations.
For example, if aliens claim their machine solves the halting problem, we could test it on millions of inputs whose halting/not-halting behaviour we already know; but even if it works for all of them, there's no way to know that it works for all inputs. For all we know, it might be a huge lookup table which happens to cover all of those inputs we tried.
A key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infinite mass (the lattice), bespoke local interactions etc. Problems standing in the way of physics decidability are typically chaos, far from equilibrium mechanics, elementary SNR considerations and so forth, not problems of logic.
>Recently it's been shown that there are real, physical processes which are undecidable
I want to push back a bit on this claim along two dimensions.
Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purely physical question about a trajectory (does this electron ever reach a certain target), yet answering it for the whole family of such machines is literally the halting problem, so there's a physical process that's undecidable.
Your examples about physical processes being undecidable are all basically just this... there examples of using reflections of light, or the flow of liquid, etc... and demonstrating that these physical processes in principle are sufficient to model a universal Turing machine.
And while it's fascinating that certain things you may not have expected can be used to model computation, it's misleading, or rather it's too strong of a claim to believe that there exist actual/real physical processes whose outcomes are undecidable. That's a subtle but very common misinterpretation of what undecidability is.
Undecidability, whether in physics or computer science, only applies to the infinitely broad class of a problem as a whole, it never applies to a specific instance of a problem. So it can never be the case that there's a certain configuration of reflections for which it's undecidable whether a ray of light reaches a target. Nor can it be the case that for a specific lattice of atoms, it's undecidable whether it has a spectral gap or not. It can only be the case that for the problem as a whole where the parameter space is entirely unbounded, there is no single algorithm that can decide if a ray of light reaches a specific target for all possible arbitrary (and infinitely many) configurations. Once you fix a specific system, then the undecidability goes away.
Not claiming that you are necessarily making this misconception, but I often see people misinterpret undecidability to mean that there exists a specific problem, like with specific inputs, where it's somehow impossible to know what the answer will be. Undecidability always requires an infinite family of instances, and it's a statement about the nonexistence of a single algorithm that correctly answers every instance in that family. It says nothing about any particular instance being unknowable/undecidable.
If I am wrong, please pardon. I suspect I am. But was this comment edited by Claude? I ask specifically because it is well written, substantive, all which is expected here, but the "push back" part, to me, must be a) an artifact of Claude, either by osmotic assimilation (Which is happening to many innocent users) or b) Claude itself.
Feel free to flag this comment if I get an answer. I do want to know.
No Claude was not involved in any way in me writing it, and honestly it's kind of getting depressing how many comments are constantly questioning peoples use of LLMs.
Just a heads up, "I want to push back on" is an idiom Claude frequently uses.
It is depressing though, writing feels like it's in part becoming a game of outpacing the latest LLM's idiosyncrasies so we can signal authenticity, which perversely, is achieved through using an LLM enough so that you can become familiar with its flavor of communication.
This is what makes me sad about the AI age; many articles now have the same phrasing, the same analogies, the same quips, structure, the same wording; once you start to see it there's no going back.
I actually laughed quite a lot to begin with, GPT models saying things like "...might look like P, but is NP wearing a hat and a lab coat..." and "...is a haunted house disguised as a git repository..."; but alas when you've heard them a million times everywhere it really starts to bite.
The other day, while reading, my AI-dar triggered on some typical claudisms, but then I remembered I was reading from a paper book that was printed in 1997...
I may be misremembering Godel's proof or misunderstanding your last paragraph, but I thought Godel's proof actually presented a specific undecidable statement. The hope then was that somehow undecidable statements could be cordoned off from decidable statements, and Turing's result showed that that wasn't possible. Perhaps that's what you mean by "the nonexistence of a single algorithm that correctly answers every instance in that family"?
It's a gap between physics and mathematics. Undecidable statements exist mathematically, but don't exist physically: mathematics and physics have different concepts of existence. Ironically, even mathematical universe hypothesis deliberately limits mathematics-as-physics to specifically resemble physics of a spontaneous material world, and this limitation is just an axiom.
There's no such thing as an undecidable statement. A single statement can't be undecidable. Undecidability is a property of a class of statements.
For example, you can ask whether a Java program, run with infinite memory, will eventually halt. For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no". Might be hard to figure out which is the correct algorithm, but the Java program is fixed so the algorithm is definitely one of the two.
However, there is no algorithm which can take an arbitrary Java program as input and determine whether it will halt. It's about the class of all possible programs.
That's a different meaning of the word "undecidable". You're talking about undecidable problems [1]. The meaning in Gödel's incompleteness theorem is different and is a synonym with independent [2].
> For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no".
This isn't true.
In general, if a program hasn't halted yet you don't know if it will.
In particular, consider the Collatz conjecture. You can't even tell if your Java implementation of it will halt for a particular input, until it does.
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 millennium problem, that still also lingers, so we don't have a controllable notion of naked/absolute undecidability for physical phenomena or for arbitrary assertions unbound by explicit logic rules in general.
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.
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 state of an molecule is a physically relevant quantity, and in theory any molecule alone should lose energy and attain it's ground state, even if finding the ground state electronic configuration is undecidable. But in reality, no molecule is ever truly isolated and so would never actually be guaranteed to enter it's ground state (or if it were truly isolated, it would not be observed at all rendering the question moot)
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 computation is not super-Turing: anything you could solve with a quantum Turing machine you could also solve with a classical Turing machine, albeit sometimes a lot slower. We know how to emulate quantum systems in classical systems.
> … so there's a physical process that's undecidable.
No, since you cannot physically build a Turing Machine. A Turing machine requires infinite tape. Any physically realizable machine doesn’t have that, so has finite states, so is decidable: enumerate the states in finite time - it halts or repeats, so all programs on a finite state machine are decidable.
Your example is not an undecudable physical process.
Godel things also don’t apply: Godel theorems are about proof of this or that from within the same system. In logic one can prove such things from an outside system, then construct towers, avoiding Godel theorems. Godel theorems also require a model of integers including multiplication (without multiplication, such systems were proven complete and decidable). However the universe does not contain a model of integers, as the physical universe is not unbounded: relativity places a finite limit in spacetime on what can interact.
Mixing math as reality fails at these requirements.
How would that work as current understanding from quantum theory is that we cannot predict which atom decays next? Is there a quantum algorithm that can do that?
> up to the point that many computer scientists now seem to equate computation with the functioning of the universe.
Do you think that's a kind of tunnel vision? If the only thing you focus on is computation, you'll probably end up seeing computation everywhere - it became a way of seeing the world.
It is a common accusation. There's a somewhat famous quote I've seen a few times:
"It's interesting to look back through history on this one. Each age has its pinnacle of technology, and each age uses that technology as a metaphor for nature, for the universe. In ancient Greece, the technological marvels were musical instruments and the ruler and compass. The Greek philosophers tried to build an entire cosmology from number, harmony, proportion, form, and so on — from mathematics, basically. Remember the music of the spheres? The Pythagoreans believed that nature was a manifestation of rational mathematics. Later on the pinnacle of technology was the clockwork. Newton wanted a clockwork universe, the entire universe as a gigantic clockwork mechanism, with all the parts interlocking and ticking over with infinite precision. Then in the 19th century along came steam power, and the universe was then depicted as an enormous heat engine, or thermodynamic machine, running down toward its heat death. Today the computer is the pinnacle of technology, so it's now fashionable to talk about nature as a computational process."
While "computer" may give us impressions of something with "a CPU" and "RAM" and "a disk drive", it does at least seem plausible that the universe as computation is a plausible base level, though. Unlike "the music of the spheres", which to the extent that it made predictions of the world, it got them wrong in the most basic way, viewing it through a lens of computation allows us to put some quite subtle and interesting limits on things. "Computation" is a pretty flexible substrate; it is difficult to imagine how the proposition "the universe is a computation and subject to the limitations thereto" could be falsified, and if it could, it is difficult to imagine how we would be able to know it was so falsified. Nevertheless the math of computation allows us to say non-trivial things about the universe as a result; it is not a vacuous generalization, though it is certainly a loose one... being able to say yet more concrete things about the nature of the computation, such as "this is exactly how gravity works", has quite a bit more utility.
The universe as a computer/computation has been explored by many (e.g., see John Wheeler and Seth Lloyd). However, the laws of physics give us a lot more predictions, so their explanatory power tend to be greater. For example, the nature of space and time.
Undecidability is a problem of answer-extraction from a process, it doesn’t preclude the process from executing deterministically. The universe could well be the live execution of a deterministic, even basic algorithm, with all kinds of questions about its execution being undecidable.
The infinite lattice doesn't represent a "real" physical processes, it's just mathematical technique for closing a (fundamentally) quantized combinatorial sum over millions of interacting elements. The gap problem exists in the limit. For real systems the spectrum can be measured (in principle) by probing the ground state. The computational paradigm is incredibly general but only within what's apparently a pretty atypical thermodynamic regime (the ordered universe).
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 running sufficiently advanced algorithms that we cant reverse engineer. If so, quantum mechanics is computable even if we cant compute it.
(Particles being TMs doesnt mean they are FAs with an infinite tape, but that they are computationally equivalent to TMs.)
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 like how every time a new technology is invented and becomes big, people start to think it explains everything. Like how in the 16th/17th centuries some people thought the universe was a big clock. Or how in the 19th centuries people thought the universe was like a big steam engine. Or now we think the universe is a big computer.
Not saying this is wrong or that I've watched all of the lectures above or anything, but it's just funny to imagine that aliens might look at us the same way we could look at a monkey society saying that the universe is like a big one of those rocks they use to smash nuts open.
Computation and information really does seem universal though, so this is just a funny thought and not serious commentary.
It strikes me that this is a kind of an escalating pattern though I don't suppose it has to be. Clock -> Steam Engine -> Computer -> AGI -> Skynet -> Throw rocks at robots -> Judgement Day. Also very not serious commentary.
On I suppose a slightly more serious note it also strikes me that there will eventually, probably, maybe be _something_ that fits best; though we are not promised to find it. And it seems wild to say that about a model because all models are fundamentally wrong, but they are usually group-able by less-wrongness, so probably fundamentally feasible.
Couldn’t all of them be right, though? In the sense that every technology associated with the functioning of the universe had a systemic, spatiotemporal and evolutive dynamic, which appears to be the sensible facets of the universe’s behavior? In that sense computation is no different, just has more primacy. It gives me some Hofstadter vibes, meaning whatever complex thing we produce within the universe is hopelessly bound to be analogous with it.
Yes, these are all our attempts at explaining the nature of reality. A kind of reaching into the unknown. A desire to understand the universe and our place in it.
From my naive pov: Related to computation is the concept of state (I know, functional languages can get away without it, sort of). I always wondered how the universe “knows” the mass of the sun. If there are some underlying functions/computations “running” in the background to keep planets moving and so on, and if the mass of planets is a key element in such computations… then either: the mass is calculated “on the fly” every time (seems expensive) or it’s a variable (how is it updated? Where is it “stored”?)
The somewhat abbreviated answer is that the "state" is formalized into the concept of fields. All the physical properties we can observe are from coupling with the relevant fields. The speed at which changes can propagate in fields is C, hence the speed of light being the same value.
As far as I understand it, the storage is the space, or rather, spacetime emerges from a system's informational capacity and the degrees of freedom along which information can spread. On the balance all information is retained but undergoes various phase transitions (the 'computations').
Functional programming very much has states. But you’re describing the transitions instead of the states directly. What it does is removing the hidden states and effects and makes them typed, explicit and contained
I think it’s easier to conceive of it like this: Each point in spacetime IS storage. Storage can be queried by interacting with it (in a variety of ways), though the process of querying affects the value not only of the querier, but also the queried, which may have side-effects as well. The interaction itself is the computation.
A simple example for the computation: It’s like placing boxes next to each other. Yes I could say 1 box + 3 boxes = 4 boxes, via explicit calculation. I could also simply place 1 box next to three boxes, and without having to explicitly calculate, by nature of the interaction, the result (4 boxes) has been produced
There is no background computation or storage. The universe IS computation and storage. Each spacetime quanta IS storage, and each interaction IS computation.
Spacetime isn't quantized as far as we know. We don't know since we don't have quantum gravity or ability to probe Planck scale. Quantum fields are continuous, it is excitations in the field, particles, that are quantized.
Ah, I thought we didn’t have strong evidence either way. Regardless, I shouldn’t have stated spacetime quanta so matter-of-factly. I just have an easier time conceptualizing if I treat everything like hypervoxels and that leaked in.
The theory of general relativity answers this exact question. It has been tested experimentally and has been found to be correct in the classical regime. By correct I mean that the experimental data agrees with theoretical prediction.
> "Ergo is a nonprofit that publishes long-form philosophical lecture courses with leading scholars. Everything we publish is freely available, without ads or paywalls."
Discrete math and Algorithms were two of my favorite college classes. They were really the only part of computer science that was mind blowing. The rest was software engineering, which was transparently "possible". Like, yes, big programs and OSs and numerical models exist, and yes I will graduate and work with them and add to them, someday, yeah sure.
But decidabilty, Godel's theorm, busy beaver numbers, etc... those were unexpected and worth the price of admission.
Thanks Prof Hadas, you made it fun to have my mind blown.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.
This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.
Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.
There remain undecidable problems even with finite memory/state space.
Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:
Emptiness: Does an LBA reject all possible inputs?
Universality: Does an LBA accept all possible inputs over its alphabet?
Equivalent: Do two LBA accept the same language?
Finiteness: Does an LBA accept a finite number of strings.
Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/
I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?
If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.
For the finite case, the more relevant question is, can you predict whether or not the computation will halt in less time than 1. executing the algorithm and 2. checking whether or not the algorithm ever loops?
Bear in mind checking whether or not the algorithm ever loops means taking the full state of the system and checking against a database of all previous states of the system. Bear in mind that the Atari 2600, and its whopping 128 bytes of RAM, has with that amount of RAM more states than there are planck volumes * planck time intervals in the known universe... by over sixty orders of magnitude. And every three additional bits you add to the RAM of the system your are looking at adds an order of magnitude (minus a bit) to that, so, nearly 3 orders of magnitude more states per byte... not per megabyte or gigabyte, per byte. Call it 2 orders of magnitude per byte if you want to be conservative.
It can be solved, if by nothing else simply by running it, in the mathematical sense. In the practical sense it's not even close. That's why we use the Turing machine analysis... technically it's an approximation because we don't actually have real Turing machines. However the size of the finite state machines we have is such that it is far more productive to simply say "the halting problem is unsolvable" than to argue about how many orders of magnitude of orders of magnitude of resources it takes to solve the question of whether or a given program terminates.
Thank you for your insightful answer, in reduction; "Don't fight a god, you won't win, and you'll definitely die in the process!"
The approach you describe though is brute force. I don't think (if there even is an answer to this problem) that it can be brute forced; that's where you run into the limits of hardware/computation/energy and start talking about timeframes which exceed the life of the universe.
I think brute force might be a useful tool in places to validate results, but if there _is_ an answer to this problem it's purely mathematical.
Apologies for sounding both excited and naive; these sorts of challenges make me happy in strange ways that no other thing does!
There is no general solution other than brute force. That's not a terribly difficult extension of the halting problem, it just takes more paperwork to deal with the edge cases, but you'll get to that result. The same basic technique works: Your supposed solution to the problem is itself some finite program, and you can feed it the "I halt only if I don't halt" problem too. The difference is that brute force is a solution, because now instead of an infinite sequence of programs you have a bounded set of programs. So whatever concrete "I halt only if I don't halt" you pass to someone within the specified limits, there is definitely some answer, but your technique won't be able to tell what it is short of just running it.
For the same reason the halting problem doesn't even have a good heuristic, neither does this. Unpredictable chaos is not an exceptional case, it is the exponentially-normal case. You have to go the other way, and construct programs deliberately designed to have the ability to tell if they halt. The term for that if you want to learn more about it is "non-Turing complete programming language", sometimes called a "sub-Turing" programming language: https://increment.com/programming-languages/turing-incomplet...
You can read that as "this is how hard it is to construct code that we can make execution guarantees about". That focuses on code that is deliberately constructed to be finite in scope and may be something that can be strictly bounded in memory use or time or both. You'll note if you spend any time working with them how hard they are to work with. That's a reflection of the limits of generalizing any such proofs of time or space of a given program.
If there is a general algorithm that does what you think, we don't even have a clue what it would look like. And we have a lot of clues there can't be any such thing.
Thanks for the link, great read. I think I get you here; in the context of a DSL where it's impossible to travel more instructions than X, suddenly you don't have a halting problem anymore as you've artificially limited that language's ability to travel beyond a known/fixed set of states.
The second you wield a language which has constructs like Haskell, where in theory you can iterate over an infinite list of items (thinking about it even any language where for i in input_var is possible); the halting problem hits you in the face like a brick.
Its almost a chicken and the egg problem, where you can't know how long it will run for/whether it will halt without already knowing the answer, but if you knew the answer, you wouldn't need the program to find it.
You might enjoy the book Escher Gödel Bach, the Eternal Golden Braid by Douglas Hofstadter, which will open up the world, power, and "danger" of proofs using contradiction to you.
Assume H(P,i) to be a program that tells you whether the program P will halt on input i. Returns true if it halts and false if it doesn't.
Define a new program G(x) that halts if x does not halt on itself as input and loops forever if x halts on itself as input:
def G(x):
if H(x,x):
while True:
pass
else:
return
Does G(G) halt?
If G(G) halts then H(G,G) is true so we end up in the infinite loop, a contradiction. If G(G) does not halt then it returns without looping, also a contradiction.
So our halting oracle H does not exist, so there can not be a function that tells you whether another function will halt on itself as input, so there can not be a function that tells you in the general case whether some other computation will halt, QED.
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 'CRUD app,' we immediately think of a specific pattern. In the same way, once you adopt a 'form,' the constraints that come with that form progressively expand the state space. In that sense, it feels like both discovery and invention.
Famous mathematicians and scientists often distinguish between model and reality, yet we tend to mistake the model's shape for reality itself. People like John Wheeler and Stephen Wolfram argue that computation is a fundamental property of the universe. But can we really say that when we downcast reality to fit human cognition, losing information in the process, and then upcast it back, the information is fully restored? I always find this point difficult.
Landauer's principle says that abstract logical operations, information erasure, necessarily increase physical entropy. That shows there's a thermodynamic cost to physically implemented information processing. But I don't think that proves computation is fundamental.
Whether it's computation or geometry, they're all abstract formalisms created by humans. But when we actually measure things, they're subject to physical laws. Still, whether that makes them fundamental is a difficult question. I think these are just results of the process where humans name phenomena and constrain them. I don't think they're the cause.
You can define computation broadly enough, as 'a process where a state changes to another state according to rules,' to make almost everything look like computation. But being able to explain something with computation and claiming that computation is fundamental are different things, aren't they?
Meaning exists within the structures and constraints of human-made formalisms. We artificially lower cognitive complexity and translate things into human language. Whether that's fundamental, I'm not sure.
Maybe I'm a reductionist. Plenty of intellectually brilliant scholars make those claims, but people like me, with slower minds, end up thinking these kinds of stupid thoughts. I wish I could organize my own thoughts bette
Ahhh this is fantastic thank you; it _is_ hard to reconcile whether problems come with the original topic or whether they are introduced by the abstraction that we _need_ to make in order to quantify a thing/explain it to ourselves and others.
Regarding the downcast/upcast; I think it _can_ be possible to do this successfully;
> I have a glass, I throw it at a hard surface. What will happen? Well (duh) the glass will (most likely) break.
This hypothesis completely ignores nearly 100% of all relevant physics and the laws surrounding the problem; the arrangement of air molecules, the arrangement of the molecules in the glass, the physical forces governing me, it reduces the entire equation down to some really basic napkin physics.
But; does the outcome work? Has my interpretation of the universe and its physics actually predicted what will happen?
Probably a stupid example, but I think that a lossy picture of the universe can still yield a correct answer.
I can't physically run a simulation of the entire universe in my brain, as my brain is part of that same universe. Lossy representations/models are a necessity in the thinking-ham bound world in which we exist.
You're right. But consider this: the geocentric model perfectly predicted planetary positions for centuries, and it was certainly useful. But could we say it was the essence of the universe? In the end, it's a useful model within limited cognition, but whether it's 'fundamental' is a separate question.
I think the key is that different phenomena require different approaches, and even if you interpret a single phenomenon through multiple mental models, none of them necessarily captures its essence. Ultimately, it's about which mental model is shared by a 'group'—not about what's fundamentally true.
We currently share the model of computation, but whether that makes it fundamental is a different story.
As a programmer, I'd put it this way: no matter how well an API describes the backend, the backend itself is not the API.
Here, the API is human knowledge, and the backend is the world
You sound like you believe in philosophical skepticism. Tell me: can a map ever properly describe the territory? When would a map properly describe the territory? (Can a theory ever properly describe reality? What does a theory need to properly describe reality?)
We know that universal Turing machines can emulate other Turing machines. Weirdos like Wolfram believe that a universal Turing machine can emulate reality. In a quick skim of this lecture series, the presenter doesn't talk about that, rather he just calls computation a scientific principal (universal and fundamental in the sense of physical laws, not fundamental in the sense of emulating reality on a computer).
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 intuitive notion. For example, some argued it was too broad because traditionally knowing that an algorithm eventually terminates was one of the requirements (to some) for something to be a legitimate algorithm. Why? Because the idea is rooted in human practical concerns and human understanding. Depending on what one cares about, one could actually reject the Turing formalization of algorithm on grounds of the class containing non-convergent (partial) functions.
All this is to say that "computation" is very much a human invention and little more than a formal model of human behaviors (we want to manipulate things algebraically). Elevating it to some objective substance of the universe is just doing 17th/18th century philosophical Idealism wrapped in new clothes.
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.
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
I saw the title and assumed an article by Wolfram. But it's by Tim Roughgarden who I know from algorithmic game theory. Anyway, I'll register my membership in the "it's more fundamental than that" camp.
I'd have to look deeper into his views, but I've already come across what seem like similar claims that try to attribute computation to the laws of physics or to matter in general or whatever.
However, these rest on category errors. Consider two characterizations of computation:
1. A mental process constituted by logical and intentional acts.
2. A mathematical model or formalism (or a set of formally equivalent formalisms).
In the case of (1), intentionality rules out computation as an extra-mental phenomenon. Things in the world aren't about something else; they just are what they are. But computation as a mental act is about something else. To claim otherwise would be like claiming deduction is a broad feature of reality, which is effectively some kind of panpsychism.
In the case of (2), if it's a mathematical model, then either by definition it doesn't exist outside the mind as such, or it must be instantiated in some objective manner. The trouble with finding instantiations is that it's not clear what constitutes an instantiation. Can you find correspondences? Sure. In fact, our physical computing machines correspond to these models in some way. But instantiation is more than mere correspondence, and this becomes even more the case when you consider that the lambda calculus corresponds to the Turing machine.
Another problem is that even mathematical models of computation cannot be said to encode mathematical operations as such. Is a Turing machine moving symbols around on an abstract tape actually adding two numbers? I would say that it is merely simulating the addition by producing results that afford that kind of interpretation.
There are a lot of long comments basically saying what I am about to say so I will try to keep this brief:
Computation is a metaphysically universal and fundamental concept, since metaphysics is (tautologically) the domain of humans and we use symbolic communication. So of course very general theories of symbolic processes (e.g. Turing machines) are pertinent to the symbolic methodology we use to understand scientific processes.
But it is a fundamental mistake to jump from that to saying computation extends to a law of the universe. Computation reflects laws of the universe, but only in the exact same way that scientific and mathematical human speech do. The mystery (still totally unsolved) is how humans are able to intuitively understand space / time / causality / etc in order to define coherent symbolic rules that reflect real processes. That computers can seemingly always implement these rules having been given the symbols is of philosophical/scientific interest, but it's solipsistic to say it's a fundamental concept of the universe.
This is a misconception. It’s more fundamental than that. There’s a fundamental connection between (Shannon) information theory and thermodynamics. The Landau Limit, whether blackholes can destroy information or not, quantum mechanics, etc.
Information is actually tangible. It’s not just an analogy or a coincidence that the word “entropy” is a word used in both physics and computer science (information theory). Thermodynamics, mind you, is perhaps THE most fundamental elements of physics and how the universe works.
Did you mean landauer?
Yes. Unable to edit it. https://en.wikipedia.org/wiki/Landauer's_principle
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 physical quantities are information, and on the other hand information is always a large collection of semi-independent semi-stochastic physical objects and can be profitably modelled by some sort of statistical mechanics. Information theory is relevant all over physics because human agents collect all sorts of physical information. The universe "doesn't care" about information in and of itself. Shannon entropy and Boltzmann entropy have similar formulas because they measure precisely the same thing; put another way, a goofy but formally equivalent way to model a gas would be a noisy radio channel communicating each molecule's kinetic energy.
The problem with the black hole information paradox isn't that information is destroyed per se, but that it appears to be destroyed in a way that violates quantum mechanics (destroying quantum state without a measurement). The theoretically predicted destruction of information points to a more general problem.
The Laundauer limit is no more fundamental to the universe than "a mechanical crane cannot violate the laws of pulleys." It says that no matter how you design your binary (or whatever) computer, it must involve an ensemble of binary states, and statistical mechanics puts an absolute floor on how little heat is required to alter such states. Whether these states are gas molecules or the written symbols "0" and "1" is immaterial.
> Information and computation are not the same thing.
Shannon information, sure.
However, algorithmic information (Kolmogorov complexity, etc.) is based on computation.
But that just takes us even further from physical relevance / universal fundamentals. Kolmogorov complexity is fundamental in computation, but its relevance in physical science is pretty selective.
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.
Best way to show this is to implement information in multiple physical substrates. Make a book out of paper and make it out of clay. Same information. The physical substrate doesn’t matter.
It’s not as simple as for example degrees of freedom and the states for a system is “information” and those one can argue are physical.
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.
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.
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.
> A physical process involves the transformation of information, so can be studied with a theory of computation.
A rock rolling downhill has state-dependent future behavior you could describe informationally, but nothing is gained by modeling it with automata theory instead of Newtonian mechanics, and it isn't computing in any substantive sense.
> It’s not just an analogy or a coincidence that the word “entropy” is a word used in both physics and computer science (information theory).
Shannon asked von Neumann what to call it, and von Neumann said "You should call it entropy, for two reasons: In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage."
I’m aware of the von Neumann joke.
There is, however, a direct equivalence between them derived from the 2nd Law of Thermodynamics. https://en.wikipedia.org/wiki/Landauer's_principle
You can say things like, “In the domain of physics, X,” “Assuming the scientific method, X,” or “Assuming the premises of logic, X.”
But “computation is a fundamental aspect of the universe”, in the way it's being understood in this thread (as opposed to the article) does not remain within any of those frameworks. It makes a claim about reality as a whole.
Once you make that kind of universal claim, all the assumptions built into “computation” - about identity, distinct states, lawful transitions, causation, logic, etc. - become part of the claim. You cannot use those assumptions silently and then present the conclusion as framework-independent.
And those frameworks come with consequences. Using the language of computation, they come with "lossiness" wrt modelling "reality".
(see Aristotle Metaphysics -> Kant CoPR -> later Wittgenstein)
The Heisenberg Uncertainty Principle and the Laws of Thermodynamics are pretty d*mn fundamental.
Also Ramanujan summation.
Prove any of this. Or at least provide a cogent argument for it. To me it looks riddled with mistakes, like
> metaphysics is (tautologically) the domain of humans
which is frankly incoherent.
Metaphysics operates one level up from physics or the sciences, asking what reality has to be like for anything, including the sciences, to be possible or meaningful at all.
I know what metaphysics is (and your description isn't accurate--science is a knowledge-producing method that doesn't depend on metaphysics in order to be meaningful), but that has nothing to do with my statement. And it's called "metaphysics" because Andronicus placed that volume after the "physics" volume when he organized Aristotle's writings.
Science absolutely does depend on metaphysics. Most famously: the validity of the scientific method is ultimately a metaphysical extension of our intuitions about inductive reasoning and causality. There is no scientific proof that the scientific method is valid. ("Our intuitions" is why I said metaphysics is tautologically the domain of humans. This is essentially Kant's philosophical legacy: science will describe what it does, but humans intuitively understand reality in ways that defy noncircular scientific description, and metaphysics must be invoked to have a rational and grounded discussion about these intuitions.)
I asked for proof of claims and I just get "it absolutely does" and a bunch more assertions, and word salad like "the validity of the scientific method is ultimately a metaphysical extension of our intuitions about inductive reasoning and causality" -- there's nothing "metaphysical" about it ... the scientific method is a disciplined application of an effective process of discovery. And '"Our intuitions" is why I said metaphysics is tautologically the domain of humans' is more word salad -- "tautologically" has no business in that sentence, and none of the rest of it makes any sense either. Humans have multiple domains, not just "the" domain. Metaphysics is a field of study that non humans capable of studying can also study. Metaphysical facts govern everything, not just humans. etc. I consider this sort of junk to border on bad faith ... it certainly isn't of any use to me, and I have no interest in engaging with it.
> There is no scientific proof that the scientific method is valid.
The scientific method is provably effective in a lawful world. That the scientific method isn't provably effective is because the world is not provably lawful ... it's logically possible for the "laws" of physics--which are simply regularities that we have discovered--to suddenly change, oscillate, be random, etc. But as long as they don't the scientific method works ... and we can't do better. (Not in this world, anyway ... in some other world there might be oracles (aka gods or bibles) that always have the right answer and we could simply query them. Of course, such oracles are also not provably correct.)
There is no single "scientific method" to speak of. Your epistemic position is ultimately just as faith based as you claim faith in God etc. is, the sciences (plural) just have a set of operations which, as you point out, seem to have practical utility and seem to be better than certain alternatives for building up shared epistemic structure.
The attitude of "we can't do better" is precisely the kind of attitude that would have hampered the creation of various sciences and their methods in the first place, and the production of scientific thought is often not as pure or logically consistent as all the methodological purists or Popperians seem to believe it is. Feyerabend, Quine, Von Foerster, Dataon and Gallison and several others have made this pretty clear and make the argument pretty forcefully in my opinion.
All sciences carry an ontology and value system along with them. Religion is also a rich and highly effective epistemic structure when your underlying ontological assumptions, values, and goals differ from those established and implicit in the scientific (predominantly utilitarian) Western enlightenment value system. Science is not able to found itself on some irrefutable bedrock "truth" correspondence any more than religion is. There is no basis by which we can actually solidify empiricism as somehow more privileged and more capital T true if we admit the possibility of human error.
Agreed. I’ll also make an observation based on this thread: the idea of computation as a fundamental law is most believable (and desirable) to people who like computers and want to reduce reality to a computer.
The belief is like a cheat code: somehow our tinkering and 9-5 job somehow grants us, the computer nerds, a deep understanding of life, the universe and everything. Deeper than scientists, philosophers, etc. It’s epistemic catnip and pretty tasty at that!
A related question might be, what's the difference between mathematical (Godel), computational (Turing,) and physical (Yang-Mills) undecideabilty/computability?
For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
I loved his Algorithms course on Coursera which I did during the brief moment Stanford MOOCs were all free. So useful for a non-CS grad doing any kind of algorithmic programming.
Those were good days.
Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection).
Our world appeared computable, but it isn't, even if P=NP.
It can be the case that both:
- The physics of the universe can be completely modeled as computation, and
- It's possible to pose undecidable problems about the way the universe unfolds
This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".
Of course, if our universe is undecidable it must be the case that computable processes can be executed within it, and it might be the case that all of the processes that are ever executed within it are computable... but it might be that some of the processes that are executed are not computable... because the machine may.. or may not?
I think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
There's no way to empirically spot an uncomputable process, since it would require infinitely-many observations.
For example, if aliens claim their machine solves the halting problem, we could test it on millions of inputs whose halting/not-halting behaviour we already know; but even if it works for all of them, there's no way to know that it works for all inputs. For all we know, it might be a huge lookup table which happens to cover all of those inputs we tried.
No, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.
Quantum mechanics is intrinsically probabilistic.
A key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infinite mass (the lattice), bespoke local interactions etc. Problems standing in the way of physics decidability are typically chaos, far from equilibrium mechanics, elementary SNR considerations and so forth, not problems of logic.
In physics we don't talk about decidability, but solvability.
>Recently it's been shown that there are real, physical processes which are undecidable
I want to push back a bit on this claim along two dimensions.
Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purely physical question about a trajectory (does this electron ever reach a certain target), yet answering it for the whole family of such machines is literally the halting problem, so there's a physical process that's undecidable.
Your examples about physical processes being undecidable are all basically just this... there examples of using reflections of light, or the flow of liquid, etc... and demonstrating that these physical processes in principle are sufficient to model a universal Turing machine.
And while it's fascinating that certain things you may not have expected can be used to model computation, it's misleading, or rather it's too strong of a claim to believe that there exist actual/real physical processes whose outcomes are undecidable. That's a subtle but very common misinterpretation of what undecidability is.
Undecidability, whether in physics or computer science, only applies to the infinitely broad class of a problem as a whole, it never applies to a specific instance of a problem. So it can never be the case that there's a certain configuration of reflections for which it's undecidable whether a ray of light reaches a target. Nor can it be the case that for a specific lattice of atoms, it's undecidable whether it has a spectral gap or not. It can only be the case that for the problem as a whole where the parameter space is entirely unbounded, there is no single algorithm that can decide if a ray of light reaches a specific target for all possible arbitrary (and infinitely many) configurations. Once you fix a specific system, then the undecidability goes away.
Not claiming that you are necessarily making this misconception, but I often see people misinterpret undecidability to mean that there exists a specific problem, like with specific inputs, where it's somehow impossible to know what the answer will be. Undecidability always requires an infinite family of instances, and it's a statement about the nonexistence of a single algorithm that correctly answers every instance in that family. It says nothing about any particular instance being unknowable/undecidable.
If I am wrong, please pardon. I suspect I am. But was this comment edited by Claude? I ask specifically because it is well written, substantive, all which is expected here, but the "push back" part, to me, must be a) an artifact of Claude, either by osmotic assimilation (Which is happening to many innocent users) or b) Claude itself.
Feel free to flag this comment if I get an answer. I do want to know.
No Claude was not involved in any way in me writing it, and honestly it's kind of getting depressing how many comments are constantly questioning peoples use of LLMs.
Yeah, that's why I invited the flag. But do not overlook how fucking depressing the endless LLM generated comments actually are too.
My apologies, and I do appreciate your reply.
Just a heads up, "I want to push back on" is an idiom Claude frequently uses.
It is depressing though, writing feels like it's in part becoming a game of outpacing the latest LLM's idiosyncrasies so we can signal authenticity, which perversely, is achieved through using an LLM enough so that you can become familiar with its flavor of communication.
This is what makes me sad about the AI age; many articles now have the same phrasing, the same analogies, the same quips, structure, the same wording; once you start to see it there's no going back.
I actually laughed quite a lot to begin with, GPT models saying things like "...might look like P, but is NP wearing a hat and a lab coat..." and "...is a haunted house disguised as a git repository..."; but alas when you've heard them a million times everywhere it really starts to bite.
The other day, while reading, my AI-dar triggered on some typical claudisms, but then I remembered I was reading from a paper book that was printed in 1997...
Unsettling. I hereby commit to self doubt on this matter exclusively. I will leave this fight to others.
What was the book in 1997? That's about the time of my first UAP sighting.
I may have been making this claim, I need to think about this for a while and re read what you have written.
This is very helpful though, thank you.
I may be misremembering Godel's proof or misunderstanding your last paragraph, but I thought Godel's proof actually presented a specific undecidable statement. The hope then was that somehow undecidable statements could be cordoned off from decidable statements, and Turing's result showed that that wasn't possible. Perhaps that's what you mean by "the nonexistence of a single algorithm that correctly answers every instance in that family"?
It's a gap between physics and mathematics. Undecidable statements exist mathematically, but don't exist physically: mathematics and physics have different concepts of existence. Ironically, even mathematical universe hypothesis deliberately limits mathematics-as-physics to specifically resemble physics of a spontaneous material world, and this limitation is just an axiom.
There's no such thing as an undecidable statement. A single statement can't be undecidable. Undecidability is a property of a class of statements.
For example, you can ask whether a Java program, run with infinite memory, will eventually halt. For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no". Might be hard to figure out which is the correct algorithm, but the Java program is fixed so the algorithm is definitely one of the two.
However, there is no algorithm which can take an arbitrary Java program as input and determine whether it will halt. It's about the class of all possible programs.
That's a different meaning of the word "undecidable". You're talking about undecidable problems [1]. The meaning in Gödel's incompleteness theorem is different and is a synonym with independent [2].
[1] https://en.wikipedia.org/wiki/Undecidable_problem
[2] https://en.wikipedia.org/wiki/Independence_(mathematical_log...
> For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no".
This isn't true.
In general, if a program hasn't halted yet you don't know if it will.
In particular, consider the Collatz conjecture. You can't even tell if your Java implementation of it will halt for a particular input, until it does.
https://en.wikipedia.org/wiki/Collatz_conjecture
And yet there is a correct algorithm — it's either the const yes algorithm or the const no algorithm.
We don't _know_ which algorithm it is, but that's not relevant to the definition of undecidability, which only requires that the algorithm exist.
Cheers, I had missed the nuance.
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 millennium problem, that still also lingers, so we don't have a controllable notion of naked/absolute undecidability for physical phenomena or for arbitrary assertions unbound by explicit logic rules in general.
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.
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 state of an molecule is a physically relevant quantity, and in theory any molecule alone should lose energy and attain it's ground state, even if finding the ground state electronic configuration is undecidable. But in reality, no molecule is ever truly isolated and so would never actually be guaranteed to enter it's ground state (or if it were truly isolated, it would not be observed at all rendering the question moot)
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 computation is not super-Turing: anything you could solve with a quantum Turing machine you could also solve with a classical Turing machine, albeit sometimes a lot slower. We know how to emulate quantum systems in classical systems.
Quantum computers can be simulated on classical computers, but it takes exponential time (completely impractical).
> … so there's a physical process that's undecidable.
No, since you cannot physically build a Turing Machine. A Turing machine requires infinite tape. Any physically realizable machine doesn’t have that, so has finite states, so is decidable: enumerate the states in finite time - it halts or repeats, so all programs on a finite state machine are decidable.
Your example is not an undecudable physical process.
Godel things also don’t apply: Godel theorems are about proof of this or that from within the same system. In logic one can prove such things from an outside system, then construct towers, avoiding Godel theorems. Godel theorems also require a model of integers including multiplication (without multiplication, such systems were proven complete and decidable). However the universe does not contain a model of integers, as the physical universe is not unbounded: relativity places a finite limit in spacetime on what can interact.
Mixing math as reality fails at these requirements.
How to build a Turing machine to tell which one of ten atoms of a radioactive element decays next?
That would be a quantum Turing Machine as radioactivity is a quantum process.
How would that work as current understanding from quantum theory is that we cannot predict which atom decays next? Is there a quantum algorithm that can do that?
> up to the point that many computer scientists now seem to equate computation with the functioning of the universe.
Do you think that's a kind of tunnel vision? If the only thing you focus on is computation, you'll probably end up seeing computation everywhere - it became a way of seeing the world.
It is a common accusation. There's a somewhat famous quote I've seen a few times:
"It's interesting to look back through history on this one. Each age has its pinnacle of technology, and each age uses that technology as a metaphor for nature, for the universe. In ancient Greece, the technological marvels were musical instruments and the ruler and compass. The Greek philosophers tried to build an entire cosmology from number, harmony, proportion, form, and so on — from mathematics, basically. Remember the music of the spheres? The Pythagoreans believed that nature was a manifestation of rational mathematics. Later on the pinnacle of technology was the clockwork. Newton wanted a clockwork universe, the entire universe as a gigantic clockwork mechanism, with all the parts interlocking and ticking over with infinite precision. Then in the 19th century along came steam power, and the universe was then depicted as an enormous heat engine, or thermodynamic machine, running down toward its heat death. Today the computer is the pinnacle of technology, so it's now fashionable to talk about nature as a computational process."
Which seems to source from https://www.edge.org/conversation/paul_davies-time-loops .
While "computer" may give us impressions of something with "a CPU" and "RAM" and "a disk drive", it does at least seem plausible that the universe as computation is a plausible base level, though. Unlike "the music of the spheres", which to the extent that it made predictions of the world, it got them wrong in the most basic way, viewing it through a lens of computation allows us to put some quite subtle and interesting limits on things. "Computation" is a pretty flexible substrate; it is difficult to imagine how the proposition "the universe is a computation and subject to the limitations thereto" could be falsified, and if it could, it is difficult to imagine how we would be able to know it was so falsified. Nevertheless the math of computation allows us to say non-trivial things about the universe as a result; it is not a vacuous generalization, though it is certainly a loose one... being able to say yet more concrete things about the nature of the computation, such as "this is exactly how gravity works", has quite a bit more utility.
The universe as a computer/computation has been explored by many (e.g., see John Wheeler and Seth Lloyd). However, the laws of physics give us a lot more predictions, so their explanatory power tend to be greater. For example, the nature of space and time.
Undecidability is a problem of answer-extraction from a process, it doesn’t preclude the process from executing deterministically. The universe could well be the live execution of a deterministic, even basic algorithm, with all kinds of questions about its execution being undecidable.
One sentence I heard somewhere wraps up the totality of computing:
"If Mathematics is the 'what', Computer Science is the 'how'".
This applies to each and everything.
If two people agreed on that statement, its entirely unclear if they agree with each other and if they found something profound in the first place.
The imo much more foundational relationship not everybody is aware of is https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
> Recently it's been shown that there are real, physical processes which are undecidable
According to the currently known laws of physics. Which we know are incomplete/incorrect in several places.
The infinite lattice doesn't represent a "real" physical processes, it's just mathematical technique for closing a (fundamentally) quantized combinatorial sum over millions of interacting elements. The gap problem exists in the limit. For real systems the spectrum can be measured (in principle) by probing the ground state. The computational paradigm is incredibly general but only within what's apparently a pretty atypical thermodynamic regime (the ordered universe).
In this case quantum thermo.
Undecidable isn't uncomputable.
"Computable" can mean probabilistic, and classical computers can function over probability distributions just fine.
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 running sufficiently advanced algorithms that we cant reverse engineer. If so, quantum mechanics is computable even if we cant compute it.
(Particles being TMs doesnt mean they are FAs with an infinite tape, but that they are computationally equivalent to TMs.)
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 like how every time a new technology is invented and becomes big, people start to think it explains everything. Like how in the 16th/17th centuries some people thought the universe was a big clock. Or how in the 19th centuries people thought the universe was like a big steam engine. Or now we think the universe is a big computer.
Not saying this is wrong or that I've watched all of the lectures above or anything, but it's just funny to imagine that aliens might look at us the same way we could look at a monkey society saying that the universe is like a big one of those rocks they use to smash nuts open.
Computation and information really does seem universal though, so this is just a funny thought and not serious commentary.
It's just Pythagoreanism.
It strikes me that this is a kind of an escalating pattern though I don't suppose it has to be. Clock -> Steam Engine -> Computer -> AGI -> Skynet -> Throw rocks at robots -> Judgement Day. Also very not serious commentary.
On I suppose a slightly more serious note it also strikes me that there will eventually, probably, maybe be _something_ that fits best; though we are not promised to find it. And it seems wild to say that about a model because all models are fundamentally wrong, but they are usually group-able by less-wrongness, so probably fundamentally feasible.
Couldn’t all of them be right, though? In the sense that every technology associated with the functioning of the universe had a systemic, spatiotemporal and evolutive dynamic, which appears to be the sensible facets of the universe’s behavior? In that sense computation is no different, just has more primacy. It gives me some Hofstadter vibes, meaning whatever complex thing we produce within the universe is hopelessly bound to be analogous with it.
Yes, these are all our attempts at explaining the nature of reality. A kind of reaching into the unknown. A desire to understand the universe and our place in it.
Here is a brief history of computability I wrote as a blog a few months ago, https://deeplp.com/blogs/f/the-birth-of-computability-theory. Hope it's helpful to the conversation.
From my naive pov: Related to computation is the concept of state (I know, functional languages can get away without it, sort of). I always wondered how the universe “knows” the mass of the sun. If there are some underlying functions/computations “running” in the background to keep planets moving and so on, and if the mass of planets is a key element in such computations… then either: the mass is calculated “on the fly” every time (seems expensive) or it’s a variable (how is it updated? Where is it “stored”?)
The somewhat abbreviated answer is that the "state" is formalized into the concept of fields. All the physical properties we can observe are from coupling with the relevant fields. The speed at which changes can propagate in fields is C, hence the speed of light being the same value.
As far as I understand it, the storage is the space, or rather, spacetime emerges from a system's informational capacity and the degrees of freedom along which information can spread. On the balance all information is retained but undergoes various phase transitions (the 'computations').
Functional programming very much has states. But you’re describing the transitions instead of the states directly. What it does is removing the hidden states and effects and makes them typed, explicit and contained
I think it’s easier to conceive of it like this: Each point in spacetime IS storage. Storage can be queried by interacting with it (in a variety of ways), though the process of querying affects the value not only of the querier, but also the queried, which may have side-effects as well. The interaction itself is the computation.
A simple example for the computation: It’s like placing boxes next to each other. Yes I could say 1 box + 3 boxes = 4 boxes, via explicit calculation. I could also simply place 1 box next to three boxes, and without having to explicitly calculate, by nature of the interaction, the result (4 boxes) has been produced
There is no background computation or storage. The universe IS computation and storage. Each spacetime quanta IS storage, and each interaction IS computation.
Spacetime isn't quantized as far as we know. We don't know since we don't have quantum gravity or ability to probe Planck scale. Quantum fields are continuous, it is excitations in the field, particles, that are quantized.
Ah, I thought we didn’t have strong evidence either way. Regardless, I shouldn’t have stated spacetime quanta so matter-of-factly. I just have an easier time conceptualizing if I treat everything like hypervoxels and that leaked in.
The theory of general relativity answers this exact question. It has been tested experimentally and has been found to be correct in the classical regime. By correct I mean that the experimental data agrees with theoretical prediction.
From the site's "About" section:
> "Ergo is a nonprofit that publishes long-form philosophical lecture courses with leading scholars. Everything we publish is freely available, without ads or paywalls."
I know what to do this weekend if it rains!
Would like to think we human are better than what is implied by the course in that we would not mistaken our model of reality as reality itself.
Discrete math and Algorithms were two of my favorite college classes. They were really the only part of computer science that was mind blowing. The rest was software engineering, which was transparently "possible". Like, yes, big programs and OSs and numerical models exist, and yes I will graduate and work with them and add to them, someday, yeah sure.
But decidabilty, Godel's theorm, busy beaver numbers, etc... those were unexpected and worth the price of admission.
Thanks Prof Hadas, you made it fun to have my mind blown.
Theoretical computer science is where it's at.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.
This is a brilliant explanation thank you.
It can be solved if the memory is bounded. But unbounded memory comes with undecidable problems.
This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.
Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.
There remain undecidable problems even with finite memory/state space.
Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:
Emptiness: Does an LBA reject all possible inputs? Universality: Does an LBA accept all possible inputs over its alphabet? Equivalent: Do two LBA accept the same language? Finiteness: Does an LBA accept a finite number of strings.
Related: the Busy Beaver problem https://news.ycombinator.com/item?id=40857041
Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/
I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?
If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.
Ahhh thank you it's effectively the known-vs-unknown space;
- How long does it take to get from A to B? => Easy if you know where A and B are, and what mode of transport you're taking to get there.
- How long does it take to get from A to _somewhere_ => As long as it takes!!
For the finite case, the more relevant question is, can you predict whether or not the computation will halt in less time than 1. executing the algorithm and 2. checking whether or not the algorithm ever loops?
Bear in mind checking whether or not the algorithm ever loops means taking the full state of the system and checking against a database of all previous states of the system. Bear in mind that the Atari 2600, and its whopping 128 bytes of RAM, has with that amount of RAM more states than there are planck volumes * planck time intervals in the known universe... by over sixty orders of magnitude. And every three additional bits you add to the RAM of the system your are looking at adds an order of magnitude (minus a bit) to that, so, nearly 3 orders of magnitude more states per byte... not per megabyte or gigabyte, per byte. Call it 2 orders of magnitude per byte if you want to be conservative.
It can be solved, if by nothing else simply by running it, in the mathematical sense. In the practical sense it's not even close. That's why we use the Turing machine analysis... technically it's an approximation because we don't actually have real Turing machines. However the size of the finite state machines we have is such that it is far more productive to simply say "the halting problem is unsolvable" than to argue about how many orders of magnitude of orders of magnitude of resources it takes to solve the question of whether or a given program terminates.
Thank you for your insightful answer, in reduction; "Don't fight a god, you won't win, and you'll definitely die in the process!"
The approach you describe though is brute force. I don't think (if there even is an answer to this problem) that it can be brute forced; that's where you run into the limits of hardware/computation/energy and start talking about timeframes which exceed the life of the universe.
I think brute force might be a useful tool in places to validate results, but if there _is_ an answer to this problem it's purely mathematical.
Apologies for sounding both excited and naive; these sorts of challenges make me happy in strange ways that no other thing does!
There is no general solution other than brute force. That's not a terribly difficult extension of the halting problem, it just takes more paperwork to deal with the edge cases, but you'll get to that result. The same basic technique works: Your supposed solution to the problem is itself some finite program, and you can feed it the "I halt only if I don't halt" problem too. The difference is that brute force is a solution, because now instead of an infinite sequence of programs you have a bounded set of programs. So whatever concrete "I halt only if I don't halt" you pass to someone within the specified limits, there is definitely some answer, but your technique won't be able to tell what it is short of just running it.
For the same reason the halting problem doesn't even have a good heuristic, neither does this. Unpredictable chaos is not an exceptional case, it is the exponentially-normal case. You have to go the other way, and construct programs deliberately designed to have the ability to tell if they halt. The term for that if you want to learn more about it is "non-Turing complete programming language", sometimes called a "sub-Turing" programming language: https://increment.com/programming-languages/turing-incomplet...
You can read that as "this is how hard it is to construct code that we can make execution guarantees about". That focuses on code that is deliberately constructed to be finite in scope and may be something that can be strictly bounded in memory use or time or both. You'll note if you spend any time working with them how hard they are to work with. That's a reflection of the limits of generalizing any such proofs of time or space of a given program.
If there is a general algorithm that does what you think, we don't even have a clue what it would look like. And we have a lot of clues there can't be any such thing.
Thanks for the link, great read. I think I get you here; in the context of a DSL where it's impossible to travel more instructions than X, suddenly you don't have a halting problem anymore as you've artificially limited that language's ability to travel beyond a known/fixed set of states.
The second you wield a language which has constructs like Haskell, where in theory you can iterate over an infinite list of items (thinking about it even any language where for i in input_var is possible); the halting problem hits you in the face like a brick.
Its almost a chicken and the egg problem, where you can't know how long it will run for/whether it will halt without already knowing the answer, but if you knew the answer, you wouldn't need the program to find it.
My head is spinning.
You might enjoy the book Escher Gödel Bach, the Eternal Golden Braid by Douglas Hofstadter, which will open up the world, power, and "danger" of proofs using contradiction to you.
Bonne lecture !
Thank you for the suggestions, I look forward to reading!
The standard argument is:
Assume H(P,i) to be a program that tells you whether the program P will halt on input i. Returns true if it halts and false if it doesn't.
Define a new program G(x) that halts if x does not halt on itself as input and loops forever if x halts on itself as input:
Does G(G) halt?
If G(G) halts then H(G,G) is true so we end up in the infinite loop, a contradiction. If G(G) does not halt then it returns without looping, also a contradiction.
So our halting oracle H does not exist, so there can not be a function that tells you whether another function will halt on itself as input, so there can not be a function that tells you in the general case whether some other computation will halt, QED.
I really do think matter wants to be sentient, being sentient is natural. Why i think that exactly, i'm not sure why, it just seems intuitive.
Your intuition could also be dead wrong.
The universe is a giant transformer.
Attention is all we need.
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 'CRUD app,' we immediately think of a specific pattern. In the same way, once you adopt a 'form,' the constraints that come with that form progressively expand the state space. In that sense, it feels like both discovery and invention.
Famous mathematicians and scientists often distinguish between model and reality, yet we tend to mistake the model's shape for reality itself. People like John Wheeler and Stephen Wolfram argue that computation is a fundamental property of the universe. But can we really say that when we downcast reality to fit human cognition, losing information in the process, and then upcast it back, the information is fully restored? I always find this point difficult.
Landauer's principle says that abstract logical operations, information erasure, necessarily increase physical entropy. That shows there's a thermodynamic cost to physically implemented information processing. But I don't think that proves computation is fundamental.
Whether it's computation or geometry, they're all abstract formalisms created by humans. But when we actually measure things, they're subject to physical laws. Still, whether that makes them fundamental is a difficult question. I think these are just results of the process where humans name phenomena and constrain them. I don't think they're the cause.
You can define computation broadly enough, as 'a process where a state changes to another state according to rules,' to make almost everything look like computation. But being able to explain something with computation and claiming that computation is fundamental are different things, aren't they?
Meaning exists within the structures and constraints of human-made formalisms. We artificially lower cognitive complexity and translate things into human language. Whether that's fundamental, I'm not sure.
Maybe I'm a reductionist. Plenty of intellectually brilliant scholars make those claims, but people like me, with slower minds, end up thinking these kinds of stupid thoughts. I wish I could organize my own thoughts bette
Ahhh this is fantastic thank you; it _is_ hard to reconcile whether problems come with the original topic or whether they are introduced by the abstraction that we _need_ to make in order to quantify a thing/explain it to ourselves and others.
Regarding the downcast/upcast; I think it _can_ be possible to do this successfully;
> I have a glass, I throw it at a hard surface. What will happen? Well (duh) the glass will (most likely) break.
This hypothesis completely ignores nearly 100% of all relevant physics and the laws surrounding the problem; the arrangement of air molecules, the arrangement of the molecules in the glass, the physical forces governing me, it reduces the entire equation down to some really basic napkin physics.
But; does the outcome work? Has my interpretation of the universe and its physics actually predicted what will happen?
Probably a stupid example, but I think that a lossy picture of the universe can still yield a correct answer.
I can't physically run a simulation of the entire universe in my brain, as my brain is part of that same universe. Lossy representations/models are a necessity in the thinking-ham bound world in which we exist.
You're right. But consider this: the geocentric model perfectly predicted planetary positions for centuries, and it was certainly useful. But could we say it was the essence of the universe? In the end, it's a useful model within limited cognition, but whether it's 'fundamental' is a separate question.
I think the key is that different phenomena require different approaches, and even if you interpret a single phenomenon through multiple mental models, none of them necessarily captures its essence. Ultimately, it's about which mental model is shared by a 'group'—not about what's fundamentally true.
We currently share the model of computation, but whether that makes it fundamental is a different story.
As a programmer, I'd put it this way: no matter how well an API describes the backend, the backend itself is not the API.
Here, the API is human knowledge, and the backend is the world
You sound like you believe in philosophical skepticism. Tell me: can a map ever properly describe the territory? When would a map properly describe the territory? (Can a theory ever properly describe reality? What does a theory need to properly describe reality?)
We know that universal Turing machines can emulate other Turing machines. Weirdos like Wolfram believe that a universal Turing machine can emulate reality. In a quick skim of this lecture series, the presenter doesn't talk about that, rather he just calls computation a scientific principal (universal and fundamental in the sense of physical laws, not fundamental in the sense of emulating reality on a computer).
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 intuitive notion. For example, some argued it was too broad because traditionally knowing that an algorithm eventually terminates was one of the requirements (to some) for something to be a legitimate algorithm. Why? Because the idea is rooted in human practical concerns and human understanding. Depending on what one cares about, one could actually reject the Turing formalization of algorithm on grounds of the class containing non-convergent (partial) functions.
All this is to say that "computation" is very much a human invention and little more than a formal model of human behaviors (we want to manipulate things algebraically). Elevating it to some objective substance of the universe is just doing 17th/18th century philosophical Idealism wrapped in new clothes.
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.
Related:
Ergo: Long Form Philosophy Lectures
https://news.ycombinator.com/item?id=48840497
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
I saw the title and assumed an article by Wolfram. But it's by Tim Roughgarden who I know from algorithmic game theory. Anyway, I'll register my membership in the "it's more fundamental than that" camp.
Computation is in the eye of the beholder
I'd have to look deeper into his views, but I've already come across what seem like similar claims that try to attribute computation to the laws of physics or to matter in general or whatever.
However, these rest on category errors. Consider two characterizations of computation:
1. A mental process constituted by logical and intentional acts.
2. A mathematical model or formalism (or a set of formally equivalent formalisms).
In the case of (1), intentionality rules out computation as an extra-mental phenomenon. Things in the world aren't about something else; they just are what they are. But computation as a mental act is about something else. To claim otherwise would be like claiming deduction is a broad feature of reality, which is effectively some kind of panpsychism.
In the case of (2), if it's a mathematical model, then either by definition it doesn't exist outside the mind as such, or it must be instantiated in some objective manner. The trouble with finding instantiations is that it's not clear what constitutes an instantiation. Can you find correspondences? Sure. In fact, our physical computing machines correspond to these models in some way. But instantiation is more than mere correspondence, and this becomes even more the case when you consider that the lambda calculus corresponds to the Turing machine.
Another problem is that even mathematical models of computation cannot be said to encode mathematical operations as such. Is a Turing machine moving symbols around on an abstract tape actually adding two numbers? I would say that it is merely simulating the addition by producing results that afford that kind of interpretation.