Skip to main content
added 129 characters in body
Source Link
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

I just noticed this questionYou ask about formal definitions, and I thought it would be important toso let me mention a certain issue regarding Turing's definition. The fact is that, although Turing had introduced the notion of computable number, his definition, which appears in the first sentence of his 1936 paper, is not the definition that is typically given today.

enter image description here

The problem is that if one wants to regard the computable numbers as represented by their programs, as Turing did, for the purpose of further computation, then with Turing's definition many seemingly computable operations on real numbers will not actually be computable. For example, there is no computable procedure to compute the sum of two computable real numbers, given programs for the summands, if one uses Turing's definition.

In regard to this question, the relevantmy main point would beis that the relevant discontinuity object appliesissue will apply just as much with respect to considerations of feasibilityin the feasible realm. OneIn particular, one should modify the definition to say a number is polytime computable, if there is a polytime algorithm to produce approximations to the real, to within a given accuracy. For example, I would find it reasonable to say that, given $n$, one wants a rational approximation within $1/2^n$ of the target real, by a polytime algorithm in $n$.

I just noticed this question, and I thought it would be important to mention that, although Turing had introduced the notion of computable number, his definition, which appears in the first sentence of his 1936 paper, is not the definition that is typically given today. The problem is that if one wants to regard the computable numbers as represented by their programs, as Turing did, for the purpose of further computation, then with Turing's definition many seemingly computable operations on real numbers will not actually be computable. For example, there is no computable procedure to compute the sum of two computable real numbers, given programs for the summands, if one uses Turing's definition.

In regard to this question, the relevant point would be that the discontinuity object applies just as much with respect to considerations of feasibility. One should modify the definition to say a number is polytime computable, if there is a polytime algorithm to produce approximations to the real, to within a given accuracy. For example, given $n$, one wants a rational approximation within $1/2^n$ of the target real, by a polytime algorithm.

You ask about formal definitions, so let me mention a certain issue regarding Turing's definition. The fact is that although Turing had introduced the notion of computable number, his definition, which appears in the first sentence of his 1936 paper, is not the definition that is typically given today.

enter image description here

The problem is that if one wants to regard the computable numbers as represented by their programs, as Turing did, for the purpose of further computation, then with Turing's definition many seemingly computable operations on real numbers will not actually be computable. For example, there is no computable procedure to compute the sum of two computable real numbers, given programs for the summands, if one uses Turing's definition.

In regard to this question, my main point is that the relevant discontinuity issue will apply just as much in the feasible realm. In particular, one should modify the definition to say a number is polytime computable, if there is a polytime algorithm to produce approximations to the real, to within a given accuracy. For example, I would find it reasonable to say that, given $n$, one wants a rational approximation within $1/2^n$ of the target real, by a polytime algorithm in $n$.

Source Link
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

I just noticed this question, and I thought it would be important to mention that, although Turing had introduced the notion of computable number, his definition, which appears in the first sentence of his 1936 paper, is not the definition that is typically given today. The problem is that if one wants to regard the computable numbers as represented by their programs, as Turing did, for the purpose of further computation, then with Turing's definition many seemingly computable operations on real numbers will not actually be computable. For example, there is no computable procedure to compute the sum of two computable real numbers, given programs for the summands, if one uses Turing's definition.

I explain more at length in my blog post, Alan Turing, on computable numbers. An excerpt:

One specific problem with Turing's approach is that on this account, it turns out that the operations of addition and multiplication for computable real numbers are not computable operations. Of course this is not what we want.

The basic mathematical fact in play is that the digits of a sum of two real numbers $a+b$ is not a continuous function of the digits of $a$ and $b$ separately; in some cases, one cannot say with certainty the initial digits of $a+b$, knowing only finitely many digits, as many as desired, of $a$ and $b$.

To see this, consider the following sum $a+b$ $$\begin{align*} &0.343434343434\cdots \\ +\quad &0.656565656565\cdots \\[-7pt] &\hskip-.5cm\rule{2in}{.4pt}\\ &0.999999999999\cdots \end{align*}$$ If you add up the numbers digit-wise, you get $9$ in every place. That much is fine, and of course we should accept either $0.9999\cdots$ or $1.0000\cdots$ as correct answers for $a+b$ in this instance, since those are both legitimate decimal representations of the number $1$.

The problem, I claim, is that we cannot assign the digits of $a+b$ in a way that will depend only on finitely many digits each of $a$ and $b$. The basic problem is that if we inspect only finitely many digits of $a$ and $b$, then we cannot be sure whether that pattern will continue, whether there will eventually be a carry or not, and depending on how the digits proceed, the initial digits of $a+b$ can be affected.

In detail, suppose that we have committed to the idea that the initial digits of $a+b$ are $0.999$, on the basis of sufficiently many digits of $a$ and $b$. Let $a'$ and $b'$ be numbers that agree with $a$ and $b$ on those finite parts of $a$ and $b$, but afterwards have all $7$s. In this case, the sum $a'+b'$ will involve a carry, which will turn all the nines up to that point to $0$, with a leading $1$, making $a'+b'$ strictly great than $1$ and having decimal representation $1.000\cdots00005555\cdots$. Thus, the initial-digits answer $0.999$ would be wrong for $a'+b'$, even though $a'$ and $b'$ agreed with $a$ and $b$ on the sufficiently many digits supposedly justifying the $0.999$ answer. On the other hand, if we had committed ourselves to $1.000$ for $a+b$, on the basis of finite parts of $a$ and $b$ separately, then let $a''$ and $b''$ be all $2$s beyond that finite part, in which case $a''+b''$ is definitely less than $1$, making $1.000$ wrong.

Therefore, there is no algorithm to compute the digits of $a+b$ continuously from the digits of $a$ and $b$ separately. It follows that there can be no computable algorithm for computing the digits of $a+b$, given the programs that compute $a$ and $b$ separately, which is how Turing defines computable functions on the computable reals. (This consequence is a subtly different and stronger claim, but one can prove it using the Kleene recursion theorem. Namely, let $a=.343434\cdots$ and then consider the program to enumerate a number $b$, which will begin with $0.656565$ and keep repeating $65$ until it sees that the addition program has given the initial digits for $a+b$, and at this moment our program for $b$ will either switch to all $7$s or all $2$s in such a way so as to refute the result. The Kleene recursion theorem is used in order to know that indeed there is such a self-referential program enumerating $b$.)

One can make similar examples showing that multiplication and many other very simple functions are not computable, if one insists that a computable number is an algorithm enumerating the digits of the number.

The definition of computable number used in computable analysis is that a real number is computable, if there is a computable procedure to produce approximations to it, to within any desired given accuracy. You don't have to get the digits right — you just have to be close enough by the metric, and the main point is that this isn't the same thing.

In regard to this question, the relevant point would be that the discontinuity object applies just as much with respect to considerations of feasibility. One should modify the definition to say a number is polytime computable, if there is a polytime algorithm to produce approximations to the real, to within a given accuracy. For example, given $n$, one wants a rational approximation within $1/2^n$ of the target real, by a polytime algorithm.