On Tue, Jan 14, 2025 at 4:56 AM PGC <multiplecit...@gmail.com> wrote:
> > > On Monday, January 13, 2025 at 11:58:38 PM UTC+1 Jesse Mazer wrote: > > > Doesn't Godel's theorem only apply to systems whose output can be mapped > to judgments about the truth-value of propositions in first-order > arithmetic? A cellular automaton would seem to have "evolving quantities > and/or qualities through numerical or some other equivalent formalism's > means", but Godel's theorem places no limitations on our ability to compute > the behavior of the cellular automaton for N time-increments, for any > finite value of N, so I would think Godel's theorem would likewise place no > limitations on our ability to compute the physical evolution of the > universe's state for any finite time interval. For some cellular automata > it may be possible to set up the initial state so that the question of > whether some theorem is ever proved true or false by the Peano axioms (or > other axioms for arithmetic) is equivalent to a question about whether the > automaton ever arrives at a certain configuration of cells, so Godel's > theorem may imply limits on our ability to answer such questions, but this > is a question about whether something happens in an infinite time period. I > assume there are similar limitations on our ability to determine whether > certain physical states will ever occur in an infinite future > (straightforwardly if we build a physical machine that derives theorems > from the Peano axioms, or a machine that derives conclusions about whether > various Turing programs halt), but most of what physicists do is concerned > with predictions over finite time intervals, I don't see how Godel's > theorem would pose any fundamental obstacles to doing that. > > Jesse > > > Gödel’s first incompleteness theorem states that any sufficiently strong > formal system (capable of arithmetic) contains statements that are > undecidable—neither provable nor disprovable within that system. The second > theorem says such a system cannot prove its own consistency from its own > axioms. These are statements about provability in formal theories. They are > not directly about whether you can compute a finite number of steps in a > system like a cellular automaton. > > You can absolutely compute, step by step, the evolving states of a > (finite) cellular automaton for N time steps, and Gödel’s theorems do not > say you can’t. They say something deeper: if your formal axioms are strong > enough to represent integer arithmetic (like Peano Arithmetic or any > Turing-complete formulation), there will be statements expressible within > that framework which it cannot resolve. That’s a statement about what can > or cannot be proven within the system, not about whether a machine can run > a simulation for some finite time. > > You also assume that Gödel’s incompleteness only restricts what can happen > in an “infinite time” scenario. For example: “Well, sure, there might be > some question about whether a certain configuration arises eventually, but > for finite intervals we have no Gödel-limited obstacles.” This misreads > Gödel: Gödel’s first theorem does not hinge on infinite time steps; it is > about the intrinsic logical structure of the formal system. Even for > trivial seeming statements involving finite objects (e.g., “this specific > integer has property P”), the theorem shows there can be statements that > the system cannot prove or disprove. It’s not that you can’t “run the > simulation long enough,” but rather that the theory itself cannot settle > certain propositions at all. > I think you are misunderstanding my claim, I didn't say that Godel's theorem itself is directly stated in terms of number of time steps of some computation, only that if we look for applications of Godel to computational dynamical systems like cellular automata or computable physics (and Deutsch's result on p. 11-13 at https://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf suggests the evolution of any finite quantum system is computable), the only applications will be to questions about whether the dynamical system ever reaches a certain state in an unlimited time. You said yourself that Godel's theorem places no limits on our ability to compute the behavior of such a system for N time steps given any specific value of N, so I don't think you disagree with this. If you do disagree, i.e. you think there is a way of applying Godel's theorem to a finite computable system that places limits on our ability to deduce something about its behavior over a finite series of time steps, please give an example. > > Yes, questions about infinite evolution (like “does the automaton ever > reach configuration C at some unbounded time?”) can become unanswerable in > principle if they encode the halting problem or an arithmetic statement. > But Gödel’s point is more general: the existence of some undecidable > statements is guaranteed, quite apart from whether they manifest in an > infinite-time scenario or not. > It's general if we are restricting the discussion to Godel's notion of "formal systems" (as he did when stating the theorems), which in modern terms is equivalent to the notion of a computational system for deciding the truth value of various possible propositions in first-order arithmetic. If you don't restrict things to Turing-equivalent systems, Godel's theorem may not imply any undecidable statements, for example all WFFs of first-order arithmetic are decidable if you introduce an uncomputable inference rule called the ω-rule, see https://philosophy.stackexchange.com/a/90311/10780 where I talked about this. And given the understanding that the theorem is specifically about computational systems, we can think in terms of a program that takes any given set of axioms, like the Peano axioms, and methodically finds all the possible propositions that can be derived from them; then for any specific WFF, one can modify the program so it will halt if it ever derives either the WFF or its negation. In that case, the claim that there are certain statements that are undecidable is equivalent to the claim that this program will never halt on such a statement, meaning that when translated into these terms it does become another "will something ever happen in an infinite time" question, even if that wasn't Godel's original formulation. > A final misconception is that the existence of straightforward computable > truths (e.g., “2 + 2 = 4” or “state s follows from state s_0 after N > steps”) somehow negates Gödel’s theorems. > > Again I think you are misunderstanding me, I certainly never intended to suggest the existence of such truths "negates" Godel's theorem--what comment of mine suggested that interpretation to you? > Therefore, you seem to mix up “we can compute local steps easily” with > “therefore there’s no deeper limit on provability.” A huge jump. > Incompleteness is about the existence of certain statements the theory > cannot decide at all—not about whether we can check how a system evolves > over N steps. > I didn't say "there's no deeper limit on provability", I explicitly said there *would* be a limit on provability about certain infinite time questions, I just made the point that most of the problems physicists look at in practice are only about dynamical behavior over finite time. (And when they occasionally do ask questions about what will happen in infinite time they are usually very specialized questions like the long-term fate of the universe in cosmology, not attempting to answer the very general question of whether any arbitrary configuration of matter/energy will occur in an infinite time.) > > It can help to see Gödel’s message as a reminder that once you allow > arithmetic (or an equivalent notion of proof) into your theoretical > framework, you automatically inherit logical “gaps” you cannot fill from > within that framework. Consequently, every time a new observation or > phenomenon appears to contradicts some current theory of the universe in > the news feeds—be it quantum mechanical or cosmological—standard practice > is to say, “We’ll just extend or refine the system,” hoping that, in > principle, you can patch all holes. From a Gödelian perspective, however, > such hopes are naive, even if made by top researchers constantly; you > cannot achieve a neat, airtight completeness once you’re in the realm of > arithmetic-level expressiveness. Each new theory you devise may bear > fruit—often very real, practical fruit—and it may rectify certain > anomalies, but it cannot be the final word, because no single formal system > can be both consistent and complete about everything you can say in it. > But it places no limits on our ability to devise a final complete theory of *dynamics*, which is what physicists are mainly interested in when they look for a physical ToE; that's equivalent to knowing the local dynamical rules of a cellular automaton, which would certainly be possible for any intelligent beings that could exist within that system. The limit is just on what this dynamical theory would imply for answers to questions about whether some state occurs in an unlimited time. Jesse -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/everything-list/CAPCWU3%2BEXV-UetC6SNGCNSg7iczHLxjZqevbZOEB8%3DQ_JkMQFQ%40mail.gmail.com.
