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

Question

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?

Answer 1

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.

Answer 2

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

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

Answer 4

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?

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.