2
$\begingroup$

This question came from the answer I've given to the question An easy example of a non-constructive proof without an obvious "fix"?.

Rereading my answer I had some doubt about the existence of an uncomputable integer number, as that proposed in my answer. For convenience I report here the definition:

Let $\gamma$ be a real number defined as, say: $\gamma= > 12.23873560031\cdots$ and define: $c=3*10^2+3*10^5+3*10^{10}+\cdots$ where we have chosen the digit $3$, but it could be any digit, and the exponents of $10$ are the positions of this digit in the decimal expansion. Then $c$ may be a number or not, depending on whether this expansion has a finite number of $3$s in its expansion. If we chose $ > \gamma= \zeta(5)$ (the Riemann zeta function), we don't know today if it has a finite number of digits $3$ (so far as I know), so we don't know if $c$ is a number or not. If someone proves that $\zeta(5)$ actually has a finite number of $3$ in its expansion then we will have two possibilities: The proof is not be constructive, i.e. we cannot find the position of the last $3$, and $c$ is really a number but it is a non-computable integer. Or the proof is constructive and we know the position of the last $3$ and the number $c$ is computable.

Searching on the web for "uncomputable integers" I've not found pertinent pages (while there are a lot of pages for "uncomputable numbers", but related to real numbers).

So, there exist uncomputable integer numbers or my answer was completely wrong?

$\endgroup$
  • $\begingroup$ Even all algebraic irrational numbers are computable. "Computable" means that there is a (finite ) algorithm that can (in principle) calculate ALL the digits of the number. In the case of an integer $N$ , the program "print($N$)" already does the job, since the input of $N$ is finite. So, $N$ clearly must be computable. $\endgroup$ – Peter Jul 24 at 18:11
4
$\begingroup$

No, there is not. If you consider an integer with the usual meaning, it is finite information. All finite information can be computed.

For example, you can build a machine $M$ and the proposition "$M$ halts on input $0$" can be impossible to prove in any known usual theory. So the integer $i$ defined by $i=0$ if $M$ halts on input $0$ else $i=1$ is not "findable". But anyway it is computable.

Remember that computable means : A program exists that can compute that information. But the existence can sometimes be proved with non constructive steps...

$\endgroup$
  • $\begingroup$ So, if I well understand, the number $c$ in my definition is computable but not "findable"? And what "findable" means exactly? $\endgroup$ – Emilio Novati Jan 26 '15 at 22:42
  • 1
    $\begingroup$ If $c$ is an integer, it is computable. But the proposition "this program P computes c" can be non provable for all P even if it's true for some P. $\endgroup$ – Xoff Jan 26 '15 at 22:45

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.