Can we get around Godel's Incompleteness theorems and Turing undecidable problems via infinite computers?
post by Noosphere89 (sharmake-farah) · 2023-04-17T15:14:40.631Z · LW · GW · 4 commentsThis is a question post.
Contents
Answers 11 JBlack 3 AnthonyC None 4 comments
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.
Answers
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.
↑ comment by Noosphere89 (sharmake-farah) · 2022-11-06T01:09:38.580Z · LW(p) · GW(p)
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.
Replies from: AnthonyC↑ comment by AnthonyC · 2022-11-06T16:41:20.312Z · LW(p) · GW(p)
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.
Replies from: JBlack↑ comment by JBlack · 2022-11-07T02:22:11.524Z · LW(p) · GW(p)
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.
Replies from: sharmake-farah↑ comment by Noosphere89 (sharmake-farah) · 2022-11-07T02:59:30.708Z · LW(p) · GW(p)
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.
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.
↑ comment by Noosphere89 (sharmake-farah) · 2022-11-05T22:33:14.018Z · LW(p) · GW(p)
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.
Replies from: AnthonyC↑ comment by AnthonyC · 2022-11-06T17:00:12.506Z · LW(p) · GW(p)
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:
Great fleas have little fleas upon their backs to bite 'em,
And little fleas have lesser fleas, and so ad infinitum.
And the great fleas themselves, in turn, have greater fleas to go on;
While these again have greater still, and greater still, and so on.For at the gates that Cantor flung apart (and Hilbert later),
Angelic fleas cavort in hosts inordinately greater.
4 comments
Comments sorted by top scores.
comment by gilch · 2022-11-05T22:12:42.181Z · LW(p) · GW(p)
[Epistemic status: a little out of my depth. There might be subtleties I'm missing.]
An oracle machine with a halting oracle is a type of hypercomputer that can "solve" (by fiat, the known laws of physics do not permit such a thing) the halting problem of any conventional Turing machine, but then an analogous oracle-machine halting problem would appear which is undecidable by these halting oracle machines, so this doesn't get rid of undecidable problems.
If we then suppose a second-order halting oracle, we can "solve" the oracle-machine halting problem, but then a new, harder, second-order oracle-machine halting problem would appear, and so on up to any order, in the arithmetical hierarchy.
Thus, we can never solve all undecidable problems, even with hypercomputers. Now, is your proposed hypercomputer model of equivalent power to a halting oracle machine? To the extent it is a well-defined model, I think so.
Replies from: sharmake-farah↑ comment by Noosphere89 (sharmake-farah) · 2022-11-05T22:27:32.714Z · LW(p) · GW(p)
Specifically, I was trying to make a reflective oracle, shown here:
https://intelligence.org/2015/04/28/new-papers-reflective/
So it's a non-standard oracle I'm trying to make.
comment by Shmi (shminux) · 2022-11-05T19:46:59.742Z · LW(p) · GW(p)
I suspect that you are falling into the standard fallacy of "changing just one thing". The universe we know is intricately interconnected, and changing one fundamental thing even a little means a lot of other seemingly unrelated things change as well, resulting in extremely drastic changes across the board.
For an often discussed example, what if the speed of light was larger/smaller/infinite? It turns out that the question is not even meaningful as stated, as the speed of light is exactly 1, dimensionless. What we perceive as the speed of light is a complex interplay between energy eigenstates of various atoms, which in turn depend on masses of quarks, the value of the fine structure constant, weak/strong/gravitational interaction, and probably even the cosmological constant. If you touched just one of those "fundamental" numbers, the resulting universe would be nothing like what we see now.
I am no expert in computability, but I would bet that a workable hypercomputer would break the physical universe as we know it, as well. I don't know how much it would break the math as we know it, but I suspect that it would be similarly drastic, to the degree where the questions you ask cease to be meaningful.
Replies from: sharmake-farah↑ comment by Noosphere89 (sharmake-farah) · 2022-11-05T22:13:53.006Z · LW(p) · GW(p)
Half correct. You're right the universe with Planck constant of zero would fall apart into infinite energy, but the dark energy constant zero version wouldn't. It would be totally normal, except for it's end state, that is it would recollapse into an infinite energy singularity rather than expand forever.