0

Suppose we take for example the smallest number strictly greater than 0 (which in the conventional real number system realm doesn't exist but in some other number systems does (e.g the hypereals).

Well it's clearly defined (we just have), but we can't come up with an algorithm that will enumerate it's decimals (0.00000.... is just 0 and if we come up with a 1 we can always find a smaller number)

I can't seem to come up with any infinitesimal both definable and computable. Maybe it's just the case they're not computable.

user403504
  • 49
  • 3
  • 9
    The hyperreals do not have a smallest number greater than $0$. They have infinitesimals, but you can divide any positive one by $2$ to get a smaller one. The infinitesimals also do not have decimal expansions-decimal expansions are reserved for the standard reals. If by computable you mean having a decimal expansion that can be calculated, none of the infinitesimals have one. I can imagine other definitions of computable in the hyperreals, but you need to define it for the question to make any sense at all. – Ross Millikan Jul 22 '20 at 15:21

1 Answers1

2

The definition of a computable number is restricted to real numbers. As Ross Millikan has pointed out, only real numbers have decimal expansions.

However, it is possible to talk about computable complex numbers, for instance. If both the real part and the coefficient of $i$ in the imaginary part are computable real numbers, then it makes sense to say the complex number is also computable. A similar remark applies to other extensions of the real numbers.

Being less familiar with hyperreals, let me talk about the Surreal numbers instead. The ordinal numbers are part of the surreals, so $\omega = \{1, 2, 3, 4, \ldots \mid\phantom 0\}$ is a surreal number, and it has an inverse $\varepsilon := \left\{0\mid \frac 12, \frac 13, \frac 14, \ldots \right\}$ which is infinitesimal.

These are well-specified non-real numbers. They are like $i$. They don't need to be calculated themselves, any more than one has to calculate $0$ or $1$. They both can be completely specifed by a countable number of symbols (as I just did). And just like infinite decimals, they can be well-approximated by the results of terminating after $n$ steps, which can be reached in a finite amount of time.

So any sensible extension of "computable" to surreals would surely consider them both computable. And because they are, so are $x +y\omega + z\varepsilon$ for computable real numbers $x, y, z$.

Paul Sinclair
  • 43,643