0

In what way do Godel's incompleteness theorems impact computers/hypercomputers? Do they somehow prevent them from being capable of computing everything (of computing literally all uncomputable/undecidable/illogical/logically impossible things)?

To ask this in another way, if Gödel's theorems "vanished" or otherwise did not hold, would that mean that computers/hypercomputers would be able to compute literally all uncomputable/undecidable things?

To take it a step further: Is it only Gödel's theorems that stop us from computing illogical/logically impossible things? For instance, without Gödel's theorems, could we compute things that are (logically) impossible to depict/describe/compute/conceive (like a circle cutting a straight line in 3 points in Euclidean geometry, which is impossible to draw/depict)? Could we compute illogical/logically impossible things that are (logically) impossible to depict/describe even by words?

Improve this question
13
  • 2
    "If Gödel's theorems vanished or did not hold ... would computers/hypercomputers be able to compute all undecidable things ?" As stated, the answer is trivial : YES. If there is no death, we will live forever.
    – Mauro ALLEGRANZA
    Apr 29, 2019 at 10:50
  • 1
    Gödel’s Incompleteness Theorems is a Mathematical theorem that applies to consistent formal systems with some "minimal" expressive capabilities. Assuming that a real compueter is the physical implementation of a formal system, then also a computer is subject to the theorem. Having said this, what are "impossible things" ? Obviously a real computer compute "possible computations".
    – Mauro ALLEGRANZA
    Apr 29, 2019 at 10:54
  • If Euclidean geometry is consistent, there are no circles cutting a straight line in 3 points (irerspective of G's Th) and thus no computer whatever can compute three distinct intersection points, because there are only two.
    – Mauro ALLEGRANZA
    Apr 29, 2019 at 10:56
  • 3
    This is probably the third time this question has been asked. Can someone tell me what is driving this question? Is it some current philosopher's work? Why would a computer be able to transcend reality? Who says they can?
    – Richard
    Apr 29, 2019 at 11:32
  • 2
    @Richard A version of Gödel's theorems have passed into popular culture, but in the popular imagination, they are a mystical force, capable of defeating science, mathematics and computing, like a holy relic warding off a vampire. And conversely, without that relic standing in their way, computers would become all-powerful.
    – Chris Sunami
    Apr 29, 2019 at 16:23

1 Answer 1

Reset to default
2

Gödel's theorems don't have agency, or cause any effects. There's nothing magic about them. What they are is a clever way of demonstrating that there are pre-existing, intrinsic limits to what can be computed. You might imagine being in a field with a fence. The field is computing, the fence is the boundaries of what can be computed, and all the problems you are considering are sheep. You don't know if every sheep is inside the fence or not. Gödel's theorems are a way of identifying a specific sheep that must be outside the fence. That proves that not every sheep is inside. In other words, by identifying a particular problem that computing cannot solve, Gödel's theorems prove that not every problem is computable.

Problems that are logically impossible are also not computable, but for reasons outside of Gödel's theorems. They are like sheep that don't exist. They cannot be said to be either inside or outside the fence, because they don't exist at all. Their impossibility has nothing to do with Gödel's theorems, one way or another. To put it another way, even if we couldn't find that one sheep outside the fence, it wouldn't mean that imaginary sheep would suddenly appear inside the fence.

The most straightforward answer to your counterfactual about what would happen if Gödel's theorems didn't exist is that there would still be problems that were uncomputable, we just wouldn't be aware that they exist (unless we found a different counterexample than the one that Gödel constructed). Gödel's theorems are not the fence --they don't establish the boundary. They just demonstrate that it does exist.

Improve this answer
2
  • but if somehow Gödel's theorems would be invalid on a computer/hypercomputer and couldn't be applied to its type of computability, wouldn't that mean that this computer/hypercomputer would be capable of computing all (even logically impossible problems)? @ChrisSunami
    – Sue K Dccia
    Apr 29, 2019 at 19:07
  • @SueKDccia I have already directly addressed this question in my answer, above. If it doesn't satisfy your concern, please clarify why.
    – Chris Sunami
    Apr 29, 2019 at 19:10

Not the answer you're looking for? Browse other questions tagged .