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.

@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?"

> "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?" For a crude example say physical existence ends, but the Platonic realm keeps going. If the Platonic realm (also part of the universe) is finite, God will know certain theorems apply to it. If the Platonic realm is infinite, he/she will know others apply. If these 3 theorems are only talking about a certain aspect of existence, shouldn't we add that disclaimer?

@JKusin OK, you're interpreting "universe" rather more broadly than I expected. But the same basic idea applies: if we work in a context which imposes a finite bound in any sense, we have to do this uniformly, and the basic impossibility barriers don't go away.

But how does the impossibility of the halting problem not go away if there are only finite number of programs and inputs?

@JKusin Because think about what the incomputability (not impossibility) of the halting problem is saying. The "infinite" version is "There is no Turing machine which tells whether a given Turing machine will halt." On the "finitized" side, once we isolate some finite set of A of "genuine" Turing machines the version we're looking at is "There is no machine in A which tells whether a machine in A will halt" (actually even this isn't quite fair, we should also finitize time, but meh).

Note that the set A occurs twice here. If we really commit to a finite universe (in whatever sense) then not only does the halting problem become smaller but our resources for computing things also become more limited! The expectation that the halting problem becomes computable if there are only finitely many programs and inputs is based on the assumption that finite things are automatically computable - which is not obviously true in a "finite ontology" anymore. This is exactly the gist of the part of my answer "as long as we're careful to uniformly impose our finiteness restriction."

If we were starting from some really big finite number, not infinity, I would be completely onboard. I am still hesitant because halving the speed of light or number of particles or turning up gravity 2x is continuous. Aren't you proposing something much more drastic to reduce something infinite to finite? No finite process gives anything truly infinite, so the reverse seems equally troubling.

@JKusin I don't understand your most recent comment. I'm just talking about being consistent about "finitizing" things - if you're saying that there are only finitely many machines under consideration for the halting problem to apply to, then there also have to be only finitely many machines under consideration for the halting problem to be putatively computed by. Think about it this way: it takes around 2^n bits of information to specify a subset of {1,...,n}. If only the numbers in {1,...,n} are "genuine," then - roughly speaking - most "ideal" subsets of {1,...,n} are not "genuine."

I guess I had in mind a less rigorous idea of the halting problem. One where it wasn't just up to a turing machine to decide on halting, perhaps something else could show a program would halt. Like a finite end to the universe. Knowing such an end would allow me to say all programs will "halt". If we make such a discovery about the universe being finite in the future, would we change the halting problem phrasing at all? I guess not.

@JKusin At that point things are sufficiently unclear that I don't think the question can be reasonably answered.

Thanks for your time and thoughtful answers.

@JKusin Any finite computer will eventually halt or repeat states on every algorithm, given a long-enough run-time. This is because there is a finite number possible memory states in a finite computer. Imagine a computer with 3 bits of memory, and you run while(true){i++} on it. You'll get 000, 001, 010, 011, 100, 101, 110, 111, and then it'll repeat 000. This kind of thing is true no matter what algorithm you run, so long as it is a finite computer.

@JKusin: If every program halts for physical reasons, then it just implies that our theories of basic string manipulation (e.g. TC) or basic arithmetic (e.g. PA−) have no real-world interpretation. You could read what I wrote here, where I also mentioned Willard's self-verifying theories.

@user21820 Thank you. This seems closest to what I am trying to understand. The next question I have if there is no real-world interpretation to these (and most of math?), do we only use them because they are useful for our goals? A unicorn also has no real-world interpretation/realization, but are not very useful to most of our goals.

@JKusin: A huge amount of technology is built on science and mathematics that could be said to rely on the correctness of PA at least at human scales. I mentioned HTTPS in the linked post. The very fact that you can read this website right now relies on RSA encryption (as stated in the certificate), which relies on Fermat's little theorem, which can be cleanly stated and proven in a weak system called ACA0 that is essentially no stronger than PA. PA is PA− plus induction. So PA/ACA0 is very useful for applied mathematics.

Regardless, to both user21820 and @JKusin, this comment thread is getting rather long. I think it would be best to continue this discussion in a chat room.

@NoahSchweber: Yea I know. I'm just being generous, just in case someone finds some real-world application that depends on lots of induction. In particular, suppose we believe that iterated consistency statements are actually 'real-world applications', then we might need to accept all the way up to ATR or something like that. And I was waiting for the "continue in chat" message. Where is it? =)

@user21820 when you say technology and science rely on the correctness of PA, could I make the case that it still suggests nothing real about numbers and PA over any other drawn-from-whole cloth system with the same structure? I can't find chat on mobile sorry guys. I also may be going way beyond me question so don't feel forced to continue for my sake.

@JKusin: I don't know what you mean at all. Perhaps you need to study RSA encryption before you make statements like "nothing real about numbers". There is nothing unreal about the huge prime numbers involved in RSA encryption and the properties (proven by PA/ACA0) of exponentiation modulo primes that enable you to read this website.

@user21820 Well what makes this website run are transitstors, electrons, energy, etc all firing and being exchanged with certain physical patterns. And the prime numbers used to set these patterns on the substrate of transistors are really pixels and characters, which are really encodings, which eventually are just high vs low voltage. It's physical all the way down in that sense

@JKusin: Err.. no. (As I said, study RSA encryption first.)

@user21820 Isn't there a classic simplified example of RSA encryption using mixing paints? Maybe I want to code my website with mechanical paint buckets...like Cloudfare uses lava lamps and cameras for randomness instead of a function.

Your last comment makes no sense. If you want, please continue in chat.