Turing’s undecidable problems, Godel’s Incompleteness theorems, and more show that arbitrarily powerful computers can’t do certain things, like map all of the mathematical multiverse.
But what happens if we modify it to make a hypercomputer? Specifically such a machine can do the following:
Can compute uncountably infinite stuff in finite time.
Now, the question. Can it evade Godel’s Incompleteness theorems and solve undecidable problems?
(If you want a story, imagine a different universe where the dark energy constant is set to zero, resulting in a Tiplerian scenario of Omega, or where Planck’s constant is zero.)
EDIT: I’ll also augment the computer with an infinite memory bank.
There are all sorts of hierarchies and classes of computing models that are “infinite” in any of a large set of different ways. However, Gödel’s theorems apply regardless because Gödel’s theorems are about mathematics, not computing.
You can in principle devise extensions of formal systems in which you allow infinite numbers of axioms and/or axiom schemata, but they’re actually boring in many ways. Gödel’s 1st incompleteness theorem doesn’t apply because you can just list every sentence of the complete theory in the axioms. Such a theory still can’t prove its own consistency though, since it can’t even express its own consistency—its infinitely many axioms can’t be expressed in one proposition.
Things get messier when you allow infinitely complex sentences. This is related to some forms of hyper-computation in the sense that any operation on such sentences would require both infinite memory and more computation than a Turing machine. There are theorems analogous to Gödel’s for such infinitary logics, even for arbitrary infinite cardinalities, but also plenty of unresolved problems including somewhat arbitrary choices in how finite logic should be extended to infinitary.
So I can evade Godel’s first Incompleteness theorems if I allow an infinite amount of axioms to prove everything in mathematics, making it complete, but I can’t prove it’s consistency. That’s a nice advantage of hypercomputers and infinite computation.
As I understand it, that point about “somewhat arbitrary choices in how finite logic should be extended to infinitary” would also include, for every one of the infinitely many undecidable-by-a-non-hypercomputer propositions, a free choice of whether to include a proposition or its negation as an axiom. Well, almost. Each freely chosen axiom has infinitely many consequences that are the no longer free choices. But it’s still (countably) infinitely many choices. But if you have countably infinitely many binary choices, that’s like choosing a random real number between 0 and 1, so there are uncountably many ways of making that extension, each of which results in a distinct infinitary system. Your proposed hypercomputer can generate all of these.
Yes, that is one example of many arbitrary choices in infinite systems. In practice that means that you give up the ability to communicate to anyone else which system you’re working with, unless you also have a channel with which to communicate an infinite amount of information to them.
However the somewhat arbitrary choices I was talking about with respect to infinitary logics was about what rules of inference you use to derive new infinite sentences. Even in finitary logic there are choices such as whether to accept proofs that use Law of Excluded Middle, as well as more esoteric principles such as modal logic, relevance logics, and paraconsistency, but when you have sentences with infinitely many clauses (or even more complex structures) then we need rules that aren’t determined by what happens with every finite number of clauses. Some of these might be very counterintuitive when building from an experience with only finitely many terms, but we can’t say they’re wrong.
Well, that’s trivially simulatable, since I can generate an infinitely large communication channel, so that’s not a constraint.
Computing uncountably infinite “stuff” is not well defined as stated. So all I can say to if it can “solve undecidable problems” is “Yes, some of them.” Which ones depends on what level of hypercomputer you’ve made, and how high up the arithmetical hierarchy it can take you.
There is a generalized halting problem: no oracle can solve its own halting problem.
Since you mentioned countability, I’ll say I do not know whether any particular type pf hypercomputer would be capable of assigning a specific cardinality (א-n for some n) to the reals.
Specifically, it can compute all of the real number line from 0-1 in finite time. Real numbers are more common than natural numbers. They are also uncountably infinite.
Then if it can compute infinite sets as large as the reals, it can handle any set of cardinality beth-1, but not beth-2 or larger. But because the cardinality of the reals is itself formally undecidable by finite logic systems (or by infinite logic systems of size less than aleph-w), I think this doesn’t give us much specificity about the limits of what that means, or where it falls on the kinds of arithmetical hierarchy schemas finite logic systems enable us to define.
For my own sanity this is about where I stop trying to delve too deep for understanding, and resort to handwaving poetic license: