8

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?

7
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Philip Klöcking
    Oct 5 at 9:37
  • What do you mean exactly by "finite"? Even in time?
    – Pablo H
    Oct 5 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.
    – J Kusin
    Oct 5 at 16:45
  • 1
    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.
    – Kevin
    Oct 6 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)...)))
    – Ben Voigt
    Oct 6 at 17:25
29

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.

4
  • 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.
    – J Kusin
    Oct 3 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 at 0:57
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Philip Klöcking
    Oct 4 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 at 3:55
8

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

4
  • 2
    I'd add collatz as an example. It is almost as easy, and unknown if it halts.
    – Yakk
    Oct 4 at 20:08
  • 1
    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 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 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.
    – Ben Voigt
    Oct 6 at 17:32
3

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."

3
  • > "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
    – J Kusin
    Oct 4 at 16:35
  • 3
    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.
    – Duncan W
    Oct 4 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.
    – Duncan W
    Oct 4 at 18:14
2

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?

8
  • 1
    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.
    – J Kusin
    Oct 5 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 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 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.
    – Mr.Mindor
    Oct 5 at 15:04
  • 1
    @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 at 21:22
1

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.

7
  • 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.
    – J Kusin
    Oct 5 at 20:39
  • 1
    @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 at 21:32
  • 1
    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 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.
    – J Kusin
    Oct 6 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 at 14:56
1

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.

4
  • 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.
    – J Kusin
    Oct 7 at 15:23
  • 1
    @J Kusin: They don't. The universe is given to us empirically. Oct 7 at 15:27
  • @MoziburUllah Do you disagree with user253751 's answer then?
    – J Kusin
    Oct 7 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 at 15:38
0

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.

2
  • See that quite literally makes no sense to me, that the universe could end and the theorems would still exist.
    – J Kusin
    Oct 4 at 14:50
  • 2
    @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.
    – morhc
    Oct 4 at 15:26
0

There are many great answers and comments who made sense of my unclear at times posts.

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.

7
  • 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 at 9:40
  • 1
    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 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.
    – Mr.Mindor
    Oct 5 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)
    – J Kusin
    Oct 5 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).
    – J Kusin
    Oct 5 at 16:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.