# If the universe is finite does that nullify Godel's incompleteness, halting problem, and Church-Turing thesis?

I'm not well versed on these topics but they all seem to rely on infinity, mainly infinite recursion or infinite space of mathematics.

If there is no always "next" algorithm, the halting problem goes away for example doesn't it?

Is a finite universe enough to spell their doom?

Related: Can a finite system prove its own consistency?

• Comments are not for extended discussion; this conversation has been moved to chat. Oct 5, 2021 at 9:37
• What do you mean exactly by "finite"? Even in time? Oct 5, 2021 at 16:35
• @PabloH Finite in time is good. But I initially left it vague because I wanted to see if things without time or space could be included, like the Platonic realm. Would a limited number of Planotic objects change our theorems at all for example. Oct 5, 2021 at 16:45
• Well, that's just going to run head-long into the issue that plenty of mathematicians and philosophers doubt the existence of Platonic objects altogether, and so limiting them to a finite quantity poses no problem for people who already believe that said finite quantity is exactly zero. Oct 6, 2021 at 6:47
• @user253751: I think the idea is that for sufficiently large S, there is no such statement consistent(S) because writing it out would exceed all available storage in the universe. And therefore you don't have to reason about consistent(S) for this ultra-large S, or decide whether it is itself consistent. You need infinite space to have infinite nesting consistent(consistent(consistent(...(S)...))) Oct 6, 2021 at 17:25

First of all, this question presupposes that mathematics is limited to describing the physical universe. Even as finite beings in a finite universe we can still try to reason about hypothetical infinities, and develop an internally-consistent (if nothing else) theory of such. (In fact this is usually what I personally think of mathematics as doing.)

But let's grant that we're focusing on "physically realizable" mathematics (and are assuming that our universe is indeed finite in every reasonable sense). We now have to be careful to uniformly apply this assumption to our reasoning. So e.g. on the one hand there are only finitely many "physically realizable" computer programs, but on the other hand it is not clear anymore that an arbitrary finite set is "phsyically computable"! All we get for free are "halfway" results like "the physically-realizable halting problem is ideally computable." The end of this old answer of mine touches on this issue a bit as well - as long as we're careful to uniformly impose our finiteness restriction, things don't actually change as much as we might expect in terms of basic metamathematics.

That said, Godel's second incompleteness theorem does stand out to a certain extent. Moreso than the first incompleteness theorem, or than Turing's theorem that the halting problem is incomputable, the second incompleteness theorem is relatively sensitive to "ultrafinitistic flavor." Dan Willard has written quite a bit on theories which prove their own consistency (in an appropriate sense); see e.g. here.

• If I'm understanding you correctly, the titular 3 theorems would go away. But new theorems would probably emerge in their places potentially very similar to the originals or potentially much different? I also hoped not to restrict the topic to physicalism, but I guess by the halting and C-T I may have undermined that goal as they talk of computation and physics not just math. Oct 3, 2021 at 21:11
• @JKusin Actually, although physical ideas are often used to explain them, Godel's and Turing's theorems are entirely mathematical; in particular, Turing machines are purely mathematical constructions, although they are inspired by computation as a physical process. (Church/Turing is a different matter, and is explicitly about "idealized real-world computation" - whatever that means.) At this point I'm confused; if you don't want to restrict the topic to physicalism, then what is the relevance of "Is a finite universe enough to spell their doom?" Oct 4, 2021 at 0:57
• Comments are not for extended discussion; this conversation has been moved to chat. Oct 4, 2021 at 15:59
• If possible, I would ask that first comment be removed from chat and put back into the comments. I think it is key to the OP’s misunderstanding and gets to the heart of the issue (or Noah, maybe you can incorporate it into your answer). Oct 5, 2021 at 3:55

The halting problem doesn't go away, even in the modified variant that would exist in a finite universe. A modified halting problem that instead of "Does this ever halt?" asks "Does this halt before the end of the universe?" is simply decided by running the algorithm until the end of the universe and checking whether it has halted. The problem with that is it doesn't really help, because if you modify it this way, you also get in the situation that your halt-checker which is simply "run the program until the end of the universe, check if it halted" doesn't halt until the end of the universe for non-halting machines. So the modified halting problem still runs into the same situation that you can't build a halt-checker that always halts (even for your modified version of "halt").

Note that a non-halting machine doesn't need to do anything particularly crazy or infinite to not halt. This simple program never halts but uses only finite memory. This is of course easy to see as non-halting, but there are other simple programs where it remains unknown whether they halt.

x := 0
begin:
x := x + 1
if x > 1 :
x := 0
goto begin

• I'd add collatz as an example. It is almost as easy, and unknown if it halts.
– Yakk
Oct 4, 2021 at 20:08
• Not only is time a problem, but space becomes a problem as well. If you limit yourself to a finite tape, there may be turing machines which provable halt on that finite tape, but the proof of which takes up more space than available in your finite universe. So, you might even have an algorithm to prove the halting of machines of that type, but any machine you could build would run out of space when attempting to do so. Oct 4, 2021 at 22:28
• Reminds me when I objected to a spec that said "XX is a finite sequence of digits". Statements in specs are supposed to be testable, so I asked how you would test that infinite sequences are not accepted. To which I got the answer: no-one said the test had to run in finite time. Oct 5, 2021 at 15:30
• @MichaelKay: Preconditions in specs don't have to be testable. The system doesn't have to detect precondition violations. Its behavior isn't specified for inputs not meeting the specification, so it can do anything it wants. Now, if the spec was "XX is a sequence of digits, possibly infinite. Output true if XX is a finite sequence, false otherwise." then the problem is in the postcondition which does have to be testable. Oct 6, 2021 at 17:32

There appears to be a misunderstanding of the philosophical background within which mathematical theorems reside. Attempts to explain this philosophical background have been met with rebuttals that are indicative of strongly held beliefs which I believe are inconsistent with it, so I'll do my best as a non-philosopher to illustrate why most mathematicians take the position that theorems are no less "real" than anything physical, and that the lack of a physically infinite universe in no way inhibits the conduction of infinite mathematics.

Take a look at the nine Peano axioms that rigorously define the (unequivocally useful) natural numbers 0,1,2...

There is a finite amount of information contained in those axioms, which can be specified in a manner independent of language as done in Whitehead & Russel's Principia, and be given to a computer in such a way that it is able to produce proofs of theorems that result from the axioms completely autonomously, with extensive libraries of such automated theorems being constructed such as the Isabelle Archive of Formal Proofs. However, those axioms describe the infinite set of natural numbers (an "infinite thing"), and can be proven to be able to answer an infinite number of questions about the structure they describe.

The similarities with supposedly more physical objects are sufficient to make the distinction practically meaningless: in order to perceive any undisputedly real object, to verify its existence and sort it into a perceptual class, one serves it a series of queries (in the form of, for instance, touching it, looking at it, turning it over, etc.) whose results are inferred via fallible perception. The result of those queries are a better cognitive model of the object and its properties.

This is not distinguishable from the way in which a mathematician interacts with the natural numbers object: queries take the form of conjectures, and imperfect perception in the form of proofs which we constantly try, but never manage, to extricate from reductionist complaints about dependence on various prejudices.

On a more personally didactic note, I see mathematics as the study of abstraction itself, and that all cognitive models of reality are dependent upon abstractions used to piece them together from sensory perception. As such, mathematics of some kind and quality is a precursor to experiencing the universe in any way, and the academic discipline of mathematics is a twofold effort to make increasingly more complex and useful abstractions and to make explicit the dependencies and statements of all abstractions we use.

Those theorems of information and computation theory you directly asked about are independent of the finiteness of the universe in precisely this way. The questions they represent can be posed not only finitely but very compactly, and their resolution similarly is possible finitely. In summary, in a finite universe, it is still possible to ask and resolve questions about "infinite universes."

• > "As such, mathematics of some kind and quality is a precursor to experiencing the universe in any way" How can this be, didn't Hartley Field in Science Without Numbers show the opposite? I do value this answer because I guess I am coming from a strong prejudice you identified (or at least strong uncertainty to commitment). But I thought mine was a viewpoint serious philosophers entertained since I heard of Field Oct 4, 2021 at 16:35
• I am extraordinarily skeptical of anyone claiming to do "Science Without Numbers," but I must admit a lack of familiarity with that work. My argument was mathematics==abstraction, and that abstraction is a precursor to experiencing the universe. There's a reason linguistics is increasingly becoming a mathematical science...even if it were possible to do science without numbers, science without abstraction is positively inconceivable. The modern form of mathematics with emphasis on formality and quantitative reasoning is the mature form of that abstraction. Oct 4, 2021 at 18:12
• It's certainly no novel or unworthy viewpoint--just quite heterodox among working mathematicians and natural scientists, and I wanted to explain some of why. Oct 4, 2021 at 18:14

No. The consistency of mathematics (thus truth of its theorems) does not depend on the finiteness of the universe. No mathematical theorem takes, as a parameter or input, the volume of the universe, the total number of particles, the time before the universe collapses, etc.

Another way to think about it is to imagine we believe the universe is finite in extent, then we discover it actually goes on forever in some direction. Why would anything in mathematics, or anything regarding computability, change because of this new observation? In another scenario, we believe the universe will end in a Big Crunch scenario, then discover some form of dark energy will cause the universe to continue forever in a steady state. What mathematical theorem would change because of this observation? How would any model of computation change?

• Do you have any advice about how to regard (wiki): "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to "run forever". What trick/interpretation do you use to make sense of "run forever"? Just ignore it and call it poor phrasing? I'm fine with doing that if that's the consensus. Runs forever to me means something about the world. Ignoring it makes me gravitate toward fictionalism I must say. Oct 5, 2021 at 2:40
• That does not mean the problem depends on time or includes time as a parameter. The “run forever” part is a physical implication resulting from the fact that something cannot be determined, thus cannot be determined no matter how much time you are allotted. It’s an unnecessary cane for the intuition to lean on for a lay-person’s understanding. Oct 5, 2021 at 3:15
• @JKusin Let's take an analog to "run forever": When I say that there are infinitely many natural numbers, I mean that whenever I have any natural number n, I can always find a greater number n+1. This number is just as real as the number n. It doesn't matter how big n is, or whether there is enough paper in the universe to write it down. Similarly with computation: Given the state of a machine that has computed n steps of an algorithm, the state of the machine after n+1 steps is well defined, and it does not matter whether there's enough time in the universe to reach step n+1. Oct 5, 2021 at 9:25
• @JKusin would you be more comfortable with this phrasing?: "the halting problem is... whether the program will finish running." Here 'run forever' just means the opposite of 'finish running'. It is not a promise that the universe is unending. If the universe happens to end, and the program is still running, when the universe happens to end, the program still did not finish, it was interrupted. Oct 5, 2021 at 15:04
• @JKusin Then you not only have to throw out things like numbers, turing machines and truth itself, but also things like friendship, ownership, stocks, good/evil, power and freedom. All of these only exist because people agree that they exist, yet they shape our very lifes. Likewise, you can't build a car without crunching some numbers, and turing machines are required to answer questions like the halting problem. I understand that it may be difficult to accept the existence of abstract things, but the consequences of their existence are just as profound as the chair I sit upon. Oct 5, 2021 at 21:22

Well, first of all, all mathematical theorems are statements are claims about what follows from certain premises. A theorem's premises not being true in a particular situation does not mean "doom" for the theorem. For instance, the Pythagorean theorem states that "c^2=a^2+b^2" follows from a and b being legs of a right triangle and c being the hypotenuse. If you have a triangle that doesn't have any right angles, then c^2 will not be equal to a^2+b^2, but that doesn't mean the Pythagorean theorem has failed, it just means it doesn't apply. So it being impossible to actually build a computer with infinite memory doesn't make Turing's claims about such a machine false.

All the claims you mention are claims about mathematics, not about the physical world. Godel's incompleteness theorem is about mathematical system, and they are not dependent on the universe for their existence. We can still discuss infinity in mathematics even if the universe is finite. It is possible that the finite nature of the universe means that a physical instantiation of a Godel formula would be impossible, but that doesn't make the formula not exist in a mathematical sense.

Turing machines are often used as models of physical computers, but technically no physical machine is actually a Turing machine, because any physical computer has a finite limit on its memory. The halting problem deals what is theoretically possible with these theoretical Turing machines, not what is possible with actual physical machines. If someone says "I have a machine that, given any Turing machine that uses X memory or less, can tell you whether that machine halts", the halting problem does not bar that claim from being true. However, that machine would itself probably take more than X memory, so we would end up at "any machine that can be built in the universe can't solve the halting problem for every other machine that can be built in the universe". The central theme that one machine can't fully analyze every other machine remains intact.

• This brings me back to another reply who said if the universe ends these theorems still exist or are still valid. I see that as almost impossible to understand. If we all agree on some abstract premise, we don't immunitize it from the world's happenings. Is Peter Parker still Spiderman when the universe ends? No. Are there numbers when the universe ends? Likewise I don't see how. There must be some connection between "abstract" objects and the universe. Oct 5, 2021 at 20:39
• @JKusin Imagine a parallel universe. A really weird one. One where there are three electrical charges instead of two, and all other kinds of differences to our own. Imagine that there are intelligent things living in it. Imagine one of them says "I define that there is a bar foo. I define that for every bar g, there is another bar that is frobnier than g, with the condition that if g is frobnier than f, and f is frobnier than e, then g is also frobnier than e." And I would answer: "Cogratulations, you have just discovered the natural numbers!" Oct 5, 2021 at 21:32
• The point is, that the existence of natural numbers is independent of our universe. As such, we do not have to immunitize natural numbers from our universe, they have existed independently of it all along. Oct 5, 2021 at 21:35
• @cmaster-reinstatemonica Another possibility is they've made something with identical structure to "natural numbers". And we made nn's to mimic nature or organize our language to capture nature's structure. To me the benefit in this is that we don't need to posit abstract objects, but still enjoy math's uses. Oct 6, 2021 at 14:22
• To my mind, denying the existence of abstract things is what adds unnecessary ballast. It requires you to explain why you don't think something like love exists, and why you expect your significant other to open the door for you in the evening. That's the can of worms that you are needlessly opening when you argue against the existence of abstract things. I have much less problems. To me, every concept that can be defined (either by pointing and saying "chair!" or by words) is equally real. Oct 6, 2021 at 14:56

I doubt it.

The only thing you gain by making the universe finite is that now you can individually check all the things in the universe (proof by exhaustion). You can't do that in an infinite universe.

So let's suppose you find a way to prove by exhaustion that for all statements S in your universe U, consistent(S) is true. But then consistent(S) is a new statement. Is consistent(S) a statement in U? If not, then you've gone outside the universe to prove its consistency.

If consistent(S) is a statement in U, then either U is infinite or it somehow has loops. If consistent(S) is a statement in U, then we need to prove consistent(consistent(S)), and consistent(consistent(consistent(S))) and so on. That's an infinite number of statements. To fit them in a finite universe, one of them has to be the same as an earlier one - there has to be an S which is the same statement as consistent(consistent(consistent(...consistent(S)...))). That seems very unlikely.

• Does this mean mathematics/formal systems suggest the universe is infinite? Seems an odd direction to reason from about reality, but if that's the actual consensus I'll go with it. Oct 7, 2021 at 15:23
• @J Kusin: They don't. The universe is given to us empirically. Oct 7, 2021 at 15:27
• @MoziburUllah Do you disagree with user253751 's answer then? Oct 7, 2021 at 15:31
• @J Kusin: I wasn't replying to that user. I was replying to your assertion. Besides, as you see in the comment below the question, I think that your question was more mathematical than philosophical and belongs to Math.SE. Oct 7, 2021 at 15:38

These logic problems are limited within the mind, not the physical universe. Whether there even is a physical universe is irrelevant to the philosophical underpinnings of the problems.

Godel Incompleteness Theorems: whether you can prove everything within a single logical framework [answer: no]

Halting Problem: can you predict whether a program will end in every case [answer: no]

Church-Turing Thesis: there is a most effective way to do mathematics using a non-existent computer

The universe could explode tomorrow, and the validity or invalidity of these questions would be unchanged.

• See that quite literally makes no sense to me, that the universe could end and the theorems would still exist. Oct 4, 2021 at 14:50
• @JKusin These problems don't have to exist in the real world to be proven as true or false. They exist as a product of our mind trying to understand the universe. In some sense, if there is no universe, there is no one to think about this and the problems would no longer exist. However, since they are products of the mind, they exist in some abstract form that if there was a mind to think about them (independent of a universe) they would still exist. Oct 4, 2021 at 15:26

There is an area that wasn't heavily touched upon, mathematical fictionalism. To me fictionalism about math offers the simplest account of pluralistic ideas of truth. One way to couch these different notions of truth is literal truths and make-believe truths. Call manifestly true facts about the real world literal truths, and any other truths make-believe truths.

A literal truth is apples fall to the ground. A make-believe truth is Peter Parker is Spiderman. A make-believe falsity is Frodo is Spiderman.

I am not trying to establish for good what literal truths are, just a first pass of the landscape.

With the above in mind, a literal truth about the universe ending (finite) means in a literal sense any program will halt when that happens. A make-believe truth is these theorems will hold regardless of that fate.

To me fictionalism makes the fewest assumptions about the reality of math, and while some answers hinted at it, I wanted to include one that explicitly mentioned it.

• Don't tell this theory to a mathematician. They'll be out for blood! - As a matter of fact, a mathematician's "make-believe" truth is much, much more fundamental and true than any of your "literal" truth. Physics has shown us over and over again that reality us much weirder than what we would take for granted; completely overthrowing our worldviews with things like space contraction, time dilation, superposition, entanglement, tunnelling, etc. In math, however, it has been proven that there are infinitely many primes, and that truth will stand beyond the end of the world. Oct 5, 2021 at 9:40
• One comment. Let’s say the universe has exactly n particles and n is even. Is the number n + 1 any less real than the number n? Is the fact that n+1 must be odd any more fictional than the fact that n is even? Let’s say the the universe exists for an even number k of Planck times. It just so happens k+1 is divisible by 3. Is the fact that, say, k is divisible by 2 any less fictional than the fact k+1 is divisible by 3? Oct 5, 2021 at 12:08
• Arbitrarily turning off the computer(universe) doesn't defeat the halting problem. In a literal sense the program may no longer be running, but it didn't halt in the sense of the problem. Halting means it finished computation. By interrupting the computation you may prevent it from finishing, but the Halting problem is about determining if a program will finish on its own, not if the machine can be destroyed. Oct 5, 2021 at 14:54
• @JustSomeOldMan Those are truths that a fictionalist will not deny. Either n or n+ 1 is odd, no way around that. And one day we may count every particle sure. A fictionalist can partake in said counting. But the fictionalist might say sure these are useful tools, perhaps indispensable to understanding cetain things about the universe, but no more than that. Numbers are ways we make sense of certain things, but are not actually an ontology. Yes you could say well n particle exist, that's the ontology. But maybe I have a different description, maybe vastly more inefficient than numbers. (1/2) Oct 5, 2021 at 16:38
• @JustSomeOldMan Example. What if I had a type of synesthesia that triggered a different color in the optic center of my brain for every number of particles. I might collect all the particles and look and see blue! Now I'm convinced the blue is some of feature of the world. But it isn't, nor is color really. It's just how I categorize/make sense of/see things. If I see red I know I have half the total paricles, green another amount. Or maybe for each particle there is a character in some holy book, do I know believe this holy book is an ontology?(2/2). Oct 5, 2021 at 16:48

I would like to comment on the question and the answers. Leaving aside if a certain mathematical theory can exist even when its assumptions/axioms are not valid in reality, let's examine what a finite universe would entail in these cases.

A. In a finite universe certain arithmetic operations cannot be total (ie be applied on any numbers). Notably addition and multiplication. Why is that? Because unrestricted addition and multiplication can result in outcomes larger than the finite size of the universe. But when multiplication and addition are not total operations, this means that Peano arithmetic is not valid theory and instead other theories of arithmetic are valid. These theories of arithmetic (based instead on subtraction and division as basic operations) not only are consistent in an appropriate sense but can explicitly prove their consistency in a finite universe (see self-verifying theories). Thus Godel's original theorem would be both unsound and practically useless.

B. Furthermore, in a finite universe, for similar reasons as previously, the set of possible machines is finite and each one restricted in its tape size, alphabet size, input size and program size. The halting problem for these restricted TMs is always decidable in principle in at most a fixed finite time which can be calculated in advance (if this time is greater than the end time of the universe then it halts anyway along with the whole universe)(see why is the halting problem decidable for LBA,halting problem is decidable on finite set of programs). Thus Turing's original theorem would be both unsound and practically useless.

Objections:

1. But multiplication cannot be total and the maximum halting time is the product of the various combinations, maybe for some machine it cannot be calculated? This is a possibility that cannot be proved to actually exist as a certainty. In a finite universe a theoretical construction of such hypothetical machine is impossible, since it would have to produce a product that cannot be produced. Thus we need not be concerned with this possibility.
2. Maybe a machine still runs even after all people have died, thus none would be there to know what happened. Turing's theorem has nothing to do with such objections, it is not concerned whether someone will witness the halting or not, it is concerned with decidability in principle. Similarly the finite halting problem is decidable in principle.