0
$\begingroup$

I know that Chaitin's constant is an uncomputable real number, but I'm curious as to if there are any proven examples of non-real uncomputable numbers? Could uncomputable numbers be complex?

The Wikipedia page on types of numbers says that computable numbers are real numbers. An answer on Quora says that computable numbers are complex numbers. Given that neither of these are really necessarily cited, I'm curious if there exists any mathematical definition of the computable numbers and whether that helps define the uncomputable numbers?

Thanks so much!

$\endgroup$
3
  • $\begingroup$ Since you cite Wikipedia: "A complex number is called computable if its real and imaginary parts are computable." $\endgroup$
    – Clement C.
    Apr 25, 2018 at 4:08
  • 1
    $\begingroup$ "Mathematical proof for the definition of the computable numbers"??? Definitions do not require proofs. If you want a non-real uncomputable number just multiply Chaitin's constant by $i$. $\endgroup$
    – Conifold
    Apr 25, 2018 at 4:11
  • $\begingroup$ @Conifold oh... wow I'm an idiot. Didn't even consider that. Thanks! $\endgroup$
    – user3684314
    Apr 25, 2018 at 5:30

2 Answers 2

Reset to default
3
$\begingroup$

The real and imaginary parts of a complex number are computable from the complex number, so the computable complex numbers are those with computable real and imaginary parts. It doesn't matter whether you look at computable numbers as reals or complex numbers.

We don't really care what the definition of a computable number is. There are lots of numbers that are clearly computable, like all the rationals. You can compute them based on the field axioms. As long as you have only countably many constants, there are only countably many computable numbers because there are only countably many finite strings of characters to compute a number. As there are uncountably many reals, most of them are uncomputable. The negative definition is what makes it hard to specify an uncomputable number. If you can define it, usually you can compute it.

$\endgroup$
3
  • 1
    $\begingroup$ Okay this makes sense to me (I'm not very mathematically inclined so that's saying something). Reading comments here (math.stackexchange.com/questions/1266587/…) helped as well. Thank you so much! $\endgroup$
    – user3684314
    Apr 25, 2018 at 5:35
  • $\begingroup$ @Ross Millikan: One should be careful using the argument of "countable many strings of symbols that make definitions ergo countably many computable numbers". It is consistent with ZFC that every number and set is definable. See here. $\endgroup$
    – Isky Mathews
    Apr 26, 2018 at 18:46
  • $\begingroup$ @IskyMathews: That may be so, but there is no (Turing-equivalent) uncountable model of computation. Computers and algorithms are finite objects. $\endgroup$
    – Kevin
    Mar 7, 2019 at 7:40
0
$\begingroup$

A computable number which can be computed to any number of digits desired by a Turing machine, according to Wolfram Math World. From this definition, which talks of digits, I would infer that computable and uncomputable numbers are a subset of real numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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