The paradox of Richard

With the help of some phrases of any language , these or other real numbers can be characterized. For example, the phrase "the ratio of the circumference of a circle to the length of its diameter" characterizes the number "pi" , and the phrase "two integers and three tenths" characterizes the number 2.3. All such phrases of this language can be numbered in a certain way (for example, if you arrange the phrases alphabetically as in a dictionary, then each phrase will get the number where it is located). Now we leave in this phrase numbering only those phrases that characterize one real number (and not two or more). The number, which is characterized in such a numbering by the phrase number n , is called the nth Richard number.

Consider the following phrase: “A real number for which the nth decimal is 1 if the n- th Richard number has the n- th decimal not 1, and the n- th decimal is 2 if the n- th Richard the nth decimal place is 1 ". This phrase defines a certain Richard number, for example, kth ; however, by definition, it differs from the k- th Richard number in the k- th decimal place. Thus, they came to a contradiction.

In computability theory, attempts to obtain the result of calculating the “Richard number" in this formulation are algorithmically unsolvable. The given verbal descriptions of the number determine not just the value itself, but the condition for the successful completion of the algorithms for calculating this value in the form of certain programs , the execution of which in the general case may require an unlimited amount of memory and infinite time in attempts to select the resulting rational number that satisfies the formulated exact value condition . There can be many ways to implement the algorithm, and all programs are correct, the execution of which gives the correct result that satisfies the formulated condition. But the satisfaction of certain conditions may be algorithmically unsolvable .

For example, the exact value of “two integers and three tenths” is computable , since the result of the calculations is a rational number that can be written as the ratio of natural numbers in a finite time using a finite amount of memory. And the exact value “the ratio of the circumference of a circle to the length of its diameter” is not computable in principle, since the desired result is actually an irrational number , the exact value of which is even theoretically impossible to imagine by any ratio of natural numbers, no matter what numbers we try to choose. For a finite time, it is possible to calculate only the approximate value of the Pi number with any finite number of digits after the decimal point, which will take time to calculate and store enough memory (i.e. only the approximate value of the Pi number as a rational number is computable ). But the exact value of Pi is not computable: any program for calculating the exact value of Pi will work infinitely long and will require an infinite amount of memory to store an increasing number of data accumulated with each iteration . The condition to write "the ratio of the circumference of a circle to the length of its diameter" by natural numbers is not feasible in principle, unless an allowable error is specified.

Similarly, when calculating a certain “Richard number”, it will be necessary to check the condition “Real number for which the nth decimal sign is 1, if the nth Richard number has the nth decimal sign and the nth decimal sign 2 if the n-th Richard number has the n-th decimal place equal to 1 ". Such a check will require the execution of a program with a recursive call of itself (the description contains operations on a certain “Richard number”, to calculate the value of which it is necessary to start again the next execution of the algorithm of this program with recursive immersion without limiting the nesting depth with the expectation of using an infinitely large amount of memory and unlimited time).

The desired “Richard number” in the above formulation is not computable and algorithmically unsolvable , i.e. there is no algorithm capable of calculating it in a finite time for the simple reason that the condition for the correct result is obviously impossible.

• Mendelssohn Elliot. Introduction to mathematical logic . - M .: "Science", 1971. - 320 p.

• Paradox berry