0
$\begingroup$

If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that cannot be described by any type of information (like a way of factorizing number 181 using classical mathematics, the mathematics we usually use, without changing nothing (without changing conditions, axioms, definitions...) of it, which it is clearly impossible)?

(I ask this because I was told by an important user in Physics Stack Exchange that this was possible for hypercomputation (if it existed), but later I spoke with other computer scientists and physicists and they told me that in no way this could happen. I can't contact the original scientist that told me that this was possible for hypercomputation, so maybe you can clear my doubts)

Improve this question
$\endgroup$
1
  • $\begingroup$ What's the difference between this question and the other one? $\endgroup$
    – Nobody
    Commented Nov 22, 2018 at 9:54

1 Answer 1

Reset to default
4
$\begingroup$

I think you have an important misunderstanding about what "uncomputable" means. It doesn't mean "doing something mathematically impossible", such as producing a non-trivial factorization of a prime number. There simply are no integers other than $1$ and $181$ that divide $181$ and it doesn't matter what method of computation you use, you will never find these non-existent factors because they just don't exist. The factoring problem is not uncomputable: you can write a computer program that will correctly factorize any number that you give it. In the case of $181$, the program will just say, "The factors are $1$ and $181$ and that's all."

A problem is uncomputable if there is no Turing machine ("computer program") that can solve it. The standard example is what's called the halting problem: you have a computer program and you want to know if it will terminate, or get stuck in an infinite loop. Turing's famous result is that there is no Turing machine that will take the description of another Turing machine as input and correctly say either "this terminates" or "this loops forever".

Some models of hypercomputation can solve this problem. That is, the "hypercomputer" can decide whether given Turing machine will terminate. However, Turing's proof is very general and applies to any sufficiently powerful model of computation. So, although the hypercomputation model might be able to solve the halting problem for Turing machines, Turing's proof can be easily adapted to show that the hypercomputer cannot solve its own halting problem. That is, there is no hypercomputer program which takes as input the source code of another hypercomputer program and correctly determines whether that program will halt.

In summary, every sufficiently powerful model of computation has uncomputable problems, so no model of hypercomputation can compute everything.

Improve this answer
$\endgroup$
6
  • $\begingroup$ so there's no model of hypercomputation that could factorize number 181 in numbers that are not 1 or 181, isn't it? I ask you this because a scientist told me once that it was possible for a hypercomputational model operating in paraconsistent logic @DavidRicherby $\endgroup$
    – bautzeman
    Commented Nov 22, 2018 at 19:18
  • $\begingroup$ As far as I can see, the issue with this hypothetical factorization is not that it's difficult to find (i.e., a more powerful computer is needed) but simply that it does not exist. I doubt that paraconsistent logic helps with that (it's a system for reasoning about inconsistencies, not for creating things that don't exist), but it's not my area. $\endgroup$
    – David Richerby
    Commented Nov 22, 2018 at 19:25
  • $\begingroup$ Okay, thanks. I had another brief question about hypercomputation related with "It from bit"-theory, from John Wheeler that would be very helpful if you could answer. Are you familiarized with this theory/idea? @DavidRicherby $\endgroup$
    – bautzeman
    Commented Nov 22, 2018 at 21:50
  • $\begingroup$ Sorry, I don't know anything about that. But if you post it as a new question, hopefully somebody else will answer. $\endgroup$
    – David Richerby
    Commented Nov 22, 2018 at 22:10
  • 1
    $\begingroup$ If you don' want it to be marked as a duplicate, you need to make it clear how it's different from the existing questions. $\endgroup$
    – David Richerby
    Commented Nov 22, 2018 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.